Реализация линейной структуры данных и оценка эффективности работы со структурой в зависимости от размерности структуры

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

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

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

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

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

Вариант: 16       

Группа: АМ-010                                                                       Преподаватель:

Студент: Лобойко И.А.                                                          Романенко Т.А.

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

Цель работы: реализовать линейную структуру данных и оценить эффективность работы со структурой в зависимости от размерности структуры.

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

Вариант: 16. Структура данных – двусвязный циклический список. Модификация АТД - Упорядоченный список.

Текст программы

template <class T>

class Elem

{

public:

                    T *elem;

                    Elem<T> *next;

                    Elem<T> *prev;

                    Elem() {next=prev=NULL; elem=NULL;}

                    Elem(T *d)

                                       {

                                       next=prev=NULL;

                                       elem = new T;

                                       elem = d;

                                       }

//int  operator>(const Elem<T>);//переопределение операции сравнения

//int  operator<(const Elem<T>);

};

//******LIST*******************************************

template <class T>

class List

{

                    public:

                                       Elem<T> *first;

                                       Elem<T> *last;

                                       int cnt;

                    int cntFind;                   //Счетчики элементарных операций

                    int cntInsert;

                    int cntDelete;

List() { first=last=NULL;cnt = 0; cntFind=cntDelete=cntInsert=0;}

List(T *d){Elem<T> *q = new Elem<T>(d); first=last=q; cnt=1; cntFind=cntDelete=cntInsert=0;}

void Print() const;

void Sort();

void Insert(T d);

int ListSize() {return cnt;}

int ListEmpty() {if (first!=NULL) return 1; else return 0;}

int GetPos(T);

Elem<T> *Find_num(int n);

int Find(T);

T GetData(int n);

void ClearList();

int Delete(int);

~List();

};

//***************************************************************************************

template <class T>class CList: public List<T> //Модификация АТД - упорядоченный список

{

public:

                    //Упорядоченная вставка элемента в список

                    void Insert(T data);

                    void Test(int SizeOfStructure);

};

//***************************************************************************************

template <class T>

List <T>::~List()

{

    Elem <T> *q = first;

                    Elem <T> *p = q->next;

                    do

                                       {

                                       p=q->next;

                                       delete q;

                                       q=p;

                                       }

                    while (p!=first);

}

//---------------------------------------------------

template <class T>

void List <T>::Insert(T n)

{

                    T *d = new T(n);

                    if(first == NULL)

                    {

                                       Elem <T> *e = new Elem <T>(d);

                                       first = e;

                                       last = first;

                                       last->next = first;

                                       first->prev = last;

                                       cnt = 1;

                    }

                    Elem <T> *e = new Elem <T>(d);

                    e->next = first;

                    first->prev=e;

                    last->next = e;

                    e->prev = last;

                    last = e;

                    first->prev = last;

                    cnt++;

}

//----------------------------------------------------

template <class T>

void List <T>::Print() const

{

    Elem <T> *q = first;

                    if (first==NULL) return;

                    do

                                       {

                                                           cout<<*q->elem<<" ";

                                                           q=q->next;

                                       }

   while (q != first);

cout<<endl;

}

//----------------------------------------------------

template <class T>

void List <T>::Sort()

{

                    Elem <T> *tmp = new Elem<T>;

                    for (int i = cnt; i>0; i--)

                    {

                                       Elem <T> *q = first;

                                       Elem <T> *p = first->next;

                    do

                                       {