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;

1

previos=current; current=current->next;

)

)

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

списка

NodePointer р; p=first;

while ( p!=NULL ) {

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

}

1

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 являются листьями, остальные узлы — внутренние. Узел с меткой а — корень. Понятие дерева используется в различных аспектах. Деревья — наиболее важные нелинейные объекты, используемые для представления данных в алгоритмах на дискретных структурах.