4774

Динамические структуры данных

Реферат

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

Динамические структуры данных. Динамические информационные структуры. Ссылочный тип данных. Ссылки. Программирование информационных динамических структур. Списки. Задачи на списки. Деревья. Бинарные деревья. Задачи на деревья. В предыдущих параграфа...

Русский

2012-11-26

151 KB

45 чел.

Динамические структуры данных.

Динамические информационные структуры.

Ссылочный тип данных. Ссылки.

Программирование информационных динамических структур.

Списки.

Задачи на списки.

Деревья.

Бинарные деревья.

Задачи на деревья.

В предыдущих параграфах были определены фундаментальные структуры данных, используемые в процедурном программировании: массивы, записи, файлы и множества. Фундаментальность этих структур означает, что они, во-первых, чаще всего используются в практике программирования, и, во-вторых, определяют методы структурирования данных - т.е. методы образования сложных структур из более простых. Например, можно определить массив из записей, запись, состоящую из множеств, файл из массивов, компоненты которых - записи, и т.д. Для каждой из таких структур данных характерно то обстоятельство, что размер памяти, отводимой для нее, определяется компилятором во время компиляции разделов типов и переменных и остается неизменным во время исполнения программы. Поэтому такие переменные-структуры называются статическими. Наряду с статическим распределением памяти мы уже использовали в программах и динамическое распределение памяти - под локальные переменные процедур и функций. Особенно выпукло динамизм здесь проявляется при использовании рекурсии.

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

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

f = (a + b)*(a - c) в виде следующей структуры:

 

Теперь вычисление значения f можно организовать "снизу-вверх", подставляя результаты операций вместо знаков операций. Легко видеть, что такой метод вычисления является универсальным.

Пример 2. Нам требуется обрабатывать набор сведений о людях (фамилия - F, возраст - A), причем обработка включает процедуры включения человека в список, исключение из списка, вывод списка как в алфавитном порядке по фамилиям, так и в порядке убывания возраста. Данные для этой задачи удобно представить в виде структуры:

 F

 A

в которой Fi - фамилии, Ai - возрасты людей, сплошные стрелки указывают на следующих в алфавитном порядке людей, а пунктирные - на следующих по росту людей.

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

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

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

Элемент динамической структуры данных 

  Информационные поля   Поля указателей

Ссылка на некоторый элемент - это по существу адрес первого (младшего) байта фрагмента оперативной памяти, отведенной под этот элемент.

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

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

Список

 P

Указатель на

начало списка

 Q

Указатель на

обрабатываемый

элемент.

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

Стэк

P

Вершина стэка

 Q

Указатель на обрабатываемый элемент

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

Очередь

 P 

 Указатель на

начало очереди

 Q

Указатель на

конец очереди.

Очередь - это такой способ представления последовательности однотипных элементов, при котором вставка элемента допускаются только в ее хвосте, а удаление - только в начале. Доступ к другим элементам очереди не поддерживается методами обработки очереди.

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

Дерево

 Указатель на

начало дерева  P

(Корень дерева)

(Листья дерева)

Деревья - это ветвящиеся структуры данных. Каждая запись в дереве, за исключением одной - корневой - имеет одного предшественника. Каждый элемент дерева, за исключением так называемых листьев, указывает на несколько "наследников".Точное определение дерева как динамической структуры данных будет дано ниже.

Граф.

 

Указатель на вершину 

 P

Граф образуют несколько записей, указатели которых выставлены произвольным образом.

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

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

2. Ссылочный тип данных. Ссылки.

Значениями ссылочного типа данных являются ссылки (указатели) на другие данные. Ссылочные типы описываются в разделе типов следующим образом:

 Type <имя ссылочного типа> = ^ <имя базового типа>

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

Примеры описаний:

1. Type Vector = Array[1..100] of Integer;

  Place = ^ Vector;

    Var a, b: Place;

 или

    Var a, b: ^ Array[1..100] of Integer;

 2. Type Item = Record

Name: String[20];

    Age: Integer

end;

Point = ^ Item;

 Var x, y: Point;

Если p - указатель на переменную типа Т, то p^ - обозначение самой этой переменной. Эта система обозначений может быть продемонстрирована так:

переменная типа ^T    переменная типа T

 

    P      P^

