1. Булеви функции. Теорема на Пост-Яблонски за пълнота. Нека J2 = { 0, 1}. Всяка функция f : J2n  J

Многократното наследяване на клас води от една страна до затруднен достъп до многократно наследените членове, а от друга страна до поддържане на множество копия на член-данните на многократно наследения клас, което е неефективно. Преодоляването на тези недостатъци се осъществява чрез използването на виртуални базови класове. Чрез тях се дава възможност да се поделят базови класове. Когато един клас е виртуален, независимо от многократното му участие като базов клас (пряк или косвен), се създава само едно негово копие.

В нашия пример, ако класът A се определи като виртуален за класовете B и C, класът D ще съдържа само един поделен базов клас A. Декларацията на базов клас като виртуален се осъществява като в декларацията на производния клас заедно с името и атрибута за област на базовия клас се укаже и запазената дума virtual. Виртуалното наследяване на един клас указва влияние само на наследниците на неговите непосредствени производни класове. То не указва влияние на тези непосредствени наследници. Дефинирането и използването на виртуални класове има редица особености. Една от тях касае дефинирането и използването на конструкторите на наследените класове. Нека A е виртуален базов клас за класа B, класът B е базов за класа D, който пък от своя страна е базов за класа E. Ако класът A има конструктор с параметри и няма конструктор по премълчаване, то този конструктор трябва да се извика в инициализиращия списък не само на класа B, но и на конструкторите D и E. С други думи, конструкторите с параметри на виртуални класове трябва да се извикват от конструкторите на всички класове, които са техни наследници, а не само от конструкторите на непосредствените им наследници. Друга особеност е промяната на реда на инициализиране. Инициализирането на виртуалните базови класове предхожда инициализирането на невиртуалните базови класове. Има и още едно уточнение. Нека класът A е базов виртуален клас за класовете B и C, които от своя страна са базови за класа D. Възможно е атрибутът за област на класа A да е public за класа B и private за класа C. Очевидно ситуацията е нееднозначна – външна функция чрез обект на D няма достъп до компонентите на A по пътя A-C-D, но има достъп по пътя A-B-D. Тази нееднозначност се преодолява с избора, че ако в някоя декларация виртуалният клас е наследен като public, счита се, че този клас се наследява като public навсякъде.

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

В тези два случая тъй като процесът на определяне на реализиране на обръщението към функцията приключва по време на компилация и не може да бъде променян по време на изпълнение на програмата се казва, че има статично разрешаване на връзката или статично свързване. Ще разгледаме пример, с дървовидна йерархия от три класа – клас Point2 за точка в равнината, клас Point3 за точка в пространството, който наследява пряко Point2 и клас ColPoint3 за оцветена точка в пространството, който наследява пряко Point3.

#include

class Point2 {

public:

{ x = a; y = b;}

void Print() const

{ cout << x << “, “ << y; }

private:

int x, y;

};

class Point3 : public Point2 {

Point3 (int a = 0, int b = 0, int c = 0) : Point2 (a, b)

{ z = c; }

void Print () const

{ Point2::Print();

cout << “, “ << z;

}

private:

};

class ColPoint3 : public Point3 {

ColPoint3 (int a = 0, int b = 0, int c = 0, int o = 0)

: Point3 (a, b, c)

{ col = o; }

void Print() const

{ Point3::Print();

cout << “colour: “ << col;

}

private:

};

Сега ще дефинираме примерна функция main.

{ Point2 p2(5, 10);

Point3 p3(2, 4, 6);

ColPoint3 p4 (12, 24, 36, 11);

Point2 *ptr1 = &p3;

ptr1 -> Print();

cout << endl;

Point2 *ptr2 = &p4;

ptr2 -> Print();

cout << endl;

}
Резултатът от изпълнението на тази функция е:

2 4

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

И в трите класа е дефинирана функция Print без параметри

от тип void. Обръщението ptr1 -> Print(); извежда първите две координати на точката p3, а обръщението ptr2 -> Print(); извежда първите две координати на точката p4, т.е. изпълнява се метода Print() на класа Point2 и в двата случая. Още по време на компилация, член-функцията Print() на Point2 е определена като функция на двете обръщения. Определянето става от типа на двата указателя – той е Point2. Връзката е определена статично и не може да се промени по време на изпълнение на програмата.

