3345

нового, за исключением усложнения обработки.

в) направленный граф

Рис. 3.14. Связанное представление деревьев, списковых структур и графов

151

следующим свойством: значение каждой вершины этого дерева больше, чем значение вершин его левого поддерева и меньше, чем значение любой из вершин правого поддерева. Сравнение проходит по числам, являющимся кардинальными числами множеств потомков (дочерей) рассматриваемой вершины.

Двоичное дерево выражения используется при представлении семантики математических выражений в трансляторах программ. Оно справедливо только для представления таких операций, которые содержат в точности два операнда. При этом каждый лист содержит простой операнд, а каждая вершина – операцию. Кроме того, левое или правое поддерево вершины, содержащей операцию, представляет собой левое или соответственно правое подвыражение, которое должно быть вычислено перед выполнением операции, соответствующей корню поддерева. Например, выражению 7+(6*4) соответствует дерево

Более подробно с формализмом деревьев мы познакомимся в лекции по алгоритмам.

3.6. Множества

Рассмотренные до сих пор структуры состояли из упорядоченных наборов элементов, при этом мы варьировали числом элементов и смесями их типов. Теперь определим структуру, которая состоит из неупорядоченного набора различающихся элементов , и называется множеством (тип данных SET), имеющим в математике

154

фундаментальное значение. (Пояснить сущность и роль множеств, как основания математики).

Не существует формального определения множества; считается, что это понятие первичное и не определяется. Интуитивно говорят, что множество есть объединение различных элементов.

Конечное множество S записывают в следующем виде:

S = {s1, s2, …, sn}, si S.

В этом случае говорят, что множество задано перечислением элементов. Мощность множества есть его кардинальное число, обозначаемое как S =card S = n. Кроме того, множество задается свойством S = {х | S(x)}, но его использование «подвластно» только интеллектуальным моделям, практически не освоенным в программировании.

Последовательное и связанное представление можно использовать и для множества, заданного перечислением элементов (далее рассматривается только такое множество). Индуцируя искусственный порядок элементов множества или используя собственный порядок, если он существует, мы можем рассматривать множество как последовательность. Если в множестве нет естественного порядка, используется метод хеширования, рассматриваемый ниже.

Основными операциями над множествами, как структурами данных, являются:

1. Проверка принадлежности элемента к множеству (то есть х

S).

2. Добавление элемента х к множеству S (если х S). 3. Исключение элемента х из множества S.

Такие операции в массовом порядке осуществляются в ин- формационно-справочных системах, которые осуществляют накапливание сведений, прием новых сведений и выдачу сведений по запросам. Типичной формой представления совокупности (множества) разнородных записей является таблица или файл. Группа файлов называется базой данных.

При этом каждый элемент множества имеет свое имя и поэтому мы имеем дело с множеством именованных объектов (на-

155

пример, фамилий, слов в словаре и т.п.). При этом будем помнить, что имя, слово – это цепочка литер, в которой каждой литере ставится в соответствие цепочка битов, которую можно дробить по частям, устанавливая закономерности в их составе. Так как никаких связей между именами, как элементами множества, не существует, то операции поиска в таких множествах можно осуществить только путем анализа (использования) свойств имени. При этом методы, основанные на сравнении всего имени или полного слова нас, из-за стремления к быстроте выполнения операций, не интересуют. Мы будем рассматривать метод быстрого поиска на основе анализа (сравнения) части имени элемента.

Если множество является упорядоченным, что чаще всего подразумевается в ЯзПр, то оно является ограниченной формой списка. Мы рассмотрим неупорядоченные множества, в которых доступ по индексу или по относительной позиции не имеет смысла. Для них возможны два специальных представления в структуре памяти.

