Информатика и выч. техника \ Структуры и алгоритмы обработки данных

Освоение технологии реализации позиционных, линейных коллекций на примере АТД «Список»

Страницы работы

14 страниц (Word-файл)

Посмотреть все страницы

Скачать файл

Фрагмент текста работы

МОРФ

Новосибирский государственный технический университет

Кафедра вычислительной техники

Лабораторная работа №2

по дисциплине «Структуры и алгоритмы обработки данных»

Линейные коллекции данных

Факультет: АВТ

Группа: Преподаватель:

Студент: Романенко Т. А.

г. Новосибирск

2005

Лабораторная работа № 2. "Линейные коллекции данных".

Цели работы: Освоение технологии реализации позиционных, линейных коллекций на примере АТД «Список». Освоение методики тестирования трудоёмкости реализации коллекций.

Задание

1. Спроектировать, реализовать и провести тестовые испытания АТД «Список» для коллекции, содержащей данные произвольного типа. Тип данных задаётся клиентской программой.

Интерфейс АТД "Список" включает следующие операции:

· опрос размера списка,

· очистка списка,

· проверка списка на пустоту,

· опрос наличия элемента с заданным значением,

· доступ к значению элемента с заданным номером в списке,

· получение позиции в списке элемента с заданным значением,

· включение нового элемента в позицию с заданным номером,

· удаление элемента из позиции с заданным номером,

· итератор для доступа к элементам списка с операциями:

- установка на начало списка,

- проверка конца списка,

- доступ к значению текущего элемента,

- переход к следующему элементу списка,

- переход к предыдущему элементу списка (для списков на базе массива или двусвязных структур),

Для тестирования эффективности операций интерфейс АТД "Список" включает дополнительную операцию

· опрос числа элементов списка, просмотренных операцией.

2. Выполнить отладку и тестирование всех операций АТД "Список" с помощью меню операций.

3. Выполнить тестирование средней трудоёмкости операций поиска, вставки и удаления элементов.

4. Провести анализ экспериментальных показателей трудоёмкости операций.

5. Составить отчёт по лабораторной работе.

Вариант №7: Структура данных – кольцевая, двусвязная, на базе адресных указателей.

Формат АТД.

АТД «Список»

Кольцевая двусвязная последовательность элементов. При создании имеет размерность равную ноль элементов. Количество элементов увеличивается вследствие добавления элементов в конец или вставки в позицию отличную от конца.

Класс iterator позволяет получать доступ к отдельным элементам структуры. Помимо этого он может хранить текущее состояние просмотра и осуществлять непосредственное перемещение по структуре данных.

Данные:

Параметры:

Текущий размер списка(количество элементов) size

Структура данных:

Динамическая последовательность элементов

Операции:

Конструктор:

Вход: параметры отсутствуют

Процесс: инициализация данных

Постусловия: нет

Опрос размера списка:

Вход: нет

Предусловия: нет

Процесс: чтение текущего размера списка

Выход: текущий размер

Постусловия: нет

Очистка списка:

Вход: нет

Предусловия: проверка размера списка size ≠ 0

Процесс: последовательное удаление элементов списка

Выход: нет

Постусловия: нет

Проверка списка на пустоту:

Вход: нет

Предусловия: проверка размера списка size ≠ 0

Процесс: определение полноты списка

Выход: true – список пуст

false – список содержит элементы

Постусловия: нет

Определение наличия элемента:

Вход: ссылка на проверяемое значение

Предусловия: проверка размера списка size ≠ 0

Процесс: поиск значения в списке

Выход: true – проверяемое значение присутствует false – проверяемое значение отсутствует в списке

Постусловия: нет

Доступ к значению по номеру:

Вход: номер

Предусловия: проверка на существование элемента с заданным номером

Процесс: последовательный переход

Выход: ссылка на значение

Постусловия: нет

Добавление элемента в конец:

Вход: ссылка на значение

Предусловия: нет

Процесс: вставка элемента конец последовательности

Выход: нет

Постусловия: нет

Получение позиции в списке элемента с заданным значением:

Вход: ссылка на искомое значение

Предусловия: нет

Процесс: последовательный просмотр списка

Выход: порядковый номер искомого элемента в случае его наличия

Постусловия: нет

Вставка:

Вход: ссылка на вставляемое значение(value) и позиция для вставки(position)

Предусловия: корректность вставки по (size+1 <= position)

Процесс: последовательный проход списка с последующей вставкой

