Конспект. Динамические структуры. Стек. Очередь

Вид материала

Конспект

Содержание Описание стека Работа с динамическим стеком Program Stack; Type Var p : tptr; {Вспомогательный указатель} Begin Var p :tptr; {Вспомогательный указатель} Begin Var p : tptr; {Вспомогательный указатель} Begin Определение: Очередь Описание очереди Принципы работы с динамической очередью Program queue; Type Var p:tptr; { Вспомогательный указатель } begin

Подобный материал:

• Список вопросов к зачету, 15.05kb.
• Лекция 2 Стек протоколов tcp/IP, 146.59kb.
• Алгоритмы на графах Поиск по графу, 428.23kb.
• 14. Лекция: Позиционно-силовое управление в системе робота-станка, 113.23kb.
• План лекции Стек tcp/IP. История создания стека tcp/IP, 128.47kb.
• Индивидуальные особенности личности, 403kb.
• Технология программирования. Вопрос, 47.89kb.
• Е. в конспект лекций «материаловедение» ч. 1 конспект, 33.7kb.
• Программа дисциплины «Операционные среды, системы и оболочки», 226.37kb.
• В курсе рассматриваются семь основных тем, 76.92kb.

Стек

Определение: Стек - это данные динамической структуры, которые представляют собой совокупность линейно-связанных однородных элементов, для которых разрешено добавлять или удалять элементы только с одного конца списка, который называется вершиной (головой) стека.


Стек функционирует по принципу LIFO (Last - In - First- Out ) - "последним пришел - первым исключается".

При записи и выборке изменяется только адрес вершины стека. Поэтому каждый стек имеет базовый адрес, от которого производятся все операции со стеком. В случае, когда стек пуст, адреса вершины и основания стека совпадают.

Стек является одной из наиболее часто употребляемых структур в программировании. Это определяется тем, что при работе со стеком нет необходимости прямо использовать адресацию памяти. Самым важным применением стека в программах является использование стека для хранения адресов возврата в программу из подпрограмм или из процедур обработки прерываний, а также передача через стек параметров в процедуры (функции), размещение в стеке локальных параметров процедур. Стеки используются в работе алгоритмов, имеющих рекурсивный характер.

Так как язык Pascal не имеет непосредственно типа данных стек, то для его моделирования наиболее подходящими структурами являются массивы (статический стек для моделирования структур заданного размера ) и динамический стек, при этом структура будет помещаться в динамической памяти, и её размер будет ограничен только размером кучи.


Условно стек можно представить в виде стакана с шариками.





^ Описание стека

Type Tptr=^TElem; {Тип указателя на элемент стека}

TElem = record {Тип элемента стека }

inf :integer; {информационная часть}

link : Tptr; {соединительная часть}

end;

^

Работа с динамическим стеком

Для работы со стеком необходимо иметь один основной указатель на вершину стека (возьмём идентификатор Top) и один дополнительный временный указатель (возьмём идентификатор P), который используется для выделения и освобождения из памяти элементов стека.

• Создание стека.
  

Исходное состояние:

1. Выделение памяти под первый элемент стека и занесение в него информации:
   

2. Установка вершины стека Top на созданный элемент:
   

• Добавление элемента стека.
  
  1. Исходное состояние:
     

2. Выделение памяти под новый элемент стека. Внесение значения в информационное поле нового элемента и установка связи между ним и "старой" вершиной стека Top:
   

3. Перемещение вершины стека Top на новый элемент:
   

• Удаление элемента стека.
  

Исходное состояние

1. Извлечение информации из информационного поля вершины стека Top в переменную Val и установка на вершину стека вспомогательного указателя P:
   

2. Перемещение указателя вершины стека Top на следующий элемент и освобождение памяти, занимаемой "старой" вершиной стека:
   

Пример 1. Разместить в стеке 10 символов и распечатать их в обратном порядке.

Hиже приводится пример программы, использующей стек. В ней используются следующие процедуры для работы со стеком:

• процедура Push(val:real), которая в зависимости от состояния стека создаёт первый или добавляет очередной элемент в вершину стека (английское название push - заталкивать);
  
• процедура Pop(var val:real), которая извлекает информацию из вершины стека с последующим освобождением её из памяти (английское название pop - выскакивать ).
  

^ Program Stack;

Type Tptr = ^TElem; {Тип указателя на элемент стека}

TElem = record {Тип элемента стека}

inf : char; {информационная часть}

link : Tptr; {соединительная часть}

