IV. Динамични структури от данни

Понятие и видове

Линейни списъци

1.      Дефиниция и видове.

2.      Предимства и недостатъци на линейните списъци спрямо масивите

3.      Реализация на линейни списъци

3.1.   Базови класове

Класът Node

Класът LList

3.2.   Класове наследници, дефиниращи възлите на списъка.

Класът MyFloatList

Класът MyCharList

Класът MyStringList

3.3.     Класове наследници, дефиниращи вида на списъка.

Клас List

3.4.     Демострационни тестващи програми.

ListDemo

 

Понятие и видове

Типовете данни, които се използват в езиците за програмиране могат да се разделят на 2 основни типа (фиг.1.): статични и динамични. Статичните данни могат да променят само своите стойности по време на изпълнение на програмата. Динамичните данни освен стойностите си могат да променят своята структура и своя адрес по време на изпълнение на програмата. При тях се дефинира само областта на допустимите им стойности и най-общите правила за изменение на структурата им. 

От своя страна статичните данни могат да се разделят на прости и сложни. Простите типове данни се характеризират с единична стойност. Това са атомарни данни (символи, цели числа, дробни числа и др.). Сложните данни се характеризират с повече от една стойност – масиви, символни низове, структури (записи), статични обекти.

Динамични данни се реализират с помощта на указатели и динамично заделяне на памет. Динамичните данни се създават на етапа на изпълнение на програмата.  Динамични данни са динамичните обекти, динамични масиви и рекурсивните данни.

Примери

//статични данни

struct PERSON{…};      //дефиниция на структура

class CAR{…};              //дефиниция на клас

int x;                                //дефиниция на статична проста променлива от цял тип

char c;                             // дефиниция на статична проста променлива от тип символ

float a[100];                    // дефиниция на статичен масив от 10 елемента тип дробни числа

PERSON One;               // дефиниция на статичен обект от тип PERSON

CAR First;                      // дефиниция на статичен обект от тип CAR

//динамични данни

int *py;                            // дефиниция на указател от тип int

py=new int;                    // динамично заделяне на памет за py

 . . .

delete py;                        // освобождаването на паметта за py

. . .

py=new int;                     // динамично заделяне на памет за py (нова)

 

float *b;                           // дефиниция на указател от тип float

b=new float[10];  // динамично заделяне на памет за масив от 10 елемента, които са дробни числа

. . .

delete b;              // освобождаването на паметта за b, унищожаване на масива

. . .

b=new float[500];            // динамично заделяне на памет за масив от 500 елемента, които са дробни числа

 

PERSON *P;                  // дефиниция на статичен обект от тип PERSON

P=new PERSON;           // динамично заделяне на памет за P, създаване на обект

. . .

delete P;              // освобождаването на паметта за P, унищожаване на обекта

. . .

P=new PERSON;           // динамично заделяне на памет за P(нова)

 

Рекурсивни данни са сложни, структурирани типове данни. Това са данни, които се съдържат в себе си или са дефинирани чрез себе си. В езика за програмиране С++ рекурсивни типове данни могат да се реализират с помощта на рекурсивни структури или рекурсивни класове.

Видовете динамични рекурсивни структури от данни са:

·         линейни списъци;

·         стекове;

·         опашки;

·         декове;

·         дървета;

·         графи.

 

 

Линейни списъци

 

1.     Дефиниция и видове.

Линейните списъци представляват динамични структури от данни. При тях както стойностите така и структурата се променят по време на изпълнение на програмата.

Линейният списък е динамична линейна структура от данни, при която всеки елемент е свързан с не повече от 2 други елемента от списъка: предшественик и наследник.  Допустимо е един елемент да е свързан само към един елемент от списъка, т.е. да има само  предшественик или само наследник.

В зависимост от начина на свързване на елементите линейните списъци биват 3 вида:

·      едносвързани – всеки елемент съдържа данни и един указател към следващия елемент от списъка. Указателят на последния елемент има стойност 0 (NULL). Елементите се обхождат само от началото към края.

 

 

 

 

 

 

 


·      двусвързани – всеки елемент съдържа данни и два указателя: към предходния и към следващия елемент от списъка. Указателят към предходния елемент на първия елемент от списъка има стойност 0 (NULL). Указателят към следващия елемент на последния елемент от списъка има стойност 0 (NULL). Елементите могат да се обхождат както от началото към края, така и от края към началото.

 

 

 

 

 

 

 

 

 


·      циклични – всеки елемент съдържа данни и един указател към следващия елемент от списъка. Указателят на последния елемент има стойност равна на адреса на първия елемент от списъка. Елементите се обхождат циклично само в едната посока, като се започне от първия елемент на списъка.

 

 

 

 

 

 

 


