МАРК РЕГНЕРУС ДОСЛІДЖЕННЯ: Наскільки відрізняються діти, які виросли в одностатевих союзах
РЕЗОЛЮЦІЯ: Громадського обговорення навчальної програми статевого виховання ЧОМУ ФОНД ОЛЕНИ ПІНЧУК І МОЗ УКРАЇНИ ПРОПАГУЮТЬ "СЕКСУАЛЬНІ УРОКИ" ЕКЗИСТЕНЦІЙНО-ПСИХОЛОГІЧНІ ОСНОВИ ПОРУШЕННЯ СТАТЕВОЇ ІДЕНТИЧНОСТІ ПІДЛІТКІВ Батьківський, громадянський рух в Україні закликає МОН зупинити тотальну сексуалізацію дітей і підлітків Відкрите звернення Міністру освіти й науки України - Гриневич Лілії Михайлівні Представництво українського жіноцтва в ООН: низький рівень культури спілкування в соціальних мережах Гендерна антидискримінаційна експертиза може зробити нас моральними рабами ЛІВИЙ МАРКСИЗМ У НОВИХ ПІДРУЧНИКАХ ДЛЯ ШКОЛЯРІВ ВІДКРИТА ЗАЯВА на підтримку позиції Ганни Турчинової та права кожної людини на свободу думки, світогляду та вираження поглядів Контакти
Тлумачний словник |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||
Існує багато способів зберігання розріджених матриць.Подання даних у вигляді розрідженої матриці Спосіб 1: Упакований спосіб зберігання розріджених матриць. Зберігаються всі ненульові елементи
рядок стовпчик
Якщо t - кількість ненульові символів, то необхідно 3t комірок. При збереженні в упакованому вигляді розрідженої матриці необхідно передбачити можливість додавання нових ненульових елементів.
а) Використання зв'язаних списків. Кожному елементу aij¹0 у пам’яті комп’ютера відповідає запис, який зберігається по стовпчикам, тобто елементу aij буде відповідати деякий запис j- стовпчика матриці. Кожен запис являє собою впорядковану трійку
Номер рядка Значення Покажчик на наступний елемент
Представлення такої матриці складатиметься з масиву голів списків ненульових елементів по стовпчиках і списку трійок <i, а, p> для кожного ненульового елементу стовпчика. Цю схему можна використовувати в перевернутому вигляді, тобто по рядках. Тоді масив голів списків зберігатиме покажчики на списки ненульових елементів рядків.
На мовіTurbo Pascal реалізація має наступний вигляд: type PNode = ^Node; (покажчик на вузол) Node = record j: word ; (використовується для індексу стовпчика) Vol: real; (значення матриці aij) 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, a21; 4, a41; 0, 2; 5, a52; 0, 3; 1, a13; 3, a33; 0, 4; 2, a24; 0, 5; 4, a45; 0, 0)
Нумеруємо пари для обчислення розміру вектора:
ℓ = (n+1+ τ)- максимальний розмір числа пар τ - повинно зберігатися в образі матриці або обчислюватися, але може зберігатися і в дескрипторі.
При описі типу за даною схемою виникає проблема, яка складається у наступному: ji-ціле, aij1- може бути будь-яким, тому використання значень цих пар різне. При цьому використовується тип запис з варіантами.
type Para=record case K: word of тип i-ї пари , яка дорівнює 0 ji 0: (j:word); i aiji else (val: real); end;
Читайте також:
|
||||||||||||||||||||||||||||||||||||||||||||||||||||
|