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