Допустими са и двусвързани циклични списъци.

1.     Предимства и недостатъци на линейните списъци спрямо масивите

·      Линейните списъци използват по-ефективно паметта на компютъра.

При работа с масиви в началото на процедурата се заделя памет за максимално допустимия брой елементи на масива. По време на изпълнението на процедурата може да се използва само малък процент от нея. Останалата памет остава блокирана.

При линейните списъци се заделя памет само за толкова елементи, колкото са необходими за конкретното изпълнение на процедурата. За всеки елемент се заделя памет в момента на неговото създаване.

·      Линейните списъци използват по-гъвкаво паметта на компютъра.

Масивите заемат непрекъсната област от паметта и при големи масиви това може да доведе до затруднения и до съобщение за недостиг на оперативна памет, въпреки че като цяло свободната оперативна памет може да надвишава необходимата за разполагане на масива. При  линейните списъци всеки елемент с разполага в паметта както проста променлива. Достатъчно е да се намери участък от паметта с обем по-голям или равен на обема на елемента. Връзката между елементите се реализира посредством указатели.

 

·      Добавянето и премахването на елемент от линеен списък е по-проста и по-бърза процедура в сравнение с масивите.

За да се добави елемент началото на масива е необходимо да се изместят с един индекс назад всички елементи от масива.

За да се добави нов елемент в началото на линеен списък е необходимо само да се пренасочат указателите за първи елемент и за следващ елемент. (По-подробно този въпрос ще бъде разгледан по-долу в текста.)

 

·      Достъпът до елементите на масив е многократно по-бърз от достъпа до елементите на линеен списък.

Достъпът до елемент на масив се получава с т.н. индекс-операция (елементът се намира на толкова байта спрямо началото на масива, колкото е произведението от неговия индекс и броя байтове, необходим за съхраняването на един обект от типа на масива).

За да се достигне до един елемент на линеен списък трябва да се обходят всички елементи преди него.

Може да се каже, че достъпът до елементите на масива е директен, а до тези на линейния списък- последователен.

За да се преодолее този недостатък на линейните списъци се прибягва до създаване на индексен масив- масив, който съдържа само адресите на последователните елементи в списъка.

2.     Реализация на линейни списъци

В настоящата разработка се спирам на реализация на едносвързан линеен списък.

За реализацията на линейни списъци в С++ могат да се използват масиви, рекурсивни структури или рекурсивни класове. В настоящата разработка се спирам на реализация посредством рекурсивни класове.

2.1.             Базови класове

За решаването на поставената задача е необходимо да се разработят 2 базови класа: Node, който описва един възел (елемент) от линейния списък и клас LList, който описва списъчната структура.

Класът Node съдържа следните компоненти:

Указател към следващия възел(елемент от списъка). Чрез него се реализира рекурсивната структура. Използвам указател, т.к. С++ не позволява включване на обекти от типа на класа, който се дефинира, но допуска включване на указатели към обекти от същия тип.

·        конструктор без параметри, в който е нулира указателя next при създаване на обекта;

·        деструктор;

·        чисто виртуалните функции:

o       virtual void input()=0;       - въвеждане на личните данни на обекта;

o       virtual void output()=0;    - изваждане на екрана на личните данни на обекта;

o       virtual float get_sortkey()=0;        - формиране на ключ, по който ще се оценява позицията на съответния обект при сортирането на елементите на списъка. В класът наследник в зависимост от данните и предпочитанията на програмиста могат да бъдат заложени различни функции на оценяване на теглото на обекта, в това число и различни хеш-функции.

Тези функции ще въдат предефинирани в класа наследник, в който ще бъдат описани конкретните данни, съдържащи се в този възел.

·  void set_next(Node *n); - промяна на стойността на указателя към следващия елемент;

·  Node * get_next(); - прочитане на стойността на указателя към следващия елемент.

 

Дефиниция на класа Node.

class Node{

            Node *next;    

public:

            Node();

virtual ~Node(){}

virtual void input()=0;

            virtual void output()=0;

            virtual float get_sortkey()=0;

            void set_next(Node *n);

            Node * get_next();

};

Дефиницията на класа Node е съхранена във файл с името Node.h, а дефинициите на член-функциите - във файл с името Node.cpp.

 

Класът LList съдържа следните компоненти:

·        int check_List(Node **First,Node **End); - прави проверка за изтриване на празен списък и списък от един елемент;

First и End се дефинират в класа-наследник, създаден за конкретната реализация на линейния списък. Те са указатели съответно към първия и последния елемент на списъка. Въпреки, че списъкът е едносвързан, реших за уместно да съхранявам освен адреса на първия елемент, и адреса на последния, с цел да ускоря работата на някои член-функции. Понеже  в член-функцията  check_List() се налага да променям стойностите на тези указатели, а функциите в С++ могат да връщат само по една стойност, се наложи да предавам по адрес променливите, в които се съхраняват указателите First и End. Член-функцията връща 1, когато списъкът е празен, т.е. няма какво да се унищожава, или когато писъкът се състои от 1 елемент, който се унищожава  в тази член-функция и 0- във всички останали случаи.