Структура памяти. Множество может быть представлено в виде линейного массива переменного размера с использованием методов представления в памяти, рассмотренных для стеков, очередей или связанных списков. Однако при таком представлении выполнение операций включения, исключения и проверки принадлежности должно сопровождаться просмотром памяти в поисках нужного элемента. Желательно найти представление, которое позволяет выполнять основные операции без поиска. Такое представление опирается на метод, известный под названием РАССЕЯННАЯ ПАМЯТЬ или ХЕШИРОВАНИЕ (например, расстановка закладок в словаре, осуществляющая дробление всего множества слов на нужные порции, что облегчает поиск нужного слова уменьшением зоны поиска).

Для множества резервируется в памяти блок, называемый ХЕШ-ТАБЛИЦЕЙ, примерно так же, как это делалось для стека и очереди. Однако в ней элементы множества располагаются не в последовательных ячейках, а случайным образом рассеиваются по всему блоку. Хитрость состоит в том, что каждый новый элемент помещается в блок таким образом, что его присутствие или отсут-

156

ствие может быть установлено позднее БЕЗ ПОИСКА по блоку. Это делается так.

Предположим, что необходимо добавить новый элемент х, представленной битовой цепочкой Вх, к множеству имен S, представленному блоком памяти MS. Позиция, которую должна занимать цепочка Вх в блоке памяти MS определяется применением к битовой цепочке Вх ХЕШ-ФУНКЦИИ. (Английский глагол ―to hash‖ имеет смысл нарезать, раскрошить или сделать из этого смесь, является грубым словом: идеи метода созданы в 1953 – 1957 гг. (Г.Лак из IBM и А.П. Ершов, СО АН СССР), а жаргонное название впервые появилось в печати в 1967г.). Ее смысл состоит в том, чтобы взять некоторую характеристику ключа (―обломок‖ битовой цепочки Вх) и использовать полученную (―усеченную‖ от полной) информацию в качестве основы поиска. То есть вычисляется хеш-функция h(Вх) и берется в качестве адреса начала поиска.

Один из простейших примеров применения хеш-функции следующий. Вычисление адреса осуществляется применительно к таблице после ее составления (случай «до составления» - принципиально сложнее). Пусть рассматривается размещение пяти слов (имен) AN, AT, NO, ON и PJ в памяти М0, М1, …, М6. При этом каждая буква представлена 5-ти разрядным кодом: А – 00000, В – 00001, С – 00010 и т.д. Тогда пять слов имеют такое представление:

157

Видим, что двоичная цепочка b6 b5 b4 , найденная хитроумно, однозначно определяет каждое из этих пяти слов и что значения этих двоичных цепочек, рассматриваемых как двоичные целые числа, лежит в пространстве адресов А={0,1,2,3,4,5,6}. Эту цепочку можно принять за хеш-функцию h(Bk)=(b6 b5 b4), которая однозначно отобразит множество из пяти имен S в память, обеспечивая естественный алфавитный порядок. Выгода при этом состоит в том, что адресация по 3х-значной двоичной хеш-функции короче каждого десятиразрядного слова. Но это относится только к заданной таблице, обычно же хеш-функция строится до составления таблицы.

Относительно полного сравнения хеш-адресация будет грубой и величина ―грубости‖ будет тем больше, чем меньшая часть битовой цепочки Вх относительно полной берется в качестве адреса. Это соответствует тому, что для различных ключей ki kj получится h(ki)=h(kj), то есть совпадение различных элементов. Такая ситуация называется коллизией. Методы разрешения коллизий рассмотрим в лекции об алгоритмах, а сейчас остановимся на самом простом. Его суть состоит в том, что по хеш-адресу исследуется соответствующая ячейка памяти MS. Если х уже принадлежит множеству S, он должен продолжать храниться в этой позиции. Если исследуемая позиция пуста, то битовая цепочка Вх помещается в нее. Любая последующая попытка проверить, не принадлежит ли х множеству S, вызовет хеширование новой битовой цепочки, получения хеш-адреса Ik, доступ по нему к соответствующей ячейке MS и нахождение там того-то и того-то. То есть делается расстановка элементов как бы ―на авось‖ и при обеспечении упорядочивания (расстановки) дальнейшего поиска по таблице не проводится.

