В.Г. Абрамов, Н.П. Трифонов, Г.Н. Трифонова - Введение в язык Паскаль (1107618), страница 65
Текст из файла (страница 65)
Цепочка с упорядоченными записямиДля устранения второго из отмеченных выше недостатков представлениятаблицы в виде простой цепочки можно поддерживать в списке определенный порядок следования записей, например, по возрастанию их ключей.При этом, правда, усложнится процедура включения новой записи в таблицу, поскольку предварительно придется найти то звено списка, после которого следует вставить звено с новой записью - так, чтобы после этойвставки все записи следовали в списке по возрастанию их ключей.Очевидно, что в этом случае поиск записи требует в среднем просмотраN/2 записей, независимо от того, имеется эта запись в таблице или нет.Действительно, если записи с заданным ключом в таблице нет, то поискможно прекратить, к а к только при последовательном переборе звеньевсписка встретится запись с ключом, больше заданного (вследствие упорядоченности записей по возрастанию их ключей искомая запись не можетбыть в списке дальше этого звена).Конечно, поддержание упорядоченности записей в списке требует определенных затрат — это выражается в том, что включение новой записи в таблицу становится более длительной операцией.
Однако эти затраты оправдаются, если включение записей производится сравнительно редко, а поискотсутствующих записей является достаточно типичным случаем.14.3.3. Дихотомический (бинарный) поиск в таблицеОсновное неудобство представления таблицы в виде списка состоит в том,что для поиска требуемой записи (или места для вставки в список включаемой новой записи) приходится последовательно перебирать все предшествующие звенья списка.Для ускорения процедуры поиска можно использовать следующийприем. Прежде всего заметим, что тексты записей можно хранить отдельноот ключей, а при ключе хранить только ссылку на текст записи. В этом случае представление таблицы схематически можно изобразить следующимобразом (через к, обозначим ключ i-й записи) :Как видно, все элементы списка в этом случае одинаковы (т.е. имеют одини тот же тип значений) — даже в том случае, если тексты записей имеютразную длину и структуру. Каждый такой элемент является записью,содержащей два поля: в одном из них содержится ключ записи, а в другом — ссылка на текст записи.
Но поскольку в паскале разрешено объединять в массивы любые однотипные значения, то такие элементы можно286объединить не в список, а в одномерный массив (вектор). Этот массивможно ввести в употребление с помощью следующих описаний (для определенности в качестве ключей будем использовать целые числа):type инд1. . N;текст = {тип текста записи)связь =+текст;запись = recordключ:integer;ссылка! связьend;вект = array Синд] of запись;var х: вект;Будем исходить из того, что компоненты массива упорядочены по возрастанию содержащихся в них ключей,Теперь у нас появилась возможность получать непосредственный доступк любому ключу по индексу i той компоненты массива х, в которой содержится этот ключ, а именно — этот ключ является значением переменнойx[i] .ключ.Это обстоятельство, наряду с упорядоченностью компонент массива повозрастанию содержащихся в них ключей, позволяет применить эффективный способ поиска записи по заданному ключу, который называется дихотомическим поиском (или просто дихотомией).Идея этого способа состоит в том, что задача поиска записи с заданнымключом сводится к задаче нахождения элемента массива х, в котором содержится этот ключ: если определен индекс этого элемента, то искомаязапись является значением переменной x[i] .ссылка!,При поиске компоненты вектора, содержащей заданный ключ к,сначалазоной поиска, естественно, является весь вектор х, поскольку ключ к может оказаться в любой компоненте.
Возьмем серединную компонентус индексом i = N/2 (если N/2 нецелое, то округляем его, например, в меньшую сторону). Если к = х[1].ключ, то поиск закончен и искомой записьюявляется значение переменной x[i] .ссылка!. Если кФ x[i] ключ, то процесспоиска продолжается. Ясно, однако, что при к < х [ 1 | . к л ю ч требуемуюкомпоненту надо искать в левой половине вектора, а в противном случаев правой его половине.
Таким образом, на следующем шаге зона поискастановится вдвое меньше.Применительно к этой новой зоне поиска используем тот же прием:в ней возьмем серединную компоненту, сравним содержащийся в нейключ с заданным ключом; и если они не равны, то для дальнейшего поискавыберем соответствующую половину этой зоны и т,д.Этот процесс завершается в двух случаях: либо на очередном шаге окажется, что серединная компонента текущей зоны поиска содержит заданныйключ (требуемая запись найдена), либо зона поиска оказалась пустой(записи с этим ключом в таблице нет).287Поскольку на каждом шаге дихотомии зона поиска уменьшалась в двараза, то в любом случае для завершения поиска потребуется сделать не более I + log2 N шагов.
Если вспомнить, что при представлении таблицы в видесписка для поиска надо сделать в среднем N/2 шагов, то видно, что эффектдихотомии быстро возрастает с ростом значения N, т.е. объема таблицы.Для реализации операции поиска введем в употребление логическуюфункцию ДХТМ, которая в качестве побочного эффекта будет присваиватьзаданной переменной значение, равное индексу компоненты, содержащейзаданный ключ.
При неуспешном поиске это значение можно считать неопределенным или равным, например, нулю — мы остановимся на второмиз этих вариантов. Описание такой функции может иметь следующий вид(с учетом ранее введенных в употребление типов):function ДХТМ < Склгач:} k: integer;{индекс ключа:} var п:var лгр,пгр:инд): boolean;integer;b: boolean: i: инд;beginлгр:=1; nrp:=N; b:=fal5e; n:=0;repeati:=trunc((лгр+пгр)/2+0.1);if k=y,[i 1.КЛК1Ч thenbegin b:=true;n:=i endel seifuntil b ork<xСi3.ключ then nrp:=i-l else лгр:=1+1(лгр)пгр)JДХТМ:=Ьend;14.3.4. Двоичное деревоРассмотренный выше способ представления таблицы обеспечивает достаточно быстрый поиск, однако он плохо приспособлен для реализации включения и исключения записей, поскольку - для поддержания упорядоченности компонент вектора — при этом приходится сдвигать все последующиекомпоненты в ту или другую сторону.
Так что этот способ разумно использовать в том случае, когда таблица изменяется сравнительно редко, а чащевсего осуществляется поиск в ней.Сейчас мы рассмотрим представление таблицы в виде двоичного дерева,которое позволяет одинаково эффективно реализовать все три операциинад таблицей, причем эта эффективность близка к эффективности дихотомического поиска.Двоичное дерево схематично можно определить следующим образом:имеется набор вершин, соединенных стрелками.
Из каждой вершины выходит не более двух стрелок (ветвей), направленных влево-вниз или вправо-вниз. Должна существовать единственная вершина, в которую не входитни одна стрелка - эта вершина называется корнем дерева. В каждую из288оставшихся вершин входит в точности одна стрелка:ЛЛ*/ \При представлении таблицы в виде двоичного дерева будем по-прежнемусчитать, что тексты записей хранятся отдельно. Тогда каждое звено (вершина дерева), соответствующее элементу таблицы, будет записью, содержащейчетыре поля.
Значением этих полей будут соответственно ключ записи,ссылки на вершину влево-вниз, на вершину вправо-вниз и на текст записи.Чтобы понять, как осуществляются основные операции над таблицейв этом случае, рассмотрим принцип построения дерева при занесении записей в таблицу. Пусть в первоначально пустую таблицу заносятся последовательно поступающие записи с ключами 70, 60, 85, 87, 90, 45, 30, 88, 35,20, 86.Первую из поступивших записей с ключом к] = 70 делаем корнем дерева.Поскольку это пока единственный элемент дерева, ссылки на соседниевершины положим равными nil (ссылку на текст записи изображать не будем, поскольку она сейчас роли не играет):70*Если ключ следующей записи к 2 окажется меньше ключа к ) , то этой записипоставим в соответствие левую вершину, в противном случае — правую.В нашем случае к 2 = 6 0 < к, =70, поэтому очередную формируемую вершину дерева делаем левой для корня:70*60*•кЗатем поступает запись с ключом к 3 = 85.
Поскольку этот ключ больше19. В. Г. Абрамов289ключа в корне, то новую формируемую вершину делаем правой для корня:708560(далее на схеме будем указывать только ключ при вершине и стрелки, которые характеризуют взаимное расположение вершин).У четвертой из поступающих записей ключ к 4 = 87. Так как этот ключбольше ключа к ( в корне дерева, то новая вершина должна размещатьсяна правой ветви дерева. Чтобы определить ее место, спускаемся по правойстрелке к очередной вершине (с ключом 85), и если поступивший ключбольше 85, то новую вершину делаем правой по отношению к этой вершине:6087Теперь принцип построения дерева достаточно ясен: если поступает очередная запись с ключом к, то — начиная с корня дерева — в зависимости отсравнения ключа к с ключом в очередной вершине идем влево или вправоот нее, до тех пор, пока не найдем подходящую вершину, к которой можноприсоединить новую вершину с ключом к.
В зависимости от результатасравнения ключа в этой вершине с поступившим ключом к делаем вновьсформированную вершину левой или правой для найденной вершины:70604520Xч35X85/ч82/8687.ч90/88Теперь рассмотрим вопрос о том, как ввести в употребление нужноенам для представления таблицы двоичное дерево.
Прежде всего обратимвнимание на следующее важное обстоятельство. Как видно, каждый элемент дерева является записью, состоящей из четырех полей, в которыхсодержатся: ключ записи, ссылка на текст записи и ссылки на левую и правую ветви. Однако в паскале каждая конкретная ссылка должна иметьопределенный тип, который зависит от типа объекта, для доступа к которому используется эта ссылка. В нашем случае каждая вершина деревабудет представляться записью из четырех полей, в трех из которых нахо290дятся ссылки.
При этом ссылка на текст записи будет иметь тип, отличный от типа ссылок на вершины дерева. С учетом этих замечаний двоичноедерево можно ввести в употребление с помощью следующих описаний:typeтекст-{тип знамения,представляющего текст запиои)укт=*текст;укзв=*звено;звено=гесог11 Ключ:integer;Лев,Прав: укзв;Ссылка: уктend;var двдер: укзв;Поиск записи в дереве. Дадим описание логической функции, осуществляющей поиск вершины дерева с заданным ключом. В качестве побочного эффекта она определяет ссылку на найденную вершину (если поискбыл успешным). В этом описании формальный параметр к представляетзаданный ключ, d — дерево, в котором ведется поиск, и Рез — переменная,которой присваивается ссылка на найденное звено:function ПОИСКВДЕР({ключ:} k:integer; var {в дереве} d,{результат:} Рез: укзв): boolean;var р: укзв;b: boolean;beginb:=false;p:=d;if d*nil thenrepeatif р+.Ключ=к then b:=trueel seif к<р+.Ключ then р:=р+.Лев else р=р+.Правuntil b or<p=nil>;ПОИСКВДЕР: =b-; Рез: =pendЗаметим, что когда в процессе анализа ключа в просматриваемой вершинемы перешли к левой или правой вершине, то тем самым мы выбрали длядальнейшего исследования левое или правое поддерево.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