Програмната реализация е следната:

int LList::check_List(Node **First,Node **End)

{

            if(*First==NULL)  return 1;                  //празен списък, не подлежи на обработка

            if(*First==*End)                                   //списък с 1 елемент

            {         

                        delete *First;                            //унищожава се елемента, сочен от указателя First (единственият елемент)

                        *End=*First=NULL;                //нулират се указателите First и End (празен списък)

                        return 1;

            }

            return 0;

}

Член-функцията е с private достъп, т.к. се използва само от член-функциите на класа.

Следващите член-функции са с protected достъп, т.к. се извикват от класа-наследник, създаден за конкретната реализация на линейния списък.

 

·  void MakeFirst(Node *el, Node **First,Node **End); - създава списък от един елемент;

Аргументите на член-функцията MakeFirst са: адресите на указателите First и End са и еl - указател към елемента, който ще се добавя в линейния списък.

Програмната реализация е следната:

void LList::MakeFirst(Node *el, Node **First,Node **End)

{

            *End=*First=el;           // пранасочване на указателите First и End към единствения елемент в списъка

}

 

·  void Add_start(Node *el, Node **First,Node **End); - добавяне на елемент в началото на списъка;

Аргументите са същите, както при член-функцията MakeFirst. Алгоритъма може да се опише по следния начин:

I стъпка.         създаване на елемента (заделяне на памет и попълване на полетата с данни);

II стъпка.      пренасочване на указателя next на новосъздадения елемент към първия за момента елемент;

III стъпка.   пренасочване на указателя за първи елемент (First) към новосъздадения елемент.

 

 

 

 

 

 

 

 

 

 

 

 


Първата стъпка се изпълнява в класа-наследник. За член-функцията Add_start() остават втората и третата стъпки. Програмната реализация е следната:

void LList::Add_start(Node *el, Node **First,Node **End)

{

            if(*First==NULL) {*End=*First=el; return;} //ако списъкът е празен се пренасочват указателите First и End към новосъздадения елемент и се напуска член-функцията.

            el->set_next(*First);                 // ІІ стъпка

            *First=el;                                  //ІІІ стъпка

}

 

·  void Add_end(Node *el, Node **First,Node **End); - добавяне в края на списъка;

Аргументите са същите, както при член-функцията MakeFirst. Алгоритъма може да се опише по следния начин:

I стъпка.         създаване на елемента (заделяне на памет и попълване на полетата с данни);

II стъпка.      пренасочване на указателя next на досегашния последен елемент към новосъздадения елемент;

III стъпка.   пренасочване на указателя за последен елемент (End) към новосъздадения елемент.

 

 

 

 

 

 

 

 


Първата стъпка се изпълнява в класа-наследник. За член-функцията Add_end() остават втората и третата стъпки. Програмната реализация е следната:

void LList::Add_end(Node *el, Node **First,Node **End)

{

            if(*First==NULL) {*End=*First=el; return;} //ако списъкът е празен се пренасочват укъзътелите First и End към новосъздадения елемент и се напуска член-функцията.

            (*End)->set_next(el);               //ІІ стъпка

            *End=el;                                  //ІІІ стъпка

}

 

·        void Add_mid(Node *el,Node *bel,Node **First,Node **End); - добавяне в средата на списъка;

Аргументите са същите, както при член-функцията MakeFirst плюс bel-адреса на елемента, след който ще става добавянето. Алгоритъма може да се опише по следния начин:

I стъпка.         създаване на елемента (заделяне на памет);

II стъпка.        пренасочване на указателя next на новосъздаденият елемент от списъка, т.е. копира се стойността на указателя next  на текущият елемент(този след който ще се добавя) в указателя next на новосъздадения;

III стъпка.     пренасочване на указателя next на текущият елемент към новосъздаденият.

 

 

 

 

 

 

 

 


Първата стъпка се изпълнява в класа-наследник. За член-функцията Add_mid() остават втората и третата стъпки.

Програмната реализация е следната:

void LList::Add_mid(Node *el,Node *bel,Node **First,Node **End)

{

            if(bel==NULL) { Add_start(el,First,End); return;} //ако предишният елемент е с адрес NULL, т.е. добавянето трябва да стане в началото на списъка се извиква член-функцията Add_start.

            if(bel==*End) { Add_end(el,First,End); return;} //ако предишният елемент е с адрес End, т.е. добавянето трябва да стане в края на списъка се извиква член-функцията Add_end.

            el->set_next(bel->get_next());              //ІІ стъпка

            bel->set_next(el);                                             //ІІІ стъпка

}

 

