Сжатое и индексное хранение линейных списков
Если в качестве индексной функции выбрать другую функцию Gb(K)=1+(поз.K-1)%3, то получим
списки:
B1b"=<(1,17,Y),(4,90,S),(7,50,U)>,
B2b"=<(2,23,H),(5,66,T),(8,88,U)>,
B3b"=<(3,60,I),(6,77,T),(9,30,S)>.
Теперь для нахождения узла K6 достаточно просмотреть только одну из трех
последовательностей (списков). При использовании функции Ga(K) это список B2a', а при
функции Gb(K) список B3b".
Для индексной функции Gc(K)=1+K1/100, где K1 - первая компонента элемента К, находим:
B1=<(17,Y),(23,H),(60,I),(90,S)>,
B2=<(66,T),(77,T)>,
B3=<(50,U),(88,W)>,
B4=<(30,S)>.
Чтобы найти здесь узел К с первым компонентом-ключом К1=77, достаточно просмотреть
список B2.
При реализации индексного хранения применяется методика А для хранения индексного списка
Х (функция Ga(X) ) и методика C для хранения подсписков B1,B2,...,Bm (функция Gc(Bi)),
т.е. используется, так называемое, A-C индексное хранение.
В практике часто используется последовательно-связанное индексное хранение. Так как
обычно длина списка индексов известна, то его удобно хранить последовательно,
обеспечивая прямой доступ к любому элементу списка индексов. Подсписки B1,B2,...,Bm
хранятся связанно, что упрощает вставку и удаление узлов(элементов). В частности,
подобный метод хранения используется в ЕС ЭВМ для организации, так называемых,
индексно-последовательных наборов данных, в которых доступ к отдельным записям возможен
как последовательно, так и при помощи ключа.
Последовательно-связанное индексное хранение для приведенного примера изображено на
рис.24, где X=
Рассмотрим еще одну задачу. На входе задана последовательность целых положительных
чисел, заканчивающаяся нулем. Составить процедуру для ввода этой последовательности и
организации ее последовательно-связанного индексного хранения таким образом, чтобы числа,
совпадающие в двух последних цифрах, помещались в один подсписок.
Выберем в качестве индексной функции G(K)=K%100+1, а в качестве индексного списка Х -
массив из 100 элементов. Следующая функция решает поставленную задачу:
#include
#include
typedef struct nd
{ float val;
struct nd *n; } ND;
int index (ND *x[100])
{ ND *p;
int i,j=0;
float inp;
for (i=0; i<100; i++) x[i]="NULL";
scanf("%d",&inp); while (inp!="0)"
{ j++; p="malloc(sizeof(ND));" i="inp%100+1;"
p->val=inp;
p->n=x[i];
x[i]=p;
scanf("%d",&inp);
}
return j;
}
Возвращаемым значением функции index будет число обработанных элементов списка.
Для индексного списка также может использоваться индексное хранение. Пусть, например,
имеется список B= с элементами
K1=(338,Z), K2=(145,A), K3=(136,H), K4=(214,I), K5 =(146,C),
K6=(334,Y), K7=(333,P), K8=(127,G), K9=(310,O), K10=(322,X).
Требуется разделить его на семь подсписков, т.е. X= таким образом, чтобы в каждый список
B1,B2,...,B7 попадали элементы, совпадающие в первой компоненте первыми двумя цифрами.
Список Х, в свою очередь, будем индексировать списком индексов Y=, чтобы в каждый список
Y1,Y2,Y3 попадали элементы из X, у которых в первой компоненте совпадают первые цифры.
Если списки B1,B2,...,B7 хранить связанно, а списки индексов X,Y индексно, то такой
способ хранения списка B называется связанно-связанным связанным индексным хранением.
Графическое изображение этого хранения приведено на рис.25.
