Конспекти лекцій та Лабораторні роботи з дисципліни "Алгоритми та структури даних" для III курсу спеціальності 121 "Інженерія програмного забезпечення" ОКР "Фаховий молодший бакалавр" Херсонського політехнічного фахового коледжу Державного університету "Одеська політехніка"
Ознайомитись з IDE Visual Studio. Навчитися створювати проект. Здобути навички у знаходженнi мінімального і максимального значення в масиві. Обладнання та ПЗ: персональний комп’ютер, Visual Studio 2008.
Персональний комп’ютер, Visual Studio 2008 або інша середа розробки для мови C++
Крім одновимірних масивів, тобто таких, де позиція елемента визначається за допомогою одного індексу, у практиці розв’язання задач часто застосовуються багатовимірні масиви. У них позиція елемента визначається записом декількох індексів. Найбільш розповсюджені двовимірні масиви або матриці. Матриці являють собою порядковий запис декількох одновимірних масивів. Місце розташування кожного елемента визначається за допомогою двох індексів — номера рядка і номера стовпця, тобто порядкового номера в рядку. Індекси двовимірних масивів записуються в квадратних дужках і нумерація індексів починається з нуля (0).
Наприклад, двовимірний масив цілих чисел int а[3][4], що має три рядки та чотири стовпці, представлений в таблиці:
| Ст1 | Ст2 | Ст3 | Ст4 | |
|---|---|---|---|---|
| Р1 | а[0][0] | а[0][1] | а[0][2] | а[0][3] |
| Р2 | а[1][0] | а[1][1] | а[1][2] | а[1][3] |
| Р3 | а[2][0] | а[2][1] | а[2][2] | а[2][3] |
У пам’яті комп’ютера масив розташовується безперервно за рядками:
а[0][0], а[0][1], а[0][2], а[0][3], а[1][0], а[1][1], а[1][2], а[1][3], … а[2][3].
Двовимірні (і багатовимірні) масиви оголошуються так:
int arr1[2][5] = {1, 5, 3, 7, 4,10, 11, 13, 14, 25};
int arr2[][5] = {1, 5, 3, 7, 4, 10, 11, 13, 14, 25};
int arr3[][5] = { {1, 5, 3, 7, 4}, {10, 11, 13, 14, 25} };
Масив задається або списком елементів у тому порядку, в якому вони розташовані у пам’яті, або подається як масив масивів, кожний з яких поміщається в свої фігурні дужки {}. При оголошенні і одночасному ініціюванні багатовимірних масивів можна опускати кількість індексів тільки першого виміру. Якщо ініціювання не здійснюється під час оголошення масиву, то кількість індексів треба вказувати явно.
У багатьох задачах розмір масиву може бути відомий лише під час виконання програми. Для цього використовують динамічні масиви, які створюються під час виконання програми за допомогою оператора new (у C++) або функцій malloc/calloc (у C).
Для створення динамічного двовимірного масиву розміром n x m можна використати масив покажчиків:
int n = 10, m = 10;
int** arr = new int*[n];
for (int i = 0; i < n; ++i) {
arr[i] = new int[m];
}
Заповнення випадковими числами:
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
arr[i][j] = rand() % 11 - 5; // від -5 до 5
Звільнення пам’яті:
for (int i = 0; i < n; ++i)
delete[] arr[i];
delete[] arr;
int x = 3, y = 4, z = 5;
int*** arr = new int**[x];
for (int i = 0; i < x; ++i) {
arr[i] = new int*[y];
for (int j = 0; j < y; ++j) {
arr[i][j] = new int[z];
}
}
// ... використання ...
// Звільнення пам’яті:
for (int i = 0; i < x; ++i) {
for (int j = 0; j < y; ++j)
delete[] arr[i][j];
delete[] arr[i];
}
delete[] arr;
Переваги:
Недоліки:
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
// робота з arr[i][j]
}
}
srand(time(0));
for (int i = 0; i < n; ++i)
for (int j = 0; j < m; ++j)
arr[i][j] = rand() % 11 - 5; // від -5 до 5
Завантажити Visual Studio. Знайдіть на робочому столі ярлик з Visual Studio 2008 або Пуск → Всі програми→ Microsoft → Microsoft Visual Studio 2008.
Створити новий проект «Visual C++ (консольное приложение Win32)». Файл → Cтворити → Проект, тип проекту «Консольное приложение Win32».
Перевірте роботу прикладів ха посиланнями нижче, поясніть їх роботу
Розв’яжіть задачу згідно з варіантом. Знайдіть час роботи програми.
Варіант 1. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Для кожного рядка масиву знайти суму елементів
Варіант 2. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Для кожного стовпця масиву знайти суму елементів.
Варіант 3. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Обчислити суму всіх елементів масиву.
Варіант 4. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Підрахувати кількість нульових елементів.
Варіант 5. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Обчислити середнє арифметичне ненульових елементів масиву.
Варіант 6. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Для кожного рядка масиву з непарним номером знайти середнє арифметичне елементів.
Варіант 7. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Для кожного стовпця масиву з парним номером знайти суму елементів.
Варіант 8. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Для кожного рядка масиву знайти мінімальний елемент.
Варіант 9. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Для кожного стовпця масиву можна знайти максимальний елемент.
Варіант 10. Даний двовимірний динамічний масив розміру 10x10 заповнений випадковими числами. Підрахувати кількість рядків, що містять лише парні числа.
rand().