·        void Del_start(Node **First,Node **End); - премахване на първия елемент от списъка;

Адресите на указателите First и End са аргументи на член-функцията. Алгоритъма може да се опише по следния начин:

I стъпка.           създава се помощна променлива, в която се запомня адреса на първия елемент;

II стъпка.        пренасочва се указателя First към втория елемент;

III стъпка.     унищожава се досегашният първи елемент.

 

 

 

 

 

 

 

 

 

 


Програмната реализация е следната:

void LList::Del_start(Node **First,Node **End)

{

            if(check_List(First,End)) return;            //Ако функцията check_List върне 1, следва че или списъкът е празен или се е състоял от единствен елемент, който е премахнат от тази функция.

            Node *pom=*First;                  //І стъпка

            *First=(*First)->get_next();      //ІІ стъпка

            delete pom;                              //ІІІ стъпка

            if((*First)->get_next()==NULL) *End=*First;  //Ако указателя  next на първия елемент има стойност  NULL, следва че списъкът е само с 1 елемент и се пренасочва указателя End към него. Изразът (*First) е заграден в коби за да се определи последователността на изпълнение на операторите, т.к. операторът * и операторът –> са с еднакъв приоритет.

}

 

·  void Del_end(Node **First,Node **End);- премахване на последния елемент от списъка;

Адресите на указателите First и End са аргументи на член-функцията. Алгоритъма може да се опише по следния начин:

I стъпка.           обхожда се списъка, за да се намери адреса на предпоследния елемент;

II стъпка.        пренасочване на указателя за последен елемент към предпоследния до момента;

III стъпка.     унищожава се последния елемент;

IV стъпка.     указателя next на  предпоследния елемент се нулира.

 

 

 

 

 

 

 

 

 

 


За да се намери адреса на предпоследния елемент е необходимо да се обходи целия списък, като се започне от първия елемент, като се използва помощна променлива (pom), в която се помни адреса на текущия елемент и да се следи стойността на указателя next на този елемент. Ако тя е NULL, то в pom се съдържа адреса на последния елемент на списъка и цикъла се напуска. В тялото на цикъла стойността на pom се запомня в променливата el. По този начин в el винаги се намира адреса на предходния елемент на pom. В момента, в който в pom се намира адресът на последния елемент, следва че в el ще се намира адресът на предпоследния елемент.

Програмната реализация е следната:

void LList::Del_end(Node **First,Node **End)

{

            if(check_List(First,End)) return; //Ако функцията check_List върне 1, следва че или списъкът е празен или се е състоял от единствен елемент, който е премахнат от тази функция.

////І стъпка. Цикъл за обхождане на списъка и намиране на адреса на предпоследния елемент. В pom – адреса на текущия елемент, а в се съхранява адреса на предшестващия  pom елемент. При напускане на цикъла в el остава адреса на предпоследния елемент.

      for(Node *el=NULL,*pom=*First ;  pom->get_next()!=NULL ;  pom=pom->get_next())                    el=pom;

      *End=el;          //ІІ стъпка

      delete (*End)->get_next();        //ІІ стъпка

      (*End)->set_next(NULL);        //ІІІ стъпка

}

 

·        void Del_mid(Node *el,Node **First,Node **End); - премахване на елемент от средата на списъка;

Аргументи на член-функцията са адресите на указателите First и End и адресът на елемента, който предстои да бъде премахнат. Алгоритъма може да се опише по следния начин:

I стъпка.           обхожда се списъка, за да се намери адреса на предходния елемент;

II стъпка.        указателя next на  предходния елемент се насочва към следващия след зададения елемент  (взема се адреса от неговия указател next);

III стъпка.     унищожава се зададения елемент.

 

 

 

 

 

 

 

 

 


За да се намери адреса на предходния елемент е необходимо да се обходи списъка, като се започне от първия елемент до достигане на зададения, като се използва помощна променлива (pom), в която се помни адреса на текущия елемент и да се следи стойността на указателя next на този елемент. Ако тя съвпада с адреса на зададения елемент, то следва че в pom се съдържа адреса на предходния елемент и цикъла се напуска. Тъй като в цикълът се използва само за  откриване на адреса на предходния елемент, тялото му е празно (състои се от празния оператор - ;)

Програмната реализация е следната:

void LList::Del_mid(Node *el,Node **First,Node **End)

{

      if(el==NULL) return;

      if(check_List(First,End)) return;

      if(el==*First) {Del_start(First,End); return;}

      if(el==*End) {Del_end(First,End); return;}

      for(Node *pom=*First ; pom->get_next()!=el ; pom=pom->get_next());//!! знакът ; не е грешка

      pom->set_next(el->get_next());

      delete el;

}

 

