Студопедия

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника



Линейные списки




Читайте также:
  1. Безынерционные нелинейные элементы
  2. Блокирование страниц в памяти. Списки описателей памяти (MDL) и их использование
  3. Главные книги мировых религий. Библия, ее состав, переводы, списки.
  4. Динамические нелинейные звенья САУ
  5. Кадровые и линейные цифровые фотографические системы.
  6. Линейные асинхронные двигатели
  7. Линейные вычислительные процессы
  8. Линейные дефекты
  9. Линейные деформации.
  10. Линейные дифференциальные уравнения

Стеки

Линейным списком называется упорядоченная структура, каждый элемент которой связан со следующим элементом. Наибольшее распространение получили два вида линейных списков: стеки и очереди.

Стек это список типа 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-01-29; просмотров: 8; Нарушение авторских прав







lektsii.com - Лекции.Ком - 2014-2021 год. (0.03 сек.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав
Главная страница Случайная страница Контакты