Связанное представление данных в памяти ЭВМ

Обычно в АИС данные часто обновляются, корректируются и при использовании последовательного представления много машинного времени тратится на перезапись данных в процессе уплотнения списка. Для ряда задач последовательное представление данных является вообще неприемлемым. В таких случаях используют связанное представление данных.

При связанном представлении в каждой записи предусматривается дополнительное поле, в которое помещается указатель (ссылка). Физический порядок следования записей в этом случае может не соответствовать логическому порядку. В памяти ЭВМ записи располагаются в любых свободных ячейках и связываются между собой указателями так, чтобы поддерживался нужный логический порядок. Указатель записи указывает на ячейку памяти, в которой хранится следующая запись. В качестве указателя обычно используется адрес ячейки.

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

Пусть, в соответствии с решаемой задачей, записи должны иметь следующий логический порядок: Зап. A, Зап. B, Зап. C, Зап. F. В этом порядке они должны читаться и обрабатываться программой. При размещении в памяти Зап. A заняла ячейку 01, Зап. B – ячейку 05, Зап. C- ячейку 03, а Зап. F – ячейку 10. Для того, чтобы обеспечить необходимый логический порядок следования записей в поле указателя каждой записи необходимо поместить адрес ячейки с логически следующей записи. Указатель обозначим АС.

Одна из ячеек, называемая головной, содержит указатель на ячейку с первой записью списка. В соответствии с этим указателем при обработке списка первым будет прочитано содержимое ячейки с адресом 01 , т.е. Зап.А. Затем прочитается содержимое ячеек 05 (Зап. В), 03 (Зап. С) и 10 (Зап. F). Символ Q, помещенный в поле указателя последней записи списка, означает конец списка. В качестве указателя конца списка может быть использован любой элемент данных, который программой чтения не воспринимается как указатель.

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

Указатели изменяются таким образом, чтобы сохранялся логический порядок следования записей.

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

Исключим из списка Зап.С, хранящуюся в ячейке с адресом 03 и имеющую адрес связи 10. Для этого значение указателя предшествующей записи (Зап.В) изменим на АС 10. Теперь доступ к Зап.С стал невозможен и эта запись оказалась исключенной из списка. Освободившаяся ячейка может быть использована для включения новой записи.

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

Включим в список Зап. D, логически следующую за записью С. Зап. D разместим в ячейке с адресом 15. После замены указателей установится следующий порядок чтения ячеей памяти 01, 05, 03, 15, 10, а список будет обрабатываться так: Зап.А, Зап. В, Зап. С, Зап. D, Зап. F.

Односвязный список можно организовать в виде замкнутого кольца.

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

Связанное представление данных используется для хранения нелинейных структур данных, а также для хранения данных в тех случаях, когда:

- заранее неизвестен предельный объем информационного массива;

- информационный массив часто подвергается изменениям и записи часто добавляются и удаляются.

Следует, однако, помнить, что связанное представление приводит к дополнительному расходу памяти из-за появления в записи дополнительного поля – поля указателя.

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

Для реализации связанного списка язык программирования должен располагать данными типа «указатель». Такой тип данных предусмотрен в языках ПЛ/1, СИ, Паскаль. В языке Паскаль с помощью особых типов данных - указателей можно осуществлять динамическое распределение памяти и создавать динамические структуры данных.

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

Пусть структура данных определена как массив М(I), где данные хранятся в следующем порядке: Зап. С, Зап. D, Зап.В, Зап. А. Таков физический порядок записей. Пусть необходимо обеспечить следующий порядок чтения или обработки записей: Зап. А, Зап.В, Зап. С, Зап. D, не совпадающий с физическим порядком их следования. Для решения этой задачи можно организовать вспомогательный вектор указателей N(J). Элементы вектора – целые числа – определяют порядковые номера (индексы) записей основного массива М(I). При обработке основного массива вначале читается элемент вспомогательного вектора N(J), а затем следует обращения к тому элементу основного массива, индекс которого хранится в этом элементе вектора, т.е. индекс обрабатываемого элемента основного массива I=N(J).

Вектор N(J), изображенный на рис. Задает следующий порядок чтения записей основного массива: Зап. А, Зап. В, Зап. С, Зап. D.

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

В файлах функции указателя может с успехом выполнять N физической записи. ОС обеспечивает прямой доступ к записи с указанным номером, т.е. к очередной записи связанного списка.