Производный класс бинарных деревьев

Чтобы учесть специфику иерархической обработки для унификации и систематизации символьных строк в программе, целесообразно сформировать класс StrNode, производный от базового класса бинарных деревьев BiNode. Объекты класса StrNode должны описывать иерархию бинарного дерева, узлы которого предназначены для хранения текстовых строк. Производный класс StrNode должен наследовать компоненты базового класса и содержать собственные частные (private) компоненты-данные и общедоступные (public) компонентные методы, учитывающие особенности иерархической обработки символьных строк. В соответствии с правилами реализации принципа наследования в системе программирования С++, декларацию класса StrNode можно специфицировать следующим образом:

Пример 5

class StrNode: public BiNode

{

private: /*спецификация собственных компонент-данных*/

public: /*спецификация собственных компонентных методов*/

};

 

Категория наследования public выбрана для того, чтобы сохранить в производном классе привилегии доступа к компонентам, установленные в базовом классе.

Пример 6

Class BiNode

{

protected:

BiNode *left;

BiNode *right;

public:

BiNode() { left = right = NULL; }

void inorder (...);

void preorder (...);

void postorder(...);

BiNode* search(void*);

virtual int identify(void*)=0;

virtual BiNode* insert(void*)=0;

};

Class StrNode: public BiNode

{

char *str;

...

public:

StrNode(const char *s);

~StrNode()

{

   cerr<<"String:\""<<str<<"\" is deleted."<<endl;

   delete []str;

}

virtual int identify(void* s)

{

   return strcmp(str,(char*)s);

}

virtual BiNode* insert(void* s)

{

   return(new StrNode((char*)s));

}

StrNode* search(void* s)

{

 ...

}

....

};

 

11.4. Определение линейного списка. Программирование связных списков в C++

Линейный список представляет последовательность из n>0 узлов x[1], x[2],...,x[n], важнейшей структурной особенностью которой является такое расположение элементов списка один относительно другого, как будто они находятся на одной линии. Иначе говоря, в такой структуре следует соблюдать условие: если n>0 и x[1] является первым узлом, а x[n] – последним, то k-тый узел x[k] следует за x[k-1] узлом и перед x[k+1] узлом для любого k лежащего в промежутке от 1 до n.

С линейными списками могут выполняться следующие операции:

· получение доступа к x[k] элементу списка для проверки и/или изменения содержания его полей.

· вставка нового узла сразу до или после x[k] узла.

· удаление x[k] узла.

· объединение в один список двух или более линейных списков.

· разбиение линейного списка на два и более списка.

· создание копии линейного списка.

· определение количества узлов с списке.

· сортировка узлов в порядке возрастания значений в определенных полях этих узлов.

· поиск узла с заданным значением некоторого поля.

Линейные списки, в которых операции вставки, удаления и операции доступа к значению чаще всего выполняются в первом и последнем узле получили специальное название: стек – линейный список, в котором операции вставки и удаления (и как правило доступа к данным) выполняются только на одном из концов списка; очередь (односторонняя очередь) – линейный список, в котором все операции вставки выполняются на одном конце списка, а все операции удаления (и доступа, как правило) – на другом; дек (двухсторонняя очередь) – линейный список, в котором все операции вставки, удаления и доступа выполняются с обоих концов. Различают дек с ограниченным вводом и ограниченным выводом, в котором операция удаления и вставки элементов соответственно выполняется только на одном из концов.

Программирование связных списков в C++.

Под связными списками понимается набор элементов, причем каждый из них является часть узла Node, который также содержит ссылку Link.

struct node{Item item; node *next;};

typedef node* Link;

 

Соответственно узлы в связном списке ссылаются на узлы и поэтому связный список называется самоссылочным.

Простые линейные списки можно рассматривать как последовательность, в которой принято одно из следующих соглашений для ссылки последнего узла, а именно:

пустая (NULL) ссылка, не указывает ни на какой узел

ссылка, которая указывает на фиктивный узел, который не содержит элемента

ссылка, которая указывает на первый узел, делает список циклическим

В каждом случае отслеживание ссылок от первого элемента до последнего формирует последовательность расположения элементов.

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

При объявлении переменной типа node для нее резервируется память во время компиляции. Однако часто приходится организовывать вычисления, связанные с резервирование памяти во время выполнения посредством вызовов системных операторов управления памятью.

Пример 1

link x = new node;

Struct node

{

Item item;

node *next;

node (Item x; node *t)

iteam = x;

next = t;

};

link t = new(x,t);

 

Если хотим удалить элемент

 

t = x -> next;

x -> next = t -> next;

Или

x -> next = x -> next;

x -> next = t;

Если хотим добавить элемент

 

t->next = x -> next;

t ->next = t;

Пример 2

Пример циклического списка (задача Иосифа).

Struct node

{

Item item;

node *next;

node (Item x; node *t)

item = x;

next = t;

};

typedef node *link;

int main(int argc; char *argv[])

{

int i;

N = atoi(argv[1]);

M = atoi(argv[2]);

link t = new node(1,1);

t -> next = t;

link x = t;

for(i=2; i<=N; i++)

x=(x -> next = new node a,t);

while(x! = x -> next)

{

for(i=1; i<N; i++)

x = x -> next;

x -> next + x -> next -> next;

}

cout << x -> item << endl;

}

}

N=9 M=5

517436928

Соглашение о ведущем и завершающем узлах связных списков.

Список циклический (не бывает пустым)

Операция	Реализация
вставка t после i	t -> next = x -> next;
удаление после x	x-> next = t; x -> next = x -> next -> next;
цикл обхода	t = head; do {...t= t -> next;} while(t!= head)
проверка на наличие минимум одного элемента	if (head -> next == head)

 

Ведущий указатель, Null – указатель завершающего узла.

инициализация	head = 0
вставка f после x	if (x==0 || head = t) head -> next =0 else { t -> next = x -> next; x -> next =t; }
удаление после x	t = x -> next; x -> next = t -> next;
цикл обхода	for(t= head; t!=; t = t -> next)...
проверка на пустоту	if(head == 0)