end;


Var top : tptr; {Указатели на конец стека}

value : char;

i: byte;


Procedure Push(val : char; var Top:Tptr); {Процедура добавления элемента}

^ Var p : tptr; {Вспомогательный указатель}

Begin

new (p);

p^.inf:=val;

p^.link:=top;

top:=p

End;


Procedure Pop(var val : char; var Top:Tptr); {Процедура удаления элемента}

Var p : tptr; {Вспомогательный указатель}

Begin

val:=top^.inf;

p:=top;

top:=p^.link;

dispose (p)

End;


Begin

new(top); { Создание указателя на вершину стека }

top:=nil;

for i:=1 to 10 do

begin

writeln (' введите символ');

readln (value);

push(value,Top); {добавление элемента в стек}

end;

i:=10;

while top<>nil do {пока не будет достигнут конец стека}

begin

pop(value, Top); {извлечение элемента из стека}

writeln (i,'-й символ - ',value);

dec (i)

end

End.


Пример 2. Ввести с клавиатуры 8 чисел и сформировать из них два стека. В первый поместить числа, которые делятся на 2, а во второй -остальные. Распечатать оба стека.


Type Tptr=^TElem; {Тип указателя на элемент стека}

TElem = record {Тип элемента стека }

inf :integer; {информационная часть}

link : Tptr; {соединительная часть}

end;


Var top1,top2 : tptr; {Указатели на конец стеков}

value : integer;

i: byte;


Procedure Push(val : integer; var top:tptr); {Процедура добавления элемента}

^ Var p :tptr; {Вспомогательный указатель}

Begin

new (p);

p^.inf:=val;

p^.link:=top;

top:=p

End;


Procedure Pop(var val : integer; var top:tptr); {Процедура удаления элемента}

^ Var p : tptr; {Вспомогательный указатель}

Begin

val:=top^.inf; p:=top;

top:=p^.link; dispose (p)

End;


Begin

new (top1); {Создание указателя на вершину 1-го стека }

new (top2); { Создание указателя на вершину 2-го стека }

top1:=nil; top2:=nil;

for i:=1 to 8 do

begin

writeln (' введите число'); readln (value);

if value mod 2 =0 then

push(value,top1)

else

push(value,top2)

end;

writeln (' 1-й стек - числа делятся на 2 ');

while top1<>nil do

begin

pop(value,top1);

writeln (value);

end;

writeln (' 2-й стек - - числа не делятся на 2');

while top2<>nil do

begin

pop(value,top2);

writeln (value);

end

End.


Задание. Проверить в выражении баланс открывающихся "(" и закрывающихся ")" скобок.

Идея алгоритма заключается в следующем. Если встречается открывающаяся скобка, то в стек помещают какой-либо символ. Если встречается закрывающаяся скобка, то проверяют состояние стека. При этом возможны следующие ситуации:

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

После того, как просмотрена вся строка символов, необходимо проверить состояние стека. Если он пуст, то баланс скобок не нарушен. В противном случае - баланса нет.

Очередь

^ Определение: Очередь - это данные динамической структуры, которые представляют собой совокупность линейно-связанных однородных элементов, для которых разрешены только два действия: добавление элемента в конец (хвост) очереди и удаление элемента из начала (головы) очереди.


Очередь функционирует по принципу FIFO (First - In - First- Out) - "первым пришел - первым исключается".

Очереди можно подразделить на две группы: статистические и динамические.

Статистические очереди представляют собой структуры ограниченной длины (т.е. с фиксированным числом элементов, которые могут одновременно находиться в ней). Как правило, подобные очереди располагаются в памяти как непрерывная последовательность байтов. Простейший пример статистической очереди - одномерный массив.

Динамические очереди фиксированной длины не имеют. Эти очереди могут содержать больший объём данных и позволяют более экономно расходовать оперативную память. Примером структуры такого типа может служить очередь, используемая для обработки событий. Объекты получают данные (события) для обработки из динамической очереди, в которую они поступают по мере появления. Такая структура позволяет буферизировать до обработки практически любое (в пределах размера динамической памяти) количество событий и более экономно расходовать память.


^ Описание очереди

Type Tptr=^TElem; {Тип указателя на элемент очереди }

TElem=record { Тип элемента очереди : }

inf : char; { информационная часть }

link : Tptr { соединительная часть }

end;


^

Принципы работы с динамической очередью

Условно очередь можно представить в виде трубки с шариками.




Для создания очереди и работы с ней необходимо иметь как минимум два указателя:

