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

Все вышерассмотренные структуры, реализовавшиеся как отображение на массив, обладают определенными недостатками, т.е. они малоэффективны при решении некоторых задач. К таким недостаткам можно отнести следующее:

1) Определенно неизвестно, сколько элементов будет иметь данная структура, т.е. нельзя сделать оценку.

2) Если мы рассматриваем некую последовательность элементов в последовательной памяти x₁, x₂, …, x_n и необходимо включить какой-либо новый элемент x в эту последовательность, то мы должны осуществить массовую операцию сдвига всех элементов, находящихся за тем элементом последовательности, после которого мы хотим включить новый элемент. После вставим этот новый элемент x на освободившееся место. Таким образом, здесь проявляется свойство физической смежности.

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

Дата добавления: 2014-01-07