·        void Clear(Node*First); - унищожава целия списък;

Т.к. стойностите на указателите First и End няма да се променят, се подава като аргумент само стойността на First.

Програмната реализация е следната:

void LList::Clear(Node * First)

{

            if(First==NULL)          return;              //списъкът вече е празен

            Node *el;

//Цикъл за обхождане на списъка. В pom се съхранява адреса на текущия елемент.

            for(Node *pom=First ; pom->get_next()!=NULL ; )

            {

                        el=pom->get_next();     // В указателя el се съхранява адресът на следващия елемент.

                        delete pom;                  //унищожава се текущия елемент.

                        pom=el;                        //текущ става следващият елемент.

            }

}

 

·        long Count(Node *Frst); - преброява елементите в списъка;

Т.к. стойностите на указателите First и End няма да се променят, се подава като аргумент само стойността на First. Член-функцията преброява елементите и връща броя им.

Програмната реализация е следната:

long LList::Count(Node *First)

{

            long n=0;                      //брояч

//цикъл за обхождане на списъка

            for(Node *pom=First ; pom!=NULL ; pom=pom->get_next(),n++);

            return n;

}

 

·        void Sort(Node **Frst, Node **End, int dir); - сортира елементите в списъка

Аргументи на член-функцията са адресите на указателите First и End и една променлива от цял тип, която показва посоката на сортиране: нагоре или надолу (Ascending или Descending).

Алгоритъма е разновидност на метода на прякото вмъкване. Списъкът се обхожда от ляво на дясно, като се започне от втория елемент. За всеки елемент (за яснота ще го наричаме текущ елемент - tel) се търси мястото му между елементите, стоящи от ляво на него, като се започне от първия елемент на списъка. Обхождането на подсписъка се реализира посредством вложен цикъл. Променливата pom сочи елемента, с който се извършва сравняването, а before_pom- предходния на  pom елемент. Когато се намери мястото му (адреса на елемента, след който трябва да бъде вмъкнат е before_pom) се проверява дали се налага преместване, т.е. дали указателят pom не сочи текущия елемент. Ако се налага преместване, се изпълняват следните стъпки:

I стъпка.           Изключва се елемента от списъка (без да се унищожава; адресът му се помни в променливата tel);

 

 

 

 

 

 


II стъпка.        Елемента се вмъква на съответното място.

 

 

 

 

 

 

 


При вмъкването се прави проверка дали не се налага вмъкване в началото на списъка, т.е. дали pom няма стойност NULL. Ако вмъкването е в началото, се коригира и указателя First.

След подреждането на целия списък с помощта на цикъл се обхожда този списък и се актуализира указателят End.

Т.к. данните могат да са сложни, сравняването става на базата на ключ, който се получава от метода get_sortkey() на обекта.

Променливата dir определя само посоката на сравняване: > нарастващ ред (dir=0) и < при намаляващ ред (dir=1).   

Програмната реализация е следната:

void LList::Sort(Node **First,Node **End, int dir)

{

   if(*First==NULL) return;

   if(*First==*End) return;

   float x;

   Node *pom, *before_pom, *before_el, *tel;

   for(before_el=*First,tel=(*First)->get_next() ; tel!=NULL ; tel=tel->get_next())

   {

               x=tel->get_sortkey();

               for(pom=*First,before_pom=NULL ; pom!=tel ; pom=pom->get_next())

               {

                           if(dir==0)

                           {if(pom->get_sortkey() > x)     break;}

                           else

                           {if(pom->get_sortkey() < x)     break;}

                           before_pom=pom;

               }

               if(pom!=tel)                  //ако се налага преместване

               {

                           before_el->set_next(tel->get_next());    //изключване

                           if(pom==*First)                                                                                    //добавяне в началото

                           {

                                       tel->set_next(*First);

                                       *First=tel;

                           }

                           else                                                                  //добавяне в средата

                           {

                                       tel->set_next(before_pom->get_next());

                                       before_pom->set_next(tel);

                           }

                           tel=before_el;

               }

               before_el=tel;

   }

   for(pom=*First ; pom->get_next()!=NULL ; pom=pom->get_next());//откриване на адреса на последния елемент

   *End=pom;

}

 

·        void OutList(Node *First); - извежда целия списък на екрана;

Т.к. стойностите на указателите First и End няма да се променят, като аргумент на член-функцията се подава само стойността на First.