Ако искаме след свърването на ptr1 с адреса на p3 да се изпълни член-функцията Print() на Point3, а също след свързването на ptr2 с адреса на p4 да се изпълни член-функцията Print() на ColPoint3, са небходими явни преобразувания от следния вид:

((Point3 *)ptr1) -> Print();

((ColPoint3 *)ptr2) -> Print();

В този случай връзките отново са разрешени статично.

При статичното свързване по време на създаването на класа трябва да се предвидят възможните обекти, чрез които ще се викат неговите член-функции. При сложни йерархии от класове това е не само трудно, но понякога и невъзможно. Езикът C++ поддържа още един механизъм, прилаган върху специален вид член-функции, наречен динамично свързване. При него изборът на функцията, която трябва да се изпълни, става по време на изпълнение на програмата. Динамичното свързване капсулира детайлите в реализацията на йерархията. При него не се налага проверка на типа. Разширяването на йерархията не създава проблеми. Това обаче е с цената на забавяне на процеса на изпълнение на програмата. Прилагането на механизма на динамичното свързване се осъществява върху специални член-функции на класове, наречени виртуални член-функции или само виртуални функции. Виртуалните методи се декларират чрез поставяне на запазената дума virtual пред декларацията им, т.е. virtual <тип_на_резултата> <име_на_метод> (параметри);

Да предположим, че е в горния пример член-функцията Print() и в трите класа е декларирана като виртуална. Тогава при обръщенията ptr1 -> Print(); и ptr2 -> Print(); коя функция ще бъде извикана се определя по време на изпълнение на програмата. Определянето е в зависимост от типа на обекта, към който сочи указателя, а не от класа към който е указателя. В случая, указателят ptr1 е към класа Point2, но сочи обекта p3, който е от класа Point3 и затова обръщението ptr1 -> Print(); води до изпълнение на функцита Print() от класа Point3. Аналогично, указателят ptr2 е към класа Point2, но сочи обекта p4, който е от класа ColPoint3 и затова обръщението ptr2 -> Print(); води до изпълнение на функцията Print() от класа ColPoint3.

Ще отбележим някои важни особености на виртуалните функции:

1. 
   Само член-функциите на класове могат да се декларират като виртуални. По технически причини конструкторите не могат да се дефинират като виртуални, но е възможно да има виртуални деструктори.
   
2. 
   Ако в даден клас е декларирана виртуална функция, декларираните член-функции със същия прототип (име, параметри и тип) в производните на класа класове автоматично стават виртуални, дори ако запазената дума virtual не присъства в тяхните декларации.
   
3. 
   Ако в производен клас е дефинирана функция със същото име като определена вече в базов клас като виртуална член-функция, но с други параметри или тип, това ще бъде друга функция, която може да бъде или да не бъде декларирана като виртуална.
   
4. 
   Възможно е виртуална функция да се дефинира извън клас. Запазената дума virtual обаче присъства само в декларацията на функцията в тялото на класа, но не и в нейната дефиниция.
   
5. 
   Виртуалните функции се наследяват като останалите компоненти на класовете.
   
6. 
   Виртуалната функция, която в действителност се изпълнява зависи от типа на аргумента.
   
7. 
   Виртуалните функции не могат да бъдат декларирани като приятели на други класове.
   

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

Съществуват три случая при които обръщението към виртуална функция се разрешава статично (по време на компилация):

1. 
   Виртуалната функция се извиква чрез обект на класа, в който е дефинирана.
   
2. 
   Виртуалната функция се извиква чрез указател към обект, но явно, чрез бинарната операция за разрешаване на достъп :: е посочена конкретната функция.
   
3. 
   Виртуалната функция се активира с тялото на конструктор или деструктор на базов клас.
   

Възможно е виртуалните функции да имат само декларация без да имат дефиниция. Такива виртуални член-функции се наричат чисти. За да се определи една виртуална функция като чиста се използва следния синтаксис:

