1. Вектор

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

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

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

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

Рис. 2. Структура вектора.

Дескриптор вектора содержит: адрес A_m начала вектора, тип элементов структуры данных или их длину L, число элементов или их начальный m и конечный n индексы. Адрес A_i элемента E_i с индексом i определяется выражением A_i = A_m + (i - m) * L.

В большинстве случаев отображение структур данных в структуры хранения в виде вектора можно выполнить, используя такой тип данных, как «массив». При этом транслятор создаёт как дескриптор вектора, так и сам вектор, а обращение к элементам вектора сводится к обращению к элементам массива. Однако транслятор создаёт статический массив с фиксированными размерами, что может явиться ограничивающим фактором его применения.

В прикладной программе можно организовать хранение данных в динамическом векторе. Для этого нужно выполнить ряд операций: 1) определить структуру дескриптора; 2) получить динамическую память под дескриптор и заполнить дескриптор управляющей информацией; 3) используя данные из дескриптора, определить размер памяти для вектора и получить динамическую память; 4) при необходимости инициализировать элементы структуры данных в векторе. Адреса элементов к ним вычисляются с использованием управляющей информации из дескриптора. В программе доступ к структуре данных, хранимой в виде вектора, осуществляется посредством указателя на дескриптор (рис. 3).

Рис. 3. Доступ к вектору через дескриптор.

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

2. Список

Список является более сложной структурой хранения, в которой элементы имеют явные связи. В списке элементы структур данных размещаются не обязательно в смежных областях памяти. Каждый элемент структуры данных содержит, по крайней мере, два поля. Одно поле – основное содержит данные этого элемента или указатель на данные, а другое поле предназначено для размещения указателя на следующий элемент. Оконечный элемент структуры данных в поле указателя содержит признак конца списка (NULL – в Си, в Паскале - Nil). Элемент структуры данных, в свою очередь, тоже может быть структурой, хранимой в виде списка. Различают списки однонаправленные, двунаправленные и циклические. Число элементов списка может изменяться. Учитывая наличие явных связей между элементами списка, иногда используют термины цепной список или связной список. Список, отражающий отношение соседства между элементами (у каждого элемента списка могут быть только один предыдущий и один последующий элементы), называется линейным. Любой другой список называется нелинейным.

Однонаправленный список (рис. 4) является простейшей формой списка.

Рис. 4. Однонаправленный список.

Достоинства однонаправленного списка – простота создания, включения и удаления элементов. Недостаток – просмотр элементов осуществляется всегда с начала списка. Правда, программа обработки ожжет запоминать указатель на текущий элемент, тогда обработку можно продолжать с него.

Циклический список (рис. 5) отличается от однонаправленного только тем, что последний элемент в поле указателя содержит не признак конца списка, а ссылку на начало списка, т.е. на первый элемент, что позволяет перейти на другую операцию обработки элементов, начиная с любого элемента списка.

Рис. 5. Циклический список.

В двунаправленном списке каждый элемент содержит два указателя – на последующий и предыдущий элементы, что позволяет вести обработку элементов как в прямом, так и в обратном направлении.

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

• тип структуры;

• имя списка;

• указатель (адрес) начала списка;

• текущее число элементов;

• описание элемента (длина, тип и т.п.).

Вместо дескриптора можно использовать только указатель.

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

Элементы структуры данных в списке могут быть упорядочены по возрастанию или убыванию значения некоторого поля данных (по ключу). Обработка упорядоченных списков во многих случаях проще обработки неупорядоченных списков.

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

Возможна организация списка и в смежной области памяти. В этом случае все элементы структуры данных имеют один и тот же тип, а число возможных элементов ограничено размерами области памяти. На рис. 1.7 приведён пример цепного списка, размещённого в одной сплошной области памяти (указатель списка размещён в другой области и содержит адрес списка). Элементами данных являются буквы. Последовательность букв, размещённых в списке, образует слово АЗБУКА.

Рис. 1.7. Цепной список в смежной области памяти.

Если обработка списка предусматривает операции как включения, так и удаления элементов, то потребуются создание и ведение двух дополнительных списков: списка свободных и списка занятых элементов. Удаляемый элемент при этом включается в список свободных, а для включения элемента используется элемент из списка свободных, если таковые имеются. В качестве указателей в таких списках могут использоваться либо индексы элементов, либо их адреса.