За да се изведат стойностите на елементите на линеен списък на екрана е необходимо да се обходи целия списък, като се започне от първия елемент. Използва се помощна променлива (pom), в която се помни адреса на текущия елемент и се следи стойността на указателя next на този елемент. Ако тя е NULL, то в pom се съдържа адреса на последния елемент на списъка и цикъла се напуска. В тялото на цикъла се извиква метода output() на конкретния обект, който е от клас, наследник на Node (проява полиморфизъм).

Програмната реализация е следната:

void LList::OutList(Node *First)

{

      cout<<"List is: ";

//цикъл за обхождане на списъка

      for(Node *pom=First ; pom!=NULL ; pom=pom->get_next())

      {

            pom->output();//извеждане на данните на конкретния обект, сочен от указателя pom;

            cout<<" ";

      }

      cout<<'\n';

}

 

 

Дефиниция на класа LList.

class LList{

      int check_List(Node **First,Node **End);//проверка за изтриване на празен списък и списък от един елемент

public:

      LList();

      ~LList();

protected:

      void MakeFirst(Node *el, Node **First,Node **End);//създава списък от един елемент

      void Add_start(Node *el, Node **First,Node **End);//добавяне в началото

      void Add_end(Node *el, Node **First,Node **End);//добавяне в края

      void Add_mid(Node *el,Node *bel,Node **First,Node **End);//добавяне в средата

      void Del_start(Node **First,Node **End);//премахване на първия елемент

      void Del_end(Node **First,Node **End);//премахване на последния елемент

      void Del_mid(Node *el,Node **First,Node **End);//премахване на елемент в средата

      void Clear(Node*First);

      long Count(Node *Frst);

      void Sort(Node **Frst, Node **End);

      void OutList(Node *First);//извежда целия списък

};

Дефиницията на класа LList е съхранена във файл с името LList.h, а дефинициите на член-функциите - във файл с името LList.cpp.

 

2.2.             Класове наследници, дефиниращи възлите на списъка.

Данните, които ще се съхраняват в отделните възли на списъка се декларират в класове, наследници на класа Node. В тези класове освен данните, задължително трябва да се дефинират и виртуалните функции на класа Node. Като примери в настоящата работа съм представила 3 класа: MyFloatList, MyCharList и MyStringList, с помощта на които реализирам списък с елементи, които са числа с плаваща запетая; списък с елементи, които са символи; списък с елементи, които са символни низове.

Класът MyFloatList съдържа следните компоненти:

·          float d – стойността на данните на елемента,

два конструктора:

·           без параметри, в който се нулира полето d;

·          с един параметър, който се присвоява на полето d

и следните член-функции с публична достъпност:

·           virtual void input() – въвеждане на стойност за d от клавиатурата;

·          virtual void output() – извеждане на стойността на d на екрана;

·          virtual float get_sortkey() – връща стойността на ключа за сортиране, в случая стойността на d.

Дефиниция на класа MyFloatList.

class MyFloatList : public Node 

{

   float d;

public:

   MyFloatList();

   MyFloatList(float x);

   virtual ~MyFloatList();

   virtual void input();

   virtual void output();

   virtual float get_sortkey();

};

Дефиницията на класа MyFloatList е съхранена във файл с името MyFloatList.h, а дефинициите на член-функциите - във файл с името MyFloatList.cpp.

 

Класът MyCharList съдържа следните компоненти:

·          float ch – стойността на данните на елемента,

два конструктора:

·           без параметри, в който се нулира полето ch;

·          с един параметър, който се присвоява на полето ch

и следните член-функции с публична достъпност:

·           virtual void input() – въвеждане на стойност за ch от клавиатурата;

·          virtual void output() – извеждане на стойността на ch на екрана;

·          virtual float get_sortkey() – връща стойността на ключа за сортиране, в случая ASCII кода  на ch.

Дефиницията на класа MyCharList е съхранена във файл с името MyCharList.h, а дефинициите на член-функциите - във файл с името MyCharList.cpp.

 

Дефиниция на класа MyCharList.

class MyCharList : public Node 

{

   char ch;

public:

   MyCharList();

   MyCharList(char c);

   virtual ~MyCharList();

   virtual void input();

   virtual void output();

   virtual float get_sortkey();

};

Дефиницията на класа MyCharList е съхранена във файл с името MyCharList.h, а дефинициите на член-функциите - във файл с името MyCharList.cpp.

 

Класът MyStringList съдържа следните компоненти:

·          float s – стойността на данните на елемента,

два конструктора:

·           без параметри, в който се нулира полето s;

·          с един параметър, който се присвоява на полето s

и следните член-функции с публична достъпност:

·           virtual void input() – въвеждане на стойност за s от клавиатурата;

·          virtual void output() – извеждане на стойността на s на екрана;

·          virtual float get_sortkey() – връща стойността на ключа за сортиране. В случая ключа се изчислява чрез позиционна хеш-функция.

