Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
рганизация памяти. Организация данных Страница 8 из 8
|
[1] Оглавление [2] Статическое и динамическое распределение оперативной памяти [3] Организация структур данных [3.1] Структура данных стек. Базовые операции над стеком [3.2] Структура данных очередь. Базовые операции над очередью [3.3] Структура данных список. Базовые операции над списком [4] Контрольные вопросы: |
Комбинированный урок №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:
|
индекс |
1 |
2 |
3 |
4 |
5 |
|
элементы массива |
‘kk’ |
‘ll’ |
‘mm’ |
‘nn’ |
‘pp’ |
|
элементы стека |
‘kk’ |
‘ll’ |
‘mm’ |
‘nn’ |
‘pp’ |
Значение указателя Vstek:=5.
Удалить два элемента из вершины стека. Состояние массива S:
|
индекс |
1 |
2 |
3 |
4 |
5 |
|
Элементы массива |
‘kk’ |
‘ll’ |
‘mm’ |
‘nn’ |
‘pp’ |
|
Элементы стека |
‘kk’ |
‘ll’ |
‘mm’ |
Значение указателя Vstek:=3.
Добавить один элемент в стек. Состояние массива S:
|
индекс |
1 |
2 |
3 |
4 |
5 |
|
Элементы массива |
‘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
End;
В этой процедуре выполняется проверка на переполнение очереди, которая может возникнуть в том случае, когда значение переменной Poinsv становится больше размера массива. При добавлении элемента в очередь значение переменной Poinsv увеличивается на единицу, а на свободное место в очереди в ее конец ставится новый элемент el.
Одним из необходимых условий при удалении элементов из очереди является проверка условия полного отсутствия в ней каких-либо элементов – очередь «пуста». Такую проверку выполняет с помощью функция пользователя Pempty.
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
end;
Создавая очередь с помощью массива, следует, что состояние очереди может не соответствовать состоянию массива ее описывающего, поскольку при удалении элемента из очереди, он не удаляется из массива, а просто меняется значение указателя Poinf.
Рассмотрим процесс моделирования и обработки очереди на конкретном примере.
Пример. Постройте очередь из 5-ти символов - ‘a’, ‘b’, ‘c’, ‘d’, ‘e’. Выведите из очереди два символа ‘a’, ‘b’ и добавьте в конец очереди символ ‘z’.
Const maxs=6;
Type och=array[1..6] of char;
Var i,Poinsv,Poinf:integer;
Cha:och;
el:char;
{процедура добавления элементов в очередь}
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
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:
|
индекс |
1 |
2 |
3 |
4 |
5 |
6 |
|
элементы массива |
‘a’ |
‘b’ |
‘c’ |
‘d’ |
‘e’ |
|
|
элементы очереди |
‘a’ |
‘b’ |
‘c’ |
‘d’ |
‘e’ |
Удаление из очереди первых двух элементов: Poinf:=3, Poinsv:=6, содержимое массива Cha:
|
индекс |
1 |
2 |
3 |
4 |
5 |
6 |
|
Элементы массива |
‘a’ |
‘b’ |
‘c’ |
‘d’ |
‘e’ |
|
|
Элементы череди |
‘c’ |
‘d’ |
‘e’ |
Добавление одного элемента в конец очереди: Poinf:=3, Poinsv:=7, содержимое массива Cha:
|
индекс |
1 |
2 |
3 |
4 |
5 |
6 |
|
элементы массива |
‘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:
|
Индекс массива |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
элементы списка |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
|
Указатель на элемент списка |
2 |
3 |
4 |
5 |
6 |
7 |
0 |
Добавление четырех элементов в список процедура Addsp: Assm:=5, Afe:=4, массив Sps:
|
Индекс массива |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
элементы списка |
9 |
8 |
7 |
6 |
0 |
0 |
0 |
|
Указатель на элемент списка |
0 |
1 |
2 |
3 |
6 |
7 |
0 |
В результате построения списка из 4-х элементов строится цепочка 6→7→8→9.
Поиск указателя на элемент со значением 8 с помощью процедуры PoshSp: j:=2, Pap:=3;
Удаление элемента со значением 8 из списка с помощью процедуры Delsp: Assm:=2, Afe:=4, массив Sps:
|
Индекс массива |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
элементы списка |
9 |
8 |
7 |
6 |
0 |
0 |
0 |
|
Указатель на элемент списка |
0 |
5 |
1 |
3 |
6 |
7 |
0 |
В результате удаления из списка элемента со значением 8 строится цепочка 6 →7→9.
Поиск указателя на элемент со значением 6 с помощью процедуры PoshSp: j:=4, Pap:=0;
Вставка элемента со значением 5 в список после элемента со значением 6 с помощью процедуры Ustsp: Assm:=5, Afe:=4, массив Sps:
|
Индекс массива |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
элементы списка |
9 |
5 |
7 |
6 |
0 |
0 |
0 |
|
Указатель на элемент списка |
0 |
3 |
1 |
2 |
6 |
7 |
0 |
В результате вставки в список элемента со значением 5 после элемента со значением 6 получаем цепочку 6 →5→7→9.
Поиск указателя на элемент со значением 9 с помощью процедуры PoshSp: j:=1, Pap:=3;
Вставка элемента со значением 15 в список после элемента со значением 9 с помощью процедуры Ustsp: Assm:=6, Afe:=4, массив Sps:
|
Индекс массива |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
элементы списка |
9 |
5 |
7 |
6 |
15 |
0 |
0 |
|
Указатель на элемент списка |
5 |
3 |
1 |
2 |
6 |
7 |
0 |
В результате вставки в список элемента со значением 15 после элемента со значением 9 получаем цепочку 6 →5→7→9→15.
Строить списки можно не только с использованием массива, но и выделять память для элементов списка динамически, освобождая эту память при удалении элементов, если это необходимо.
траница 8 из 8