38022

Лабораторная работа № 3 ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ АТД ДЕРЕВО Цель работы: исследовать и изучить АТД.

Лабораторная работа

Архивоведение и делопроизводство

n] of integer; vr :tree; Реализация деревьев с использованием списков сыновей. Списки сыновей составляются для каждого узла.1 можно составить соответствующие списки сыновей рис.5 Тип для реализации АТД дерево через списки сыновей рис.

Русский

2013-09-25

1.59 MB

11 чел.

6

Лабораторная работа № 3

«ПРЕДСТАВЛЕНИЕ И РЕАЛИЗАЦИЯ АТД «ДЕРЕВО»»

Цель работы: исследовать и изучить АТД «дерево».

Задача работы: овладеть навыками составления структур АТД «дерево» и написания программ по исследованию АТД «дерево» на любом языке программирования.

Порядок работы :

  1.  изучить описание лабораторной работы;
  2.  по заданию, данному преподавателем, разработать структуру АТД «дерево»;
  3.  написать программу на языке ПАСКАЛЬ;
  4.  отладить программу;
  5.  решить задачу;
  6.  оформить отчет.

Краткая теория

Рассмотрим все реализации АТД «дерева» на простом примере (рис. 3.1).

Реализация «дерева» посредством массивов. Обычно используется схема с курсорами, где A[i]=j, если узел j является родителем узла i, и A[i]=0, если узел является корнем. Для дерева (рис. 3.1) массив из курсоров на родителей – это рис. 3.2.

Запишем тип для данной структуры:

Type

tree=array[1..n] of integer;

var A:tree;

Реализация деревьев с использованием списков сыновей. Списки сыновей составляются для каждого узла. Так, например, для дерева рисунка 3.1 можно составить соответствующие списки сыновей (рис. 3.3 – 3.5)

Тип для реализации АТД «дерево» через списки сыновей (рис. 3.3):

Type

Tree=array[1..n] of ^ptree;

ptree=record

element:integer;

next:ptree;

end;

var

A:tree;

А для реализации АТД «дерево» через списки сыновей посредством массивов нужно использовать следующий тип:

Type

Tree=array[1..n] of record

element:integer;

next:integer;

End;

Var

A:tree;

Реализация деревьев через левых сыновей и правых братьев. Здесь используются курсоры на левых сыновей и правых братьев. Ячейка структуры состоит из трёх полей: left_son, element, right_brother.

Тогда тип для данной структуры (рис. 3.5) будет иметь вид:

Type

Tree=array[1..n] of record

left_son:integer;

element:integer;

right_brother:integer;

End;

Var

A:tree;

Если ввести ещё одно логическое поле, то можно «дерево» рис. 3.1 представить в другом виде рис. 3.6. Для этой реализации тип будет выглядеть так:

Type

Tree=array[1..n] of record

left_son:integer;

element:integer;

right_brother:integer;

uk_parent:Boolean;

End;

Var

A:tree;

Если в поле uk_parent стоит 1, то в поле right_brother этой же ячейки стоит индекс на родителя правого брата.

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

Поэтому рассмотрим данную реализацию (рис. 3.8) на примере другого дерева (рис. 3.7).

     

А для этой реализации АТД «дерево» тип будет таким:

Type

Tree=array[1..n] of record

left_child:integer;

right_child:integer;

End;

Var

A:tree;

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

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

  1.  PARENT – это оператор, который возвращает родителя для заданного узла из «дерева». Если заданный узел является корнем, то оператор возвращает условный знак, обозначающий «нулевой узел», что соответствует выходу за пределы «дерева».
  2.  LEFTMOST_CHILD – этот оператор используется для определения самого левого сына заданного узла в «дереве». Если заданный узел является листом, то возвращается знак, обозначающий «нулевой узел», так как он не имеет сына.
  3.  RIGHT_SIBLING – этот оператор возвращает правого брата заданного узла из «дерева» или знак, обозначающий «нулевой узел», если такого не существует. Для этого находится родитель для заданного узла, а потом и все сыновья найденного родителя, затем среди этих сыновей находится узел, расположенный справа от заданного узла.
  4.  LABEL – этот оператор осуществляет возврат метки заданного узла из «дерева». Для этого необходимо, чтобы на узлах «дерева» были определены метки.
  5.  CREATEi – семейство операторов, создающих новый корень с определённой меткой, а далее для этого корня создаёт i сыновей, которые становятся корнями следующих поддеревьев. Эти операторы создают «дерево» с определённым корнем. Если i=0, то будет создан лишь один узел, который является одновременно и корнем, и листом.
  6.  ROOT – этот оператор создаёт корень «дерева». Если в «дереве» ещё нет элементов, то возвращается знак, который говорит о том, что «дерево» пустое.
  7.  MAKENULL – этот оператор делает заданное «дерево» пустым.

Задания по вариантам:

Для заданного по варианту «дерева» составить все рассмотренные реализации: 1) посредством массивов; 2) списков сыновей; 3) левых сыновей и правых братьев; 4) левых и правых сыновей.

После этого составить программу для заданной по варианту реализации АТД «дерева» (см. табл. 3.1). В программе необходимо реализовать один из операторов, заданных по вашему варианту (табл. 3.2).

Таблица 3.1

Выбор способа реализации АТД «дерево»

Название реализации

Вариант

посредством массивов

1, 5, 9, 13, 17, 21, 25, 29, 33, 37, 41, 45, 49

списков сыновей

2, 6, 10, 14, 18, 22, 26, 30, 34, 38, 42, 46, 50

