Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Розріджені матриці
Інформація про навчальний заклад
ВУЗ:
Національний технічний університет України Київський політехнічний інститут
Інститут:
Не вказано
Факультет:
ЗІ
Кафедра:
Не вказано
Інформація про роботу
Рік:
2022
Тип роботи:
Звіт до лабораторної роботи
Предмет:
Програмування складних алгоритмів
Частина тексту файла (без зображень, графіків і формул):
Національний технічний університет України
«Київський політехнічний інститут імені Ігоря Сікорського»
ЗВІТ
до лабораторної роботи № 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 <iostream>
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, 0, 0, 0, 1},
{0, 1, 0, 0, 0, 0, 1, 0},
{0, 2, 6, 0, 0, 0, 0, 0}
};
int size = sizeMatrix(sparseMatrix);
int** compactMatrix = new int* [3];
for (int i = 0; i < 3; i++)
compactMatrix[i] = new int[size];
making_newMatrix(sparseMatrix, compactMatrix);
print_sparseMatrix(sparseMatrix);
print_compactMatrix(compactMatrix, size);
swapColumn(sparseMatrix, size);
making_newMatrix(sparseMatrix, compactMatrix);
print_sparseMatrix(sparseMatrix);
print_compactMatrix(compactMatrix, size);
delete[] compactMatrix;
return 0;
}
//Функція підрахунку кількості елементів для стисненої матриці
int sizeMatrix(int sparseMatrix[N][M])
{
int size = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (sparseMatrix[i][j] != 0)
size++;
return size;
}
//Функція створення стисненої матриці
void making_newMatrix(int sparseMatrix[N][M], int** compactMatrix)
{
int k = 0;
for (int i = 0; i < N; i++)
for (int j = 0; j < M; j++)
if (sparseMatrix[i][j] != 0)
{
compactMatrix[0][k] = i;
compactMatrix[1][k] = j;
compactMatrix[2][k] = sparseMatrix[i][j];
k++;
}
}
//Функція виведення на екран матриці у розгорнутому вигляді
void print_sparseMatrix(int sparseMatrix[N][M])
{
cout << "Sparse Matrix:\n";
int count = 0;
for (int i = 0; i < N; i++)
{
for (int j = 0; j < M; j++)
{
cout << sparseMatrix[i][j] << " ";
}
cout << endl;
}
}
//Функція виведення на екран матриці у стисненому вигляді
void print_compactMatrix(int** compactMatrix, int size)
{
cout << "\nCompact Matrix: \nRow: ";
for (int i = 0; i < size; i++)
cout << compactMatrix[0][i] << " ";
cout << "\nColumn: ";
for (int i = 0; i < size; i++)
cout << compactMatrix[1][i] << " ";
cout << "\nValue: ";
for (int i = 0; i < size; i++)
cout << compactMatrix[2][i] << " ";
cout << endl;
}
//Функція обміну стовпців
void swapColumn(int sparseMatrix[N][M], int size)
{
int j = 0;
cout << "\n\nTransform the matrix!\n";
for (int i = 0; i < N; i++)
{
swap(sparseMatrix[i][j], sparseMatrix[i][j+2]);
swap(sparseMatrix[i][j+1], sparseMatrix[i][j+3]);
swap(sparseMatrix[i][j+4], sparseMatrix[i][j + 6]);
swap(sparseMatrix[i][j+5], sparseMatrix[i][j + 7]);
}
}
Результат
/
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора