7.Последовательное представление данных в памяти эвм.

В памяти ЭВМ данные могут иметь последовательное представление или связанное представление. При последовательном представлении данные в памяти ЭВМ размещаются в соседних последовательно расположенных ячейках, при этом физический порядок следования записей должен соответствовать их логическому порядку, т.е. логическая структура данных поддерживается физическим порядком следования данных в памяти. Совокупность записей размещенных в последовательно расположенных ячейках памяти называется последовательным списком. Для хранения структуры данных в виде последовательного списка в памяти выделяется блок свободных ячеек под максимально ожидаемый размер информационного массива. Пусть записи имеют следующий логический порядок: Зап. B, Зап.A, Зап.F, Зап.C,…, Зап.N. Эти записи размещены в памяти следующим образом

а) Если записей окажется меньше, чем предполагалось, то память останется неиспользованной – это первый недостаток последовательного представления. В процессе ведения последовательного списка записи добавляются и удаляются. Новые записи добавляются в конец списка, и так запись N+1 добавится в ячейку [N+1]. Если количество новых записей окажется больше чем количество свободных ячеек в зарезервированном блоке, то эти записи не удастся разместить в списке – это второй недостаток последовательного списка. При удалении записей остаются свободные ячейки. Если например удалить (б) Зап.A и Зап.F, то ячейки 102 и 103 окажутся свободными. Список, в котором есть свободные ячейки, называется неплотным. Со временем значительное число ячеек может оказаться свободным, для того чтобы эти участки памяти не пустовали весь массив записей время от времени перезаписывается при этом все записи передвигаются и список уплотняется (в). Для перезаписи списка требуется дополнительное машинное время – это третий недостаток последовательного списка. В процессе корректировки записи, подлежащие обновлению, читаются из списка, в них вносятся изменения. Скорректированная запись записывается в конец списка в свободной ячейке, старые записи считаются удаленными.

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

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

8.Связанное представление данных в памяти эвм.

Обычно в АИС данные часто обновляются, редактируются, и при использовании последовательного представления много машинного времени тратится на уплотнение списка. Для ряда задач последовательное представление данных неприменимо, в таких случаях используют связанное представление данных. При связанном представлении в каждой записи предусматривается дополнительное поле, в котором размещается указатель или ссылка. Физический порядок следования записей в этом случае может не соответствовать логическому. В памяти ЭВМ записи располагаются в любых свободных ячейках и связываются между собой указателями, так чтобы поддерживался нужный логический порядок. Указатель записи указывает на ячейку памяти, в которой хранится следующая запись. В качестве указателя обычно используется адрес той ячейки, в которой хранится следующая по логике запись. Структуры хранения, основанные на связанном представлении, называют связанным списком. Если каждая запись связанного списка содержит один указатель, то список называется односвязным, при большем количестве указателей список называется многосвязным. Пусть в соответствии с решаемой задачей записи должны иметь следующий логический порядок Зап.A, Зап.B, Зап.C, Зап.F

Пусть при размещении в памяти Зап.A-01, Зап.B-05, Зап.C-03, Зап.F-10

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

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

Ячейка с удаленной записью может быть использована как свободная ячейка для размещения новых данных. Такие ячейки с помощью специальной программы называемой «сборщиком мусора» включаются в список свободных ячеек.

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

Включим в исходный список Зап.D, логически следующую за Зап.С. Зап.D разместим в ячейке 15. После замены указателей установится следующий порядок чтения ячеек памяти 01,05,03,15,10 а список будет обрабатываться Зап.A, Зап.B, Зап.C, Зап. D,Зап.F. Т.к. для размещения новых записей могут использоваться любые свободные ячейки, список может расти неограниченно и предварительного резервирования памяти под список не требуется. Односвязный список можно организовать в виде замкнутого кольца

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

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

В некоторых задачах требуется продвигаться по списку и в прямом и в обратном направлениях, для этого в каждую запись придется ввести дополнительный указатель задающий продвижение по списку в обратном направлении, такой список называется двунаправленным. В поле обратного указателя заносится адрес ячейки с логически предшествующей записью. Головная ячейка в этом случае должна содержать указатель на первую и последнюю ячейки списка, обрабатывать такой список можно как с начала так и с конца списка. Для реализации связанного списка язык программирования должен располагать данными типа указатель. Такой тип данных предусмотрен в языках C, PASCAL. Если таких данных в языке нет, то связанный список можно смоделировать с помощью структуры массива. Пусть структура данных определена как массив M(I), физически в этом массиве данные размещены в следующем порядке Зап.C, Зап. D, Зап.B, Зап.A. Пусть необходимо обеспечить следующий порядок обработки записей: Зап.A, Зап.B, Зап.C, Зап. D. Для этого можно организовать вспомогательный вектор N(J). Элементы вектора - целые числа, соответствующие порядковым номерам, т.е. индексы записей основного массива M(I). При обработке основного массива читается элемент вспомогательного массива N(J), а затем следует обращение к тому элементу основного массива индекс которого хранится в текущем элементе вектора, т.е I= N(J)

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