Клас, който съдържа поне една чисто виртуална функция се нарича абстрактен клас. Основното свойство на абстрактните класове е, че не е възможно от тях да се създават обекти. Чистите виртуални функции могат да се предефинират в производните класове със същите прототипи, а може и да не се предефинират. Когато производния клас наследи чисто виртуална функция без да я предефинира, той също става абстрактен. В случай, че производния клас предефинира всички чисто виртуални функции на своя базов клас, той става конкретен и от него могат да се създават обекти.

Абстрактните класове са предназначени да служат като базови на други класове. Чрез тях се обединяват в обща структура различни йерархии. Обикновено, абстрактните базови класове определят интерфейса за различни типове обекти в йерархията на класовете. Всички обработки в йерархията могат да прилагат един и същ интерфейс, използвайки полиморфизъм – дефинират се указатели от абстрактния базов клас и след това те се използват за полиморфно опериране с обектите на производните конкретни класове.
13. Структури от данни. Стек, опашка, списък, дърво. Основни операции върху тях. Реализация.
Под структура от данни се разбира организирана информация, която може да бъде описана, създадена и обработена с помощта на програма. За да се определи една структура от данни е необходимо да се направи:

• 
  логическо описание на структурата, което я описва на базата на декомпозицията и на по-прости структури, а също на декомпозиция на операциите над структурата на по-прости операции;
  
• 
  физическо представяне на структурата, което дава метода за представяне на структурата в паметта на компютъра.
  

(last in – first out, LIFO).

Широко се използват два основни начина за представяне на стек: последователно и свързвано. При последователното представяне, предварително в паметта се запазва блок, вътре в който се помества стекът и той там расте и се съкращава. При включване на елементи в стека, те се поместват в последователни адреси в неизползваната част веднага след върха на стека.

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

За задаване на стека е достатъчен указател към върха на стека.

В общия случай елементите на стека при свързаното представяне се състоят от две полета – inf (данните, записани в елемента) и link (указател към следващия елемент).

Сега ще дефинираме клас, който реализира свързаното представяне на стек.

Първо ще дефинираме помощен клас Item, който реализира двойната кутия, чрез която се представят елементите на стека.

За по-голяма общност, дефинираме класовете като шаблони.

template class Stack;

template

class Item {

friend class Stack ;

private:

{ inf = x;

link = NULL;

}

T inf;

};

Тъй като класът Item използва класът Stack в декларацията си, затова прототипът на класа Stack предшества декларацията на класа Item. Всички членове на Item са капсулирани. Чрез декларацията за приятелство, класът Item позволява само на класа Stack да създава и обработва негови обекти. Сега вече сме готови да дефинираме класът Stack. Тъй като стекът се реализира в динамичната памет, за този клас трябва изрично да се реализира каноничното представяне – деструктор, обикновени конструктори, конструктор за присвояване и операторна функция за присвояване.

class Stack {

public:

Stack (const T&);

Stack ();

~Stack ();

Stack (const Stack &);

Stack& operator= (const Stack &);

void push (const T&);

bool pop (T&);

bool top(T&) const;

bool empty () const;

private:

Item *start;

void delStack();

void copyStack (const Stack &);

};

template

Stack::Stack (const T& x)

{ start = new Item (x); }

template

Stack::Stack ()

{ start = NULL; }

template

Stack::~Stack ()

{ delStack(); }

template

Stack::Stack (const Stack &r)

{ copyStack(r); }
template

Stack& operator= (const Stack &r)

{ if (this != &r)

{ delStack ();

copyStack (r);

}

return *this;

}

template

void Stack::delStack ()

{ Item *p;

while (start)

{ p = start;

start = start -> link;

delete p;

}

}

template

void Stack::copyStack (const Stack &r)

{ if (!r.start) start = NULL;

else {

Item *p = r.start, *q, *s;

start = new Item(p -> inf);

q = start;

p = p -> link;

while (p)

{ s = new Item (p -> inf);

q -> link = s;

q = s;

p = p -> link;

}

}

}

template

void Stack::push (const T& x)

{ Item *p = new Item(x);

p -> link = start;

start = p;

}

template

bool Stack::pop (T& x)

{ if (!start) return false;

Item *p = start;

x = start -> inf;

start = start -> link;

delete p;

return true;

}

template

bool Stack::top (T& x) const

{ if (!start) return false;

x = start -> inf;

return true;

}

template

bool Stack::empty () const

{ return start == NULL; }

