Алгоритмы и структуры данных на С++. Аксёнова Е.А - 27 стр.

UptoLike

ВУЗ: 

ПетрГУ | Петрозаводск

Составители: 

Рубрика: 

2.3. Связное представление линейных списков 27
связи в каждом элементе. Обозначим link(x
i
) – поле связи узла
x
i
, loc(x
i
) – адрес i-го узла. В рассматриваемом представлении
списка в каждом узле истинно равенство l ink(x
i
) = l oc(x
i+1
)−
−loc(x
i−1
) (рис. 2.14).
Рис. 2.14
Таким образом, если известен адрес текущего узла и адрес пред-
шествующего узла, то можно вычислить адреса всех узлов при
прохождении списка в обоих направлениях.
• Списки с 1.5 связями [7]. В этом представлении используются
узлы с двумя связями (ссылки вперед и назад) и с одной связью
(ссылки назад через один) (рис. 2.15). В таком списке возможен
проход вперед и назад, но памяти на ссылки нужно в полтора
раза меньше, чем у двухсвязных списков.
Рис. 2.15
Примеры применения связных списков
Наиболее часто используемое применение связных списков – это
хранение переменного числа элементов. Такие задачи возникают в
системном программировании, в задачах искусственного интеллекта
и других приложениях.
Связные списки могут применяться для хранения разреженных
матриц (матриц с большим количеством нулевых элементов).
2.3.   Связное представление линейных списков                       27


       связи в каждом элементе. Обозначим link(xi ) – поле связи узла
       xi , loc(xi ) – адрес i-го узла. В рассматриваемом представлении
       списка в каждом узле истинно равенство link(xi ) = loc(xi+1 )−
       −loc(xi−1 ) (рис. 2.14).




                               Рис. 2.14

     Таким образом, если известен адрес текущего узла и адрес пред-
     шествующего узла, то можно вычислить адреса всех узлов при
     прохождении списка в обоих направлениях.
   • Списки с 1.5 связями [7]. В этом представлении используются
     узлы с двумя связями (ссылки вперед и назад) и с одной связью
     (ссылки назад через один) (рис. 2.15). В таком списке возможен
     проход вперед и назад, но памяти на ссылки нужно в полтора
     раза меньше, чем у двухсвязных списков.




                               Рис. 2.15


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

Страницы