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

В памяти ЭВМ данные могут иметь последовательное представление или связанное представление.

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

Пример: список студентов в журнале.

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

Пусть записи имеют следующий логический порядок: Зап. В, Зап. А, Зап. F, Зап. С, …., Зап.N. Эти записи разместятся в памяти ЭВМ так, как это показано на рис. Если записей окажется меньше, чем предполагалось, то память останется неиспользованной. Это – первый недостаток последовательного списка.

В процессе ведения последовательного списка записи добавляются и удаляются. Новые записи добавляются в конец списка. Так запись N+1 поместится в ячейку 100+(N+1). Если количество новых записей окажется больше, чем число свободных ячеек в зарезервированном блоке, то эти записи не удастся разместить. Это второй недостаток последовательного списка.

При удалении записей в памяти остаются свободные ячейки. Если, например, удалить Зап. А и Зап. F, то ячейки 102 и 103 окажутся свободными. Список, в котором содержатся свободные ячейки, называется неплотным.

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

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

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

Последовательное представление наиболее просто реализуется программно.