Структура данных очередь. Базовые операции над очередью

Оглавление

Статическое и динамическое распределение оперативной памяти. 1

Организация структур данных. 1

Структура данных стек. Базовые операции над стеком.. 1

Структура данных очередь. Базовые операции над очередью.. 3

Структура данных список. Базовые операции над списком.. 5

Контрольные вопросы: 7

Комбинированный урок №18

Тема:Организация памяти. Стековая память. Директива управления памятью ($M).

Цель: изучить принципы организации памяти, сформировать понятие о структуре данных типа «стек», «очередь», «список».

Статическое и динамическое распределение оперативной памяти

Возможна также организация динамического размещения данных, при котором под некоторые данные и программы память выделяется непосредственно во время…

Организация структур данных

Под связной структурой данныхпонимается построенная и сформированная информация, состоящая из отдельных связанных в определенном порядке элементов,… Каждая структура данных характеризуется: взаимосвязью доступных элементов… К типовым связным структурам данных относятся: стек, очередь, список.

Структура данных стек. Базовые операции над стеком

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

Принцип построения стека – «последний вошел» и «первый вышел» (last in, first out – англ. яз.) или сокращенно LIFO. В каждый конкретный момент времени элементы добавляются и удаляются из одного конца, который называют вершиной стека. Примером стека может служить стопка книг на полке, вагоны, поставленные электровозом, в тупике.

Основные базовые операции при построении стека:

- добавить (разместить) новый элемент в вершину стека;

- выбрать (удалить) элемент из вершины стека.

Структура данных типа «стек» может быть описана с помощью одномерного массива. Память для элементов стека может так же быть выделена динамически.

Например, дан стек из пяти элементов, содержащий строковые данные.

Const maxs=5;

Type Stek=array[1..maxs] of string;

Var Vstek : integer; {вершина стека}

S : Stek; {массив с элементами стека}

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

Procedure AddST(Var S:stek; Var Vstek:integer; Var el:string);

Begin

If Vstek=maxs then

Begin

writeln('Переполнение стека');

Exit

end;

Vstek:=Vstek+1; {увеличить индекс вершины стека на единицу}

S[Vstek]:=el {разместить новый элемент в стеке}

End;

При удалении элементов из стека (процедура EdelSt) необходимо проверить, не является ли стек пустым. Эта проверка может выполняться с помощью функции пользователя Sempty.

Function Sempty(Vstek:integer):boolean;

Begin

if Vstek=0 then Sempty:=true {стек является пустым}

else Sempty:=false {стек не является пустым}

end;

При удалении элемента из стека значение индекса массива (индекс вершины стека) уменьшается на единицу. Значение удаляемого элемента присваивается переменной el.

Procedure EdelSt (Var S:stek; Var Vstek:integer;Var el:string);

Begin

If Sempty(Vstek) Then

Begin

writeln('Стек пустой');

Exit

end;

el:=S[Vstek];

Vstek:=Vstek-1 {уменьшить индекс вершины стека}

end;

Создавая стек с помощью массива, следует, что состояние стека может не соответствовать состоянию массива его описывающего, поскольку при удалении элемента из стека, он не удаляется из массива, а просто меняется значение указателя вершины стека.

Пример.Постройте с помощью массива стек из пяти строковых элементов. Разместите в стеке пять элементов: ‘kk’, ‘ll’, ‘mm’, ‘nn’, ‘pp’. Удалите из стека два элемента ‘nn’ и ‘pp’ и добавьте новый элемент ‘rr’.

Type Stek=array[1..maxs] of string;

Var i,Vstek:integer;

S:Stek;

el:string;

Procedure AddST(Var S:stek; Var Vstek:integer; Var el:string);

Begin

If Vstek=maxs then

Begin

writeln('Переполнение стека');

Exit

end;

Vstek:=Vstek+1;

S[Vstek]:=el

End;

Function Sempty(Vstek:integer):boolean;

Begin

If Vstek=0 then Sempty:=true

Else Sempty:=false

end;

Procedure EdelSt (Var S:stek; Var Vstek:integer; var el:string);

Begin

If Sempty(Vstek) Then

Begin

writeln('Стек пустой');

Exit

end;

el:=S[Vstek];

Vstek:=Vstek-1

end;

