12. Очередь, представление и реализация основных операций с помощью динамических переменных.

Графическое представление очереди: имеет две точки доступа. head – для удаления элементов, tail – для добавления элементов.

Описание типа: struct tqueue {int inf; tqueue *next};

1. Инициализация очереди : head = NULL, tail = NULL;

2. Добавление элемента в очередь:

r=new tqueue; r->inf=x; r->next=NULL;

if (head =NULL)

{head = r; tail = r;};

else {tail->next=r; tail = r};

Указатель r ссылается на новый элемент => для вставки надо изменить значения трёх указателей: Указатель на следующий узел в новом узле 1) (r->next=NULL); Указатель на следующий узел в текущем узле 2) (tail->next=r) и внешнего указателя 3) (tail=r). Так как добавляемый элемент всегда последний, то его указующей части r->next присваивается NULL.

3. Взятие элемента из очереди.

if (head!=NULL)

{r=NULL;

x=head-> inf; head=head->next;

delete r;} // удаление 1-го элемента.

r – указатель на 1-ый элемент (r=head).

4. Освобождение динамической памяти, занятой очередью.

void clear_queue (tqueue *&head)

{tqueue *r;

while (head!=NULL)

{r=head; head=head->next; delete r;}}

13. Реализация основных операций со списком: добавление, удаление, поиск.

Описание элемента списка в общем виде:

struct tnode {int inf; tnode *next;}

1. Добавить элемент с указателем p за элементом с указателем q.

p->next=q->next;

q->next=p;

2. Добавить элемент с указателем p перед элементом с указателем q, то есть добавить p после q, а затем поменять местами.

tnode *r =new tnode;

p->next=q->next; q->next=p;

r->inf=p->inf; p->inf=q->inf; q->inf = r->inf;

3. Удалить элемент расположенный за элементом с указателем q.

q->next=q->next->next;

или r=q->next; q->next=r->next; delete r;

4. Удалить элемент с указателем p.

r=first;

if (p==first) {first=first->next; delete r;}

else

{while (r->next!=p) r=r->next;

r1=r->next; r->next=r->next->next; delete r1;}

5. Найти элемент с заданным значением ключевого поля.

r=first; b=1;

while (r!=NULL&&b)

{if (r->inf!=x) r=r->next;

else b=0;};

if (!b) cout<<r->inf<<endl;

14. Деревья, основные операции над деревьями, представление дерева массивом.

Дерево – древовидная структура с базовым типом Т, либо пустая структура, либо узел типа Т, с которым связано конечное число древовидных структур с базовым типом Т поддерева.

Пусть базовый тип – множество букв.

(a (b (d (i) ) (e) (f) ) (c (g) (h (k) (l) ) ) )

Дерево – неориентированный связный граф без циклов с n вершинами и n-1 ребром.

Дерево – конечное множество элементов, называемых узлами: узел у находящийся под узлом х – потомок(сын) х, а узел х – предок(отец) у. Если х на уровне I, то y на уровне i+1.

Корень дерева – узел не имеющий отца. Max. уровень элемента – высота(глубина).

Если узел не имеет сыновей, то он терминальный – лист, а тот, который не является листом – внутренний. Количество потолков узла – степень. Количество ветвей или рёбер, которые надо пройти, чтобы продвинуться от корня к узлу х – длина пути Lx.

Упорядоченное дерево – такое, у которого ветви каждого узла (узлы) упорядочены, то есть следующие 2 дерева будут различны.

Бинарное дерево – множество узлов, каждый из которых либо пуст, либо состоит из узла, связанного с 2-мя различными бинарными деревьями (левое и правое поддеревья узла), то есть каждый узел имеет 0, 1 или 2 сына.

Операции над деревьями:

1. Построение дерева.

2. Добавление элемента в упорядоченное дерево.

3. Удаление элемента из упорядоченного дерева.

4. Обход бинарного дерева. (Прямой +ab, Симметричный a+b, Обратный ab+)/

5. Поиск в дереве величины с ключом равным данному.

Представление массивом: компоненты д.б. типа, 2 поля указывают на поддеревья узла(содержать их адреса), остальные поля – информационная часть – данные, хранящиеся в этом узле.

Tree	Info	Left	Right
1	*	2	3
2	+	6	4
3	-	9	5
4	/	7	8
5	*	10	11
6	A	0	0
7	B	0	0
8	C	0	0
9	D	0	0
10	E	0	0
11	F	0	0

(a+b/c)*(d-e*f)

Struct T {char info;

Int left, right;} Tree[11];

Это позволяет находить путь от корня к узлу, если значением каждого элемента a[i], является указатель на родителя узла i. Корень ссылается либо на себя, либо на 0. Значением одного из полей может быть указатель на родителя:

a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]
0	1	1	2	2	5	5	5	3	3

Значения массива:

Цикл: while(b) {cout<<b<<’\t’; b=a[b];} выведет на экран путь от вершины b к корню. Т.е для b=7 выведет 7521.