Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 6
з дисципліни «Програмування складних алгоритмів»
Тема «Розріджені матриці»
Варіант № 11
Лабораторна робота № 6
Розріджені матриці
Мета: ознайомитися з поняттям «розріджена матриця», її особливостями та доцільності застосування.
Завдання до лабораторної роботи
Розробити спосіб економного зберігання в пам’яті розріджених матриць. Виконати індивідуальне завдання над стисненою матрицею. Вивести матрицю до та після обробки у стисненому та розгорнутому вигляді.
Варіант
Індивідуальне завдання
11
Поміняти попарно елементи (1,2 ↔ 3,4; 5,6 ↔ 7,8; …) у кожному рядку масиву.
Теоретичні відомості
Матриця — це двовимірний об’єкт даних, що складається з m рядків і n стовпців, тому має загальні значення m*n . Якщо більшість елементів матриці мають значення 0 , то вона називається розрідженою матрицею.
Чому використовують розріджену матрицю замість простої матриці?
Зберігання: Є менше ненульових елементів, ніж нулі, і, отже, менше пам'яті можна використовувати для зберігання лише цих елементів.
Час обчислень: час обчислень можна заощадити, логічно розробивши структуру даних, яка обходить лише ненульові елементи.
Приклад розрідженої матриці:
/
Представлення розрідженої матриці двовимірним масивом призводить до втрати великої кількості пам’яті, оскільки нулі в матриці в більшості випадків не мають користі. Отже, замість того, щоб зберігати нулі з ненульовими елементами, ми зберігаємо лише ненульові елементи. Це означає зберігання ненульових елементів з потрійними (рядок, стовпець, значення).
Розріджені матричні уявлення можна зробити багатьма способами, наступними є два поширені уявлення:
Представлення масиву;
Представлення зв'язаного списку.
Метод 1. Використання масивів:
2D-масив використовується для представлення розрідженої матриці, в якій є три рядки, названі як
Рядок: індекс рядка, де розташований ненульовий елемент;
Стовпець: індекс стовпця, де розташований ненульовий елемент;
Значення: значення ненульового елемента, розташованого за індексом – (рядок, стовпець).
/
Спосіб 2: Використання зв'язаних списків
У зв'язаному списку кожен вузол має чотири поля. Ці чотири поля визначаються як:
Рядок: індекс рядка, де розташований ненульовий елемент;
Стовпець: індекс стовпця, де розташований ненульовий елемент;
Значення: значення ненульового елемента, розташованого за індексом – (рядок, стовпець);
Наступний вузол: адреса наступного вузла.
/
Результати роботи
Ініціалізуємо двовимірний масив розмірністю NхM, (4 х 8). Створюємо функцію sizeMatrix() для підрахунку кількості елементів для стисненої матриці. Для цього вкладеним циклом for() проходимось по рядках та стовпцях. Підраховуються ті елементи, які не дорівнюють нулю. Функція making_newMatrix() створює стиснену матрицю. Для цього у main() створюється динамічний масив на три рядки: рядок, стовпець, значення. Записуємо відповідні значення із розрідженої матриці у стиснену. Функції print_sparseMatrix() та print_compactMatrix() виводять початкові дані та результат на екран. Для обміну попарно елементів для кожного рядка масиву створимо функцію swapColumn().
1.4. Висновок
У ході лабораторної роботи було ознайомлено з поняттям «розріджена матриця», доцільності використання розрідженої матриці замість простої та методи реалізації. Написано програму, яка попарно змінює місцями елементи кожного рядка масиву за схемою, що подана в індивідуальному завданні.
Лістинг програми
#include
using namespace std;
const int N = 4, M = 8;
int sizeMatrix(int sparseMatrix[N][M]);
void making_newMatrix(int sparseMatrix[N][M], int** compactMatrix);
void print_sparseMatrix(int sparseMatrix[N][M]);
void print_compactMatrix(int** compactMatrix, int size);
void swapColumn(int sparseMatrix[N][M], int size);
int main()
{
int sparseMatrix[N][M] =
{
{0, 0, 3, 0, 4, 0, 2, 0},
{0, 0, 5, 7, ...
