Сжатое и индексное хранение линейных списков
При хранении больших объемов информации в форме линейных списков нежелательно хранить
элементы с одинаковым значением, поэтому используют различные методы сжатия списков.
Сжатое хранение. Пусть в списке B= несколько элементов имеют одинаковое значение V, а
список B'= получается из B заменой каждого элемента Ki на пару Ki'=(i,Ki). Пусть далее
B"= - подсписок B', получающийся вычеркиванием всех пар Ki=(i,V). Сжатым хранением В
является метод хранения В", в котором элементы со значением V умалчиваются. Различают
последовательное сжатое хранение и связанное сжатое хранение. Например, для списка B=,
содержащего несколько узлов со значением Х, последовательное сжатое и связанное сжатое
хранения, с умалчиванием элементов со значением Х, представлены на рис.22,23.
Достоинство сжатого хранения списка при большом числе элементов со значением V
заключается в возможности уменьшения объема памяти для его хранения.
Поиск i-го элемента в связанном сжатом хранении осуществляется методом полного
просмотра, при последовательном хранении - методом бинарного поиска.
Преимущества и недостатки последовательного сжатого и связанного сжатого хранений
аналогичны преимуществам и недостаткам последовательного и связанного хранений.
Рассмотрим следующую задачу. На входе заданы две последовательности целых чисел M=, N=,
причем 92% элементов последовательности М равны нулю. Составить программу для вычисления
суммы произведений Mi * Ni, i=1,2,...,10000.
Предположим, что список М хранится последовательно сжато в массиве структур m с
объявлением:
struct
{ int nm;
float val; } m[10000];
Для определения конца списка добавим еще один элемент с порядковым номером
m[j].nm=10001, который называется стоппером (stopper) и располагается за последним
элементом сжатого хранения списка в массиве m.
Программа для нахождения искомой суммы имеет вид:
# include
main()
{ int i,j=0;
float inp,sum=0;
struct /* объявление массива*/
{ int nm; /* структур */
float val; } m[10000];
for(i=0;i<10000;i++) /* чтение списка M */
{ scanf("%f",&inp); if (inp!="0)"
{ m[j].nm="i;" m[j++].val="inp;" } }
m[j].nm="10001;" /* stopper */
for(i="0,j=0;" i<10000; i++)
{ scanf("%f",&inp); /* чтение списка N */
if(i="=m[j].nm)" /* вычисление суммы */
sum+="m[j++].val*inp;" }
printf( "сумма произведений Mi*Ni равна %f",sum);}
Индексное хранение используется для уменьшения времени поиска нужного элемента в списке
и заключается в следующем. Исходный список B = разбивается на несколько подсписков
В1,В2, ...,Вm таким образом, что каждый элемент списка В попадает только в один из
подсписков, и дополнительно используется индексный список с М элементами, указывающими
на начало списков В1,В2, ...,Вm.
Считается, что список хранится индексно с помощью подсписков B1,B2, ...,Bm и индексного
спискa X = , где ADGj - адрес начала подсписка Bj, j=1,M.
При индексном хранении элемент К подсписка Bj имеет индекс j. Для получения индексного
хранения исходный список В часто преобразуется в список В' путем включения в каждый узел
еще и его порядкового номера в исходном списке В, а в j-ый элемент индексного списка Х,
кроме ADGj, может включаться некоторая дополнительная информация о подсписке Bj.
Разбиение списка В на подсписки осуществляется так, чтобы все элементы В, обладающие
определенным свойством Рj, попадали в один подсписок Bj.
Достоинством индексного хранения является то, что для нахождения элемента К с заданным
свойством Pj достаточно просмотреть только элементы подсписка Bj; его начало находится
по индексному списку Х, так как для любого К, принадлежащего Bi, при i не равном j
свойство Pj не выполняется.
В разбиении В часто используется индексная функция G(K), вычисляющая по элементу К его
индекс j, т.е. G(K)=j. Функция G обычно зависит от позиции К, обозначаемой поз.K, в
подсписке В или от значения определенной части компоненты К - ее ключа.
Рассмотрим список B= с элементами
К1=(17,Y), K2=(23,H), K3=(60,I), K4=(90,S), K5=(66,T),
K6=(77,T), K7=(50,U), K8=(88,W), K9=(30,S).
Если для разбиения этого списка на подсписки в качестве индексной функции взять
Ga(K)=1+(поз.K-1)/3, то список разделится на три подсписка:
B1a=<(17,Y),(23,H),(60,I)>,
B2a=<(90,S),(66,T),(77,T)>,
B3a=<(50,U),(88,W),(30,S)>.
Добавляя всюду еще и начальную позицию элемента в списке, получаем:
B1a'=<(1,17,Y),(2,23,H),(3,60,I)>,
B2a'=<(4,90,S),(5,66,T),(6,77,T)>,
B3a'=<(7,50,U),(8,88,W),(9,30,S)>.