выбор того или иного представления последовательности в значительной степени зависит от типа операций, выполняемых с элементами последовательности.

Рис. 2.2 Дважды связанный f список

Алгоритм 2.2. Программа на Pascal е включения и исключения элементов из списка

Program (Связанный список данных)

uses CRT;

type

NodePointer=ANode;

Node= RECORD (Элемеш связанного списка} s :Integer; {Элемент последовательности} next .-NodePointer;

{Указатель на следующий элемент}

END;

const first :NodePointer=NIL;

{Указатель начала списка}

{Генерация нового элемента списка} function InitNode: NodePointer;

var newNode :NodePointer;

begin

Now(newKode); {Выделить память новому элементу} newNodeA.s:=Random(99)+1;

newNodeA.next:=NIL; InitNode:=newNode; end;

(Включить новый элемент в начало списка} procedure IncludeNode( newNode: NodePointer );

begin

newNodeA.next:=first; first:=newNode; end;

{Удалить из списка k-й элемент}

procedure ( к: Integer

var previos, current :NodePointer;

i : Integer; begin i i =0 f

current:-first; while currentoNIL do begin i;=i+l;

if i=k then begin { k-й элемент найден}

if first=current then f irst : =currentA. next else previos .next: =current .next;

(Удаление из списка)

dispose(current);

break; end;

previos:=current; current: =currentA. next;

end; end;

procedure (Печать элементов списка}

var p :NodePointer;

begin

WriteLn;

p:=first;

while ponil do begin Write (pA.s:3, i р:=рЛ .next

end; end;

Var (Main) i,m,n : Integer; begin {Main)

ClrScr; Randomize;

n:=17; (Список из п элементов}

for i:=l to n do IncludeNode (InitNode) ;

PrintNodeList;

WriteLn;

m:=17; (Удалить из списка m-й элемент) DeleteNode (m); PrintNodeList; ReadKey; end. (Main)

Алгоритм 2.3. Программа на Си включения и исключения элементов из списка

#include <stdio.h> tinclude <stdlib.h> ttinclude <conio.h>

typedef struct tagNode{ Элемент связанного списка int s; Элемент последовательности tagNode *next; Указатель на следующий элемент

}Node;

typedef Node *NodePointer;

Node *first=NULL; Указатель начала списка NodePointer InitNode( void ){ Генерация нового

NodePointer newNode;

newNode=new Node; Выделение памяти

новому элементу newNode->5=randcm(99) + 1; Значение нового

newNode->next=NULL;

return newNode;

Включить новый элемент в начало списка . void IncludeNode ( NodePointer newNode ) { newNode->next=f irst; first=newNode ;

void DeleteNode ( int k ) { Удалить из списка

k-й элемент NodePointer previos, current; int i; i=0;

current=first; while ( current ! -NULL ) ( i++;

if( i==k ) { k-й элемент найден

iff first= = current ) first=current->next; else previos->next=current->next; Удалить

из списка

delete current; break;

previos=current; current=current->next;

void ( void ){ Печать элементов

списка

NodePointer р; p=first;

while ( p!=NULL ) {

printf( %3d ,p->s) ; p=p->next;

void void

int i,m,n; clrscr() ; randomize() ;

n-=17; Список из п элементов

for( i=0; i<n; i++ ) IncludeNode ( InitNode ( ) ); PrintNodeList (); printf ( \n );

элемент

DeleteNode(m) ; PrintNodeList (); getch();

Связанное представление предпочтительнее лишь в том случае, если в значительной степени используются операции включения и исключения элементов.

2.2. Представление деревьев

Конечное корневое дерево 7формально определяется как непустое конечное множество упорядоченных узлов, таких, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы разбиты на т 0 поддеревьев Т2,..., Т/п.

Корневое дерево на рис. 2.3 содержит 9 узлов, помеченных буквами от а до л Узлы с метками e,f, с, g,h, r являются листьями, остальные узлы - внутренние. Узел с меткой а - корень. Понятие дерева используется в различных аспектах. Деревья - наиболее важные нелинейные объекты, используемые для представления данных в алгоритмах на дискретных структурах.

Рис. 2.3. Корневое дерево с тремя поддеревьями

Важной разновидность корневых деревьев являются бинарные деревья. Бинарное дерево Глибо пустое, либо состоит из выделенного узла, называемого корнем, идвух бинарных поддеревьев: левого 7 , и правого

Лесом называют упорядоченное множество деревьев. Тогда дерево можно определить как непустое множество узлов, такое, что существует один выделенный узел, называемый корнем дерева, а оставшиеся узлы образуют лес с поддеревьями корня.

2.2.1. Представление деревьев

на связанной

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

first

Рис. 2.4. Регулярная связанная структура представления дерева

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

Рис. 2.5. Универсальная связанная структура представления дерева

Применение указателей и связанных списков придает памяти гибкость, необходимую для представления различных структур. Но при этом легко и перестараться; поэтому следует избегать слишком большого количества указателей; сложность программной поддержки таких структур возрастает экспоненциально , теряется четкость основной структуры, которую пытаются представить в памяти (последний пример представления дерева это

наглядно подтверждает).

2.2.2. Представление деревьев на смежной памяти

Представление деревьев на смежной памяти (одномерный

массив) предполагает неявное присутствие ребер, переход по которым выполняется посредством арифметических операций над индексами элементов массива - смежной памяти. Формирование таких деревьев с помощью адресной арифметики можно осуществлять двумя способами. Идея первого способа применима при любом постоянном количестве ребер, выходящих из вершин (регулярное дерево). Рассмотрим данный способ формирования на примере двоичного (бинарного) дерева.

Пусть имеется одномерный массив смежных элементов а2,..., ап. Неявная структура двоичного дерева определяется как на рис. 2.6.

По дереву на рис. 2.6 легко перемещаться в обоих направлениях. Переход вниз на один уровень из вершины а [к] можно выполнить, удвоив индекс k (индекс левого поддерева) или удвоив и прибавив 1 (индекс правого поддерева). Переход вверх на один уровень из вершины а[т] можно вьшолнить, разделив m пополам и отбросив

дробную часть. Рассмотренная структура применима к любому дереву с постоянным количеством ребер, выходящих из вершин.

2-2697

-а[1]

a[2k]

a[2k+l].

a[m]

a[n]

Рис. 2.6. дерево на смежной памяти с последовательной

нумерацией вершин

Другой способ, основанный на индексной арифметике, применим только для двоичных деревьев. Пусть для представления дерева используется одномерный массив а,-, ам,..., dj. Корнем дерева полагают элемент ат, где индекс элемента корня рассчитывается по формуле т = (/+j)/2\, т.е. середина массива. Левое поддерево располагается в массиве в а/+1,..., ат \, а правое поддерево - в массиве ат+1, ат+2,..., dj. Корни поддеревьев рассчитываются подобным же образом, как и корень основного дерева. Второй способ формирования двоичных деревьев на смежной памяти имеет довольно ограниченное применение. Основное его использование - поиск данных, в сортированных массивах, таблицах и т.д.

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

задается в текстовом файле исходных данных. Результаты расчетов всех маршрутов сохранить в выходном текстовом файле. Каждый маршрут представить как последовательную комбинацию меток а,Ь,с посещаемых вершин треугольника при движении по нему. Каждый маршрут должен включать

метку, где первой и последней меткой должна быть вершина а.

Пример файла исходных данных:

Задача. Написать программу поиска всех замкнутых маршрутов длины п< 15 по ребрам треугольника abc. Длину ребра принять равной 1. Начальная и конечная точка искомых маршрутов - вершина а. Длина маршрута п

а

Выходной файл для данного примера:

abcba 1 ababa 2 acaba 3 abaca 4 асаса 5 acbca 6

В алгоритме 2.4 представлена программа расчета всех искомых маршрутов длины я. Алгоритм делится на две части. В первой части (процедура CreateTreeAbc) выполняется формирование двоичного регулярного дерева на смежной памяти рис. 2.7.

Алгоритм 2.4. Программа на Pascal t поиска замкнутых маршрутов по треугольнику Program {Движение по треугольнику АЬс)

uses CRT,DOS;

const n max=$fcOO; {Максимальная память для дерева}

type Vector-array[l..n max] of Char;

var f :Text; {Текстовый файл)

z :Vector; {Двоичное дерево движения по треугольнику} Procedure CreateTreeAbc( n:Integer ) ;

{Формирование дерева}

k, level,m,ml,m2 :LongInt;

begin

z[l]:=a; {Вершина a)

level: =1; {Номер уровня}

ml:=l; {Индекс первой вешины уровня)

m2:=l; {Индекс последней вешины уровня)

while level<=n do begin

for k:=ml to m2 do begin {Заполнить следующий

уровень дерева}

m:=2*k;

case z[k] of

a : begin z[m] :=b; z[m+l]:=c; end;

b: begin г [m] :=c ; z [m+1] :=a; end;

c: begin z [m] :=a; z [m+1 ] : =b; end; end; end;

level:=level+l;

ml:=2*ml; m2:=2*m2+l; end; end;

Procedure RouteTreeAbo( n:Integer ); (Формирование

маршрутов}

i,k,ml,m2,r :LongInt;

begin

r: =0; {Количество маршрутов } k:=l;

for i:=l to n do k:=2*k;

ml:-k;{Индекс первой вершины на последнем уровне! m2:=2*k-l; {Индекс последней вершины

на последнем for i:=ml to m2 do Ьед1п{Проход от листьев

к вершинам дерева}

k:=i;

if z[k]=a then begin r:=r+l; WriteLn(f); repeat

Write(f,z[k]); k:=k div 2; until k=0; Write(f, r) ; end; end; end;

Var {Main> n :Integer; {Длина маршрута

begin {Main}

Assign(f,treeabc.in ) ;

Reset (f); (Фай/ открыт для чтения)

Read(f,n); {Ввод данных}

Close(f);

Assign(f,treeabc.out ) ;

открыт для

CreateTreeAbc(n); (Формировать дерево Abe

сверху вниз) RouteTreeAbc(з) ; (Формировать маршруты

от листьев к вершине)

Close (f); end. {Main}

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

по нему. Два ребра, выходящих из каждой вершины, показывают возможные варианты выбора дальнейшего маршрута продвижения по треугольнику. В каждом случае из вершин а, Ь, с можно попасть в любые две другие вершины. Индексы меток дерева прохода на рис. показывают соответствующее их место в массиве

данных (смежной памяти).

л л л /\ /\ л /С д

6] с[17] с[18]а[19] с[20] а[21] аг22] b[23]
с[24] а[25] а[26] b[27] а[28] b[29] bf30]
ф

b[16] с[17] с[18]а[19] с[20] а[21] af22] b23] с[24] а[25] а[26] b[27] а[28] Ь[29] ЬГЗО] cl]

Рис. 2.7. Двоичное дерево маршрутов по треугольнику на смежной памяти

Во второй части алгоритма выполняется формирование искомых маршрутов (процедура RouteTreeAbc), основой для построения которых служит дерево прохода на рис. 2.7. Для формирования всех маршрутов теперь достаточно подняться по нему от листьев с метками а вершины треугольника к корню, запоминая пройденные метки. Ясно, что число маршрутов будет равно числу

вершин на последнем уровне (количество листьев) с меткой а. 2.3. Представление множеств

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

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

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