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

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

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

Сравнительный анализ  теоретических и экспериментальных оценок эффективности операций.

Из графика, приведенного выше,  видна линейная зависимость трудоемкости операций от размера структуры данных(количество

Похожие материалы

Информация о работе