Связанное распределение

Cтраница 1

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

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

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

Связанное распределение памяти обеспечивает существенно более высокую гибкость при работе со списками, чем последовательное распределение, значительно упрощая включение нового узла в список и исключение из него. [4]

Связанное распределение стека такое же легкое, как и последовательное распределение. Мы сохраняем символ / в качестве указателя ячейки, являющейся вершиной стека, и используем поле LINK элемента стека для указания элемента, находящегося под данным элементом в стеке. Нижний элемент стека имеет пустой указатель Л в поле LINK, и / Л означает пустой стек. [5]

Использование связанного распределения, как правило, предполагает существование некоторого механизма поиска пустого пространства для нового узла, когда мы хотим включить в список некоторую вновь образованную информацию. Для этой цели обычно существует специальный список, называемый списком свободного пространства. Множество всех узлов, которые в данный момент не используются, связано в список, ничем не отличающийся от любых других списков; переменная связи AVAIL ссылается на верхний элемент этого списка. [6]

В связанном распределении такого соотношения не существует, и доступ ко всем элементам последовательности, кроме первого, не является прямым и эффективным. Например, при последовательном представлении, если длина последовательности задана, то легко найти средний ее элемент; это же самое сделать труднее, если последовательность задается связанным списком. [7]

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

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

Примеры связанных линейных списков.| Пример двунаправленного линейного списка. [10]

Структура линейного списка, представленная с помощью связанного распределения, называется также цепной структурой или цепью. [11]

Корневое дерево с тремя поддеревьями.| Регулярная связанная структура представления дерева. [12]

Почти все машинные представления деревьев основаны на связанных распределениях. Каждый узел состоит из поля данных и некоторых полей для указателей. В следующем примере представления дерева каждый узел имеет по три поля указателей. [13]

Почти все машинные представления деревьев основаны на связанных распределениях ( представления в виде последовательных распределений для некоторых типов бинарных деревьев будут введены в разд. Каждый узел состоит из поля INFO и некоторых полей для указателей. [14]

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

Страницы: 1 2 3