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

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

Сжатое хранение. Пусть в списке B= несколько элементов имеют одинаковое значение V, а список B’= получается из B заменой каждого элемента Ki на пару Ki’=(i,Ki). Пусть далее B= — подсписок B’, получающийся вычеркиванием всех пар Ki=(i,V). Сжатым хранением В является метод хранения В, в котором элементы со значением V умалчиваются. Различают последовательное сжатое хранение и связанное сжатое хранение. Например, для списка B=, содержащего несколько узлов со значением Х, последовательное сжатое и связанное сжатое хранения, с умалчиванием элементов со значением Х, представлены на рис.22,23.

1,C 3,Y 6,S 7,H 9,T
Рис.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];

Реализация односвязного списка c++ Часть 1 | Урок #133


Читать еще…

Понравилась статья? Поделиться с друзьями: