Линейные списки
Стеки
Линейным списком называется упорядоченная структура, каждый элемент которой связан со следующим элементом. Наибольшее распространение получили два вида линейных списков: стеки и очереди.
Стек это список типа LIFO (последним пришел – первым вышел). Стек имеет одну точку доступа, которая называется вершиной.
Аналогом стека является стопка книг, в которой дополнение и изъятие книг происходит сверху. Другим примером может служить обойма с патронами (магазин), в которой зарядка и подача для стрельбы выполняется с одного конца. Именно этим примером объясняется бывшее в употреблении русскоязычное название стека “магазин”.
Широкое применение нашли стеки в программировании. Иногда они реализуются аппаратным образом. Через стеки передаются параметры при обращении к процедурам. Если имеется цепочка вызова вложенных процедур, то локальные переменные могут сохраняться в стеке, который расширяется при загрузке процедуры и сокращается при возврате из нее. В Ассемблере имеется регистр стека и соответствующие команды для работы с ним.
Стеки могут представляться как в статической, так и динамической памяти. В статическом представлении стек задается одномерным массивом, величина которого определяется с запасом. Пусть он описан в виде Var Stack[1..N] of T, где T – тип элементов стека. Вершина стека задается индексом массива Top.
Дополнение в стек производится командами
Top:= Top+1;
Stack[Top]:=NewElement;
Удаление из стека выполняется командой Top:= Top-1.
Для обработки возможных ошибок при дополнении необходимо проверять выход за границы массива, а при удалении проверять непустоту стека.
Рассмотрим подробнее организацию стека в динамической памяти. Ниже приведен текст программы, позволяющей выполнять операции дополнения, удаления и выдачи на экран элементов стека.
Program StekWork; { процедуры работы со стеком }
Uses Crt;
Type
Ukaz=^Stek;
Stek=record
Name: string;
Next: ukaz
end;
Var
Top, Kon: ukaz;
Rname: string;
C, Pr: char;
B: boolean;
N: integer;
Procedure SozdDob; {создание стека и добавление элементов}
Var B: boolean;
Begin
B:=True;
While B do
Begin
Write('Введите очередной элемент ');
ReadLn(Rname);
if Rname='конец' then B:=False
else
begin
New(Kon);
{ создание элемента стека, на который указывает Kon }
Kon^.Next:=Top;
Kon^.Name:=Rname;
Top:=Kon
end
end;
End;
Procedure Udal; {удаление из стека}
Begin
if Top=Nil then
WriteLn('Попытка удалить из пустого стека !!!')
else
begin
Kon:=Top;
Top:=Top^.Next;
Dispose(Kon);
{ удаление бывшей вершины стека }
end
End;
Procedure Pech; {выдача содержимого стека на экран}
Begin
if Top=Nil then
WriteLn(' Стек пуст !!!')
else
begin
Kon:=Top;
WriteLn(' Состояние стека: ');
While Kon<>Nil do
begin
WriteLn(Kon^.Name);
Kon:=Kon^.Next
end
end
End;
{ НАЧАЛО ОСНОВНОЙ ПРОГРАММЫ }
Begin
ClrScr;
Top:=Nil;
B:=True;
While B do
begin
WriteLn(' Выберите режим работы:');
WriteLn('1-добавление в стек');
WriteLn('2-удаление из стека');
WriteLn('3-выдача на экран');
WriteLn('4-конец работы');
ReadLn(N);
case N of
1: SozdDob;
2: Udal;
3: Pech;
4: B:=False
end
end
End.
Иногда приходится вставлять элементы в середину списка. При статическом описании в этом случае приходится сдвигать часть массива. Это достаточно трудоемкая операция, особенно если она повторяется в цикле.
Для демонстрации гибкости динамических структур данных рассмотрим следующую простую задачу. Имеется стек, описанный в предыдущем примере. Требуется вставить элемент с именем NewName после элемента KeyName. Пусть переменные P и Q имеют тип Ukaz.
P:=Top; B:=True;
While (P<>Nil) and B do
if P^.Name = KeyName then
Begin
B:=False; {для выхода из цикла}
New(Q);
Q^.Name:= NewName;
Q^.Next:=P^.Next;
P^.Next:=Q
End
else P:= P^.Next;
А теперь видоизменим задачу. Пусть вставка требуется перед элементом KeyName. На первый взгляд кажется, что сейчас придется сохранять указатель на предыдущий элемент либо анализировать вместе с текущим и следующий элемент, но указатели позволяют выбрать более простое и красивое решение. Изменения касаются последних трех операторов, следующих после New(Q).
Q^:= P^;
P^.Name:=NewName;
P^.Next:=Q;
Первый оператор обеспечивает копирование элемента KeyName на место вновь организуемого элемента. При этом автоматически обеспечивается связь с элементом, стоявшим ранее после KeyName, так как поле указателя Next также копируется. Остается откорректировать старый элемент KeyName. В качестве упражнения предлагается проследить, потребуются ли изменения в том случае, когда элемент KeyName находится в вершине стека.
Рассмотрим более содержательную задачу. С клавиатуры вводится строка, представляющая собой математическое выражение с вложенными скобками трех видов: “{}”, “[]” и “()”. Старшинство скобок не задано, то есть любая пара скобок может быть вложена в любую другую. Требуется проверить синтаксическую правильность расстановки скобок, что определяется следующим правилом: каждой закрывающей скобке должна предшествовать открывающая того же вида и того же уровня вложенности.
Для решения этой задачи можно использовать стек. Выражение сканируется по символам. Каждая открывающаяся скобка заносится в стек. При встрече закрывающей скобки проверяется символ из вершины стека. Он должен быть открывающей скобкой того же вида. Наконец, по завершению просмотра стек должен быть пустым.
Program Syntax;
{ анализ вложенности скобок, стек на указателях }
Type
Ukaz=^Stek;
Stek=record { элемент стека }
Ch: char; { символ (открывающие скобки) }
Next:ukaz { следующий элемент }
end;
Var
Top, Kon: ukaz;
Vir: string[80]; { исходное выражение }
I, N: integer;
A, B, Pr: char;
Procedure Dob;
{ добавление в стек; A-добавляемый символ }
Begin
New(Kon);
Kon^.Next:=Top;
Kon^.Ch:=A;
Top:=Kon
End;
Procedure Udal(var Pr:char);
{ исключение из стека; Pr='e'-признак ошибки }
Begin
Pr:='o';
if Top=Nil then Pr:='e'
else
case A of
')': if Top^.Ch<>'(' then Pr:='e';
']': if Top^.Ch<>'[' then Pr:='e';
'}': if Top^.Ch<>'{' then Pr:='e';
end;
if Pr<>'e' then
begin { удаление элемента из вершины }
Kon:=Top;
Top:=Top^.Next;
Dispose(Kon);
end
End;
Begin { начало основной программы }
WriteLn('Введите выражение');
ReadLn(Vir);
Top:=Nil;
N:=Length(Vir); { длина выражения }
For I:=1 to N do
begin
A:=Vir[I]; { очередной символ }
case A of
'(','[','{': Dob;
{ добавление в стек открывающей скобки }
')',']','}':
begin
Udal(Pr);
{ проверка вершины стека; удаление, если нет ошибки }
if Pr='e' then
begin
WriteLn('Ошибка в позиции ', I);
ReadLn; { пауза }
Exit { выход из программы }
end
end
end
end;
if Top<>Nil then
{ в конце не пустой стек }
WriteLn('Нет последних закрывающих скобок')
else
WriteLn('Все в порядке !!!');
ReadLn { заключительная пауза }
End.
Эта программа легко корректируется (на уровне контекстной замены) для случая статического представления стека с помощью массива. Приведем описание переменных и процедур данной версии программы.
Program Syntax; { анализ вложенности скобок, стек - массивом }
Var
Stek:array [1..80] of char;
Top, Kon: integer;
Vir: string[80]; { исходное выражение }
I, N: integer;
A, B, Pr: char;
Procedure Dob;
{ добавление в стек; A-добавляемый символ }
Begin
Top:=Top+1;
Stek[Top]:=A
End;
Procedure Udal(var Pr:char);
{ исключение из стека; Pr='e'-признак ошибки }
Begin
Pr:='o';
if Top=0 then Pr:='e'
else
case A of
')': if Stek[Top]<>'(' then Pr:='e';
']': if Stek[Top]<>'[' then Pr:='e';
'}': if Stek[Top]<>'{' then Pr:='e';
end;
if Pr<>'e' then Top:=Top-1;
{ удаление элемента из вершины }
End;
Программа может быть усовершенствована. В приведенном варианте не анализируется допустимость символов выражения, не проводится анализ характера ошибки, просмотр выполняется до первой ошибки и т.п.
Дата добавления: 2015-08-21; просмотров: 847;