Еще раз укажем на то, что при описании ссылочной переменной p память резервируется только для нее. Значением p по существу является начальный адрес размещения p^ в памяти.

Для резервирования памяти под данное типа Т^ в языке используется процедура New.

New (<переменная ссылочного типа>)

Исполнение процедуры New(p) заключается в заполнении ячейки памяти, отведенной под переменную p начальным адресом участка памяти, в котором будет размещено значение p^. Размер этого участка определяется типом переменной p.

Для освобождения памяти, отведенной ранее под T^, используется процедура Dispose.

Dispose(<переменная ссылочного типа>)

Пример 3.

Program ExamNewDis;

 Type Vector = Array[1..100] of Integer;

       Place = ^Vector;

 Item = Record

    Name: String[20];

 Age: Integer

end;

Point = ^Item;

 Var a, b: Place;

   x, y: Point;

 i: Integer;

Begin

  New(x); New(y);

  Read(x^.Name); Read(x^.Age);

y^ := x^;

Dispose(x);

New(a);

For I:= 1 to 100 do a^[i] := Sqr(i)+1;

b := a;

Dispose(a);

End.

Здесь при обращении к процедуре New(x) будет отведено 22 байта под x^, при выполнении New(y) - 22 байта под y^, а при выполнении New(a) - 200 байт под a^. (Мы считаем, что под целое число отводится 2 байта). Оператор y^ := x^ пересылает данные из записи x^ в запись y^. Память, занимаемая x^, освобождается оператором Dispose(x). Для переброски указателя с одного данного на другое используется оператор присваивания. Пусть, например, p и q - переменные одного ссылочного типа и имеет место ситуация

     P

      Q

Тогда после выполнения оператора p := q схема изменится:

    P 

 Q

Обратите внимание на то, что данные, на которые до присваивания ссылалась p, становятся недоступными! В рассматриваемом примере ссылка b установлена оператором b := a на массив a^. Поэтому оператор Dispose(a), освобождая память, лишит защиты не только массив a^, но и массив b^! Поэтому следующий оператор New может разместить данные на месте массива b.

На примерах с информационными динамическими структурами мы видели, что некоторые поля ссылочных типов могут быть не заполнены ссылками на другие записи, причем программист должен явным образом это указывать. Для этого используется стандартное имя Nil. (После выполнения операторов p := Nil; q := Nil указатели p и q указывают на одно и то же данное - в никуда!)

4. Программирование информационных динамических структур.

Простейшие характерные приемы обработки динамических структур данных рассмотрим на следующем примере:

 Пример 4.

а) Построить динамическую структуру данных, изображенную на рисунке:

  First

(Данные xi - целые числа.)

 б) Прочесть данные в следующей последовательности: x1 x4 x3 x1, x1 x2 x3.

 Решение.

 Тип элемента структуры определим следующим образом:

 Type Point = ^ Item;

    Item = record

   Data: Integer;

   Right, Left: Point

  End;

Для построения структуры используем две переменных типа Point - p и First.

 Program Structure;

 Type Point = ^ Item;

   Item = Record

      Data: Integer;

     Right, Left: Point

  End;

 Var p, First: Point;

Begin

 New(p); First := p; Read(p^.Data);   {построен первый элемент структуры}

 New(p^.Left); Read(p^.Left^.Data);   {построен второй элемент структуры}

 New(p^.Right); Read(p^.Right^.Data);  {построен четвертый элемент структры}

 p := p^.Left;

 New(p^.Left); p := p^.Left; Read(p^.Data);

 p^.Right := Nil; p^.left := First;      {построен третий элемент структуры}

 p := First^.Right;    {p установлен на 4-ый элемент }

 p^.Left := First^.Left;

 p^.Right := First^.Left^.Left;    {указатели выставлены. Построение окончено}

       {начало блока чтения}

 Writeln('x1,x4,x3,x1:');

 p := First;

 Write(p^.Data,''); p := p^.Right;

 Write(p^.Data,''); p := p^.Right;

 Write(p^.Data,''); p := p^.Left;

 Write(p^.Data,'');

 p := First;

 Writeln; Writeln('x1,x2,x3:');

 Write(p^.Data,''); p := p^.Left;

 Write(p^.Data,''); p := p^.Left;

 Write(p^.Data,'');

 Writeln('Конец работы')

 end.

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

5. Списки.

В этом разделе рассматриваются процедуры, реализующие стандартные средства работы со списками: поиск элемента, удаление элемента, вставка элемента. Аналогичными средствами пользуются и при обработке других информационных структур. Элемент списка описывается следующим образом:

Type Point = ^ Item;

  Item = Record

        Data: Integer; Next: Point

        End;

Отметим характерную деталь: описание элемента динамической структуры рекурсивно! Таким образом, описание динамических структур невозможно без явного описания типов элементов этих структур.

  место вставки   удаляемый элемент 

 First

       Nil 

Found 

а) Поиск. Процедура Search осуществляет поиск элемента списка с числом x в качестве значения поля Data и возвращает ссылку Found на этот элемент. Если такой элемент в списке отсутствует, Found = Nil.

Procedure Search(var Found, First: Point; x: Integer);

 Begin

 Found := First;

 While (Found <> Nil) and (Found^.Data <> x)

  do Found := Found^.Next

 End;

б) Вставка. Процедура InsList добавляет элемент в список на место, предшествующее Found^ (см. рисунок). Ссылка Found устанавливается на вставленный элемент.

Procedure InsList(var Found: Point, x:Integer);

  Var p: Point;

 Begin

  New(p);

  p^.Data := Found^.data;

  Found^.Data := x;

  p^.Next := Found^.Next;

  Found^.Next := p

 End;

 Found

 First

   P

в) Удаление. Процедура DelList удаляет из списка элемент Found^. Ссылка Found устанавливается на элемент, следующий за удаленным.

Procedure DelList(Found: Point);

  Var p: Point;

    y: Integer;

 Begin

  y := Found^.Next^.Data;

  p:= Found^.Next;

  Found^.Next := Found^.Next^.Next;

  Found^.Data := y;

  Dispose(p) {сборка мусора}

 End;

Found  

 First

  P

Отметим один явный недостаток процедур InsList и DelList: они непригодны для обработки последнего элемента списка! InsList для правильной работы требует наличия элемента Found^.Next^, а DelList - элемента Found^.Next^.Next. Поэтому, если требуется вставить в список последний элемент, указатель Found должен быть выставлен на Nil, но тогда Found^.Next не определен! Аналогичная ситуация имеет место и при удалении последнего элемента.

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

а) Последний элемент списка можно считать признаком конца, поле Data которого не содержит значащей информации и указатель Found на него по условию не может быть установлен.

б) Можно изменить условия вставки-удаления: ссылка Found по условию устанавливается на элемент, предшествующий месту вставки или удаляемому элементу. Тогда отдельно (вне процедур) нужно рассматривать случай, когда обрабатывается 1-ый элемент. Сами же процедуры в этом варианте упрощаются.

Procedure Ins(var Found: Point, x:Integer);

  Var p: Point;

 Begin

  New(p);

  p^.Data := x;

  p^.Next := Found^.Next;

  Found^.Next := p;

 End;

Procedure Del(Found: Point);

  Var p: Point;

 Begin

  p:= Found^.Next;

  Found^.Next = Found^.Next^.Next;

  Dispose(p) {сборка мусора}

 End;

Часто вставке/удалению предшествует поиск места изменения списка. Для правильной работы процедур Ins и Del процедуру Search необходимо модифицировать. Просматривать список следует "на шаг вперед". Рассмотрим вариант процедуры поиска места элемента со значением поля Data = x в списке First с упорядоченными по возрастанию значениями полей Data.

 Procedure ForwardSearch(var Found, First: Point; var isFirst: Boolean; x: Integer);

  Begin

  Found := First;

   If First^.Data >= x

    then isFirst := True

    else begin

    isFirst := False:

    While (Found^.Next <> Nil) and (Found^.Next^.Data < x)

     do Found := Found^.Next;

    end

  End;

Если isFirst = True, то место - первое, иначе на место указывает Found^.Next.

Задачи на списки.

Элемент списка описывается следующим образом:

  Type Point = ^ Item;

     Item = Record

          Key: Integer;

          Data: Real;

          Next: Point

            End;

1.Реализовать процедуру слияния двух списков, элементы которых расположены по возрастанию значений полей Key. При равных значениях полей Key значения полей Data складываются. Оценить сложность алгоритма по времени в терминах длин списков.

