2.6. Сжатое и индексное хранение линейных списков

При хранении больших объемов информации в форме линейных списков нежелательно хранить элементы с одинаковым значением, поэтому используют различные методы сжатия списков.

Сжатое хранение. Пусть в списке B= несколько элементов имеют одинаковое значение V, а список B'=< K₁ ', K₂',..., K_n' получается из B заменой каждого элемента K_i на пару K_i'=(i, K_i). Пусть далее B"=< K₁", K₂",..., K_m" > - подсписок B', получающийся вычеркиванием всех пар K_i=(i,V). Сжатым хранением В является метод хранения В", в котором элементы со значением V умалчиваются. Различают последовательное сжатое хранение и связанное сжатое хранение. Например, для списка B=, содержащего несколько узлов со значением Х, последовательное сжатое и связанное сжатое хранения, с умалчиванием элементов со значением Х, представлены на рис.11,12.

Р ис. 11. Последовательное сжатое хранение списка

Рис. 12. Связное сжатое хранение списка

Достоинство сжатого хранения списка при большом числе элементов со значением V заключается в возможности уменьшения объема памяти для его хранения.

Поиск i-го элемента в связанном сжатом хранении осуществляется методом полного просмотра, при последовательном хранении – методом бинарного поиска.

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

Рассмотрим следующую задачу. На входе заданы две последовательности целых чисел M=< M₁, M₂,..., M₁₀₀₀₀>, N=<N₁, N₂,..., N₁₀₀₀₀>, причем 92% элементов последовательности М равны нулю. Составить программу для вычисления суммы sum= M_i * N_i.

Предположим, что список М хранится последовательно сжато в массиве структур m с объявлением:

struct {

int nm;

float val;

} m[10000];

Для определения конца списка добавим еще один элемент с порядковым номером m[j].nm=10001, который называется стоппером (stopper) и располагается за последним элементом сжатого хранения списка в массиве m.

Программа для нахождения искомой суммы имеет вид:

#include <STDIO.H>

#define MAX_I 10000

void main()

{

int i,j=0;

floatinp,sum=0;

struct{ /* объявление массива */

int nm; /* структур */

float val;

} m[MAX_I];

for(i=0; i< MAX_I; i++) /* чтениесписка M */

{

scanf("%f",&inp);

if (inp!=0)

{

m[j].nm=i;

m[j++].val=inp;

}

}

m[j].nm= MAX_I+1; /* stopper */

for(i=0,j=0; i< MAX_I; i++)

{

scanf("%f",&inp); /* чтение списка N */

if(i==m[j].nm) /* вычисление суммы */

sum+=m[j++].val*inp;

}

printf( "сумма произведений Mi*Ni равна %f",sum);

}

Индексное хранение используется для уменьшения времени поиска нужного элемента в списке и заключается в следующем. Исходный список B = < K₁, K₂ , ..., K_n>разбивается на несколько подсписков B₁, B₂ , ..., B_m таким образом, что каждый элемент списка В попадает только в один из подсписков, и дополнительно используется индексный список с М элементами, указывающими на начало списков B₁, B₂ , ..., B_m. Считается, что список хранится индексно с помощью подсписков B₁, B₂ , ..., B_m и индексного списка X = < ADG₁, ADG₂, ..., ADG_m>, где ADG_j - адрес начала подсписка B_j, j=1…m.

При индексном хранении элемент К подсписка B_j имеет индекс j. Для получения индексного хранения исходный список В часто преобразуется в список В' путем включения в каждый узел еще и его порядкового номера в исходном списке В, а в j-ый элемент индексного списка Х, кроме ADG_j, может включаться некоторая дополнительная информация о подсписке B_j. Разбиение списка В на подсписки осуществляется так, чтобы все элементы В, обладающие определенным свойством Р_j, попадали в один подсписок B_j.

Достоинством индексного хранения является то, что для нахождения элемента К с заданным свойством Р_j достаточно просмотреть только элементы подсписка B_j; его начало находится по индексному списку Х, так как для любого КB_i, при ij свойство Р_j не выполняется.

В разбиении В часто используется индексная функция G(K), вычисляющая по элементу К его индекс j, т.е. G(K)=j. Функция G обычно зависит от позиции К, обозначаемой поз.K, в подсписке В или от значения определенной части компоненты К - ее ключа.

Рассмотрим список B=< K₁, K₂ , ..., K₉> с элементами К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).

Если для разбиения этого списка на подсписки в качестве индексной функции взять G_a (K)=1+(поз.K-1)/3, то список разделится на три подсписка:

B_1a=<(17,Y),(23,H),(60,I)>,.

B_2a=<(90,S),(66,T),(77,T)>,.

B_3a=<(50,U),(88,W),(30,S)>.

Добавляя всюду еще и начальную позицию элемента в списке, получаем:

B_1a'=<(1,17,Y),(2,23,H),(3,60,I)>,о

B_2a'=<(4,90,S),(5,66,T),(6,77,T)>,о

B_3a'=<(7,50,U),(8,88,W),(9,30,S)>.

Если в качестве индексной функции выбрать другую функцию G_b (K)=1+(поз.K-1)%3, то получим списки:

