Управление памятью при статической реализации списков


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

Первый - более простой, но менее эффективный: все свободные ячейки в связующей части содержат какой-либо специальный номер, например – число ( -1). Тогда при начальном создании пустого списка во все ячейки (кроме нулевой с заголовком) в связующие части помещается значение ( -1). Если при удалении элемента из списка соответствующая ячейка должна стать свободной, то в ее связующую часть записывается значение ( -1), что возвращает эту ячейку в набор свободных. При добавлении нового элемента поиск свободной ячейки организуется просмотром всего массива до обнаружения первой ячейки со значением ( -1). Именно эта операция в некоторых случаях может приводить к росту вычислительных затрат, если случайно все свободные ячейки оказались в конце массива, а сам массив является достаточно большим (например, содержит сотни тысяч ячеек).

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

Какие дополнительные действия необходимы для реализации данного способа? Прежде всего, при создании пустого списка все ячейки массива (кроме нулевой) связываются во вспомогательный список свободных ячеек:

for i := 1 to N-1 do StatList [ i ]. Next := i + 1;

StatList [ N ]. Next := 0;

Начало вспомогательного списка задается переменной StartFree с начальным значением 1. Удаление элемента из основного списка приводит к изменению связующей части удаленного элемента и изменению значения переменной StartFree на индекс удаленного элемента. При добавлении нового элемента свободная ячейка определяется по значению переменной StartFree с последующим ее изменением.

На следующей схеме показаны три состояния базового массива для реализации списка на 10 элементов.

Состояние пустого списка: StartFree = 1

 

                     

 

Состояние списка с шестью элементами:

· Занятые ячейки массива: 3 – 1 – 2 – 8 – 10 – 5

· Свободные ячейки: 6 – 9 – 4 – 7 , StartFree = 6

 

  Инф.2 Инф.3 Инф.1   Инф.6     Инф.4   Инф.5

 

Состояние списка со всеми десятью элементами:

· Занятые ячейки: 8 – 2 – 5 – 6 – 7 – 10 – 1 – 4 – 3 – 9

· Свободных ячеек нет: StartFree = -1

 

  Инф.7 Инф.2 Инф.9 Инф.8 Инф.3 Инф.4 Инф.5 Инф.1 Инф.10 Инф.6

 



Дата добавления: 2020-07-18; просмотров: 568;


Поиск по сайту:

Воспользовавшись поиском можно найти нужную информацию на сайте.

Поделитесь с друзьями:

Считаете данную информацию полезной, тогда расскажите друзьям в соц. сетях.
Poznayka.org - Познайка.Орг - 2016-2024 год. Материал предоставляется для ознакомительных и учебных целей.
Генерация страницы за: 0.008 сек.