2.Реализовать процедуру сцепления (конкатенации) двух списков. Оценить сложность алгоритма по времени в терминах длин списков.

3.Реализовать процедуру сортировки списка слиянием. Оценить сложность алгоритма по времени и памяти (в худшем случае).

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

а) F: File of Record Key: Integer; Data: Real End; с сохранением порядка расположения элементов в файле. Оценить сложность алгоритма по времени.

б) F: File of Record Key: Integer; Data: Real End; Список должен быть упорядочен по значениям полей Key. Оценить сложность алгоритма по времени.

5.Реализовать процедуры Push и Pop соответственно добавления и удаления элемента для стэка.

6.Реализовать процедуры Push и Pop соответственно добавления и удаления элемента для очереди.

 

6. Деревья

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

<список> ::= Nil | <элемент списка>   <список>

Здесь символ "::=" означает "есть по определению", "|" - "или", "   " - указатель (ссылка).

Аналогично можно определить и ветвящиеся структуры - так называемые деревья. Элемент такой структуры (узел дерева) определяется как запись, содержащая несколько полей ссылок. Например:

Type Point = ^ Item;

   Item = Record

      Data: Integer;

      Right, Left: Point

      End;

 

Type       

 Link = ^ TreeVert;

 TreeVert = Record

      Data: Real;

      Key : Integer;

      Left, Middle, Right : Link

End;

Количество ссылочных полей узла дерева называется степенью ветвления (арностью) узла. Рекурсивное определение дерева тогда имеет вид:

 <дерево> ::= Nil | < узел дерева >

 

<дерево>  <дерево>  . . .  <дерево>

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

Бинарные деревья.

 Бинарное дерево имеет вид  

 T(v)

                   v 

   L(v)        R(v)

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

Пример 5: Пусть A = a1, a2,..., ,an - последовательность целых чисел. Для того, чтобы отсортировать последовательность А, состоящую из элементов ai 

а) построим бинарное дерево, удовлетворяющее следующему свойству: для любого узла дерева v любой элемент L(v) v любой элемент R(v)

б) построим последовательность из узлов дерева, в которой элементы расположены в соответствии с этим же принципом: последовательность {L(v)}, v, последовательность {R(v)}.

Легко видеть, что выходная последовательность будет упорядоченной.

Решение.

 Последовательность A мы реализуем в виде списка. Нам понадобятся процедуры:

построения списка из чисел, вводимых с клавиатуры;

построения дерева, удовлетворяющего свойству п.а);

построения списка, удовлетворяющего свойству п.б);

вывода списка.

Типы элементов динамических структур данных задачи:

Type Point = ^ Item;

 Item = Record

  Key: Integer; Next: Point

  End;

Link = ^ Vertex;

Vertex = Record

  Key: Integer;

 Left, Right: Link;

  End;

Программа решения задачи:

Program ListSort;

{описания типов данных}

 Var A, B: Point;

   LastB:Point; {конец списка B}

    Tree: Link;

 {описания процедур}

 {процедура ввода списка}

 {процедура построения дерева из списка}

 {процедура построения списка из дерева}

 {процедура вывода списка}

 

Begin {раздел операторов}

   InpList(A);     {процедура ввода списка}

   Tree := Nil;

   TreeBild(Tree, A);    {процедура построения дерева Tree из списка A}

   B := Nil;

   ListBild(Tree, B);    {процедура построения списка B из дерева Tree}

   OutList(B);     {процедура вывода списка}

  End. {конец программы}

Procedure InpList(var P: Point);   {процедура ввода списка}

  Var Ch: Char;

    Q: Point;

 Begin

  P := Nil;      {пустой список}

  Writeln('Для ввода числа нажмите y');

  ch := Readkey;

  While ch = 'y' do begin

  New(Q);      {формирование нового элемента списка}

  Writeln('Input Item:');

  Read(Q^.Key);

  Q^.Next := P;     {включение нового элемента в список}

  P := Q;      {указатель списка - на начало списка}

  Writeln('Продолжить ввод? Y/N ');

  ch:= Readkey

 end

End;

