Составители:
39
дексами строки и столбца матрицы
(рис. 6). Такой способ хранения назы-
вается последовательным представле-
нием разреженных матриц.
Доступ к элементу матрицы A с ин-
дексами i и j выполняется выборкой
индекса i из поля Row, индекса j из
поля Colum и значения элемента из
поля Value. Следует отметить, что
элементы матрицы обязательно запо-
минаются в порядке возрастания но-
меров строк для ускорения поиска.
Такое представление матрицы A
сокращает используемый объем памя-
ти. Для больших матриц экономия па-
мяти является очень актуальной про-
блемой.
Однако последовательное представление разреженных матриц име-
ет определенные недостатки. Так, включение и исключение новых эле-
ментов матрицы вызывает необходимость перемещения большого чис-
ла существующих элементов. Если включение новых элементов и их
исключение осуществляется часто, то можно использовать описывае-
мый ниже метод связанных структур.
Метод связанных структур переводит статическую структуру матри-
цы в динамическую. Эта динамическая структура реализована в виде
циклических списков.
Для такого представления разреженных матриц требуется следую-
щая структура элемента списка:
type
PElement = ^TypeElement; {указатель на тип элемента}
TypeElement = record {тип элемента списка}
Left: PElement; {указатель на предыд. элемент в строке}
Up: PElement; {указатель на предыд. элемент в столбце}
Value: TypeData; {значение элемента матрицы}
Row: integer; {индекс строки матрицы}
Colum: integer; {индекс столбца матрицы}
end;
Связанная структура для разреженной матрицы A показана на рис. 7.
Colum Value
136
159
212
247
258
274
3110
4312
543
575
Row
Рис. 6. Последовательное пред-
ставление разреженных матриц
Страницы
- « первая
- ‹ предыдущая
- …
- 37
- 38
- 39
- 40
- 41
- …
- следующая ›
- последняя »
