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

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

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

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

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

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

Вариант:1

Группа: АМ-015

Бригада:1

Студенты: С.

Новосибирск 2002

Цель лабораторной работы

Реализация типовых коллекций данных в виде Абстрактных Типов Данных (АТД) на языке высокого уровня С++. Оценка и анализ эффективности алгоритмов реализации АТД. Формирование библиотеки разработанных АТД.

Задание

Спроектировать, реализовать и провести тестовые испытания АТД для линейной коллекции - "Список" и ее модификации. Список базируется на заданной вариантом структуре данных.

Формат АТД

Структура данных - динамический массив. Модификация АТД - Стек.

Описание иерархии классов

Классы «Динамический массив»(«ДМ») и «Стек» похожи по своей внутренней организации. Но некоторые методы «ДМ» не могут быть использованы в классе «Стек» т. к. противоречат самому определению стек. Это операции «Вставка по лог. номеру», «Удаление по лог. номеру». Некоторые данные класса «ДМ» так же не используются, т. к. они предназначены для тестирования алгоритмов.

Назначение данных и методов классов «ДМ» и «Стек»

Класс «ДМ» шаблонный класс, соответственно, класс «Стек» так же шаблонный.

Класс «ДМ»

template<class T> class Cmass

{

protected: //переменные, которые использует наследованный класс

int count;//количество элементов

int size;//размер массива

int oldsize;//в случае увеличения размера

T *elem;

private: //переменные для тестирования, не нужны для наследованного класса

long ins; //счётчик для функции вставки

long del; //счётчик для функции удаления

long find; //счётчик для функции поиска

Методы класса «ДМ»

public:

Cmass(int _size=10){}//конструктор, размер задан по умолчанию

~Cmass(){}//деструктор

//Функции помеченные virtual наследуются классом «Стек».

virtual int GetCount(){}//получить количество элементов (текущее)

virtual int GetSize(){}//получить размер массива

void Include(T dat){}//включение элемента в конец массива

virtual void ClearStruct(){}//очистить объект класса.

T GetData(int num){}//получить значение по индексу

int GetPos(T key){} // получение позиции по заданному значению

bool MasEmpty(){}//пустой ли массив

private: //служебная функция

void DelNumTemp(int num){}//удаление по лог. номеру, если не надо изменять размер массива. Вызывается внутри функции DelNum после проверки переполнения.

public: //общедоступная

void DelNum(int num){}//удаление по лог. номеру с изменением разм. массива

private: //служебная функция

void InsNumTemp(int num, T dat){}//вставка по лог. номеру, если не надо изменять размер массива. Вызывается внутри функции InsNum после проверки переполнения.

public: //общедоступная

void InsNum(int num, T dat){}//вкл-е по лог. номеру с увелич. размерности

int Search(T key){}//функция поиска элемента. Возвращает лог. номер элемента. -1 - в случае неудачи.

long * GetStat(){}// используется для получения счетчиков по функциям во время тестирования. 0-ins, 1- del, 2- find.

void ClearStat(){}//очистить счетчики статистики.

};

Класс «Стек»

template <class T>

class Stek: public virtual Cmass<T>//указывается наследование

{

enum{emp=-1};//нет данных

int dno;//дно стека

int top;//вершина стека

Методы класса «Стек»

public:

Stek(int _size=10){}//в конструктор добавлена инициализация данных свойственных классу «Стек». По правилам наследования сначала вызывается конструктор класса потомка затем уже наследованного класса.

void Push(T dat){}// «погрузить» данные в стек. Обыкновенное включение в конец.

T Pop(){}//получить из стека данные

bool Full(){}//заполнен?

void ClearStruct(){}//очистка стека. Добавлены некоторые действия специфические для класса «Стек».

};

Графики и таблицы с полученными оценками эффективности алгоритмов операций для наихудшего, наилучшего и среднего случаев функционирования АТД

Размер массива (N)	DelNum (a)	Find (b)	InsNum (c)	T(N)
N=10	0.127	0.103	0.2125	13.3125
N=50	0.025	0.23	0.045	74.045
N=100	0.013	0.0164	0.021	131.664

T(N)=a*N^2 + b*N+c

Количество операций =100.

Как видно из графика, построенного по экспериментальным значениям, зависимость T(N) линейна. С увеличением размера массива линейно увеличивается трудоёмкость алгоритма. Количество операций практически не влияет на T(N).

Литература:

1)  Конспект лекций по «СА и ОД»

2)  World Wide Web