Для стека определены операции занесения в стек и извлечения элемента из стека. Операция занесения элемента в стек определяется только значением элемента. Извлечение элемента заключается в присвоении переменной значения первого элемента стека и удалении этого элемента.
В примере приводится пример программы, которая создает стек и выводит его на экран. После инициализации стек пуст, ввод очередного численного значения добавляет его в начало списка.
Пример. Программа, демонстрирующая работу со стеком.
program stack_demo;
type
nodeptr = ^nodetype;
nodetype = record
number : Integer;
nextnode : nodeptr;
end;
var
stack : nodeptr;
invalue : Integer;
procedure push(var st : nodeptr; value ; Integer);
var
p : nodeptr;
begin
New(p);
Р^.number ::= value;
P^.nextnode := st;
st := p;
end;
procedure write_stack(stack : nodeptr);
var
p : nodeptr;
begin
p := stack;
while p nil do
begin
Writeln(p^.number:3);
p := p^.nextnode;
end;
end;
begin
stack^.nextnode := nil;
WriteLn('Введите элементы стека. Завершение ввода О');
Read(invalue);
while invalue 0 do begin
push(stack, invalue);
Read(invalue);
end;
write_stack(stack);
end.
Очередь, как и стек, является частным случаем списка. Доступ возможен только к первому и к последнему элементам очереди. Данные могут быть добавлены в конец очереди и удалены из ее начала (рисунок - 3). Элемент, который был добавлен в очередь первым, первым достигнет ее начала. Английское обозначение такой структуры данных — FIFO (First In First Out), то есть «первый вошел — первый вышел».
Как и для стека, для очереди определены операции занесения элемента в очередь и его извлечения из очереди.
Пример. Программа, демонстрирующая работу с очередью.
program queue_demo;
type
nodeptr = ^nodetype;
nodetype = record
number : Integer;
nextnode : nodeptr;
end;
var
queue. top. bottom : nodeptr;
invalue : Integer;
procedure in__queue(var top. bottom : nodeptr; value : Integer);
var
p : nodeptr;
begin
New(p);
P^.number := value;
P^.nextnode := nil;
if top = nil then top := p
else bottom^.nextnode := p;
bottom := p;
end;
procedure write_queue(queue : nodeptr.);
var
p : nodeptr;
begin
P := queue;
while p nil do
begin
Write(p^.number:3);
p := p^.nextnode;
end;
end;
begin
queue^.nextnode := nil;
bottom^.nextnode = nil;
WriteLn(‘Введите элементы очереди. Завершение ввода О’);
Read (nvalue);
while invalue 0 do begin
in_queue (queue.bootom.invalue );
Read(invalue);
end;
write_queue(queue);
end.
Структура «дерево» является обобщением линейного списка. В списке каждый узел содержит указатель на другой узел. В дереве каждый узел содержит несколько указателей на несколько узлов. Если указателей два («правый^ и «левый^), такое дерево называется бинарным (рисунок 4). Один из указателей может быть равен nil.
Начальная точка дерева называется корневым узлом. У корневого узла нет входящих в него ветвей, есть только исходящие. Вершина, на которую имеется указатель из другой вершины, называется потолком этой вершины. Последняя, соответственно, называется предком. Если вершина не имеет потолков, она называется терминальной вершиной.
В бинарном дереве целочисленных значений часто придерживаются соглашения о том, что во всех левых вершинах должны находиться меньшие числа, а в правых — большие.
Основные операции над деревьями — это занесение элемента в дерево, удаление элемента из дерева и обход дерева.
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.