78215

Организация памяти. Организация данных

Лекция

Информатика, кибернетика и программирование

Добавление элементов в стек может быть описано с помощью процедуры ddST. Добавление нового элемента в стек должно сопровождаться размещением нового элемента в массив и увеличением значения переменной Vstek на единицу. Function SemptyVstek...

Русский

2015-02-07

138.5 KB

2 чел.

екция: Организация памяти. Организация данных          8 из 8

Оглавление

[1] Оглавление

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

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

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

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

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

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

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

Тема: Организация памяти. Организация структур данных.

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

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

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

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

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

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

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

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

К типовым связным структурам данных относятся: стек, очередь, список.

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

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

Принцип построения стека – «последний вошел» и «первый вышел» (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.

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

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

  1.  Какое различие между статической и динамической памятью?
  2.  Структура данных стек. Опишите принцип работы с данной организацией данных.
  3.  Структура данных очередь. Опишите принцип работы с данной организацией данных.
  4.  Структура данных список. Опишите принцип работы с данной организацией данных.

траница 8 из 8


 

А также другие работы, которые могут Вас заинтересовать

78831. Театр. Theatre 48.5 KB
  Every nation and every country has its own customs and traditions. In Great Britain traditions play a more important part in the life of the people than in other countries. Englishmen are proud of their traditions and carefully keep them up.
78832. Добридень тобі, Україно моя! 141 KB
  Мета: Проаналізувати особливості життєвого та творчого шляху Павла Тичина; дослідити роль П. Тичини як громадського діяча. Розвивати пам’ять, декламаторські здібності, виховувати любов до українського поетичного слова, формувати національну свідомість, творчу особистість.
78833. Вже у фермера в дворі наступає Новий рік 48.5 KB
  Срібні дзвіночки дзвеніли під вікнами і все що бажали у цей святковий день маленькі колядники неодмінно збувалося. Входять до классу колядники Панігосподарко Чи дозволите колядувати Колядувати дім звеселяти А як же Кажуть що в тій хаті і добра не буде яку колядники...
78834. Шевченкове ім’я нам сіяє, як зоря 289 KB
  Активізувати та збагачувати знання дітей про життя та творчість Тараса Григоровича Шевченка; вчити учнів сприймати поезію Кобзаря серцем і душею, викликати інтерес до поезії; виховувати любов до України; спонукати учнів до вияву власних творчих здібностей та їх розвитку...
78835. Урочиста лінійка до дня народження Т.Г.Шевченка 46 KB
  Звучить пісня Реве та стогне Дніпр широкий Учитель Навесні коли тануть сніги А на рясті просяє веселка Повні сили й живої снаги Ми вшановуєм пам΄ять Шевченка. Трагічна та яскрава доля Тараса Шевченка як і доля його...
78836. Хто він, Т.Г. Шевченко? 940 KB
  Бесіда з учнями: учні висловлюють свої думки з приводу поставленого запитання Слово вчителя: Отже ми поки що тільки припускаємо що у Шевченка могли виникати думки про те як просвітити український люд світлом науки. Шевченка. Однак хто ще з такою силою пристрасті як Шевченко звеличив...
78837. Кобзарем його ми звемо… 124.5 KB
  Благословен той день і час Коли прослалась килимами Земля яку сходив Тарас Малими босими ногами Земля яку скропив Тарас Дрібними росами сльозами 9 березня 1814 р. В хаті Григорія Шевченка блиснув у вікні єдиний на все село вогник і народилася нова кріпацька душа для пана а для України...
78838. Написання твору за репродукцією картини Івана Івановича Шишкіна «Зима» 152 KB
  Формувати навички планування, самоконтролю, самоаналізу. Удосконалювати навички каліграфічного грамотного письма. Допомагати учням розкривати їх здібності, формувати пізнавальну активність, розширювати її за рамками картини, поповнювати словниковий запас. Духовно збагачувати внутрішній світ учнів.