ЭЛЕМЕНТЫ ДИНАМИЧЕСКИХ МНОЖЕСТВ

1. ЭЛЕМЕНТЫ ДИНАМИЧЕСКИХ МНОЖЕСТВ

Элемент динамического множества описывается записью, содержащей различные поля. Поскольку элементы множества должны быть различными, значения полей записи позволяет однозначно идентифицировать соответствующий элемент множества. В большинстве случаев для идентификации достаточны значения одного или нескольких полей записи. Минимальный набор полей, по которым производится идентификация элементов множества, называется первичным ключом (или просто ключом). В дальнейшем, для простоты будем считать, что ключ состоит из одного поля[1]. Между множеством элементов и множеством значений их ключей существует взаимнооднозначное соответствие. Т.е. каждому элементу множества соответствует в точности одно значение ключа, а каждому значению ключа соответствует в точности один элемент. Например, пусть элементами динамического множества являются студенты. Соответствующие записи содержат поля: «номер зачетной книжки», «фамилия», «пол», «дата рождения» и «номер группы». Ключевым здесь является поле «номер зачетной книжки». У каждого студента в один момент времени может быть только одна зачетка, и одна зачетная книжка может принадлежать только одному студенту.

Понятие ключа важно, поскольку большинство операций над динамическим множеством осуществляется посредством ключа.

Помимо полей, описывающих элементы множества, запись содержит служебные поля, необходимые для организации структур данных. Как правило, структуры данных для динамических множеств состоят из записей, являющихся динамическими переменными. Доступ к этим записям осуществляется через указатели, и в служебных полях записи хранятся указатели на «соседние» элементы структуры данных. Благодаря этому обеспечивается связность структуры данных и доступ к одним элементам посредством других. Последнее очень полезно, поскольку для доступа ко всем элементам структуры данных достаточно, как правило, знать адрес (значение указателя) только одного из них.

Скачано с www.znanio.ru