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

Рис. 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).