BEGIN {основная программа}

Vstek:=0; {}

for i:=1 to 5 do {добавить элементы}

Begin

Write('dEl=');

readln(el);

AddST(S,Vstek,el)

end;

For i:=1 to 2 do {удалить элементы}

Begin

EdelSt(S,Vstek,el);

Writeln('yel=',el);

end;

writeln('nel=');

readln(el);

Addst(S,Vstek,el) {добавить элемент}

END.

Рассмотрим порядок выполнения алгоритма решения задачи более подробно.

Добавление пяти элементов в стек. Состояние массива S:

 

индекс
элементы массива	‘kk’	‘ll’	‘mm’	‘nn’	‘pp’
элементы стека	‘kk’	‘ll’	‘mm’	‘nn’	‘pp’

Значение указателя Vstek:=5.

Удалить два элемента из вершины стека. Состояние массива S:

 

индекс
Элементы массива	‘kk’	‘ll’	‘mm’	‘nn’	‘pp’
Элементы стека	‘kk’	‘ll’	‘mm’

Значение указателя Vstek:=3.

Добавить один элемент в стек. Состояние массива S:

 

индекс
Элементы массива	‘kk’	‘ll’	‘mm’	‘rr’	‘pp’
Элементы стека	‘kk’	‘ll’	‘mm’	‘rr’

Значение указателя Vstek:=4.

Структура данных очередь. Базовые операции над очередью

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

Очередь– это упорядоченный набор связанных элементов, которые добавляются к ней с одного конца, а удаляются (выбираются) с другого конца.Принцип построения очереди – «первый вошел» и «первый вышел» (first in, first out – англ. яз.) или сокращенноFIFO.

Основываясь на принципах построения очереди, определим основные базовые операции над ней:

- добавить (разместить) новый элемент в конец очереди;

- выбрать и удалить элемент из начала очереди.

При описании очереди может быть использован одномерный массив. Для создания очереди из элементов массива используются дополнительно две переменные. Одна переменная – Poinf – содержит индекс массива первого элемента очереди, а вторая Poinsv – индекс массива со свободным местом в очереди в каждый текущий момент времени. В начале работы с очередью обе переменные принимают значения Poinf:=1 и Poinsv:=1. Если очередь является пустой, то значения этих переменных равны между собой Poinsv=Poinf.

Например, необходимо смоделировать очередь элементов, которая состоит из символов.

Const maxs=6;

Type och=array[1..maxs] of char; {очередь из символов}

Var Cha:och;

{Для добавления элементов в очередь используется процедура пользователя AddCH}

Procedure AddCH(s:char; Var Cha:och; Var Poinsv:integer);

Begin

If Poinsv>maxs then

Begin

writeln('Переполнение очереди');

Exit

end;

Cha[poinsv]:=el;

Poinsv:=Poinsv+1

В этой процедуре выполняется проверка на переполнение очереди, которая может возникнуть в том случае, когда значение переменной Poinsv становится… Одним из необходимых условий при удалении элементов из очереди является… Function Pempty(PoinSv,PoinF:integer):boolean;

Begin

if Poinsv=PoinF then Pempty:=true {очередь пуста}

else Pempty:=false {в очереди есть элементы}

end;

Для удаления элементов из очереди может быть использована процедура EdelCH. Значение удаляемого элемента присваивается переменной el. После удаления элемента из очереди значение переменной Poinf (указатель на первый элемент в очереди) увеличивается на единицу.

Procedure EdelCH (Var CHa:och; Var Poinsv,Poinf:integer; Var el:char);

Begin

If Pempty(Poinsv,Poinf) Then

Begin

writeln('Очередь пуста');

Exit

end;

el:=Cha[Poinf];

Poinf:=Poinf+1

Создавая очередь с помощью массива, следует, что состояние очереди может не соответствовать состоянию массива ее описывающего, поскольку при… Рассмотрим процесс моделирования и обработки очереди на конкретном примере. … Пример.Постройте очередь из 5-ти символов - ‘a’, ‘b’, ‘c’, ‘d’, ‘e’. Выведите из очереди два символа ‘a’, ‘b’ и…

Begin

If Poinsv>maxs then

Begin

writeln('Переполнение очереди');

Exit

end;

Cha[poinsv]:=el;

