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


 

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

36809. Приготовление стандартного раствора КМnО4 иустановление его нормальности и титра по щавелевой кислоте 61 KB
  Тема: Приготовление стандартного раствора КМnО4 иустановление его нормальности и титра по щавелевой кислоте. Теоретические основы: Перманганатометрия это метод объемного анализа в котором в качестве стандартного раствора используется раствор перманганата калия. В основе метода лежит использование стандартного раствора КМnО4 . нормальность и титр раствора перманганата калия определяют по щавелевой кислоте которая является восстановителем и отдает при этом 2 электрона.
36810. Установление нормальности и титра тиосульфата по бихромату (метод йодометрия) 57 KB
  Тема: Установление нормальности и титра тиосульфата по бихромату метод йодометрия. Определение нормальности и титра тиосульфата по бихромату калия методом йодометрии. Для определения окислителей используют раствор тиосульфата натрия N2S2O3. Выделившийся йод титруют раствором тиосульфата натрия точно известной нормальности.
36811. Определение количества хлорида натрия в растворе. Метод осаждения 50 KB
  Материальнотехническое обеспечение: Штатив Бунзена титровальный набор титровальные колбы банки для слива воронки бюретка пипетки Мора капельницы раствор хлорида натрия NCL стандартный раствор 005Н gNО3 5 раствор хромата калия K2CrO4 дистиллированная вода. Расчет нормальности и титра раствора NCl. Теоретические основы: В методе Мора в качестве стандартного раствора используется 005Н gNO3 титр и нормальную концентрацию которого устанавливают по раствору NCl индикатором является 5 ый раствор К2СrO4....
36812. Определение общей жесткости воды г. Симферополя методом комплексиметрии 52.5 KB
  Тема: Определение общей жесткости воды г. Умения: Учиться проводить исследования общей жесткости воды г. Различают временную устраняемую и постоянную жесткость воды. Сумма временной и постоянной жесткости воды определяет ее общую жесткость.
36813. Приготовление раствора точной заданной концентрации 69.5 KB
  Тема: Приготовление раствора точной заданной концентрации. Умения: Используя рациональные способы ведения технологических процессов учиться готовить растворы различной концентрации уметь рассчитывать массу вещества массу раствора нормальность и титр. Титр показывает сколько граммов вещества растворено в 1мл раствора. Как приготовить 250мл 01 Н раствора перекристаллизованной чистой двухосновной щавелевой кислоты Н2С2О4 2Н2О которую используют для...
36814. ИЗУЧЕНИЕ ПОГЛАЩЕНИЯ СВЕТА 916.5 KB
  КРАТКАЯ ТЕОРИЯ Прохождение света через вещество ведет к возникновению колебаний электронов вещества под воздействием электромагнитного поля волны и сопровождается потерей энергии этой волны затрачиваемой на возбуждение колебаний электронов. Поэтому интенсивность падающего света по мере проникновения волны в вещество уменьшается. Действительно интенсивность световой волны прошедшей среду толщиной d уменьшается по закону: I=I0ekd 1 где I0 –...
36815. Моделирование командных генераторов гармонических сигналов 55.5 KB
  Цель работы: определить схемы с помощью которых можно задать воздействие и рассчитать их параметры. схема моделирования Определим параметры модели: задание сигнала 2. схема моделирования Определим параметры модели: Таким образом данная схема не реализует синусоидальный сигнал невозможно скомпенсировать косинусоидальную составляющую. схема моделирования Определим параметры модели: задание сигнала 4.
36816. Информационно – образовательная среда вуза 73.5 KB
  Содержание работы: Задание №1 Сформируйте электронный глоссарий по тематике Информационно – образовательная среда: База данных Банк данных Дистанционное обучение Индивидуальный образовательный маршрут Индивидуальная образовательная траектория Информатизация образования Информационная деятельность Информационная подготовка Информационно – коммуникационная среда Информационно – коммуникационная предметная среда Информационно – методическое обеспечение учебно – воспитательного процесса Информационнообразовательная...
36817. Изучение возможностей работы в текстовом редакторе MS Word 64 KB
  проделайте следующие операции: Создайте тестовый документ с помощью меню Файл Создать. Установите параметры и размеры страницы открыв диалоговое окно Параметры страницы в меню Файл. Чтобы отменить ваши неправильные действия воспользуйтесь командой Отменить из меню Правка. Чтобы вернуть отмененное действие воспользуйтесь командой Повторить из меню Правка.