1. на начало очереди (возьмём идентификатор BegQ);
   
2. на конец очереди (возьмём идентификатор EndQ).
   

Кроме того, для освобождения из памяти удаляемых элементов требуется дополнительный временный указатель (возьмём идентификатор P). Дополнительный указатель также часто используется в других ситуациях для удобства работы с очередью.

• Создание очереди
  
  1. Исходное состояние:
     

2. Выделение памяти под первый элемент очереди:
   

3. Установка указателей на созданный первый элемент:
   

• Добавление элемента очереди.
  

1. Исходное состояние:
   

2. Выделение памяти под новый элемент и занесение в него информации:
   

3. Установка связи между последним элементом очереди и новым, а также перемещение указателя "конец очереди" EndQ на новый элемент:
   

• Удаление элемента очереди.
  

1. Исходное состояние:
   

2. Извлечение информации из удаляемого элемента в переменную Val и установка на него вспомогательного указателя P:
   

3. Переустановка указателя начала очереди BegQ на следующий элемент, используя значение поля Link, которое хранится в первом элементе. После этого освобождается память начального элемента очереди, используя дополнительный указатель P:
   

Пример 1.

Hиже приводится пример программы, заносящей в очередь 10 символов, набранных на клавиатуре пользователем, и выдающей их на экран в той же последовательности. В ней используются следующие процедуры:

• процедура AddEl(val:real) используется для добавления к очереди нового элемента val;
  
• процедура GetDelEl(var val:real) используется для удаления из очереди элемента val.
  

^ Program queue;

Type Tptr=^TElem; {Тип указателя на элемент очереди }

TElem=record { Тип элемента очереди : }

inf : char; { информационная часть }

link : Tptr { соединительная часть }

end;

Var begq,endq : Tptr; { Указатели на начало и конец очереди }

value : char;

i : byte;


Procedure AddEl(val : char); { Процедура добавления элемента }

^ Var p:tptr; { Вспомогательный указатель }

begin

new(p);

p^.inf:=val;

p^.link:=nil;

if endq=nil then begq:=p

else endq^.link:=p;

endq:=p

end;


Procedure GetDelEl(var val : char); { Процедура удаления элемента }

var p : TPtr; { Вспомогательный указатель }

begin

val:=begq^.inf;

p:=begq; begq:=p^.link;

if begq=nil then endq:=nil;

dispose(p)

end;


begin

new(begq); { Создание указателей на начало и конец очереди }

new(endq);

begq:=nil; { Установление указателей на nil }

endq:=nil;

for i:=1 to 10 do

begin

writeln(' введите символ');

readln(value);

addel(value);

end;

i:=1;

while begq<>nil do

begin

getdelel(value);

writeln(i,'-й символ - ',value);

inc(i)

end

end.


Пример 2. Сформировать две очереди по 5 элементов. Объединить очереди в одну, в которой элементы исходных очередей чередуются (начиная с первого элемента первой очереди).


Дек

Дональд Кнут ввел понятие усложненной очереди, которая называется дек (от англ. deq - double ended queue, т.е. очередь с двумя концами).


Определение: Дек - это такой последовательный список, в котором как включение, так и исключение элементов может осуществляться с любого из двух концов списка.


В каждый момент времени у дека доступны как первый, так и последний элемент, причем добавлять и удалять элементы можно и в начале, и в конце дека.

Частный случай дека - дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры дека аналогичны логической и физической структуре кольцевой FIFO-очереди. Однако, применительно к деку целесообразно говорить не о начале и конце, а о левом и правом конце.


Дек удобнее представлять двусвязным (разнонаправленным) линейным списком.


Операции над деком:

• включение элемента справа;
  
• включение элемента слева;
  
• исключение элемента справа;
  
• исключение элемента слева;
  
• определение размера;
  
• очистка.
  

Физическая структура дека в статической памяти идентична структуре кольцевой очереди. Динамическая реализация является очевидным объединением стека и очереди.


Задачи, требующие структуры дека, встречаются в вычислительной технике и программировании гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется программистом без каких-либо специальных средств системной поддержки.

Примером дека может быть, например, некий терминал, в который вводятся команды, каждая из которых выполняется какое-то время. Если ввести следующую команду, не дождавшись, пока закончится выполнение предыдущей, то она встанет в очередь и начнет выполняться, как только освободится терминал. Это FIFO очередь. Если же дополнительно ввести операцию отмены последней введенной команды, то получается дек.