Опашката е крайна редица от елементи от един и същи тип. Операцията включване е допустима за елементите от единия край на редицата, който се нарича край на опашката, а операцията изключване на елемент – само за елементите от другия край на редицата, който се нарича начало на опашката. Възможен е пряк достъп само до елемента, намиращ се в началото на опашката. При тази организация на логическите операции, пръв се изключва най-отдавна включеният елемент. Затова опашката се определя още като структура от данни “пръв влязъл – пръв излязъл”

(first in – first out, FIFO).

Широко се използват два основни начина за физическо представяне на опашка: последователно и свързано.

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

При свързаното представяне последователните елементи на опашката се съхраняват на различни места в оперативната памет, а не в последователно разположени полета. Връзката между отделните елементи се осъществява чрез указател към следващия елемент. Ако елементът е последен в опашката, стойността на този указател трябва да бъде някаква различима стойност (например NULL). За задаване на опашката са достатъчни указатели към началото и края на опашката. В общия случай елементите на опашката при свързаното представяне се състоят от две полета – inf (данните, записани в елемента) и link (указател към следващия елемент). Сега ще дефинираме клас, който реализира свързаното представяне на опашка.

Първо ще дефинираме помощен клас Item, който реализира двойната кутия, чрез която се представят елементите на опашката.

За по-голяма общност, дефинираме класовете като шаблони.

template class Queue;

template

class Item {

friend class Queue ;

private:

Item (const T& x = 0)

{ inf = x;

link = NULL;

}

T inf;

Item *link;

};

Тъй като класът Item използва класът Queue в декларацията си, затова прототипът на класа Queue предшества декларацията на класа Item. Всички членове на Item са капсулирани. Чрез декларацията за приятелство, класът Item позволява само на класа Queue да създава и обработва негови обекти. Сега вече сме готови да дефинираме класът Queue. Тъй като опашката се реализира в динамичната памет, за този клас трябва изрично да се реализира каноничното представяне – деструктор, обикновени конструктори, конструктор за присвояване и операторна функция за присвояване.

template

class Queue {

public:

Queue(const T&);

Queue();

~Queue();

Queue (const Queue &);

Queue& operator= (const Queue &) ;

void InsertElem (const T&);

bool DeleteElem (T &);

bool ViewElem(T &) const;

bool empty() const;

private:

Item *front, *rear;

void delQueue();

void copyQueue (const Queue &);

} ;

template

Queue::Queue(const T& x)

{ front = new Item(x);

rear = front;

}

template

Queue::Queue() {

front = rear = NULL;

}

template

Queue::~Queue() {

delQueue();

}

template

Queue::Queue (const Queue &r)

{ copyQueue (r); }

template

Queue& Queue::operator= (const Queue &r)

{ if (this != &r)

{ delQueue();

copyQueue(r);

}

return *this;

}

template

void Queue::delQueue()

{ T x;

while (DeleteElem(x));

}

template

void Queue::copyQueue(const Queue &r)

{ front = rear = NULL;

if (r.front) {

Item *p = r.front;

while (p)

{ InsertElem (p -> inf);

p = p -> link;

}

}

}

template

void Queue::InsertElem (const T& x)

{ Item *p = new Item(x);

if (front) { rear->link = p; rear = p; }

else front = rear = p;

}

template

bool Queue::DeleteElem (T &x)

{ if (!front) return false;

Item *p = front;

x = p -> inf;

if (front == rear) front = rear = NULL;

else front = front -> link;

delete p;

return true;

}

template

bool Queue::ViewElem(T &x) const

{ if (!front) return false;

x = front -> inf;

return true;

}

template

bool Queue::empty() const

{ return front == NULL; }

Списъкът е крайна редица от елементи от един и същ тип. Операциите включване и изключване на елемент са допустими на произволно място в редицата. Възможен е достъп до всеки елемент на редицата (пряк или непряк в зависимост от реализацията на списъка).

Има два основни начина за представяне на списък в паметта на компютъра: свързано представяне с една връзка, свързано представяне с две връзки и последователно представяне.

При последователното представяне списъкът се представя чрез масив, т.е. елементите на списъка са последователно разположени в паметта, но това представяне не се използва, тъй като включването и изключването на елемент е неефективно и освен това заради добре развитите средства за динамично разпределение на паметта.

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

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