Procedure TreeBild(var T: Link; P: Point);  {процедура построения дерева из списка}

  Var x: Integer;

 Procedure Find_Ins(var Q: Link; x: Integer);

 Procedure Ins(var S: Link);

   Begin {процедуры вставки элемента}

    New(S);

    S^.Key := x;

    S^.Left := Nil; S^.Right := Nil

   End;{процедуры вставки элемента}

  

Begin {процедуры поиска и вставки элемента}

   x := P^.Key;

   If Q = Nil

    then Ins(Q)

    else if x < Q^.Key

     then Find_Ins(Q^.Left, x)

     else Find_Ins(Q^.Right, x)

   End; {процедуры поиска и вставки элемента}

  Begin {процедуры построения дерева из списка}

   If P <> Nil

   then begin

    Find_Ins(T, P^.Key);

    TreeBild(T, P^.Next)

   end

  End; {процедуры построения дерева из списка}

Тонким местом организации управления в процедуре построения дерева является передача ссылок на вершины обрабатываемых структур в виде параметров-переменных. Это позволяет порождать узлы дерева без использования дополнительных указателей.

{процедура построения списка из дерева}

 Procedure ListBild(var T: Link; var F: Point);

   Var Temp: Point;

   Begin

   If T <> Nil

    then begin

     ListBild(T^.Left, F);

     New(Temp); {порождение нового элемента}

     Temp^.Key := T^.Key;

     Temp^.Next := Nil;

     If F = Nil

      then begin

       F := Temp; LastB := Temp

      end

    else begin

     LastB^.Next := Temp; LastB := Temp

    end;

    {переменная LastB - указатель на последний элемент строимого списка}

    ListBild(T^.Right, LastB^.Next)

   end

  End;{процедуры построения списка из дерева}

 

Procedure OutList(var P: Point); {процедура вывода списка}

  Var x: Integer;

 Begin

  If P <> Nil

   then begin

   Write(P^.Key, ' ');

   OutList(P^.Next)

   end

 End;{процедуры вывода списка}

 

{процедура вывода дерева -использовалась при отладке}

 Procedure OutTree(var T: Link);

 Begin

  If T <> Nil

  then begin

   OutTree(T^.Left);  {левое поддерево}

   Write('V = ', T^.Key);  {корень дерева}

   OutTree(T^.Right);  {правое поддерево}

  end

 End;{процедуры вывода дерева}

В процедурах ListBild и OutTree использован общий принцип обработки дерева - так называемый обход дерева слева - направо:

L(v) -обработка левого поддерева; v - обработка корня; R(v) - обработка правого поддерева.

Обработка L(v) и R(v) реализована как рекурсивный вызов процедуры обработки дерева. Кроме обхода слева направо, в задачах используются также и другие порядки перечисления узлов. Для бинарных деревьев это:

   L(v) - v - R(v) - слева направо;

   R(v) - v - L(v) - справа налево;

   v - L(v) - R(v) - сверху вниз;

   L(v) - R(v) - v - снизу вверх.

Если в процедуре ListBild применить обход справа налево, элементы списка B будут упорядоченными по убыванию. В процедуре Find_Ins по существу применен обход сверху вниз в модификации: v - L(v) или R(v) (в зависимости от результата сравнения x < Q^.Key).

Если в виде дерева представлено арифметическое выражение (пример 1), процедуру вычисления его значения нужно программировать обходом снизу-вверх: вычислить значение левого операнда, правого операнда, результат бинарной операции. Нетрудно увидеть, что если при построении дерева Tree любое левое поддерево будет содержать столько же узлов, сколько и соответствующее правое, для его построения потребуется O(n*log2n) сравнений. Однако в худшем случае (если, например, исходный список упорядочен), для вставки каждого следующего узла алгоритм будет следовать по одной и той ветви (например, левой). Поэтому алгоритм тратит O(n2) сравнений, т.е. не является эффективным. Однако его можно модифицировать таким образом, чтобы процедура TreeBild строила т.н. сбалансированное дерево. Тогда алгоритм сортировки станет эффективным.

Задачи на деревья.

1.Класс арифметических выражений, содержащий однобуквенные переменные, операции +, -, *, / и круглые скобки, назовем классом простейших выражений. Реализовать:

процедуру построения дерева простейшего арифметического выражения, заданного в виде строки.

