38022

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

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

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

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

Русский

2013-09-25

1.59 MB

14 чел.

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

         

          

         

         

         

         

         

         

         

         

         

    

         

         

         

         

    


 

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

37760. ОТРАВЛЯЮЩИЕ ВЕЩЕСТВА РАЗДРАЖАЮЩЕГО ДЕЙСТВИЯ. КЛИННИКА, ДИАГНОСТИКА, ЛЕЧЕНИЕ 70.5 KB
  Уже в первой мировой войне почти все воюющие страны применяет различные ОВ, избирательно действующие на окончания чувствительных нервов в верхних дыхательных путях с последующей реакцией организма в виде слезотечения, кашля, рвоты, затрудненного, дыхания и т.д
37761. Исследование разветвленной линейной электрической цепи постоянного тока 109.5 KB
  Цель работы Экспериментальная проверка законов Кирхгофа и основных свойств линейных цепей постоянного тока. Экспериментальная часть Схема установки R1 = 100 Ом R2 = 50 Ом R3 = 25 Ом Е1 = 75 В E2 = 10 В Проверка законов Кирхгофа Измерено Вычислено I1 I2 I3 Ik 009 016 0065 0005 I1 I2 I3 = 0.065 А Вывод: Экспериментально были проверены законы Кирхгофа. Выставив необходимые значения сопротивлений и проведя необходимые измерения и...
37762. Измерение вязкости жидкости по методу падающего шарика 45.5 KB
  Измерение температуры жидкости t= 0C Расчет искомой величины. Расчет плотности материала шариков 2. Расчет вязкости жидкости Расчет границы погрешностей. Расчет границы абсолютной погрешности результата измерения плотности материала шариков Расчет границы относительной погрешности результата измерения вязкости жидкости Расчет границы абсолютной погрешности результата измерений плотности Окончательный результат: вязкость жидкости при температуре t= 0C.
37763. Методы противодействия радиоэлектронным закладным устройствам, предназначенным для снятия конфиденциальной информации 48.88 KB
  Цели и учебные вопросы Цели лабораторной работы: ознакомление с возможностями комплекса Крона НМ и программного обеспечения Филин Ультра; получение практических навыков: по проведению радиомониторинга в контролируемой зоне по обнаружению поиску и блокированию радиозакладных устройств Учебные вопросы: классификация поисковых устройств для проведения радиомониторинга см. Место: лаборатория Технические средства обеспечения безопасности Используемые технические средства: автоматизированный комплекс обнаружения электронных...
37764. Безпека SMTP і спам 760.04 KB
  У результаті цього спам став практично нерозв'язною проблемою так як було неможливо визначити хто насправді є відправником повідомлення фактично можна відправити лист від імені будьякої людини. DT CRLF Вказує на початок повідомлення. Для завершення повідомлення вказується CRLF . Повідомлення доставляються клієнтові за протоколом POP а надсилаються як і раніше за допомогою SMTP.
37765. Робота з діалоговими компонентами 2.09 MB
  Виконавши лабораторну роботу, я освоїв роботу програм з такими діалоговими компонентами як OpenDialog та SaveDialog для зв’язку з файлами (їх створення, збереження або відкриття вже існуючих), PrinterSetupDialog для налагодження підключених принтерів для друку, FindDialog та ReplaceDialog для пошуку та заміни тексту. Також закріпив навички роботи з компонентами середовища Delphi TMemo та TMainMenu, зрозумів основні принципи створення текстового редактора.
37766. Безопасность жизнедеятельности. Чрезвычайные ситуации мирного и военного времени, организация защиты населения 262.51 KB
  Безопасность жизнедеятельности — это область научных знаний, изучающая общие опасности, угрожающие каждому человеку, и разрабатывающая соответствующие способы защиты от них в любых условиях обитания человека.
37767. Протокол для передачі файлів FTP 189.19 KB
  Для переходу в інший каталог використовую команду CWD: CWD incoming. Для того щоб створити в цій директорії вводжу команду STOR: STOR myfile. Переходжу в інший каталог за допомогою команди CWD: cwd incoming та вводжу команду PWD яка відображає вмістиме каталогу з яким встановлений звязок:. Вводжу команду LS що відображає файли і підкаталоги в даному каталозі.
37768. Розробка складних додатків з використанням графіки 1.16 MB
  ps unit Unit1; {mode objfpc}{H} interfce uses Clsses SysUtils FileUtil LResources Forms Controls Grphics Dilogs Menus StdCtrls ExtCtrls Spin; type { TForm1 } TForm1 = clssTForm Button1: TButton; Button2: TButton; Button3: TButton; ColorDilog1: TColorDilog; MinMenu1: TMinMenu; MenuItem1: TMenuItem; MenuItem2: TMenuItem; MenuItem3: TMenuItem; MenuItem4: TMenuItem; MenuItem5: TMenuItem; MenuItem6: TMenuItem; MenuItem7: TMenuItem; MenuItem8: TMenuItem; MenuItem9:...