Дефиницията на класа MyStringList е съхранена във файл с името MyStringList.h, а дефинициите на член-функциите - във файл с името MyStringList.cpp.

 

2.3.             Класове наследници, дефиниращи вида на списъка.

Докато базовите класове изграждат скелена на линейната структура, класовете наследници се използват за създаване на действителната линейна стуктура.

Клас List

За изграждането на едносвързан линеен списък съм създала класа List, наследник на класа LList. В него, като лични данни съм дефинирала указателите First и End, съответно за първи и последен елемент на линейния списък. В конструктора тези указатели се нулират. В деструктора се извиква член-функцията Clear(), която унищожава целият списък, освобождава заетата от него памет и нулира указателите First и End.

Член-функцията AddToStart реализира добавяне на елемент в началото на линейния списък. Тя има един аргумент от тип Node (указател към елемента, който ще се добавя). Тя извиква член-функцията на базовия клас Add_start, като й подава за аргументи указателят към новия елемент и адресите на указателите First и End.

Член-функцията AddToEnd реализира добавяне на елемент в края на линейния списък. Тя има един аргумент от тип Node (указател към елемента, който ще се добавя). Тя извиква член-функцията на базовия клас Add_end, като й подава за аргументи указателят към новия елемент и адресите на указателите First и End.

Член-функцията AddSort реализира добавяне на елемент към линейния списък, като търси неговата позиция спрямо останалите елементи, така че списъкът да е сортиран. Тя има два аргумента- указателят към новия елемент и целочислено число, което показва посоката на сортиране: 0 – нарастващ ред, 1 – намаляващ ред. С помощта на цикъл се обхожда списъкът, докат се намери мястото на елемента. В променливата tel се съхранява адреса на текущия елемент в списъка, а в променливата pom – адресът на неговия предшественик. Сравняването става по стойността на сортиращия ключ. Ако сортирането е в нарастващ ред, се търси елемент със стойност по-голяма от новия, и новият се вмъква преди него (поради таова вмъкване “преди” се налага помненето на адреса на елемента, предхождащ текущия). Ако сортирането е в намаляващ ред - елемент със стойност по-малка от новия.

След като бъде открита позицията на елемента, се извиква член-функцията на базовия клас Add_mid().

Програмната реализация е следната:

void List::AddSort(Node *el,int dir)

{

   Node *tel, *pom;

   if(dir==0)                     //нарастващ ред

               for(pom=NULL,tel=First ; tel!=NULL ; tel=tel->get_next())

               {

                           if(tel->get_sortkey() > el->get_sortkey())          break;

                           pom=tel;

               }

   else                              //намаляващ ред

               for(pom=NULL,tel=First ; tel!=NULL ; tel=tel->get_next())

               {

                           if(tel->get_sortkey() < el->get_sortkey())          break;

                           pom=tel;

               }

   Add_mid(el,pom,&First,&End);

}

 

Член функциите RemoveFromStart() и RemoveFromEnd() изключват съответно първия и последния елемент от списъка. Те просто извикват съответните член-функции на базовия клас.

Интерес представлява член-функцията RemoveElement(). Тя има за аргумент указателя към обект, съдържащ данните, които трябва да се изтрият от списъка. За търсене на елемента, съдържащ тези данни отново се използва член.функцията get_sortkey(). Т.к. тази член-функция връща число с плаваща запетая, сравняването трябва да се извършва с някаква точност – числото E. Ако елементът бъде открит, се извиква член-функцията на  Del_mid() на базовия клас.

Програмната реализация е следната:

int List::RemoveElement(Node *el)

{

   double E=0.0001;                    //точност на сравняването

   for(Node *pom=First ; pom!=NULL ; pom=pom->get_next())

   {

               if(abs(pom->get_sortkey() - el->get_sortkey())<E)       break;

   }

   if(pom!=NULL) {         Del_mid(pom,&First,&End); return 1;}

   else return 0;

}

Член-функциите Sort(), Clear(), OutList() и Count() просто извикват съответните член-функции на базовия клас. Т.к. имената на функциите в базовия клас и наследника съвпадат се използва уточненото им име.

 

Дефиниция на класа List.

class List : public LList 

{

   Node *First,*End;

public:

   List();

   virtual ~List();

   void AddToStart(Node *el);

   void AddToEnd(Node *el);

   void AddSort(Node *el,int dir);

   void RemoveFromStart();

   void RemoveFromEnd();

   int RemoveElement(Node *el);

   void Sort(int dir);

   void Clear();

   void OutList();

   long Count();

};

Дефиницията на класа List е съхранена във файл с името List.h, а дефинициите на член-функциите - във файл с името List.cpp.

2.4.             Демострационни тестващи програми.

ListDemo