Първо ще дефинираме помощна структура Item, която реализира двойната кутия, чрез която се представят елементите на списъка.

За по-голяма общност, дефинираме структурата Item и класа LList като шаблони.

template

struct Item {

T inf;

Item *link;

};

Сега вече сме готови да дефинираме класът LList. Тъй като едносвързаният списък се реализира в динамичната памет, за този клас трябва изрично да се реализира каноничното представяне – деструктор, обикновени конструктори, конструктор за присвояване и операторна функция за присвояване.

template

class LList {

public:

LList(const T&);

LList();

~LList();

LList(const LList &);

LList& operator= (const LList &);

void IterStart (Item * = NULL);

Item * Iter();

bool IterView(T &) const;

void InsertToEnd (const T&);

void InsertToBegin (const T&);

void InsertAfter (Item *, const T&);

void InsertBefore (Item *, const T&);

void DeleteAfter (Item *, T &);

void DeleteBefore (Item *, T &);

void DeleteElement (Item *, T &);

int length() const;

void print() const;

void concat (const LList &);

void reverse();

bool empty() const;

private:

Item *start, *end, *current;

void delLList();

void copyLList(const LList &);

};

template

LList::LList (const T& x)

{ start = new Item ;

start -> inf = x;

start -> link = NULL;

end = start;

}

template

LList::LList()

{ start = end = NULL; }

template

LList::~LList()

{ delLList(); }

template

LList::LList (const LList &r)

{ copyLList (r); }

template

LList& LList::operator= (const LList &r)

{ if (this != &r)

{ delLList();

copyLList(r);

}

return *this;

}

template

void LList::delLList()

{ Item *p;

while (start)

{ p = start;

start = start -> link;

delete p;

}

end = NULL;

}

template

void LList::copyLList(const LList &r)

{ start = end = NULL;

Item *p = r.start;

while (p)

{ InsertToEnd (p -> inf);

p = p -> link;

}

}

template

void LList::IterStart (Item *p)

{ if (p) current = p;

else current = start;

}

template

Item * LList::Iter()

{ Item *p = current;

if (current) current = current -> link;

return p;

}

template

bool LList::IterView(T &x)

{ if (!current) return false;

x = current -> inf;

return true;

}

template

void LList::InsertToEnd(const T& x)

{ Item *p = new Item;

p -> inf = x;

p -> link = NULL;

if (!start) start = end = p;

else { end -> link = p; end = p; }

}

template

void LList::InsertToBegin(const T& x)

{ Item *p = new Item;

p -> inf = x;

p -> link = start;

start = p;

if (!end) end = p;

}

template

void LList::InsertAfter (Item *p, const T& x)

{ Item *q = new Item;

q -> inf = x;

q -> link = p -> link;

p -> link = q;

if (p == end) end = q;

}

template

void LList::InsertBefore (Item *p, const T& x)

{ Item *q = new Item;

*q = *p;

p -> inf = x;

p -> link = q;

if (end == p) end = q;

}

template

void LList::DeleteBefore (Item *p, T &x)

{ Item *q = start;

if (q -> link == p)

{ x = q -> inf;

start = start -> link;

delete q;

}

else {

while (q -> link -> link != p) q = q -> link;

DeleteAfter (q, x);

}

}

template

void LList::DeleteAfter (Item *p, T &x)

{ Item *q = p -> link;

x = q -> inf;

p -> link = q -> link;

if (end == q) end = p;

delete q;

}

template

void LList::DeleteElement (Item *p, T &x)

{ if (p == start)

{ x = p -> inf;

if (start == end) start = end = NULL;

else start = start -> link;

delete p;

}

else if (p == end) {

Item *q = start;

while (q -> link != end) q = q -> link;

q -> link = NULL;

delete end;

end = q;

}

else DeleteBefore(p -> link, x);

}

template

void LList::print () const

{ Item *p = start;

while (p)

{ cout << p -> inf << ‘ ‘;

p = p -> link;

}

cout << endl;

}

template

int LList::length () const

{ Item *p = start;

int n = 0;

while (p)

{ n++; p = p -> link; }

return n;

}

template

