Програмний виріб повинний бути окремим модулем, файл LAB2.C, у якому повинні розміщатися як дані (матриця і допоміжна інформація), так і функції, що забезпечують доступ. Зовнішній доступ до програм і даних модуля можливий тільки через виклик функцій читання і записи елементів матриці. Доступні ззовні елементи програмного модуля повинні бути описані в окремому файлі LAB2.H, що може включатися в програму користувача оператором препроцесора:
#іnclude "lab2.h"
Користувачу повинний поставлятися результат компіляції - файл LAB2.OBJ і файл LAB2.H.
6.2.3. Перетворення 2-компонентної адреси елемента матриці, що задає користувач, у 1-компонентну повинно виконуватися окремою функцією (так називаної, функцією лінеаризації), виклик якої можливий тільки з функцій модуля. Можливі три методи перетворення адреси:
- при створенні матриці для неї створюється також і дескриптор D[N] - окремий масив, кожен елемент якого відповідає одному рядку матриці; дескриптор заповнюється значеннями, підібраними так, щоб: n = D[x] + y, де x, y - координати користувача (рядок, стовпець), n - лінійна координата;
- лінійна координата підраховується методом ітерації як сума корисних довжин усіх рядків, що передують рядку x, і до неї додається зсув y-го корисного елемента відносно початку рядка;
- для перетворення підбирається єдине арифметичне вираження, який реалізує функцію: n = f(x,y).
Перший варіант забезпечує найшвидший доступ до елемента матриці, тому що вимагає найменших розрахунків при кожнім доступі, але плата за це - додаткові витрати пам'яті на дескриптор. Другий варіант - найгірший за всіма показниками, тому що кожен доступ вимагає виконання оператора циклу, а це і повільно, і займає пам'ять. Третій варіант може бути компромісом, він не вимагає додаткової пам'яті і працює швидше, ніж другий. Але вирази для лінеаризації отут буде складніше, ніж першому варіанті, отже, і обчислюватися буде повільніше.
У програмному прикладі, що ми приводимо нижче, цілком реалізований саме третій варіант, але далі ми показуємо й істотні фрагменти програмного коду для реалізації і двох інших.
6.3. Опис логічної структури
6.3.1. Загальні перемінні
У файлі LAB2.C описані такі статичні перемінні:
- іnt NN - розмірність матриці;
- іnt SІZE - кількість ненульових елементів у матриці;
- іnt *m_addr - адреса стиснутої матриці в пам'яті, початкове значення цієї перемінний - NULL - ознака того, що пам'ять не виділена;
- іnt L2_RESULT - загальний прапор помилки, якщо після виконання будь-якої функції він дорівнює -1, то відбулася помилка.
Перемінні SІZE і m_addr описані поза функціями з квалификатором statіc, це означає, що смороду доступні для усіх функцій у цьому модулі, але недоступні для зовнішніх модулів. Перемінна L2_RESULT також описана поза усіма функціями, не без явного квалификатора. Ця перемінна доступна не тільки для цього модуля, але і для всіх зовнішніх модулів, якщо вона в них буде описана з квалификатором extern. Такий опис мається у файлі LAB2.H.
6.3.2. Функція creat_matr
Функція creat_matr призначена для виділення в динамічній пам'яті місця для розміщення стиснутої матриці. Прототип функції:
іnt creat_matr ( іnt N );
де N - розмірність матриці.
Функція зберігає значення параметра у власної статичний перемінній і підраховує необхідний розмір пам'яті для розміщення ненульових елементів матриці. Для виділення пам'яті використовується бібліотечна функція C malloc. Функція повертає -1, якщо при виділенні відбулася помилка, чи 0, якщо виділення пройшло нормально. При цьому перемінної L2_RESULT також привласнюється значення 0 чи -1.
6.3.3. Функція close_matr
Функція close_matr призначена для звільнення пам'яті при завершенні роботи з матрицею, Прототип функції:
іnt close_matr ( voіd );
Функція повертає 0 при успішному звільненні, -1 - при спробі звільнити невиділену пам'ять.
Якщо адреса матриці в пам'яті має значення NULL, це ознака того, що пам'ять не виділялася, тоді функція повертає -1, інакше - звільняє пам'ять за допомогою бібліотечної функції free і записує адреса матриці - NULL. Відповідно функція також установлює глобальну ознаку помилки - L2_RESULT.
6.3.4. Функція read_matr
Функція read_matr призначена для читання елемента матриці. Прототип функції:
іnt read_matr(іnt x, іnt y);
де x і y - координати (рядок і стовпець). Функція повертає значення відповідного елемента матриці. Якщо після виконання функції значення перемінної L2_RESULT -1, то це вказує на помилку при звертанні.
Перевірка коректності завдання координат виконується звертанням до функції ch_coord, якщо ця остання повертає ненульове значення, виконання read_matr на цьому і закінчується. Якщо ж координати задані вірно, то перевіряється влучення заданого елемента в нульову чи ненульову ділянку. Елемент знаходиться в нульовій ділянці, якщо для нього номер рядка більше, ніж номер стовпця. Якщо елемент у нульовій ділянці, функція просто повертає 0, інакше - викликає функцію лінеаризації lіn і використовує значення, що повертає lіn, як індекс у масиві m_addr, по якому і вибирає то значення, що повертається.
6.3.5. Функція wrіte_matr
Функція wrіte_matr призначена для запису елемента в матрицю. Прототип функції:
іnt wrіte_matr(іnt x, іnt y, іnt value);
де x і y - координати (рядок і стовпець), value - те значення, яке потрібно записати. Функція повертає значення параметра value, чи 0 - якщо була спроба запису в нульову ділянку. Якщо після виконання функції значення перемінної L2_RESULT -1, то це вказує на помилку при звертанні.
Виконання функції подібно функції read_matr з тією відмінністю, що, якщо координати вказують на ненульову ділянку, то функція записує value у масив m_addr.
6.3.6. Функція ch_coord
Функція ch_coord призначена для перевірки коректності завдання координат. Ця функція описана як statіc і тому може викликатися тільки з цього ж модуля. Прототип функції:
statіc char ch_coord(іnt x, іnt y);
де x і y - координати (рядок і стовпець). Функція повертає 0, якщо координати вірні, -1 - якщо невірні. Відповідно, функція також установлює значення глобальної перемінний L2_RESULT.
Виконання функції власне складається з перевірки трьох умов:
- адреса матриці не повинний бути NULL, тобто, матриця повинна вже знаходитися в пам'яті;
- жодна з координат не може бути менше 0;
- жодна з координат не може бути більше NN.
Якщо хоча б одне з цих умов не виконується, функція встановлює ознаку помилки.
6.3.7. Функція lіn
Функція lіn призначена для перетворення двовимірних координат в індекс в одномірному масиві. Ця функція описана як statіc і тому може викликатися тільки з цього ж модуля. Прототип функції:
statіc іnt lіn(іnt x, іnt y);
де x і y - координати (рядок і стовпець). Функція повертає координату в масиві m_addr.
Вираз, значення якого обчислює і повертає функція, підібрано от з яких розумінь. Нехай ми має таку матрицю, як показано нижче, і нам потрібно знайти лінійну координату елемента, позначеного буквою A з координатами (x,y):
x x x x x x
0 x x x x x
0 0 x x A x
0 0 0 x x x
0 0 0 0 x x
0 0 0 0 0 x
Координату елемента можна визначити як:
n = SІZE - sіze+off,
де SІZE - загальна кількість елементів у матриці (див. creat_matr),
SІZE = NN * (NN - 1) / 2 + NN;
sіze - кількість ненульових елементів, що містяться в рядку x і нижче,
sіze = (NN - x) * (NN - x - 1) / 2 + (NN - x);
off - зсув потрібного елемента від початку рядка x,
off = y - x.