Выход: нет

Постусловия: нет

Удаление:

Вход: порядковый номер удаляемого элемента(position)

Предусловия: корректность удаления(size <= position)

Процесс: последовательный проход с последующим удалением

Выход: нет

Постусловия: нет

Опрос числа элементов, просмотренных операцией:

Вход: нет

Предусловия: нет

Процесс: чтение числа элементов, просмотренных операцией

Выход: число элементов просмотренных операцией

Постусловия: нет

КЛАСС «ИТЕРАТОР»

Конструктор по умолчанию:

Вход: нет

Предусловия: нет

Процесс: инициализация данных

Выход: нет

Постусловия: нет

Конструктор копирования:

Вход: ссылка на объект класса ИТЕРАТОР

Предусловия: нет

Процесс: инициализация данных

Выход: нет

Постусловия: нет

Оператор =:

Вход: ссылка на объект класса ИТЕРАТОР

Предусловия: нет

Процесс: инициализация данных

Выход: ссылка на текущий объект класса ИТЕРАТОР

Постусловия: нет

Установка на начало списка:

Вход: нет

Предусловия: нет

Процесс: установка в стартовое положение

Выход: нет

Постусловия: нет

Проверка на достижение конца списка:

Вход: нет

Предусловия: нет

Процесс: проверка на достижение конца

Выход: true – конец достигнут

false – конец не достигнут

Постусловия: нет

Доступ к значению текущего элемента:

Вход: нет

Предусловия: нет

Процесс: получение ссылки на объект Выход: ссылка на объект

Постусловия: нет

Оператор ++:

Вход: нет

Предусловия: нет

Процесс: переход к следующему элементу

Выход: ссылка на текущий объект класса ИТЕРАТОР Постусловия: нет

Оператор --:

Вход: нет

Предусловия: нет

Процесс: переход к предыдущему элементу Выход: ссылка на текущий объект класса ИТЕРАТОР Постусловия: нет

КОНЕЦ КЛАССА «ИТЕРАТОР»

Получение итератора на начало списка:

Вход: нет

Предусловия: нет

Процесс: создание итератора на начало списка

Выход: итератор на начало списка

Постусловия: нет

КОНЕЦ АТД «СПИСОК»

«Список».

template<class T>

class list

{

public:

list();

~list();

inline size_t Size() const;

inline void Clear();

bool Empty() const;

bool Value(const T &value) const;

T& At(size_t number) const;

void Add(const T &value);

size_t Position(const T &value);

void Insert(const T &value, size_t position);

void Remove(size_t position);

inline size_t Number() const;

class iterator

{

public:

iterator();

explicit iterator(node *begin);

iterator(const iterator &it);

iterator& operator = (const iterator &it);

void beg();

bool end() const;

T& operator * () const;

const iterator& operator++();

const iterator& operator--();

};

const list<T>::iterator begin_iterator() const;

};

Описание методики тестирования трудоемкости операций.

Размер списка варьируется в пределах от 10 до 100 000 элементов. После тестирования на экран выводятся размер списка и средняя трудоёмкость операций поиска, вставки и удаления (среднее число просмотренных элементов списка).

Для нахождения средней трудоемкости операции необходимо протестировать эти операции при худшем(упорядочен по возрастанию) и лучшем(упорядочен по убыванию) варианте разброса. Это сказывается только на операции поиска, т.к. мы последовательно просматриваем все элементы. На операции вставки и удаления разброс элементов не сказывается, т.к. мы точно определяем позицию вставки или удаления.

Полученные числа просмотренных элементов при худшем и лучшем разбросах складываются и делятся пополам(усредняются).

Таблицы и графики.

При оценке трудоемкости операции поиска ищется элемент со значением, находимым по формуле: Value = Size/2 + Size/3, где Size – количество элементов в массиве.

При оценке трудоемкости операции вставки производится вставка элемента со значением: Value = Size + 1, - в позицию: Position = Size/2 + Size/3.

При оценке трудоемкости операции удаления, номер удаляемого элемента находится по формуле: Position = Size/2 – Size/3.

Таблица с полученными оценками трудоёмкости операций для среднего случая функционирования АТД.

Количество элементов	10	50	100	500	1000	5000	10000	50000	100000
Поиск	4	24	49	249	499	2499	4999	24999	49999
Вставка	3	10	18	85	168	835	1668	8335	16668
Удаление	1	8	16	83	166	833	1666	8333	16666