B_1b"=<(1,17,Y),(4,90,S),(7,50,U)>,

B_2b"=<(2,23,H),(5,66,T),(8,88,U)>,

B_3b"=<(3,60,I),(6,77,T),(9,30,S)>.ь

Теперь для нахождения узла K₆ достаточно просмотреть только одну из трех последовательностей (списков). При использовании функции G_a (K) это список B_2a', а при функции G_b (K) список B_3b".

Для индексной функции G_c (K)=1+ K_1’ /100, где K_1’ - первая компонента элемента К, находим:

B₁ =<(17,Y),(23,H),(60,I),(90,S)>,

B₂ =<(66,T),(77,T)>,

B₃ =<(50,U),(88,W)>,

B₄ =<(30,S)>.

Чтобы найти здесь узел К с первым компонентом-ключом K_1’ =77, достаточно просмотреть список B₂.

При реализации индексного хранения применяется методика А для хранения индексного списка Х (функция G_a (X) ) и методика C для хранения подсписков B₁, B₂ ,..., B_m(функция G_c (B_i)), т.е. используется, так называемое, A-C индексное хранение.

На практике часто используется последовательно-связанное индексное хранение. Так как обычно длина списка индексов известна, то его удобно хранить последовательно, обеспечивая прямой доступ к любому элементу списка индексов. Подсписки B₁, B₂ ,..., B_m хранятся связанно, что упрощает вставку и удаление узлов(элементов). В частности, подобный метод хранения используется в ЕС ЭВМ для организации, так называемых, индексно-последовательных наборов данных, в которых доступ к отдельным записям возможен как последовательно, так и при помощи ключа.

П оследовательно-связанное индексное хранение для приведенного примера изображено на рис.13, где X = < ADG₁, ADG₂, ADG₃, ADG₄>

Рис. 13. Последовательно-связанное индексное хранение списка

Рассмотрим еще одну задачу. На входе задана последовательность целых положительных чисел, заканчивающаяся нулем. Составить функцию для ввода этой последовательности и организации ее последовательно-связанного индексного хранения таким образом, чтобы числа, совпадающие в двух последних цифрах, помещались в один подсписок.

Выберем в качестве индексной функции G(K)=K%100+1, а в качестве индексного списка Х – массив из 100 элементов. Следующая функция решает поставленную задачу:

#include<STDIO.H>

#include<STDLIB.H>

#include <MATH.H>

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("%f",&inp);

while (inp!=0)

{

j++;

p=(ND*)malloc(sizeof(ND));

i=fmod(inp,100);

p->val=inp;

p->n=x[i];

x[i]=p;

scanf("%d",&inp);

}

return j; //общее количество элементов в списках

}

Возвращаемым значением функции index будет число обработанных элементов списка.

Для индексного списка также может использоваться индексное хранение. Пусть, например, имеется список B=<K₁, K₂, …, K₁₀> с элементами K₁=(338,Z), K₂=(145,A), K₃=(136,H), K₄=(214,I), K₅=(146,C), K₆=(334,Y), K₇=(333,P), K₈=(127,G), K₉=(310,O), K₁₀=(322,X).

Требуется разделить его на семь подсписков, т.е. X=<X₁, X₂, …, X₇> таким образом, чтобы в каждый список B₁, B₂ ,..., B₇ попадали элементы, совпадающие в первой компоненте первыми двумя цифрами. Список Х, в свою очередь, будем индексировать списком индексов Y=<Y₁, Y₂, Y₃>, чтобы в каждый список Y₁, Y₂ , Y₃ попадали элементы из X, у которых в первой компоненте совпадают первые цифры. Если списки B₁, B₂ ,..., B₇ хранить связанно, а списки индексов X, Y индексно, то такой способ хранения списка B называется связанно-связанным связанным индексным хранением. Графическое изображение этого хранения приведено на рис.14.

Рис. 14. Связанно-индексное хранение списка

Задания для самоконтроля

1. Линейный список F из M целых чисел, большинство элементов которого равно нулю, хранится связанно сжато. Написать функцию для нахождения i-го элемента списка.

2. Линейный список F целых чисел хранится последовательно-связанно индексно, так что числа, совпадающие в последней цифре, помещаются в один подсписок. Написать функцию определения: имеется ли в списке элемент со значением V.

3. На входе задана последовательность целых положительных чисел, оканчивающихся нулем. Написать фрагмент программы для ввода чисел и организации их последовательно-связанного индексного хранения. При этом числа, у которых первая и третья цифры совпадают, соответственно должны помещаться в один список.

4. На входе заданна последовательность n троек (Xi, Yi, Pi), где Xi-немецкое слово; Yi- его английский эквивалент и Pi – частота использования (в %) слова Xi в «типичном немецком тексте». Последовательность пар (Xi, Yi), интерпретируемая как линейный список, хранится последовательно-связанно индексно. Элементы, совпадающие по первой букве немецкого слова, помещаются в один связанный список, где упорядочены по убыванию частоты использования (чтобы быстрее находить чаще используемые слова). Написать программу формирования этой структуры данных и осуществления пословной трансляции немецкого предложения из М слов. Если для конкретного немецкого слова нет перевода, то оставлять его не переведенным.