Новиков Ф.А. Дискретная математика для программистов (860615), страница 59
Текст из файла (страница 59)
Толковый словарь или энциклопедия: записью является словарная статья,а ключом — заголовок словарной статьи (обычно его выделяют жирным шрифтом).2. Адресная книга: ключом является имя абонента, а записью — адресная информация (телефоп(ы), почтовый адрес и т.
д.).3. Банковские счета: ключом является номер счета, а записью — финансоваяинформация (которая может быть очень сложной).Таким образом, ассоциативная память должна поддерживать по меньшей меретри основные операции:1) добавить (ключ, запись);2) пайти (ключ, запись);3) удалить (ключ).Эффективность каждой операции зависит от структуры данных, используемойдля представления ассоциативной памяти. Эффективность ассоциативной памяти в целом зависит от соотношения частоты выполнения различных операцийв данной конкретной программе.ЗАМЕЧАНИЕТаким образом, невозможно указать способ организации ассоциативной памяти, которыйоказался бы наилучшим во всех возможных случаях.9.4.2. Способы реализации ассоциативной памятиДля представления ассоциативной памяти используются следующие основныеструктуры данных:1) неупорядоченный массив;2) упорядоченный массив;9.4.
Деревья сортировки3153) дерево сортировки — бинарное дерево, каждый узел которого содержит ключ(и указатель па запись) и обладает следующим свойством: значения ключаво всех узлах левого поддерева меньше, а во всех узлах правого поддерева —больше, чем значение ключа в узле;4) таблица расстановки (или хэш-таблица).При использовании неупорядоченного массива алгоритмы реализации операцийассоциативной памяти очевидны:1. Операция «добавить (ключ, запись)» реализуется добавлением записи в конецмассива.2. Операция «найти (ключ, запись)» реализуется проверкой в цикле всех записейв массиве.3. Операция «удалить (ключ)» реализуется поиском удаляемой записи, а затемперемещением последней записи на место удаляемой.Для упорядоченного массива имеется эффективный алгоритм поиска, описанныйв следующем подразделе.
Реализация остальных операций очевидна. Основноевнимание в этом разделе уделено алгоритмам выполнения операций с деревомсортировки.ОТСТУПЛЕНИЕТаблицы расстановки являются чрезвычайно важным практическим приёмом программирования, подробное описание которого не включено в учебник из экономии места.Вкратце основная идея заключается в следующем. Подбирается специальная функция,которая называется хэш-функцией, переводящая значение ключа в адрес хранения записи(адресом может быть индекс в массиве, помер кластера па диске и т. д.). Таким образом,по значению ключа с помощью хэш-функции сразу определяется место хранения записии открывается доступ к ней.
Хэш-функция подбирается таким образом, чтобы разнымключам соответствовали, по возможности, разные адреса из диапазона возможных адресов записей. Как правило, мощность множества ключей существенно больше размерапространства адресов, которое, в свою очередь, больше количества одновременно хранимых записей.
Поэтому при использовании хэширования возможны коллизии — ситуации,когда хэш-функция сопоставляет один и тот же адрес двум актуальным записям с различными ключами. Различные методы хэширования отличаются друг от друга способамиразрешения коллизий и приёмами вычисления хэш-функций.9.4.3. Алгоритм бинарного (двоичного) поискаПри использовании упорядоченного массива для представления ассоциативнойпамяти операция поиска записи по ключу может быть выполнена за время0(log2n) (где п — количество записей) с помощью следующего алгоритма, известного как алгоритм бинарного (или двоичного) поиска.316Глава 9.
ДеревьяАлгоритм 9.7 Бинарный поискВход: упорядоченный массив A: array [l..n] of record к: key,г: info endrecord; ключ a : key.Выход: индекс записи с искомым ключом а в массиве А или 0, если записи стаким ключом нет.b: = 1 { начальный индекс части массива для поиска }е: = п { конечный индекс части массива для поиска }while Ъ ^ в doс: =(Ь + е)/2 { индекс проверяемого элемента (округленный до целого) }if А[с].к > a thenе: = с - 1 { продолжаем поиск в первой половине }else if А [с], к < a thenb: = с + 1 { продолжаем поиск во второй половине }elsereturn с { нашли искомый ключ }end ifend whilereturn 0 { искомого ключа нет в массиве }ОБОСНОВАНИЕДостаточно заметить, что на каждом шаге основного цикла искомым элемент массива (если он есть) находится между (включительно) элементами с индексами b и е.
Поскольку диапазон поиска на каждом шаге уменьшаетсявдвое, общая трудоёмкость не превосходит log2 п.•9.4.4. Алгоритм поиска в дереве сортировкиСледующий алгоритм находит в дереве сортировки узел с указанным ключом,если он там есть.Алгоритм 9.8 Поиск узла в дереве сортировкиВход: дерево сортировки Т, заданное указателем на корень; ключ а : key.Выход: указатель р на найденный узел или nil, если в дереве нет такого ключа.р: = Т { указатель на проверяемый узел }while р ф nil doif а < p.i thenp\=p.l { продолжаем поиск слева }else if а > p.i thenр: = p . r { продолжаем поиск справа }elsereturn р { нашли узел }end ifend whilereturn nil { искомого ключа нет в дереве }9.4. Деревья сортировки317ОБОСНОВАНИЕ ЭТОТ алгоритм работает в точном соответствии с определениемдерева сортировки: если текущий узел не искомый, то в зависимости от того,меньше или больше искомый ключ по сравнению с текущим, нужно продолжатьпоиск слева или справа соответственно.•9.4.5.
Алгоритм вставки в дерево сортировкиСледующий алгоритм вставляет в дерево сортировки узел с указанным ключом. Если узел с указанным ключом уже есть в дереве, то ничего не делается.Вспомогательная функция NewNode описана в подразделе 9.4.7.Алгоритм 9.9 Вставка узла в дерево сортировкиВход: дерево сортировки Т, заданное указателем па корень; ключ а : key.Выход: модифицированное дерево сортировки Т.if Т = nil thenТ : = NewNode(a) { первый узел в дереве }return Тend ifр : = Т { указатель на текущий узел }while true doif a = p.i thenreturn T { в дереве уже есть такой ключ }end ifif a < p.i thenif p.I = nil thenp.i: = NewNode(a) { создаём новый узел }return T { и подцепляем его к р слева }elsep:=p.l { продолжаем поиск места для вставки слева }end ifelseif a > p.i thenif p.r — nil thenp.r: = NewNode(a) { создаём новый узел }return T { и подцепляем его к р справа }elseр : =р.г { продолжаем поиск места для вставки справа }end ifend ifend ifend while318Глава 9.
ДеревьяОБОСНОВАНИЕ Алгоритм вставки, в сущности, аналогичен алгоритму поиска: вдереве ищется такой узел, имеющий свободную связь для подцепления новогоузла, чтобы не нарушалось условие дерева сортировки. А именно, если новыйключ меньше текущего, то либо его можно подцепить слева (если левая связьсвободна), либо нужно найти слева подходящее место. Аналогично, если новыйключ больше текущего.•ОТСТУПЛЕНИЕВ последнее время в среде профессиональных программистов наблюдается противоестественное и достойное сожаления явление — обфускация программ, то есть искусственноесоставление текстов программ таким образом, чтобы сделать их как можно более непонятными для читателя.
Обычно обфускация обосновывается необходимостью защитыинтеллектуальной собственности, хотя на самом деле, по мнению автора, часто являетсяпроявлением комплекса неполноценности, развивающегося на фоне недостаточного уровня профессиональной подготовки. Для иллюстрации последнего тезиса приведём примертого, как не надо писать программы, проведя обфускацию алгоритма 9.9.Вход: дерево сортировки, заданное указателем на корень Т : fN, где N = record i : key,I : array [0..1] of f N end record; ключ a : key.Выход: модифицированное дерево сортировки Т.if Т = nil thenТ : = NewNode(a)return Tend ifp:=Twhile true doif a = p.i thenreturn Tend ifb\ = a > p.iif p.i[6] = nil thenp.i [6]: = N e w N o d e ( a )return Telsep:=p.l[b]end ifend whileЭта программа примерно вдвое короче, чуть медленнее (доступ к элементу массива обычно медленнее доступа к полю структуры), использует неявное приведение false к-• О,true > 1, и её трудно понять без дополнительных пояснений.9.4.6.
Алгоритм удаления из дерева сортировкиСледующий алгоритм удаляет из дерева сортировки узел с указанным ключом.Если узла с указанным ключом нет в дереве, то ничего не делается. Вспомогательные процедуры Find и Delete описаны в следующем подразделе.9.4. Деревья сортировки319Алгоритм 9.10 Удаление узла из дерева сортировкиВход: дерево сортировки Т, заданное указателем на корень; ключ а : key.Выход: модифицированное дерево сортировки Т.Find(T,a,p,q, s) { поиск удаляемого узла }if р = nil thenreturn Т { нет такого узла — иичего делать не нужно }end ifif p.r = nil thenDelete(p,q,p.l,s) { случай 1, рис. 9.12, слева }elseи: =р.гif и.I = nil thenu.l: =p.lDelete(p, q, u, s) { случай 2, рис. 9.12, в центре }elsew: =u;v: = u.lwhile v.l Ф nil dow\ = v\v. = v.lend whilep.i: = v.iDelete(v,w,v.r, - 1 ) { случай 3, рис. 9.12, справа }end ifend ifreturn TОБОСНОВАНИЕУдаление узла производится перестройкой дерева сортировки.
Приэтом возможны три случая (не считая тривиального случая, когда удаляемогоузла нет в дереве и ничего делать не нужно).320Глава 9. Деревья[ 1 ] Правая связь удаляемого узла р пуста (см. рис. 9.12, слева). В этом случаелевое поддерево 1 узла р подцепляется к родительскому узлу q с той же стороны, с которой был подцеплен узел р. Условие дерева сортировки, очевидно,выполняется.[ 2 ] Правая связь удаляемого узла р пе пуста и ведёт в узел и, левая связькоторого пуста (см. рис. 9.12, в центре). В этом случае левое поддерево 1 узла рподцепляется к узлу и слева, а сам узел и подцепляется к родительскому узлуq с той же стороны, с которой был подцеплен узел р.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