процедуру вычисления значения простейшего арифметического выражения, заданного деревом при значениях переменных, вводимых с клавиатуры.

процедуру преобразования дерева в строку.

2. В параграфе 9, алгоритм пирамидальной сортировки, изложен метод представления массива в виде бинарного дерева. Реализовать процедуру построения этого дерева по массиву V[1..n].

3. Книга состоит из 3-глав. Каждая глава содержит 3 параграфа. а каждый параграф - 3 раздела. Все указанные структурные части книги имеют названия. Реализовать :

процедуру построения оглавления книги в виде тернарного дерева;

диалоговую процедуру поиска названия каждой части книги по ее номеру;

вывод оглавления на экран с помощью различных обходов;

поиск раздела по его названию.

4. Реализовать процедуры сравнения двух однотипных бинарных деревьев T1 и T2 на равенство (T1 = T2) и вложение (T1 ) T2), используя следующие рекурсивные определения:

Через root(T) обозначим корень дерева T. Тогда

T1 = T2, если root(T1) = root(T2) и L(root(T1)) = L(root(T2)), R(root(T1)) = R(root(T2))

T1  T2, если root(T1)=root(T2) или T1=Nil и L(root(T1)) L(root(T2)), R(root(T1)) R(root(T2))

5. Реализовать процедуру поиска в дереве T1 поддерева, равного T2. Использовать процедуру сравнения из предыдущей задачи

6. Реализовать процедуры, иллюстрирующие графически:

построение бинарного дерева;

поиск узла с данным ключом различными обходами.


 

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

31941. Семантика и функции кавычек в современном русском языке (на материале печатных СМИ) 189 KB
  Объектом диссертационного исследования являются кавычки распространение которых в языке СМИ подтверждает тенденцию к экспрессивизации газетнопублицистического текста. Научная новизна диссертационного исследования заключается в следующем: выявлены основные тенденции употребления факультативных кавычек в современном русском языке; переносная метаязыковая и модальная функции кавычек впервые раскрыты на обширном языковом материале отражающем реалии начала XXI века; установлены семантические процессы влияющие на выделение слова кавычками...
31942. Банковская система РФ 26.5 KB
  Основной целью банковской системы является обслуживание оборота капитала в процессе производства и обращения товаров. Банковская система является главным звеном финансовокредитной системы государства так как на нее падает нагрузка по кредитнофинансовому обслуживанию хозяйственного оборота страны. Основные задачи банковской системы любой страны: обеспечение эффективного и бесперебойного функционирования системы расчетов в народном хозяйстве; аккумуляция временно свободных ресурсов в стране; кредитование производства обращения...
31943. Р. БАРТ СЕМАНТИКА ВЕЩИ 54 KB
  Прежде всего как же нам определить вещь до того как выяснять каким образом вещи могут чтото значить В словарях даются расплывчатые дефиниции: вещь объект [object] это то что доступно зрению это то что мыслится по отношению к мыслящему субъекту; короче как говорится в большинстве словарей это некоторая вещь дефиниция которая ничего нам не даёт если только не попытаться выяснить какие коннотации имеет данное слово. Вещь очень быстро у нас на глазах начинает казаться или даже существовать как чтото нечеловеческое...
31944. Понятия текст/реальность, письмо/жизнь 38.5 KB
  Главная проблема письма и реальности состоит в постановке вопроса как соотносится письмо и реальность: проясняет ли письмо реальность вытесняет ли реальность каковы границы между письмом и реальностью или же письмо – это онтологическое понятие Вторая проблема – это рассмотрение письма как акта коммуникации и третья – письмо как знаковая система противопоставленная реальности письмо является моделирующей новую реальность системой вследствие чего возникает вопрос: письмо – вторичная или первичная реальность И являясь материально...
31946. Общественное мнение как социальный феномен и его функционирование в системе властных отношений 138.5 KB
  Проблема общественного мнения всегда была одной из самых актуальных в сфере общественных наук таких как политология философия социология психология. мы находим интерпретации понятия общественного мнения первые попытки осознания его роли и значения в общественной жизни. Гоббс В новое время осмыслению феномена общественного мнения способствовало творчество английских философовматериалистов Ф. Руссо Важное место в эволюции взглядов на роль общественного мнения в государственном управлении принадлежало французскому Просвещению XVIII в.