Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 38
Текст из файла (страница 38)
Приведеииая выше программа фазы вывода служит примером работы со списком, который «пульсирует», т. е. зле!сеиты которого добавляются и удаляются в непредсказуемом порядке. Слсдовательгю, это пример процесса, полностью д:= )сеай; тиЬ|1е д~п11 бо Ьеп)п !вывести этот элемент, затем исключить его) птие1п(д~.йеу) г:=- г — 1; 1:=д !Лга)1; д:=- д).пехц «умеиьшить счетчик предшествеиииков у всех его последователей в списке ведомых 1; если какой-либо счетчик стал равен О, добавить этот элемент к списку ведущих д» епб реоагапз !орзо~ !(1приг,о!при!); !уре 1«е!' = '11«аде«; !геГ = 1!«аИсг; 1еайег =.
тесотй Ьеу; 1п!«ее«; сочи!; !п1екег; ! аИ: !гс1; псх! , 'Ь е!'. епй; !«аИег = гесегй !И: 1ге3'; пах!! !«еу епй; чае Бса«1, га11, р,д: Ье!'; г: !ге~; е.' 1п!еее«; х,у: !и!ееег; !ппс!!оп Х(и' !и!ееег): 1«е!'; ! ссылка иа ведущего с ключом и') тех Ь: 1«ер; Ьеа!и Ь:=- ЬеаЫ; !аИ";,йеу;= !е; пЬИе Ь!.Ьеу ~ и йе Ь;= Ь).пех1; 1Х Ь = 1аИ1Ьеп Ьеьйа )в списке нет элемента с ключом и! пе!«РаИ); е:== -'+1; Ь).сока!:= О,' Ь1,!«аИ:= п!!1 Ь!',пах! 1= 1аИ епй,' Л:=Ь епй )Ц; Ьеи!а )ипициаиия списка ведущих !йиктивнегМ племен!!шв) пеи(!~еаг1), '!аИ ',= Ьеой; е;=- О; (!раза ввода) геаг1(х); иЬИех ~ Ойа ьеа)п гвиану); и'«1!«1п(х,у); р;= Х1х); а:= Х(у),' пси (!); !', и1:= И; !)'.пех1:=' рТ 1«а!11 р",,!!чл1;--- 1: !11.со!т1 .'= ~Х .соип1 )- 1ге гсаИ1х) ° й; ! поиск ведун!их со счегпчикомО) р;=-.
йеал; ЬеаЫ:== и!1; ъЬ!!е р ~-. 1аИйе Ьее!п а;=- р; р;= р~.пех1; !! д",,сонг!! = О 1Ьеа Век!а д'опек!:= Ьеай! Ьеа4 1= И 219 4.4. Лревовионив сгруктурвг еп4 ° 41 (Фаза во«вода) д . '— — Ьеаг1„ ТТЬ11е г1 ае пй до Ьее1п атее!п(у(,1сеу)1 к;=.=- г — 1; с:=- у(ага11; у 1== д,.гехт; ИЫ1е Г ье в1 до Ьее1и р:=- г1лг1; р1.свинг;=- р1.свои( — 1; Ы р1.сошгФ вЂ” - О ТЬеп Ьее1п (включенпе р1 в д-список) р~,всх1:=- у,' д 1=- р епй; = 1)лекс епд епй; И Х ва О ТЬЕП жс11Е1П (ТН1З ЗЕТ 1З Наг РАНТ1КЬЬТ Онагнеа') еп4 .
Программа 4 2. Топологячссквя сортяровка. используюшего гибкость, которую обеспечивает явно связан- ный список. 4.4. ДРЕВОВИДНЫЕ СТРУКТУРЫ 4.4.1. Основные понятия и определения Мы виделн, что последовательности н списки можно определить следуюшнм образом: любая последовательность (список) с базовым типом Т вЂ” это либо: 1) пустая последовательность (список); либо 2) конкатенация (цепочка) из элемента типа Т и последовательности с базовым типам Т. Здесь для определения принципов структурирования (следования илп итерации) используется рекурсия.
Следование н итерация встречается настолько часто, что нх обычно считают фундаментальными «образамн» как структур данных, так и «управления» в программах, Однако всегда следует помнить, что с помошью рекурсий их только можно определять, но рекурсии можно эффективно и элегантно использовать для определения более сложных структур, Хорошо известным примером служат деревья.
Пусть древовидная структура определяется следуюшнм образом: древовидная структура с базовым типом Т вЂ” это лнбш 1) пустая структура; либо 220 Е, динамические информационные структуры 2) узел типа Т, с которым связано конечное число древовидных структур с базовым типом Т, называемых поддеревьями. Из сходства рекурсивных определений последовательностей и древовидных структур видно, что последовательность (список) есть древовидная структура, у которой каждый узел имеет не более одного «поддереватк Поэтому последовательность (список) называется также вьсрожденным деревом.
Существует несколько способов изображения древовидной структуры. Например, пусть базовый тип Т есть множество букв; такая древовидная структура разными способами изображена на рис, 4.17, Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны, С помощью графа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребительному термину «дерево», Однако довольно странно, что деревья принято рисовать перевернутыми или — если кто-то предпочитает иначе выразить этот факт — изображать корпи дерева.
Но последняя формулировка вводит в заблуждение, так как верхний узел (А) обычно называют корнем. Хотя мы сознаем, что в природе деревья представляют собой несколько более сложные образования, чем наши абстракции, мы будем в дальнейшем древовидные структуры называть просто деревьями. Упорядоченное дерево — это дерево, у которого ветви каждого узла ) порядоченны, Следовательно, даа упорядоченных дерева на рис. 4.1 — это особые, отличные друг от друга деревья.
Узел у, который находится непосредственно под узлом х, называется (непосредственным) потомком х; если з находится на уровне й то говорят, что у — на уровне т' + 1. Наоборот, узел л. называется (непосредственным) предком 1п Считается, что корень дерева расположен па уровне 1.Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой. Если элемент нс имеет потомков, он назьиается терминальным элементом илн листом, а элемент, не являющийся терминальным, называется внутренним узлом, Число (непосредственных) потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степень дерева. Число ветвей, или ребер, которые нужно пройти, чтобы продвинуться от корня к узлу х, называется вчиной пути к х, Корень имеет длину пути 1, его непосредствснные потомки— длину пути 2 и т.
д. Вообще, узел па уровне т имеет длину пути й Длина пути дерева определяется как сумма длин путей всех его узлов. Оиа также называется длиной внутреннего пути, Например, длина внутреннего путп дерева, изобра- 4, Диналиеегние ии4орнакионнме сгрунтрры женного на рнс. 4.17, равна 52. Очевидно, что средняя длина пути Р~ есть ! 14.34) а где и; — число узлов на уровне й Для того чтобы определить, по называется длиной внешнего пути, мы будем дополпячь дерево специальным узлом каждый раз, когда и нем встречается нулевое поддерево.
Г1рн этом мы считаем, что все узлы должны иметь одну н ту же степень — степень дерева. Следовательно, подобное расширение дерева предполагает запол- Рнс, 4.18. два раалнчнмх заварных дерева. иенце пустых ветвей, разумее~ся, при этом специальные узлы не нмек)т дальнейших потомков. Дерево на рнс, 4.17, допел* ненное специальными узлами, показано на рис. 4,19, где специальные узлы изображены квадратиками. Рнс.
4.19. Тернарное дерево со снеьаалыннмн уаламн, Днако внешнего пути теперь определяется как сумма длин путей всех специальных узлов. Если число специальных уэлен на уровне 1 есть гпь то средняя длина внешнего пути Рн равна (4.35) 4.4. Древовидные структур»с 223 У дерева, приведенного на рис. 4.19, длина внешнего пути равна 153. Число специальных узлов т, которые нужно добавить к дереву степени с4, непосредственно зависит от числа и исходных узлов.
Заметим, что на каждый узел указывает ровно одна ветвь. Следовательно, в расширенном поддереве имеется т + и ветвей. С другой стороны, из каждого исходного узла выходят д ветвей, а из специальных узлов — ни одной. Поэтому всего пмеется дсс+ 1 ветвей (1 даст ветвь, указываюсцую иа корень). Из этих двух формул мы получаем следующее равенство между числом т специальных узлов и п исходных узлов; да+1 = т+п, или т = (д — 1) п + 1. (4.36) Максимальное число узлов в дереве заданной высоты Ь достигается в случае, когда все узлы имеют д поддеревьев, кроме узлов уровня Ь, не имеющих нн одного. Тогда в дереве степени д первый уровень содержит 1 узел (корень), уровень 2 содержит д его потомков, уровень 3 содержит ест потомков д узлов уровня 2 и т.
д. Это дает следующую величину: л-с Ьси(Ь)=1+ ас+ с! + ... + ос '= 2 сс' (4.37) в качестве максимального числа узлов для дерева с высотой Ь и степенью д. При д = 2 мы получаем В-с Ьс (Ь) = Х 2'= 2" — 1. (4.38) Сса Упорядоченные деревья степени 2 играют особо важную роль, Онп называются бинарньслси деревьялси. Мы определяем упорядоченное бинарное дерево как конечное множество элементов (узлов), каждый из которых либо пуст, либо состоит ссз корня (узла), связанного с двумя различньсвси бинарнасми деревьями, называемыми левылс и правылс поддеревом корня. В следующих пунктах этого раздела мы будем рассматривать исключительно бинарные деревья и поэтому будем употреблять слово «дерево», имея в виду «упорядоченное бинарное дерево».
Деревья, и:леющие степень больше 2, называются сильно ветвяи!илсися деревьями (ти!!сшау !геев), они рассматриваются в разд, 5 этой главы. Знакомыми примерами бинарных деревьев являются фамильное (генеалогическое) дерево с отцом и матерью человека в качестве его потомков (!), история теннисного турнира, где узлом является каждая игра, определяемая ее победтстсленс, а поддеревьями — две предыдущие игры соперников; арифметическое выражение с двухместными операциями, где каждая ц улиционные ссууккуды операция представляет собой ветвящийся узел с операндами в качестве поддеревьев (см.
рпс. 4.20). Теперь мы обратимся к проблеме представления деревьев. Ясно, что изображение таких рекурсивнь1х структур (точнее, рекурсивно определенных. — Прим. Ред.) с разветвлениями предполагает исгюльзовгнпе ссылок, Очевидно, что ие имеет смысла описывать переменные с фиксированной древовидной структурой, вместо этого узлы определяются как переменные Рис. 4.20. Вырвженне (а+ Ь)с)'(н — е'"(), ~редстввденное в виде дерева. с фиксированной структурой, т, е. фиксированного типа, где степень дерева определяет число компонент-ссылок, указываюшнх на поддеревья данного узла. Ясно, что ссылка на пустое поддерево обозначается через п(1.
Следовательно, дерево на рис. 4.20 состоит из компонент такого типа: (уре поде =гесогд ойч сйаг; )е)(, гЧ(йп ') пос(н епс( и может строиться, как показано на рис. 4.2!. Ясно, что существуют способы представления абстрактной древовидной структуры в терминах других типон данных, например таких, как массив. Это — общепринятый способ но всех языках, где нет средств динамического размещения ком. попент и указания их с помощью ссылок. В этом случае дерево на рис.
4.20 можно представить переменной-массивом, описанной как (: аггау(1..11) о1 гесогд орч айаг; (еГ(, г(йй(: (п(ейег епд (4.40) и со значениями компонен~, приведенными в табл. 4.3. 22о 4,4. Древовидные структуры Хотя подразумевается, что массив 1представлястабстрактную структуру дерева, мы будем называть его все жс не деревом, а массивом согласно явному определеншо. Мы не будем обсуждать другие возможные представления деревьев в системак, где отсутствует динамическое распределение памяти, НН ЫН Рпс. 4.21. Дерево, представпеавое как структура папина поскольку мы считаем, что системы программирования и языки, имеющие зто свойство, являются или станут широко распространенными. Таблица 4.З.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
