в качестве индексной функции выбрать
B1a=, B2a=, B3a=.
Добавляя всюду еще и начальную позицию элемента в списке, получаем:
B1a'=, B2a'=, B3a'=.
Если в качестве индексной функции выбрать другую функцию Gb(K)=1+(поз.K-1)%3, то получим списки:
B1b"=, B2b"=, B3b"=.
Теперь для нахождения узла K6 достаточно просмотреть только одну из трех последовательностей (списков). При использовании функции Ga(K) это список B2a', а при функции Gb(K) список B3b".
Для индексной функции Gc(K)=1+K1/100, где K1 - первая компонента элемента К, находим:
B1=, B2=, B3=, B4=.
Чтобы найти здесь узел К с первым компонентом-ключом К1=77, достаточно просмотреть список B2.
При реализации индексного хранения применяется методика А для хранения индексного списка Х (функция Ga(X) ) и методика C для хранения подсписков B1,B2,...,Bm (функция Gc(Bi)), т.е. используется, так называемое, A-C индексное хранение.
В практике часто используется последовательно-связанное индексное хранение. Так как обычно длина списка индексов известна, то его удобно хранить последовательно, обеспечивая прямой доступ к любому элементу списка индексов. Подсписки B1,B2,...,Bm хранятся связанно, что упрощает вставку и удаление узлов(элементов). В частности, подобный метод хранения используется в ЕС ЭВМ для организации, так называемых, индексно-последовательных наборов данных, в которых доступ к отдельным записям возможен как последовательно, так и при помощи ключа.
Последовательно-связанное индексное хранение для приведенного примера изображено на рис.24, где X=.
Рис.24. Последовательно-связанное индексное хранение списка.
Рассмотрим еще одну задачу. На входе задана последовательность целых положительных чисел, заканчивающаяся нулем. Составить процедуру для ввода этой последовательности и организации ее последовательно-связанного индексного хранения таким образом, чтобы числа, совпадающие в двух последних цифрах, помещались в один подсписок.
Выберем в качестве индексной функции G(K)=K%100+1, а в качестве индексного списка Х - массив из 100 элементов. Следующая функция решает поставленную задачу:
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий