Учебно-методическии комплекс дисциплины «Структуры и алгоритм обработки данных» (стр. 13 )

const

  МАХ =  100;

var

  stack: array[1..100] of integer;

  tos:integer; {points  to  top  of stask}

{ помещение объекта  в  стек  }

procedure  Push(i:integer);

begin

  if tos>=MAX then writeln ('Stask full')

  else

  begin

  stack[tos]:=i;

  tos:=tos+l;

  end;

end; { конец  процедуры  помещения объекта  з стек}

{ выборка  объекта из  стека  }

function  Pop: integer;

begin

  tos:=tos-l;

  if tos<l then

  begin

  writeln (' Stack underflow');

  tos:=tos+l;

  Pop:=0;

  end

  else Pop : =stack [tos];

end;  ( конец функции  выборки объекта из  стека }

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

Операция  Содержимое стека

Push(A)  A

Push(В)  В А

Push (С)  ;.  С В А

Pop, выбирается С  В А

Push(F)  F В А

Pop, выбирается F  В А

Pop, выбирается В  А

Pop, выбирается A.  пусто

Рис.3. Работа стека.

СВЯЗАННЫЕ СПИСКИ

Очереди и  стеки  обладают  двумя общими  свойствами.  Во-первых,  доступ  к находящимся  в  них данных подчиняется строгим  правилам.  Во-вторых, операции поиска  имеют разрушительный характер. Если  выбранный из стека  или очереди элемент не будет где-нибудь сохранен, то он будет потерян.  Кроме  того, стеки  и очереди  для  своей  работы требуют  наличия  непрерывной  области  памяти (непрерывность должна обеспечиваться по крайней мере логически). В отличии от стека и очереди связанный список позволяет осуществлять доступ к любым  элементам, поскольку каждая единица  информации  имеет  указатель  на следующий  элемент данных  в цепочке.  Элементами связанного списка являются сложные структуры данных, тогда как стеки и очереди  могут работать и с простыми и со сложными структурами данных. Операция поиска в связанном списке  не приводит к удалению  и уничтожению элемента. В  данном  случае  следует предусмотреть дополнительно операцию удаления элемента из списка. Связанные списки используются в двух основных случаях. Во-первых,  при создании массивов, которые располагаются в оперативной памяти и размер  которых заранее неизвестен. Если вы заранее знаете, какого размера память потребуется для решения вашей  задачи,  то  вы можете использовать простой  массив.  Однако,  если действительный размер списка вам неизвестен, то вы должны  применить связанный список.  Во-вторых,  связанные списки используются в  базах данных  на  дисках. Связанный список позволяет быстро выполнять вставку и удаление элемента данных без реорганизации  всего  дискового файла. По  этим причинам связанные списки широко используются в программах по управлению базами данных. Связанные списки могут иметь одиночные или двойные связи. Список с одной связью содержит элементы, каждый  из  которых имеет связь  со следующим  элементом данных.  В списке с двойной связью каждый элемент имеет связь как со следующим элементом,  так  и с предыдущим элементом. Тип связанного  списка выбирается  в зависимости от решаемой задачи.

Задания для самостоятельной работы

1.  Составьте программу, иллюстрирующую работу калькулятора с четырьмя операциями.

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

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

4.  Дан список слов. Выведите на экран слова списка, которые:

a)  Оканчиваются и начинаются одной и ой же литерой;

b)  Начинаются с той же литеры, что и следующее слово;

c)  Совпадает с последним или первым слогом

5.  Дан текстовый файл. Распечатайте текст в обратном порядке слов.

Лабораторная работа №2. Реализация структур данных типа дерево.

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

       Рассматривается четвертая структура данных, которая называется двоичным деревом.  Имеется много  типов деревьев. Однако, двоичные деревья занимают особое положение. Если такие деревья упорядочить, то операции поиска, вставки и удаления будут выполняться очень быстро. Каждый элемент двоичного дерева имеет информационные поля,  связь с левым элементом и  связь с правым элементом. При  описании деревьев используется  специальная терминология. Первый элемент дерева называется его корнем. Каждый элемент называют вершиной (или листом) дерева,  а часть  дерева  носит название  поддерева.  Вершина,  которая не имеет поддеревьев,  называется терминальной  вершиной.  Высота  дерева равна числу уровней вершин в дереве. В дальнейшем при рассмотрении деревьев можно считать, что в памяти они  располагаются так же, как на бумаге. Однако следует помнить, что деревья представляют собой лишь способ представления данных в памяти, а память в действительности имеет линейную форму.

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

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

Упорядоченность дерева зависит от порядка доступа  к дереву. Процесс  доступа к каждой вершине дерева называется обходом дерева.

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

при прохождении во внутреннем  порядке:  а  Ь с d e f g;

при прохождении в прямом порядке:  d  Ь а с f e g;

при прохождении в обратном порядке:  а  с b e g f d.

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

type

  TreePointer = tree;

  tree  = record

  data:  char;

  left:  TreePointer;

  right:TreePointer;

end;

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

function Stree (root, r: TreePointer;data:char);TreePointer;

begin

if r=nil then

begin

  new(r);  {  получить новую  вершину }

  г. left:=nil;

  г. right:=nil;

  г. data:=data;

  if data<root. data then root. left:=r

  else  root. right:=r;

Stree:=r;

End else

  begin

  if datar. data  then STree : =STree ( r,  r. left, data)

  else STree : =STree (r,  r. right,  data);

  end;

  end;  { конец функции добавления элемента в двоичное  дерево }

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

{call  STree}

if  rt=nil rt:=STree(rt,  rt,  info)

else dummy : STree (rt,  rt,  info);

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

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