LastElem^.NextElem:= ServiceVar;
LastElem:= ServiceVar
end
end;
При выборе элемента из очереди информационное поле первого ее элемента должно быть присвоено результирующей переменной, а сам элемент должен быть исключен из очереди и удален. Здесь необходима также проверка на то, являлся ли этот элемент в очереди единственным, и если да, то необходимо соответствующим образом изменить указатель на последний элемент.
procedure SelectFromQueue( var FirstElem, LastElem: Queue; var Result: TypeOfElem);
var
ServiceVar: Queue;
begin
if not ( ( FirstElem= nil ) and ( LastElem= nil ) ) then begin
Result:= FirstElem^.Elem;
ServiceVar:= FirstElem;
{убираем 1-ый элемент из очереди}
FirstElem:= FirstElem^.NextElem;
{был ли это последний элемент}
if FirstElem= nil then
LastElem:= nil;
dispose( ServiceVar )
Из механизма LIFO следует, что в стеке доступен только последний занесенный его элемент √ так называемая вершина стека. Главный элемент, представляющий весь список как единый объект, в случае стека оказывается лишним, его роль выполняет вершина стека. Элемент, занесенный в стек раньше других имеет ссылку nil (см. рис. 6).
Структура данных, представляющая стек, могла бы выглядеть следующим образом:
type
TypeOfElem= {};
Assoc= ^ElementOfStack;
ElementOfStack= record
Elem: TypeOfElem;
NextElem: Pointer
Stack= Assoc;
Рассмотрим реализацию основных операций над стеком.
Для создания нового пустого или очистки существующего стека достаточно присвоить указателю на первый его элемент (вершину) значение nil.
procedure CreateStack ( var StackHead: Stack);
StackHead:= nil
Условием пустоты стека является значение его вершины, равное nil.
function StackIsClear( var StackHead: Stack ): Boolean;
StackIsClear:= ( StackHead= nil )
Для включения элемента в стек, необходимо создать новый элемент типа стек, затем инициализировать его информационное поле. В заключение изменить его указатель и указатель на первый элемент стека так, чтобы первым стал новый элемент.
procedure IncludeInStack( var StackHead: Stack; NewElem: TypeOfElem );
ServiceVar: Stack;
{создание нового элемента}
 new( ServiceVar );
ServiceVar^.Elem:= NewElem;
{созданный элемент сделать вершиной стека}
ServiceVar^.NextElem:= StackHead;
StackHead:= ServiceVar
При выполнении этой операции информационное поле элемента, находящегося в вершине стека, должно быть присвоено в качестве значения некоторой переменой, а сам элемент должен быть исключен из стека и уничтожен.
procedure SelectFromStack( var StackHead: Stack; var Result: TypeOfElem);
ServiceVar: Assoc;
if StackHead <> nil then begin
{выбор элемента из вершины}
Result:= StackHead^.Elem;
{запоминание ссылки на старую вершину}
ServiceVar:= StackHead;
{исключение из стека и уничтожение элемента}
StackHead:= StackHead^.NextElem;
Необходимо обратить внимание на введение вспомогательной переменной ссылочного типа ServiceVar для осуществления удаления элемента. Типична ошибка, связанная с попыткой решить эту задачу через dispose( StackHead ).
Разберем решение типичной задачи, связанной с обработкой стека.
Текст задания
Используя стек (считать уже описанными тип Stack с информационным элементом типа Char, функцию StackIsClear (проверка пустоты стека) и процедуры CreateStack (очистка стека), IncludeInStack (вставка элемента в стек), SelectFromStack (выборка элемента из стека)) решить следующую задачу: в текстовом файле f записана без ошибок формула следующего вида:
<формула>::= <цифра>|M(<формула>,<формула>)|m(<формула>,<формула>)
цифра::= 0|1|2|3|4|5|6|7|8|9
где M обозначает функцию max, а m √ min. Вычислить (как целое число) значение данной формулы (например, M( 5, m( 6, 8)): 6).
Решение
program StackSample;
FileType= File of Char;
Source: FileType;
function formula( var t: FileType ): integer;
TypeOfElem= Char;
S: Stack;
c, op, x, y: char;
new( ServiceVar );
procedure SelectFromStack( var StackHead: Stack; var Result: TypeOfElem );
reset( t );
CreateStack( S );
while not eof( t ) do begin
read(t, c);
{обработка очередной литеры текста (литеры ╚(╩ и ╚,╩ игнорируются)}
if c in ['0'..'9','M','m'] then IncludeInStack( S, c)
else
if c= ')' then begin {конец формулы вида p(x, y)}
{в конце стека находится тройка op x y, она удаляется
из стека, выполняется операция op и результат
записывается в стек}
SelectFromStack( S, y );
SelectFromStack( S, x );
SelectFromStack( S, op );
case op of
'M'{max}: if x > y then c:= x else c:= y;
'm'{min}: if x < y then c:= x else c:= y
IncludeInStack( S, c )
end; {of while}
{в стеке осталась одна цифра √ значение всей формулы; цифра переводится в целое число}
SelectFromStack( S, c );
formula:= ord( c ) - ord( '0' )
assign( Source, 'c:\temp\source.txt' );
writeln( Formula( Source ) );
end.
Элементы двоичного дерева помимо информативной части имеют две ссылки √ на нижний левый и на нижний правый элементы. Принцип построения двоичного дерева заключается в том, что очередной элемент в зависимости от значения информативной части должен попасть в правое (если информационная часть включаемого элемента больше информационной части корня) или левое (в противном случае) поддерево. При этом в рамках выбранного поддерева определение местоположения нового элемента производится аналогично (см. рис. 7).
Данную структуру целесообразно описать следующим образом:
Assoc= ^ElemOfTree;
ElemOfTree= record
Left, Right: Pointer
function FoundInTree( Elem: TypeOfElem; var Tree, Result: Pointer ): Boolean;
b: Boolean;
b:= False;
ServiceVar:= Tree;
if Tree <> nil then
repeat
if ServiceVar^.Elem= Elem then b:= True
if Elem < ServiceVar^.Elem then ServiceVar:= ServiceVar^.Left
else ServiceVar:= ServiceVar^.Right
until b or ( ServiceVar= nil );
FoundInTree:= b;
Result:= ServiceVar
Страницы: 1, 2, 3, 4, 5
