Вход

Древовидные структуры

Реферат по программированию
Дата добавления: 19 июня 2006
Язык реферата: Русский
Word, rtf, 6.9 Мб (архив zip, 627 кб)
Реферат можно скачать бесплатно
Скачать
Не подходит данная работа?
Вы можете заказать написание любой учебной работы на любую тему.
Заказать новую работу
30 Содержание: 1. Исследовательская часть ……………………………………….2 1.1. Основные понятия и определения ……………………..2 2. Конструкторская часть ………………………………………..1 5 2.1. Основные операции с бинарными деревьями …….1 5 2.2. Поиск по дереву с включением ……………………...1 9 2.3. Удаление из дерева ………………………………………3 0 3. Технологическая часть……………………………………….. 35 Список литературы 1. Исследовательская часть. Древовидные структуры 1.1. Основные понятия и определения. П оследовательности и списки можно опре делить следующим образом: любая последовательность (спи сок) с базовым типом Т — это либо: 1) пустая последовательность (список); либо 2) конкатенация (цепочка) из элемента типа Т и последова тельности с базовым типом Т. Здесь для определения принципов структурирования (сле дования или итерации) используется рекурсия. Следование и итерация встречается настолько часто, что их обычно счи тают фундаментальными «образами» как структур данных, так и «управления» в программах. Однако всегда следует помн ить, что с помощью рекурсии их только можно опреде лять, по рекурсии можно эффективно использо в ать для определения более сложных структур. Хоро шо известным примером служат деревья. Пусть дре вовидная структура определяется следующим образом: дре во ви д ная структура с базовым типом Т — это либо: 1 ) путая структура; либо 2) узел типа Т, с которым связано конечное число древовид ных структур с базовым ти по м Т, называемых подде ревьями. Из сходства рекурсивных определений последовательно стей и древовидных структур видно, что последовательность (список) есть древовидная структура, у которой каждый узел имеет не более одного «поддерева». Поэтому последователь ность (список) называется также вырожденным деревом. Существует несколько способов изображения древовидной структуры. Например, пусть базовый тип Т есть множество букв; такая древовидная структура разными способами изо бражена на рис. 1. Все эти представления демонстрируют одну и ту же структуру и поэтому эквивалентны. С помощью графа можно наглядно представить разветвляющиеся связи, которые по понятным причинам привели к общеупотребитель ному термину «дерево». Однако довольно странно, что де ревья принято рисовать перевернутыми или — если кто-то предпочитает иначе выразить этот факт — изображать корни дерева. Но последняя формулировка вводит в заблуждение, так как верхний узел (А) обычно называют корнем. Хотя мы сознаем, что в природе деревья представляют собой не сколько более сложные образования, чем наши абстракции, в дальнейшем древовидные структуры будем называть просто деревьями. Упорядоченное дерево — это дерево, у которого ветви каж дого узла упорядоче ны . Следовательно, два упорядочен ных дерева на рис. 2 — это особые, отличные друг от друга деревья. Узел у, который находится непосредственно под узлом х, называется (непосредственным) потомком х; если х находится на уровне i , то говорят, что у — на уровне i + 1. Наоборот, узел х называется (непосредственным) предком y . Считается, что корень дерева расположен на уровне 1. Макси мальный уровень какого-либо э лемента дерева называет cz его глубиной или высотой. Если элемент не имеет потомков, он называется терми нальным элементам или листом, а элемент, не являющ ийся терминальным, называется внутренним узлом. Число ( не по средственных) потомков внутреннего узла называется его степенью. Максимальная степень всех узлов есть степе нь де рева. Число ветвей, или ребер, которые нужно пройти, чт обы продвинуться от корня к узлу х, называется длиной пути к х . Корень имеет длину пути 1, его непосредственные потом к и — длину пути 2 и т. д. Вообще, узел на уровне i имеет дли ну пути i . Длина пути дерева определяется как сумма дли н пу тей всех его узлов. Она также называется длиной вн ут рен него пути. ( a ) ( A ( B ( D ( I ), E ( J , K , L )), C ( F ( O ), G ( M , N ) , H ( P )))) ( b ) ( c ) ( d ) Рис. 1. Представления древовидной структуры: (а) вложенные множества; ( b ) вложенные скобки; (с) ломаная последовательность; ( d ) граф. Например, длина внутреннего пути дерева, изобра женного на рис. 1 . , равна 52. Очевидно, что средняя длина пути P I есть ( 1.1 ) где n i - число узлов на уровне i . Для того чтобы определить, что называется длиной в нешнего пути, мы будем дополнят дерево специальным узлом каждый раз, когда в нем в с тре чается нулевое поддерево. П ри этом мы считаем, что все узлы должны иметь одну и ту же степень — степень дерева. Следо вательно, подобное расшире ние дерева предполагает запол нение Рис. 2 . Два различных бинарных дерева. пустых ветвей, разум еется, при этом специальные узлы не имеют дальнейших потомков. Дерево на рис. 1 , допол ненное специальными узлами, показано на рис. 3 , где спе циальные узлы изображены квадратиками. Рис. 3 . Тернарное дерево со специальными узлами. Длина внешнего пути теперь определяется как сумма дл ин путей всех специальных узлов. Если число специальных узлов на уровне i есть . m i , , то средняя длина внешнего пути P E равна ( 1.2 ) У дерева, приведенного на рис. 3 , длина внешнего пути равна 153. Число специальных узлов m , которые нужно добавить к дереву степени d , непосредственно зависит от числа п ис ходных узлов. Заметим, что на каждый узел указывает ровно одна ветвь. Следовательно, в расширенном поддереве имеется m + п ветвей. С другой стороны, из каждого исходного узла выходят d ветвей, а из специальных узлов — ни одной. По этому всего имеется dn +1 ветвей (1 дает ветвь, указываю щую на корень). Из этих двух формул мы получаем следую щее равенство между числом т специальных узлов и п исход ных узлов: dn + 1 = т + п, или m = ( d — l ) n 1 . ( 1.3 ) Максимальное число узлов в дереве заданной высоты h достигается в случае, когда все узлы имеют d поддеревьев, кроме узлов уровня h , не имеющих ни одного. Тогда в дереве степени d первый уровень содержит 1 узел (корень), уровень 2 содержит d его потомков, уровень 3 содержит d 2 потомков d узлов уровня 2 и т. д. Это дает следующую величину: ( 1.4 ) в ка честве максимального числа узлов для дерева с высотой h и степенью d . При d = 2 мы получаем ( 1.5 ) Упорядоченные деревья степени 2 играют особо важную роль. Они называются бинарными деревьями. Мы определяем упорядоченное бинарное дерево как конечное множество эле ментов (узлов), каждый из которых либо пуст, либо состоит из корня (узла), связанного с двумя различными бинарными деревьями, называемыми левым и правым поддеревом корня. В следующих пунктах этого раздела мы будем рассматривать исключительно бинарные деревья и поэтому будем употреб лять слово «дерево», имея в виду «упорядоченное бинарное дерево». Деревья, имеющие степень больше 2, называются сильно ветвящимися деревьями ( multiway trees ) . Знакомыми примерами бинарных деревьев являются фа мильное (генеалогическое) дерево с отцом и матерью человека в качестве его потомков (!), история теннисного турнира, где узлом является каждая игра, определяемая ее победителем, а поддеревьями — две предыдущие игры соперников; арифме тическое выражение с двухместными операциями, где каждая операция представляет собой ветвящийся узел с операндами в качестве поддеревьев (см. рис. 4 ). Теперь мы обратимся к проблеме представления деревьев. Ясно, что изображение таких рекурсивных структур (точнее, рекурсивно определенных. — Прим. ред.) с разветвлениями предполагает использование ссылок. Очевидно, что не имеет смысла описывать переменные с фиксированной древовидной структурой, вместо этого узлы определяются как переменные Рис. 4. Выражение (а+ b / c )*( d — e * f ), представленное в виде дерева. с фиксированной структурой, т. е. фиксированного типа, где степень дерева определяет число компонент-ссылок, указы вающих на поддеревья данного узла. Ясно, что ссылка на пус тое поддерево обозначается через nil . Следовательно, дерево на рис. 4 состоит из компонент ов такого типа: type node = record op: char; left , right : ^ node ( 1.6 ) end и может строиться, как показано на рис. 5 . Ясно, что существуют способы представления абстракт ной древовидной структуры в терминах других типов данных, например таких, как м ассив. Это — общепринятый способ во всех языках, где нет средств динамического размещения ком понент ов и указания их с помощью ссылок. В этом случае де р ево на рис. 4 можно представить переменной-массивом, описанной как t: аггау [1. .11] of record op: char; left , right : integer ( 1.7 ) end и со значениями компонент ов , приведенными в табл. 1 .1 . Хотя подразумевается, что массив t представляет абстракт ную структуру дерева, мы будем называть его все же не дере вом, а массивом согласно явному определению. Мы не будем обсуждать другие возможные представления деревьев в си стемах, где отсутствует динамическое распределение памяти, Рис. 5 . Дерево, представленное как структура данных. поскольку мы считаем, что системы программирования и язы ки, имеющие это свойство, являются или станут широко рас пространенными. Таблица 1 .1 . Дерево, представленное с помощью массива * 2 3 + 6 4 — 9 5 1 7 8 * 10 11 а 0 0 Ь 0 0 с 0 0 d 0 0 е 0 0 / 0 0 1 2 3 4 5 6 7 8 9 10 11 Прежде чем обсуждать, ка к лучше использовать деревья и как выполнять операции с деревьями, мы покажем на при мере , как программа может строить дерево. Предположим, что нужно сформировать дере в о, содержащее узлы типа, опи санного в ( 1.6 ), а значениям узлов будут п чисел, прочи танных из входного файла. Для усложнения задачи потре буем построить дерево с п узлами и минимальной высотой. Чтобы достичь минимальной высоты при данном числе узлов, нужно располагать максимально возможное число уз лов на всех уровнях, кроме самого нижнего. Это можно сде лать оч е н ь просто, если распределять все поступающие узлы Рис. 6 . Идеально сбалансированные деревья. поро в ну слева и справа от каждого узла. В результате по строенное дерево при данном n имеет вид, как показано на рис. 6 для п = 1 …, 7. Правило равномерного распределения при известном числе узлов п лучше всего формулируется с помощью рекурсии: 1. Взять один узел в качестве ко р н я. 2. Построить левое поддерево с nl = n div 2 узлами тем же способом. 3. Построить правое поддерево с п r = п— nl — 1 узлами тем же способом. Это правило описано реку рсивн ой процедурой tree , вхо дящей в програм му 1 .1 , которая читает входной файл и строит идеально сбалансированное дерево. Мы получаем такое опре деление : program bui l dtree ( input , output ); type ref = ^ node ; n о de = record к ey : integer ; left , right : ref end ; Var n : integer ; root: ref; function tree (n: integer); ref; var newnode: ref; x , nl , nr : integer ; begin построение идеально сбалансированного дерева с n узлами if n = 0 then tree:= nil else begin nl := n div 2; nr := n— nl— 1; r e ad(x); new ( newnode); with newnode ^ do begin key := x; left:= tree(nl); right := tree(nr) end ; tree := newnode end end tree ; procedure printree(t:ref; h: integer); var i: integer; begin печать дерева t со сдвигом h if t <> nil then with t ^ do begin printtree(left, h+1); for i:= 1 to h do write(' '); writeln(key); printtree(right, h+l) end end printtree ; begin первое целое число есть число узлов read(n) ; root := tree(n); printtree(root,0) end . Программа 1 .1 . Построение идеально сбалансированного дерева . Дерево идеально сбалансировано, если для каждого его узла количества узлов в левом и правом поддереве раз личаются не более чем на 1. Предположим, например, что и меются следующие входные данные для дерева с 21 узлом: 21 8 9 11 15 19 20 21 7 3 2 15 6 4 13 14 10 12 17 16 18 Тогда программа 1 .1 строит идеально сбалансированное де рево, показанное на рис. 7 . Рис. 7 . Дере в о, построенное с помощью программы 1.1 . Отметим простоту и ясность этой программы, достигнутые благодаря использованию рекурсивных процедур. Очевидно, что рекурсивные алгоритмы особенно уместны, когда про грамма должна обрабатывать данные, структура которых определена рекурсивно. Это вновь отражается в процедуре printtree , которая печатает полученное дерево: пустое дерево не печатается для поддерева уровня L , а вначале печатается его левое поддерево, затем узел, который выделяется предше ствующими L пробелами, и, наконец, печатается его правое поддерево. Преимущество рекурсивного алгоритма особенно наглядно по сравнению с его нерекурсивной формулировкой. Читателю предлагается проявить с вою изобретательность и написать нерекурсивную программу, строящую такие же деревья, прежде чем смотреть на ( 1.8 ). Эта программа приведена без дальнейших комментариев и может служить упражнением для читателя. Ему предлагается выяснить, как и почему она работает. program buildtree ( input , output ); type ref = ^ node; node = record key: integer; left, right: ref end ; Var i,n,nl,nr,x: integer; root,p,q,r,dmy: ref; s: array [1.. 30] of стек record n: integer; rf; ref end ; begin первое целое число есть число узлов read(n); new(root); new(dmy); фиктивный элемент i:= 1; s[1].n := n; s[1].rf : = root; repeat n := s[i].n; r:= s[i] .rf; i:= i— 1; из стека if n = 0 then r ^ .right := nil else begin p := dmy; (1.8) repeat nl:= n div 2; nr:= n— nl— 1; read(x); new q); q ^ .key := x; i :=i+1; s[i].n := nr; s[i].rf:= q; в стек n := nl; p ^ .left := q; p := q until n =0; q ^ .left := nil; r ^ .right := dmy ^ .left end until I = 0; printtree (root ^ .right,0) end . 2. Конструкторская часть. 2.1. Основные операции с бинарными деревьями . Имеется много задач, которые можно выполнять на древо видной структуре; распространенная задача — выполнение заданной операции Р с каждым элементом дерева. Здесь Р рассматривается как параметр более общей задачи посеще ния в сех узлов, или, как это обычно называют, обхода дерева. Если рассматривать эту задачу как единый последова тельный процесс, то отдельные узлы посещаются в некотором определенном порядке и могут считаться расположенными лине йно. В самом деле, описание мног их алгоритмов суще ственно упрощается, если можно говорить о переходе к сле дующему элементу дерева, имея в виду некоторое упоря дочение. Существуют три принципа упорядочения, которые есте ственно вытекают из структуры деревьев. Так же как и саму древовидную структуру, их удобно выразить с помощью ре курсии. Обращаясь к бинарному дереву на рис. 8 , где R обозначает корень, а А и В — левое и правое поддеревья, мы можем определить такие три упорядочения: 1. Сверху вниз: R , А, В (посетить корень до поддеревьев); 2. Слева направо: A, R, В 3. Снизу вверх: А, В, R (посетить корень после подде ревьев) Обходя дерево на рис. 4 и выписывая символы, находя щиеся в узлах, в том порядке, в котором они встречаются, мы получаем следующие последовательности: 1. Сверху вниз: * + a/b c — d * ef 2. Слева на право a + b / c * d — e * f 3. Снизу вверх: abc/ + def * — * Мы узнаем три формы записи выражений: обход сверху вниз дает префиксную запись, обх о д снизу вверх — постфикс ную запись, Рис. 8 . Б инарное дерево. а обход слева направо дает привычную инфикс ную запись, хотя и без скобок, необходимых для определения порядка выполнения операций. Теперь выразим эти три метода обхода как три конкрет ные программы с явным параметром t , означающим дерево, с которым они имеют дело, и неявным параметром Р, озна чающим операцию, которую нужно выполнить с каждым уз лом. Введем следующие определения : type ref = ^ node node = record … ( 2. 1 ) left,right: ref end Эти три метода легко сформулировать в виде рекурсивных процедур; они вновь служат примером того, что действия с рекурсивно определенными структурами данных лучше всего описываются рекурсивными алгоритмами. p rocedure preorder (t : ref); begin if t <> nil then begin P(t); preorder(t ^ .left); ( 2.2 ) preorder(t ^ .right) end end procedure postorder(t: ref); begin if t <> nil then begin posorder(t ^ . left); postorder (t ^ .right); ( 2.3 ) P ( t) en d end procedure inorder(t: ref); begin if t <> nil then begin wordcr ( t ^ . le ft) ; P ( t ); ( 2.4 ) I norder ( t ^ . right ) end end . Отметим , что ссылка t передается как параметр - значение . Это отражает тот факт, что здесь существенна сама ссылка (указание) на рассматриваемое поддерево, а не переменная, значение которой есть эта ссылка и которая могла бы изме нить значение, если бы t передавался как параметр-пере менная. Пример подпрограммы, осуществляющей обход дерева,— это подпрограмма печати дерева с соответствующим сдвигом, выделяющим каждый уровень узлов (см. программу 1 .1 ). Бинарные деревья часто используются для представления множеств данных, элементы которых ищутся по уникальному, толь ко им присущему ключу. Если дерево организовано таким об разом, что для каждого узла t i все ключи в левом подде реве , меньше ключа t i , а ключи в правом поддереве больше клю ча t i , то это дерево называется деревом поиска. В дереве по иска можно найти место каждого ключа, двигаясь начиная от корня и переходя на левое или правое поддерево каждого уз ла в зависимости от значения его ключа. Как мы видели, п элементов можно организовать в бинарное дерево с высотой не более чем log п. Поэтому для поиска среди п элементов может потребоваться не более log n сравнений, если дерево идеально сбалансировано. Очевидно, что дерево — намного более подходящая форма организации такого множества дан ных, чем линейный список, который рассматривался в преды дущем разделе. 30 S Рис. 9 . Дерево поиска с барьером. Так как этот поиск проходит по единственному пути от корня к искомому узлу, его можно запрограммировать с по мощью итерации ( 2.6 ): function loc(x: integer; t : ref): ref; var found: boolean; begin found := false; while ( t <> . nil) Л - found do begin ( 2.6 ) if t ^ .key — x then found := true els e if t ^ .key > x then t := t ^ .left else t := ^ .right end ; loc := t end . Функция loc x , t ) имеет значение nil , если в дереве с кор нем t не найдено ключа со значением х. Так же как в случае по иска по списку, сложность усло в и я окончания цикла за ст авляет искать лучшее решение. При поиске по списку .конце его помещается барьер. Этот прием можно применить в случае поиска по дер еву. Использование ссылок позво л яет связать все терминальные узлы дерева с одним и тем же барьером . Полученная структура — это уже не просто дерево, а скорее, дерево, все листья, которого прицеплены внизу к одному якорю (см. рис. 9 ). Барьер можно также считать общ им представлением всех внешних (специальных) узлов, кот орыми дополняется исходное дерево (см. рис. 3 ). По лу ченная в результате упрощенная процедура поиска описана ниже: function loc(x : integer; t: ref) : ref; begin s ^ .key := x; барьер ( 2.7 ) while t ^ .key <> x do if x < t ^ .key then t : = t ^ .left else t := t ^ . right; loc := t e nd . Отметим, что если в дереве с корнем t не найдено ключа со значением х, то в этом случае loc ( x , t ) принимает значе ние s , т. е. ссылки на барьер. Ссылка на s просто принимает н а себя роль ссылки nil . 2.2. Поиск по дереву с включением . Возможности техники динамического размещения пере м е нных с доступом к ним через ссылки вряд ли полностью проявляются в тех примерах, где по строенная структура данн ых остается неизменной. Более подходящими примерами слу жат задачи, в которых сама структура дерева изменяется, т . е. дерево растет и/или уменьшается во время выполнения программы. Это также .случай, когда другие представления данных, такие, как массив, не подходят и когда дерево с эле ментами, связанными ссылками, как раз и есть подходящая структура. Прежде всего рассмотрим случай постоянно растуще го, н о никогда не убывающего дерева. Хорошим примером этого является задача построения частотного словаря, которая уже разбиралась, когда речь шла о связанных списках. Вернемся к ней снова. В этой задаче задана последовательность слов н нужно установить число появлений каждого слова. Это оз начает, что, начиная с пустого дерева, каждое слово ищется в дереве. Если оно найдено, увеличивается его счетчик появле ний, если нет — в дерево вставляется новое слово (с .началь ным значением счетчика, равным 1). Мы называем э ту задачу поиском по дереву с включением. Предполагаются следующие описания типов : type ref = ^ word', word= record key : integer; ( 2.8 ) count: integer; left, right: ref end Считая, кроме того, что у нас есть исходный файл ключей f , а переменная root указывает на корень дерева поиска, мы можем записать программу следующие образом: reset(f); while -eof(f) do ( 2.9 ) begin read(f,x); search(x,root) end Определение пути поис ка здесь вновь очевидно. Но сели он приводит в «тупик», т. е. к пустому поддереву, обозначен- Рис. 10 . Включение в у порядоченное бинарное дерево. ному ссылочным значением nil , то данное слово нужно вста вить в дер ев о н а мест о пустого под де рева. Рассмотрим, на пример, бинарное дерево, показанное на рис. 10 , и включе ние в него слова " Paul ". Результат показан пунктирными ли ниями на том же рисунке. Целиком работа алгоритма приведена в программе 2. 1 . Процесс поиска представлен в виде рекурсивной про цедуры. Отметим , что е е параметр р передастся как параметр-пере менная, а не как параметр-значение. Это существенно, по скольку в случае включения переменной должно присваи ваться некоторое новое значение ссылке, которая перед этим имела значение nil . Для входной последовательности, состоя щей из 21 числа, которая обрабатывалась с помощью про граммы 1 .1 , построившей дерево на рис. 7 , программа 2. 1 строит бинарное дерево поиска, показанное н а рис. 11 . Рис . 11 . Д е ре во поиска, построенное с пом ощ ью программы 2. 1 . Использование барьера вновь несколько упрощает задачу, что показано в ( 2.10 ). Понятно, что в начале программы пе ременная root должна инициироваться ссылкой на барьер, а не значением nil , и п е р е д каждым поиском очередного слова искомое значение х должно присваиваться нолю ключа в барьере procedure se arch(x: integer; var p: ref); begin if x < p ^ .key then searclt(x,p ^ . left) else if x > p ^ .key t hen search(x,p ^ .right) else it p <> s then p ^ .count : = p ^ .count + 1 else begin включение n e w(p); ( 2.10 ) with p ^ do begin key := x; left := s; right := s; count := 1 en d end end . program treesearch ( input , output ); поиск с включением по двоич ному дереву type ref = ^ word; word = record key: integer; count: integer; left, right: ref; end ; var root: ref; k: integer; procedure printtree(w: ref; l : integer); var i: integer; begin if w <> nil then with w ^ do begin printtree(left, l +1); for i := 1 to i do write(' '); writeln(key); printtree(right, l +1) end end ; procedure search(x: integer; var p: ref); begin if p = nil then begin слова нет в дереве; включить его new (p); with p ^ do begin key := х ; count := 1; left := nil; right := nil end end else if x < p ^ . key then search(x, p ^ .left) else if x > p ^ .key then sear c h(x, p ^ .right) else p ^ .count := p ^ .cou nt + 1 end search ; begin root : = nil; while - eof (input) do begin read(k); sear ch( k, root) end ; printtree ( root ,0) end Программ a 2. 1 . Поиск с включениями. Еще раз, теперь уже последний, построим альтернативную версию этой программы, отказавшись от использования ре курсии. Но сейчас избежать рекурсии не та к просто, как в случае б ез включения, так как для того, чтобы производить включение, нужно помнить пройденный путь по крайней мере на один шаг назад. В программе 2. 1 он запоминается автома тически при использовании параметра-переменной. Чтобы правильно привязать включаемую компоненту, мы должны иметь ссылку на ее предка и знать, включается она в качестве правого или левого поддерева. Для этого вводятся две переменные: р2 и d (для направления): procedure search ( x: integer; root: ref); var p1, p2: ref; d: integer; begin p2 := root; p1 := p2 ^ .right; d := 1; while ( р 1 <> nil) Л (d <> 0) do begin p2 := p1; if x < p1 ^ .key then begin p1 := p1 ^ .left; d := - 1 end else if x > p1 ^ .key then begin p 1 := p 1 ^ .right; d : = 1 end else d := 0 end ; i f d = 0 then p 1 ^ . count : p 1 ^ .co un t + 1 else begin включение new(p 1 ); with p 1 ^ do begin key := x ; left := nil; right : = nil; count : = 1 end ; if d < 0 then p 2 ^ . .left := p 1 else p2 ^ .right := p 1 end end . ( 2.11 ) Как и в случае поиска с включением по списку, используются две с с ылки pi и р2, такие, что в процессе поиска р2 всегда указывает на предикат pl ^ . Чтобы удовлетвори т ь этому усло вию в начале поиска, вводится вспомогательный фиктивный элемент, н а который указывает root . Начало действительного дерева поиска обозначается ссылкой root ^ . right . Поэтому про грамма должна начинаться операторами new ( root ); root ^ . right : = nil вместо начального присваивания root := nil Хотя задача этого алгоритма — поиск, его можно приме нить и для сортировки. В самом деле, он очень напоминает метод сортировки включением, а поскольку вместо массива используется дерево, пропадает необходимость перемещения компонент а выше места включения. Сортировку с помощью дерева можно запрограммировать почти столь же эффек тивно, как и лучшие методы сортировки массивов. Но не о бхо димо принять некоторые меры предосторожности. Разумеется, при появлении одинаковых ключей, теперь надо поступать иначе. Если в случае х = р ' . key алгоритм работает так же, как и в случае х > р ^ . key , то он представляет метод устой чивой сортировки, т. е. элементы с одинаковыми ключами появляются в той же последов ат ельности при обычном обходе дерева, что и в процессе их включения в дерево. Вообще говоря, имеются лучшие способы сортировки, но в задачах, где требуется и поиск, и сортировка, алгоритм поиска по дереву с включением весьма рекомендуется. Он действительно очень часто применяется в трансляторах и про граммах работы с банками данных для организации объектов, которые нужно хранить и искать в памяти. Подходящий при мер — построение таблицы перекрестных ссылок для задан ного текста. Исследуем эту задачу подробно. Наша цель — написать программу, которая (читая текст f и печатая его с добавлением последовательных номеров строк) собирает все слова этого текста, сохраняя при этом номера строк, в которых они встречались. Когда этот про смотр закончится, нужно по с троить таблицу, содержащую все собранные слова в алфави тно м порядке, со списками соответствующих строк. Очевидно, что дерево по иска (называемое также лексико графическим деревом) лучше всего подходит для представ ления слов, встречающихся в т ексте. Теперь каждый узел не только содержит слово в качестве значения ключа, но одно временно представляет собой начало списка номеров строк. Каждую запись номера строки мы будем называть отметкой. Следовательно, в этом примере мы встречаем и деревья, и ли нейные списки. Программа состоит из двух основных частей (см. программу 2. 2 ): фазы чт ен ия текста и построения дерева и фазы печати таблицы. Ясн о что последняя является част ным случаем процедуры обх од а дерева, где посещение каж дого узла предполагает печа т ь, значения ключа слова и про ход по связанному с ним списку номеров строк (отметок). Кроме того, полезно привести еще некоторые пояснения, от носящиеся к программе 2. 2 : 1. Словом считается любая последовательность букв и цифр, начинающаяся с буквы. program crossref ( f , output ); построение таблицы перекрестных ссылок с использованием двоичного дерева const c 1 = 10; длина слова с2 = 8; количество слов в строке с 3 = 6; количество цифр в числе с 4 = 9999; максимальный номер строки type alfa packed array [1 . . c 1 ] of char; wordref = ^ word; itemref = ^ item; word = record k ey: alfa; first, last: itemref; left, right: wordref end ; item = packed record ln o: 0 . . c4; next: itemref end ; var root: wordref; k,kl: integer; n : integer ; номер текущей строки id: alfa; f : text; a: array [ 1 .. c 1] o f char; procedure search (var w l: wordref); var w: wordref; x: itemref; begin w : = wl; if w = nil then begin n ew(w); new(x), with w ^ do begiu key := id; left := nil; right := nil; first := x; last := x end ; x ^ .lno :— n; x ^ .next : = nil; w1 : = w end else if id < it w ^ .key then search(w ^ .left) else if id > w ^ .key then search (w ^ .right) else begin new(x); x ^ .lno: = n; x ^ .next : = nil; w ^ .last ^ .next : = x; w ^ .last := x end end search ; procedure printtree(w: wordref); procedure printword(w:word); var l: integer; x: itemref; begin write (' ', w.key); x := w.first; I := 0; repeat if l = c2 then begin writlen; l := 0; write(' ':cl+l) end ; l:= l+1; write(x ^ .lno: сЗ ); x:= х ^ .next until x = nil; writeln end printword ; begin if w <> nil then begin printtree(w ^ .left); printword(w ^ ); printtree(w ^ .right) end end printtree ; begin root := nil; n:= 0; k1:= cl; page (output); reset(f); while - eof(f) do begin if n = c4 then n:= 0; n := n + l ; write ( n :сЗ); следующая строка write (' '); while — e oln( f ) do begin просмотр непустой строки if f ^ in ['a' .. ' z '] then begin k := 0; repeat if k < cl then begin k : = k +1; a[k] := f ^ ; end ; write(f ^ ); get(f) until - ( f ^ in ['a'.. 'z' ,'0 '. .'9 ']); if k
© Рефератбанк, 2002 - 2017