Для пояснения рассмотрим следующий пример. Пусть имеется пространство имен S всех двоичных цепочек фиксированной длины 8. Предположим, что известен максимальный размер таблицы – шесть имен. Далее, мы выбрали память из восьми ячеек М0, М1, …, М7, (пространство адресов А – восемь единиц). В качестве хеш-функции мы выбрали такую, что из 8-ми разрядной двоичной

158

цепочки каждого имени берутся три самых правых разряда, интерпретируемых как двоичное целое. Запишем:

х1=00010110 h(x1)=(110)2=6 – равно max размеру x2=00100100 h(x2)=(100)2=4

x3=00111010 h(x3)=(010)2=2 x4=10101100 h(x4)=(100)2=4 x5=11110000 h(x5)=(000)2=0

Видим, что принятая хеш-функция отображает х2 и х4 в один адрес – 4й, то есть мы получили коллизию.

Для ее разрешения одно из этих двух имен должно храниться в другом месте (в памяти из восьми ячеек есть еще место – два относительно max и три относительно реального). Поэтому мы помещаем х4 в незанятую ячейку, скажем М5, как первую свободную ячейку, следующую за его собственным адресом h(x4)=4. При этом пустые ячейки таблицы отличаются от занятых, например приписыванием дополнительного разряда.

Даже наилучшая хеш-функция (как грубое приближение к полному сравнению) не может дать полной гарантии того, что различные элементы данных при хешировании дадут разные хешадреса. Общее желание состоит в том, чтобы хеш-функция распределяла генерируемые ею хеш-адреса по блоку памяти как можно равномернее.

Хеширование используется при обработке множеств данных большой мощности. Если множество элементов маломощно, то используется метод характеристической функции множества, с которой оперируют по правилам логического умножения и логического сложения. Этот вопрос более подробно рассматривается в п.3.11.

3.7. Абстрактный тип данных

Рассмотренное выше разнообразие типов данных определялось разнообразием их структурных характеристик, определяющих закономерности построения сложных типов данных из множества

159

более простых (элементарных). Однако содержание любой целеустремленной системы (ситуации), разрешаемой субъектом, в том числе и с использованием компьютера, определяется не только структурой, но и функцией, являющейся принципиально отличной от структуры (почти ортогональной) категорией. Поэтому возникает естественное желание попытаться создать дополнительное разнообразие типов данных исходя из функциональных соображений. Такой подход приводит к концепции абстрактных типов данных, являющихся в настоящее время одной из передовых компьютерных технологий.

Его использование является возможным потому, что понятие «тип данных» включает (точнее подразумевает) не только совокупность их значений, но и набор основных операций, определенных для этих значений. Грубо говоря, это означает, что в программе, написанной на языке с сильной типизацией (например, Паскаль), каждый объект имеет тип, определяющий допустимые значения этого объекта и набор операций, применимых к этому объекту. Типы бывают встроенными (в ЯзПр) и определяемыми программистом. При этом транслятор с такого языка гарантирует невозможность присваивания объектам недопустимых значений и применения к объектам недопустимых операций за счет некоторой совокупности проверок, осуществляемых как на этапе трансляции, так и на этапе выполнения. Так, параметры, передаваемые в процедуры и функции, подвергаются контролю на соответствие типов. То есть типы данных играют ключевую роль в автоматизации диагностики ошибок и обеспечивают существенное улучшение «удобочитаемости» программ. Однако, строгая типизация, как любая совокупность правил, требующих выполнения, накладывает ограничения на «вольность» программирования. Абстрактность типов данных это обстоятельство несколько смягчает.

Абстрактность заключается в том, что если задан полный набор операций, необходимых для получения всех значений данных, то программисту совершенно не обязательно знать как эти значения получаются. Ибо они всегда получатся. Его задача состоит только в установлении всех необходимых путей (связей) в про-

160