Програмата ListDemo демонстрира възможностите на класа List, като във възлите на списъка са разположени обекти от тип MyFloatList. За целта съм създала главна функция main, в която се дефинира обекта А от тип List. Указателят elA е от тип MyFloatList и се използва за съхраняване на адреса на новосъздадения елемент.  Указателят pomA от тип MyFloatList е помощен. Целочислените променливи  k и m се използват за избор на точка от менюто и подменютата.

В тялото на тази функция се извежда меню, състоящо се от 10 команди. Всяка една от командите се избира чрез нейния номер. Оператор switch осигурява изпълнението на избраното действие. Изборът на командите “Sort the List “ и “Add sort” води до извеждане на подменю за избор на посоката на сортиране.

Безкраен цикъл for осигурява многократното извеждане на менюто. От програмата се излиза, като се въведе номера на командата End.  За по-добра нагледност при всяко завъртане на цикъла се показва съдържанието на списъка.

Програмната реализация е следната:

void main()

{

            List A;

            MyFloatList *elA, *pomA;

            int k,m;

            for(;;)               //безкраен цикъл

            {

                        cout<<"\n1.Add to List on Start\n";

                        cout<<"2.Add to List on End\n";

                        cout<<"3.Remove from Start\n";

                        cout<<"4.Remove from End\n";

                        cout<<"5.Sort the List\n";

                        cout<<"6.Add sort\n";

                        cout<<"7.Remove element\n";

                        cout<<"8.Count of List elements\n";

                        cout<<"9.Clear the List\n";

                        cout<<"10.End\n";

                        cout<<"Choice (1-10):";cin>>k;

                        switch(k)

                        {

                        case 1:  elA=new MyFloatList; //създаване на новия елемент

elA->input();                //въвеждане на данните на новия елемент

A.AddToStart(elA);     //добавяне на елемента в началото на списъка

break;

                        case 2:  elA=new MyFloatList; //създаване на новия елемент

elA->input();                //въвеждане на данните на новия елемент

A.AddToEnd(elA);       //добавяне на елемента в края на списъка

break;

                        case 3:  cout<<"A: ";                 //подсказка

A.RemoveFromStart(); //изключване на първия елемент от списъка

cout<<'\n';                    //нов ред

break;

                        case 4:  cout<<"A: ";                 //подсказка

A.RemoveFromEnd();//изключване на първия елемент от списъка

cout<<'\n';                    //нов ред

break;

                        case 5:             

                                    do{                  //цикъл за избор на посоката на сортиране

                                                cout<<"Direction:\n  1.Ascending.\n  2.Descending.\nChoose (1 or 2)";

                                                cin>>m;

                                                switch(m)

                                                {

                                                case 1:  A.Sort(0);        break;  //сортиране в нарастващ ред

                                                case 2: A.Sort(1);         break; //сортиране в намаляващ ред

                                                }

                                    }while (m<1 || m>2);

                        break;

                        case 6:  elA=new MyFloatList; //създаване на новия елемент

elA->input();                //въвеждане на данните на новия елемент

                                    do{                              //цикъл за избор на посоката на сортиране

                                                cout<<"Direction:\n  1.Ascending.\n  2.Descending.\nChoose (1 or 2)";

                                                cin>>m;

                                                switch(m)

                                                {

                                                case 1:  A.AddSort(elA,0);       //добавяне на елемента към списъка, така че елементите да се сортират в нарастващ ред

break;

                                                case 2: A.AddSort(elA,1);        //добавяне на елемента към списъка, така че елементите да се сортират в нарастващ ред

break;

                                                }

                                    }while (m<1 || m>2);

                        break;

                        case 7:  cout<<"Input the element data: "; //подсказка

pomA=new MyFloatList;          //създаване на помощен елемент

pomA->input();                        //въвеждане на данните на помощния елемент

                                    if(A.RemoveElement(pomA))  //изключване на елемента с данни, еднакви с данните на помощния елемент

                                                cout<<"\nSuccess removing.\n";//подсказка

                                    else

                                                cout<<"\nUnsuccess removing.\n";//подсказка

                                    delete pomA;                //унищожаване на помощния елемент

                        break;

                        case 8:cout<<"The element count is:"<<A.Count()<<"\n";                      break;

                        case 9:A.Clear();                      break;

                        case 10:exit(0);             break;  //затваряне на програмата

                        default:cout<<"Error!";

                        }

                        cout<<"A:  ";A.OutList();          //извеждане на всички елементи на списъка

            }

}

Главната функция е съхранена във файл с името ListDemo.cpp. За да се компилира програмата е необходимо да се създаде файл-проект, в който да се включат файловете:

·        ListDemo.cpp

·        List.cpp

·        MyFloatList.cpp.

 

Целият сорс можете да изтеглите от тук.