левых сыновей и правых братьев

3, 7, 11, 15, 19, 23, 27, 31, 35, 39, 43, 47

левых и правых сыновей

4, 8, 12, 16, 20, 24, 28, 32, 36, 40, 44, 48

Таблица 3.2

Выбор оператора

Номер оператора

Вариант

1

1, 8, 15, 22, 29, 36, 43, 50

2

2, 9, 16, 23, 30, 37, 44

3

3, 10, 17, 24, 31, 38, 45

4

4, 11, 18, 25, 32, 39, 46

5

5, 12, 19, 26, 33, 40, 47

6

6, 13, 20, 27, 34, 41, 48

7

7, 14, 21, 28, 35, 42, 49

         

          

         

         

         

         

         

         

         

         

         

    

         

         

         

         

    


 

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

26875. Задний мозг 3.96 KB
  Задний мозг metencephalon состоит из мозжечка cerebellum и мозгового варолиева моста pons cerebri Varoli . Между ними остаётся глубокая щель верхушка шатра fastigium являющаяся дорсальным отделом четвертого мозгового желудочка. Построен из серого и белого мозгового вещества. Построен он из белого мозгового вещества по периферии и серого в виде ядер.
26876. Продолговатый мозг 4.44 KB
  От начала пирамид отходит VI пара отводящий черепномозговых нервов. От перекреста XII пара подъязычный; от боковой поверхности продолговатого мозга отходят: пары нервов лицевой слуховой языкоглоточный блуждающий и добавочный. На нём выступает лицевой холмик colliculus facialis где сосредоточены ядра отводящего и лицевого нервов. Позади лицевого холмика расположено поле подъязычного нерва area hypoglossi а латерапьнее от него находится серое крыло alia cinerea в котором лежат ядра...
26877. Желудочки головного мозга 5 KB
  Желудочки головного мозга. К желудочкам головного мозга относятся: Боковые желудочки ventriculi laterales telencephalon; Боковые желудочки головного мозга лат. ventriculi laterales полости в головном мозге содержащие ликвор наиболее крупные в желудочковой системе головного мозга. Третий желудочек ventriculus tertius diencephalon; Третий желудочек мозга ventriculus tertiusнаходится между зрительными буграми имеет кольцевидную форму так как в него прорастает промежуточная масса зрительных бугровmassa intermedia thalami.
26878. Оболочки и сосуды головного и спинного мозга 4.04 KB
  Оболочки и сосуды головного и спинного мозга Головной и спинной мозг окружен тремя мозговыми оболочками meninges. В области большого затылочного отверстия оболочки головного мозга переходят в оболочки спинного мозга. 4 показаны оболочки головного мозга. Твердая оболочка спинного мозга отделена от внутренней поверхности позвоночного канала от надкостницы позвоночного канала надоболочечным эпидуральным пространством.
26879. Общие закономерности строения и ветвления спинномозговых нервов 5.94 KB
  Спинномозговые нервы от спинного мозга отходят метамерно в соответствии с делением костной основы и подразделяются на шейные грудные поясничные крестцовые и хвостовые. Черепномозговые нервы отходят от продолговатого с XII по V пару и среднего мозга IV и III пары. Черепномозговые нервы отходят преимущественно одним корнем соответствующим дорсальному или вентральному корешку спинномозгового нерва. Строение Спинномозговые или спинальные нервы 31 пара берут начало в спинном мозге и выходят из него между соседними позвонками почти по...
26880. Грудные спинномозговые нервы. Плечевое сплетение 3.12 KB
  Грудные спинномозговые нервы. Основные нервы Дорсальный нерв лопатки тп. dorsalisscapulae Надлопаточный нерв п. suprascapularrs Подлопаточные нервы шї.
26881. Поясничные спинномозговые нервы. Поясничное сплетение 3.08 KB
  Только первые 2 4 поясничных нерва имеют белые соединительные ветви но все получаютсерые соединительные ветви и делятся на дорсальные и Вентральные ветви. Дорсальные ветви идут в разгибатели йоясницы и отдают латеральные кожные ветви в ягодичные краниальные нервы nn. Вентральные ветви образуют поясничное сплетение т plexuslumbales соединяющееся с крестцовым сплетением Подвздошноподчревный нерв п. genitofemoral і s 16 начинается от L III II и IV и отдает ветви в малую поясничную квадратную поясничную и брюшные мышцы и идет по...
26882. Крестцовые спинномозговые нервы. Крестцовое сплетение 2.6 KB
  Крестцовые спинномозговые нервы эти нервы делятся на передние и задние ветви при этом передние ветви выходят на тазовую поверхность крестца в полость таза задние на дорсальную его поверхность. Задние ветви в свою очередь делятся на внутренние и наружные. Внутренние ветви иннервируют нижние сегменты глубоких мышц спины и оканчиваются кожными ветвями в области крестца ближе к средней линии. Наружные ветви I III крестцовых спинномозговых нервов направляются книзу и имеют название средних кожных нервов ягодиц пп.
26883. Седалищный нерв 5.99 KB
  Седалищный нерв Седалищный нерв п. Он и ннервирует всю конечность за исключением некоторых ягодичных мышц сгибателей тазобедренного сустава и разгибателей коленного сустава. Проходит позади тазобедренного сустава и делится на большеберцовый и малоберцовый нервы идущие в области бедра вместе по медиальной поверхности двуглавой мышцы бедра почти до коленного сустава. Малоберцовый нерв п.