Ортогональные списки (мультисписки)

 

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

Ортогональный список позволяет на множестве одних и тех же атрибутов, содержащих информацию, организовать различные списки, упорядоченные по различным признакам. Рассмотрим список студентов, каждый узел которого содержит следующие информационные поля: фамилия_ имя_отчество, средний балл, дата рождения, адрес, номер зачетки и т.п. Пусть необходимо упорядочить список студентов по двум признакам: в алфавитном порядке по фамилии и в соответствии со средним баллом. Этого можно достичь, если построить два отдельных списка, но элементы хранения информационных полей в этом случае продублируются, что приведет к неэффективному использованию оперативной памяти, особенно, если количество информационных полей велико. Более рациональным решением является использование мультисписка, содержащего два списка, каждый из которых организован, например, в виде двусвязного циклического списка: по алфавиту элементы списка упорядочены с помощью атрибутов связи fnext и fprev, а по среднему баллу те же самые элементы упорядочены с помощью атрибутов связи bnext и bprev. Для удобства обработки мультисписок содержит головной элемент, на который установлен указатель. Структура мультисписка студентов представлена на рис. 39.

 

Рис. 39. Структура мультисписка студентов

 

Описание элемента хранения мультисписка студентов:

   

Type
Str30 = String[30];	{ тип для описания фамилии_имени_отчества }
PMulty_List: ^ Multy_List;				{ тип – указатель на узел мультисписка }
Multy_List = record		{ описание элемента хранения узла мультисписка}
fam: Str30;				{ фамилия_имя_отчество }
ball: real;				{ средний балл }
...
fnext, fprev: PMulty;				{ атрибуты связи в списке по фамилии }
bnext, bprev: PMulty;			{ атрибуты связи в списке по среднему баллу }
end;
Var head: PMulty;				{ указатель на “голову” мультисписка }

 

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

 

Procedure Print_Fam(head: PMulty);	{ распечатка мультисписка, }
Var p: PMulty;	{ упорядоченного по алфавиту }
begin
if (head <> nil) then begin	{ список существует? }
p:=head^.fnext;	{ установить вспомогательный указатель }
while (p <> head) do begin	{ весь список пройден? }
writeln(p^.fam, p^.ball);	{ распечатать информационные поля }
p:=p^.fnext	{ перейти к следующему узлу }
end;
end;
end;

 

Procedure Print_Ball(head: PMulty);	{ распечатка мультисписка, }
Var p: PMulty;	{ упорядоченного по среднему баллу }
begin
if (head <> nil) then begin	{ список существует? }
p:=head^.bnext;	{ установить вспомогательный указатель }
while (p <> head) do begin	{ весь список пройден? }
writeln(p^.fam, p^.ball);	{ распечатать информационные поля }
p:=p^.bnext	{ перейти к следующему узлу }
end;
end;
end;

 

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

 

3	0	5
0	0	30
2	10	0

 

Мультисписки обеспечивают эффективное хранение таких структур в памяти – хранятся только те элементы, которые отличны от нуля (рис. 40). Каждый элемент входит в два списка – в список-строку и в список-столбец. Вся матрица представляется (m + n) списками, где m и n соответственно число строк и число столбцов. Каждый элемент мультисписка хранит значение элемента матрицы, номер строки, номер столбца и две ссылки – на следующий элемент в строке и на следующий элемент в столбце (если используются односвязные списки). Указатели на начала этих списков хранятся в двух массивах.

 

 

Рис. 40. Разреженная матрица, представленная в виде структуры мультисписка

 

Описание элемента хранения разреженной матрицы.

 

Const
Nrow = 10;					{ количество строк }
Ncol = 20;					{ количество столбцов }
Type
PMatrix: ^ Matrix;					{ тип – указатель на узел мультисписка }
Matrix = record			{ описание элемента хранения узла мультисписка}
val: word;					{ значение элемента }
row, col: word;					{ номер строки, номер столбца }
frow, fcol: PMatrix;			{ атрибуты связи в списках по строке и по столбцу }
end;
Prow=array[1..Nrow] of PMatrix;				{ тип – массив указателей на первые узлы списков строк }
Pcol=array[1..Ncol] of PMatrix;					{ тип – массив указателей на первые узлы списков столбцов }
Var
r: Prow;		{ массив указателей на первые узлы списков строк }
c: Pcol;	{ массив указателей на первые узлы списков столбцов }

 

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

 

Procedure Print_Matrix(var fr: Prow);				{ fr – массив указателей на списки строк }
Var p: PMatrix; i: byte;		{ p – вспомогательный указатель для прохода по строке }
begin
for i:=1 to Nrow do begin				{ просмотр строк }
p:=fr[i];	{ установка вспогательного указателя на первый элемент списка строки }
while (p<> nil) do begin				{ список строки не пуст? }
writeln ('Matrix[', p^.row, ',', p^.col, ']=', p^.val);					{ вывод значения}
p:=p^.frow;			{ переход к следующему элементу в строке }
end;
end;
end;

 

Примечание. Массив указателей на списки строк передается по ссылке, чтобы избежать копирования массива в стеке при передаче параметров процедуры.

 

Разнородные списки

 

По составу элементов списки подразделяются на однородные и разнородные. Все виды списков, рассматриваемые до сих пор, являются однородными, т.к. они состоят из элементов одного и того же типа. Если список включает элементы различных типов, то он называется разнородным. Особенности обработки разнородных списков состоят в том, что в каждый элемент списка вводится дополнительный атрибут, позволяющий определить тип элемента списка и соответствующим образом интерпретировать содержимое его информационных полей (5.2.1).

Примером разнородного списка является список, содержащий информацию о геометрических фигурах, составляющих некоторый проект (рис. 41).

 

Рис. 41. Структура разнородного списка