Poinsv:=Poinsv+1

End;

{функция проверки условия пустой очереди}

Function Pempty(PoinSv,PoinF:integer):boolean;

Begin

If Poinsv=PoinF then Pempty:=true

Else Pempty:=false

end;

{процедура вывода элементов из очереди}

Procedure EdelCH (Var CHa:och; Var Poinsv,Poinf:integer; Var el:char);

Begin

If Pempty(Poinsv,Poinf) Then

Begin

writeln('Очередь пуста');

Exit

end;

el:=Cha[Poinf];

Poinf:=Poinf+1

end;

BEGIN {основная программа}

Poinsv:=1;

Poinf:=1;

{добавление элементов в очередь}

For i:=1 to 5 do

Begin

Write('EO='); readln(el);

Addch(el,Cha,Poinsv)

end;

{удаление из очереди двух элементов}

For i:=1 to 2 do

Begin

EdelCh(Cha,Poinsv,Poinf,el);

Writeln('el=',el);

end;

writeln('nel=');

readln(el);

{добавление элемента в конец очереди}

Addch(el,Cha,Poinsv)

END.

Рассмотрим порядок выполнения алгоритма задачи:

Построение очереди из 5-ти элементов имеем указатель на элемент очереди Poinf:=1, указатель на свободное место в массиве Poinsv:=6, содержимое массива Cha:

индекс
элементы массива	‘a’	‘b’	‘c’	‘d’	‘e’
элементы очереди	‘a’	‘b’	‘c’	‘d’	‘e’

 

Удаление из очереди первых двух элементов: Poinf:=3, Poinsv:=6, содержимое массива Cha:

индекс
Элементы массива	‘a’	‘b’	‘c’	‘d’	‘e’
Элементы череди			‘c’	‘d’	‘e’

 

Добавление одного элемента в конец очереди: Poinf:=3, Poinsv:=7, содержимое массива Cha:

индекс
элементы массива	‘a’	‘b’	‘c’	‘d’	‘e’	‘z’
Элементы очереди			‘c’	‘d’	‘e’	‘z’

Структура данных список. Базовые операции над списком

Структуры данных очередь и стек являются частными представлениями более сложной структуры данных списка. Списки бывают различных типов. Рассмотрим линейные однонаправленные списки и кольцевые однонаправленные списки.

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

Кольцевой однонаправленный список- это линейный список, который имеет дополнительную связь между последним и первым элементов.

Базовые операции с однонаправленным линейным списком следующие:

¾ построить пустой список;

¾ добавить элемент в список;

¾ отыскать нужный элемент в списке;

¾ удалить элемент из списка;

¾ вставить элемент в список.

Однонаправленный линейный список может быть представлен в виде двумерного массива. При представлении списка с помощью двумерного массива Sps элементы этого массива Sps[1,j] содержат элементы списка, а элементы массива Sps[2,j] являются указателями и определяют индекс (позицию) каждого последующего элемента в списке. Такой список может быть представлен и в виде одномерного массива, элементами которого являются предопределенные записи из двух полей, смысловое назначение которых аналогично двумерному массиву.

Рассмотрим основные базовые операции по работе с однонаправленным линейным списком, описанные с помощью процедур пользователя, на конкретной задаче.

Задача.Опишите и постройте с помощью двумерного массива Sps линейный однонаправленный список из пяти целых чисел и сделайте этот список пустым. После этого добавьте в список четыре элемента 9,8,7,6, затем найдите указатель на элемент 8 и удалите этот элемент. В конце работы со списком вставьте после элемента со значением 6 элемент со значением 5, предварительно отыскав указатель на элемент со значением 6, а элемент со значением 15 вставьте после элемента со значением 9.

Const maxel=7;

Type Spis=array[1..2,1..maxel] of integer;

Var Assm, Afe : integer; { Assmуказывает индекс/адрес первого элемента в списке свободных мест}{ Afe – индекс (адрес) первого элемента в списке. }

El,i,pap,j:integer;

Sps:Spis;

Procedure Nspis(Var Sps:Spis); {процедура оформления пустого списка}

Begin

For i:=1 to maxel-1 do

Sps[2,i]:=i+1;

Sps[2,maxel]:=0;

Assm:=1;

Afe:=0;

end;

Procedure Addsp(Var Sps:Spis); {процедура добавления элемента в список}

Var Asmn:integer;

Begin

Asmn:=Sps[2,Assm];

Sps[1,Assm]:=el;

Sps[2,Assm]:=Afe;

Afe:=Assm;

Assm:=Asmn

end;

Procedure DelSp(Pap,j:integer; Var Sps:Spis); {процедура удаления элемента из списка}

Begin

Sps[2,Pap]:=Sps[2,j];

Sps[2,j]:=Assm;

Assm:=j

end;

Procedure UstSp(j:integer; Var Sps:Spis); {процедура вставки элемента в список}

Var Asmn:integer;

Begin

Asmn:=Sps[2,Assm];

Sps[2,Assm]:=Sps[2,j];

Sps[2,j]:=Assm;

Sps[1,Assm]:=El;

Assm:=Asmn;

end;

Procedure PoshSp(Var Sps:Spis; el:integer; Var Pap,j:integer); {процедура поиска указателя (адреса) на элемент списка}

Begin

j:=Afe;

Pap:=0;

While (Sps[1,j]<>el) and (j<>0) do

Begin

Pap:=j;

j:=Sps[2,j];

end;

if j=0 then Writeln('Элемент не найден')

end;

BEGIN {Основная программа}

Nspis(Sps); {построение пустого списка}

for i:=1 to 4 do

begin

write(‘el[‘,i,’]=’);

readln(el);

Addsp(Sps) {добавление элементов в список по одному}

end;

el:=8; {найденный указатель j, pap – предыдущий указатель}

PoshSp(Sps,el,pap,j); {поиск указателя на элемент со значением 8}

Delsp(pap,j,sps); {удаление элемента с указателем j}

el:=6;

PoshSp(Sps,el,pap,j); {поиск указателя на элемент со значением 6}

el:=5;

Ustsp(j,Sps); {вставка элемента со значением 5 после элемента со значением 6}

el:=9;

PoshSp(Sps,el,pap,j); {поиск указателя на элемент со значением 9}

el:=15;

Ustsp(j,Sps); {вставка элемента со значением 15 после элемента со значением 9}

END.

Распишем детально порядок выполнения основного алгоритма.

Построение пустого списка процедура Nspis: Assm:=1, Afe:=0, массив Sps:

 

Индекс массива
элементы списка
Указатель на элемент списка

Добавление четырех элементов в список процедура Addsp: Assm:=5, Afe:=4, массив Sps:

 

Индекс массива
элементы списка
Указатель на элемент списка

В результате построения списка из 4-х элементов строится цепочка 6→7→8→9.

Поиск указателя на элемент со значением 8 с помощью процедуры PoshSp: j:=2, Pap:=3;

Удаление элемента со значением 8 из списка с помощью процедуры Delsp: Assm:=2, Afe:=4, массив Sps:

 

Индекс массива
элементы списка
Указатель на элемент списка

В результате удаления из списка элемента со значением 8 строится цепочка 6 →7→9.

Поиск указателя на элемент со значением 6 с помощью процедуры PoshSp: j:=4, Pap:=0;

Вставка элемента со значением 5 в список после элемента со значением 6 с помощью процедуры Ustsp: Assm:=5, Afe:=4, массив Sps:

 

Индекс массива
элементы списка
Указатель на элемент списка

В результате вставки в список элемента со значением 5 после элемента со значением 6 получаем цепочку 6 →5→7→9.

Поиск указателя на элемент со значением 9 с помощью процедуры PoshSp: j:=1, Pap:=3;

Вставка элемента со значением 15 в список после элемента со значением 9 с помощью процедуры Ustsp: Assm:=6, Afe:=4, массив Sps:

 

Индекс массива
элементы списка
Указатель на элемент списка

В результате вставки в список элемента со значением 15 после элемента со значением 9 получаем цепочку 6 →5→7→9→15.

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

Контрольные вопросы:

1. Дайте определение статической и динамической памяти. Назовите различие между ними.

2. Дайте определение структуре данных «стек». Опишите принцип работы с данной организацией данных.

3. Дайте определение структуре данных «очередь». Опишите принцип работы с данной организацией данных.

4. Дайте определение структуре данных «список». Опишите принцип работы с данной организацией данных.