• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

Існує багато способів зберігання розріджених матриць.

Подання даних у вигляді розрідженої матриці

Спосіб 1: Упакований спосіб зберігання розріджених матриць. Зберігаються всі ненульові елементи

рядок стовпчик

Якщо t - кількість ненульові символів, то необхідно 3t комірок. При збереженні в упакованому вигляді розрідженої матриці необхідно передбачити можливість додавання нових ненульових елементів.

а) Використання зв'язаних списків.

Кожному елементу a_ij¹0 у пам’яті комп’ютера відповідає запис, який зберігається по стовпчикам, тобто елементу a_ij буде відповідати деякий запис j- стовпчика матриці. Кожен запис являє собою впорядковану трійку

Номер рядка Значення Покажчик на наступний

елемент

Представлення такої матриці складатиметься з масиву голів списків ненульових елементів по стовпчиках і списку трійок <i, а, p> для кожного ненульового елементу стовпчика.

Цю схему можна використовувати в перевернутому вигляді, тобто по рядках. Тоді масив голів списків зберігатиме покажчики на списки ненульових елементів рядків.

На мовіTurbo Pascal реалізація має наступний вигляд:

type

PNode = ^Node; (покажчик на вузол)

Node = record

j: word ; (використовується для індексу стовпчика)

Vol: real; (значення матриці a_ij)

Next: Pnode;

end;

PtrArray = array [1...65520 div SizeOf(PNode) of PNode];

Matr = record

n,m: word;

PBody: PtrArray;

end;

PMatr = ^Matr;

Іноді використовують алгоритми пакування даних, які не використовують зв'язаних списків. Для них потрібно менше пам'яті, але додавання і видалення ненульових елементів при такому алгоритмі зберігання даних вимагають циклічного зсуву елементів масиву. Нижче описуються чотири такі схеми.

б) Використання одновимірних масивів (векторів)

Схема І (nxm) (по стовпчиках)

Кожному елементу матриці відповідає запис, який має наступний вигляд:

Нуль в першій комірці означає кінець даного стовпчика. Друга комірка в цьому випадку містить номер наступного стовпчика. Нулі в обох комірках вказують на кінець масиву, що зберігає матрицю. Число комірок, необхідних для зберігання матриці, розраховується по формулі

2 (n + τ +1)

Розглянемо застосування Схеми І на прикладі:

Ця матриця для якої τ = 7, n = 5 зберігатиметься у вигляді масиву:

(0, 1; 2, a₂₁; 4, a₄₁; 0, 2; 5, a₅₂; 0, 3; 1, a₁₃; 3, a₃₃; 0, 4; 2, a₂₄; 0, 5; 4, a₄₅; 0, 0)

Нумеруємо пари для обчислення розміру вектора:

ℓ = (n+1+ τ)- максимальний розмір числа пар

τ - повинно зберігатися в образі матриці або обчислюватися, але може зберігатися

і в дескрипторі.

При описі типу за даною схемою виникає проблема, яка складається у наступному: j_i-ціле, a_ij1- може бути будь-яким, тому використання значень цих пар різне. При цьому використовується тип запис з варіантами.

type

Para=record

case K: word of тип i-ї пари , яка дорівнює 0 j_i

0: (j:word); i a_iji

else (val: real);

end;

Читайте також:

1. II. Багатофакторний дискримінантний аналіз.
2. Але відмінні від значення функції в точці або значення не існує, то точка називається точкою усувного розриву функції .
3. Багато уваги приділяється підготовці засідань педагогічних рад.
4. Багатоаспектне класифікування об’єктів винаходу
5. Багатоаспектний підхід до прийняття управлінськихрішень
6. Багатовимірні випадкові величини. Система двох випадкових величин
7. Багатоелектронні атоми.
8. Багатозначних слів
9. Багатозначні слова
10. Багатозначні слова
11. Багатозначність і недомовленість.
12. БАГАТОЗНАЧНІСТЬ СЛІВ

Переглядів: 1559