Физическое представление данных, страница 3

α (i) = β + (i-1) m – Адресная функция

Движение вниз по дереву осуществляется путем удвоенного индекса и прибавлением единицы

Y2*2+1

Y2*2

Y2

Адрес узла вычисляется по адресной функции.

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

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

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

Включение записи в список осуществляется путем изменения адреса ссылки узла Y2.

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

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

6.2.3. Связанный линейный список с использованием индекса

Линейный список с последовательном распределением памяти

		Связанный линейный список