void LList::concat (const LList &r)

{ Item *p = r.start;

while (p)

{ InsertToEnd (p -> inf);

p = p -> link;

}

}

template

void LList::reverse ()

{ Item *p, *q, *temp;

if (start == end) return;

p = start;

q = NULL;

start = end;

end = p;

while (p)

{ temp = p -> link;

p -> link = q;

q = p;

p = temp;

}

}

template

bool LList::empty () const

{ return start == NULL; }

Функциите Iter, IterStart и IterView реализират т.н. итератор. Итераторът е указател към текущ елемент на редица. Общото на всички итератори е тяхната семантика и имената на техните операции. Обикновено операциите са:

++ - приложена към итератор, премества този итератор да сочи към следващия елемент на редицата;

-- - приложена към итератор, премества този итератор да сочи към предишния елемент на редицата;

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

В шаблона LList, итераторът е current. Функцията IterStart инициализира итератора да сочи към началото на списъка, ако за нея не е указан аргумент или е указан аргумент NULL. Ако за нея е указан друг аргумент, той е началната стойност на итератора. Операцията ++ се реализира от функцията Iter, която между другото връща стария итератор. Операцията -- не е реализирана, тъй като списъкът е само с една връзка и тя би била неефективна.

Oперацията * се реализира от функцията IterView.

Сега ще дефинираме клас, който реализира свързаното представяне на списък с две връзки.

Първо ще дефинираме помощна структура Item, която реализира тройната кутия, чрез която се представят елементите на списъка.

За по-голяма общност, дефинираме структурата Item и класа DLList като шаблони.

template

struct Item {

T inf;

Item *pred;

Item *succ;

};

Сега вече сме готови да дефинираме класът DLList. Тъй като двусвързаният списък се реализира в динамичната памет, за този клас трябва изрично да се реализира каноничното представяне – деструктор, обикновени конструктори, конструктор за присвояване и операторна функция за присвояване.

template

class DLList {

public:

DLList(const T&);

DLList();

~DLList();

DLList(const DLList &);

DLList& operator= (const DLList &);

void IterStart (Item * = NULL);

void IterEnd (Item * = NULL);

Item * IterPred();

Item * IterSucc();

bool IterView(T &) const;

void InsertToEnd (const T&);

void InsertToBegin (const T&);

void InsertAfter (Item *, const T&);

void InsertBefore (Item *, const T&);

void DeleteAfter (Item *, T &);

void DeleteBefore (Item *, T &);

void DeleteElement (Item *, T &);

int length() const;

void print() const;

void concat (const DLList &);

void reverse();

bool empty () const;

private:

Item *start, *end, *current;

void delDLList();

void copyDLList(const DLList &);

};

template

DLList::DLList (const T &x)

{ start = new Item ;

start -> inf = x;

start -> pred = start -> succ = NULL;

end = start;

}

template

DLList::DLList()

{ start = end = NULL; }

template

DLList::~DLList()

{ delDLList(); }

template

DLList::DLList (const DLList &r)

{ copyDLList(r); }

template

DLList& DLList::operator= (const DLList &r)

{ if (this != &r)

{ delDLList();

copyDLList(r);

}

return *this;

}

template

void DLList::delDLList()

{ Item *p;

while (start)

{ p = start;

start = start -> succ;

delete p;

}

end = NULL;

}

template

void DLList::copyDLList (const DLList &r)

{ start = end = NULL;

Item *p = r.start;

while (p)

{ InsertToBegin(p -> inf);

p = p -> link;

}

}

template

void DLList::IterStart (Item *p)

{ if (p) current = p;

else current = start;

}

template

void DLList::IterEnd (Item *p)

{ if (p) current = p;

else current = end;

}

template

Item * DLList::IterPred ()

{ Item *p = current;

if (current) current = current -> pred;

return p;

}

template

Item * DLList::IterSucc ()

{ Item *p = current;

if (current) current = current -> succ;

return p;

}

template

bool DLList::IterView (T &x) const

{ if (!current) return false;

x = current -> inf;

return true;

}

template

void DLList::InsertToEnd (const T x)

{ Item *p = new Item ;

p -> inf = x;

p -> pred = end;

p -> succ = NULL;

if (!start) { start = end = p; }

else { end -> succ = p; end = p; }

}

