2015-04-08
950
Цель работы: научиться строить словари на базе линейных списков и открытого хеширования данных.
Порядок выполнения работы
1. Ознакомиться с теоретической частью лабораторной работы.
2. Выполнить практическое задание.
3. Оформить отчет по лабораторной работе.
Задание. Необходимо реализовать очередь на базе списков, применяя комбинированный алгоритм для ее обслуживания. Затем продемонстрировать выполнение основных операций с элементами очереди: поиск, добавление, удаление.
Использование стеков для построения различных форм представления выражений
Абстрактный тип данных «стек»
Стек – это специальный тип списка, в котором все вставки и удаления выполняются только на одном конце, называемом вершиной (top). В англоязычной литературе для обозначения стеков используется аббревиатура LIFO (last-in-first-out – последний вошел и первый вышел).
Удобным вариантом представления стека является способ на основе списка, в котором добавление новых элементов и извлечение имеющихся происходит с одного конца списка. Значением указателя, представляющего стек, является ссылка на вершину стека. Каждый элемент стека содержит поле ссылки на следующий элемент. В этом случае описать стек можно следующим образом.
Type ptr = ^stack; {Указатель на элемент стека}
Stack = record
data: integer; {Поле данных}
next: ptr;{Указатели на следующий элемент очереди}
End;
Var st: ptr;
Если стек пуст, то значение указателя st равно nil.
Рассмотрим программную реализацию нескольких наиболее часто выполняемых операторов с элементами стека.
1) Процедура записи элементов в стек содержит один параметр: указатель на начало стека. Эта процедура выполняется аналогично вставке элемента в начало списка.
2) Процедура извлечения элементов из стека содержит один параметр: указатель на начало стека. Сначала печатается элемент из вершины стека, а затем изменяется указатель на вершину стека.
1) Procedure WriteStack (var st: ptr);
var i:integer; x:ptr;
begin
for i:=1 to 5 do {В стек заносится пять элементов}
begin
new(x);
readln(x^.data);
x^.next:=st;
st:=x;
end;
end;
2) Procedure print(var st:ptr);
begin
writeln('Вывод элементов стека');
while st<> nil do
begin
writeln (st^.data);
st:= st^.next;
end;
end;