template

void DLList::InsertToBegin (const T x)

{ Item *p = new Item ;

p -> inf = x;

p -> pred = NULL;

p -> succ = start;

if (!end) { start = end = p; }

else { start -> pred = p; start = p; }

}

template

void DLList::InsertAfter (Item *p, const T x)

{ Item *q = new Item ;

q -> inf = x;

q -> pred = p;

q -> succ = p -> succ;

p -> succ = q;

if (q -> succ) q -> succ -> pred = q;

else end = q;

}

template

void DLList::InsertBefore (Item *p, const T x)

{ Item *q = new Item ;

q -> inf = x;

q -> succ = p;

q -> pred = p -> pred;

p -> pred = q;

if (q -> pred) q -> pred -> succ = q;

else start = q;

}

template

void DLList::DeleteAfter (Item *p, T &x)

{ Item *q = p -> succ;

x = q -> inf;

p -> succ = q -> succ;

if (q -> succ) q -> succ -> pred = p;

else end = p;

delete q;

}

template

void DLList::DeleteBefore (Item *p, T &x)

{ Item *q = p -> pred;

x = q -> inf;

p -> pred = q -> pred;

if (q -> pred) q -> pred -> succ = p;

else start = p;

delete q;

}

template

void DLList::DeleteElement (Item *p, T &x)

{ x = p -> inf;

if (start == end) { start = end = NULL; }

else if (p == start)

{ start = start -> succ;

start -> pred = NULL;

}

else if (p == end)

{ end = end -> pred;

end -> succ = NULL;

}

else {

p -> pred -> succ = p -> succ;

p -> succ -> pred = p -> pred;

}

delete p;

}

template

int DLList::length () const

{ Item *p = start;

int n = 0;

while (p)

{ n++; p = p -> succ; }

return n;

}

template

void DLList::print () const

{ Item *p = start;

while (p)

{ cout << p -> inf << ‘ ‘;

p = p -> succ;

}

cout << endl;

}

template

void DLList::concat (const DLList &r)

{ Item *p = r.start;

while (p)

{ InsertToEnd (p -> inf);

p = p -> succ;

}

}

template

void DLList::reverse ()

{ Item *p, *temp;

if (start == end) return;

p = start;

start = end;

end = p;

while (p)

{ temp = p -> succ;

p -> succ = p -> pred;

p -> pred = temp;

p = temp;

}

}

template

bool DLList::empty() const

{ return start == NULL; }

Функциите IterPred, IterSucc, IterStart, IterEnd и IterView реализират т.н. итератор. Итераторът е указател към текущ елемент на редица. Общото на всички итератори е тяхната семантика и имената на техните операции. Обикновено операциите са:

++ - приложена към итератор, премества този итератор да сочи към следващия елемент на редицата;

-- - приложена към итератор, премества този итератор да сочи към предишния елемент на редицата;

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

В шаблона DLList, итераторът е current. Функцията IterStart инициализира итератора да сочи към началото на списъка, ако за нея не е указан аргумент или е указан аргумент NULL. Ако за нея е указан друг аргумент, той е началната стойност на итератора. Аналогично, функцията IterEnd инициализира итератора да сочи към края на списъка, ако за нея не е указан аргумент или е указан аргумент NULL. Ако за нея е указан друг аргумент, той е началната стойност за итератора. Операцията ++ за итератора се реализира от функцията IterSucc, която между другото връща стария итератор. Операцията -- се реализира от функцията IterPred, която между другото връща стария итератор. Операцията * се реализира от функцията IterView.

Каталог: fmi
fmi -> Софтуерни технологии
fmi -> Лекции и семинарни занятия по аналитична геометрия
fmi -> 3d-алгоритъм на Chaikin
fmi -> Лекции по увод в програмирането
fmi -> Лекции и семинарни занятия по линейна алгебра
fmi -> Конкурентно Програмиране
fmi -> Лекции по компютърни мрежи и комуникации
fmi -> Ще предпочетеш да наблюдаваш света отстрани или ще се присъединиш към най-голяма студентска организация?
fmi -> Лекции по обектно-ориентирано програмиране

Изтегляне 5.91 Mb.

Сподели с приятели: