Харківський політехнічний інститут
 Скачать 174.04 Kb.
|
|
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ ТЕХНІЧНИЙ УНІВЕРСИТЕТ “ХАРКІВСЬКИЙ ПОЛІТЕХНІЧНИЙ ІНСТИТУТ” КАФЕДРА ПРОГРАМНОЇ ІНЖЕНЕРІЇ ТА ІНФОРМАЦІЙНИХ ТЕХНОЛОГІЙ УПРАВЛІННЯ ЗВІТ З ЛАБОРАТОРНОЇ РОБОТИ №1 з дисципліни “Основи теорії алгоритмів” Виконав студент групи КН-221-г Литовченко Валентин Віталійович Перевірив: Доцент. каф. ПІІТУ С. В. Солонська ХАРКІВ 2022 ЛАБОРАТОРНА РОБОТА 1. БАЗОВІ СТРУКТУРИ ДАНИХ Мета роботи: познайомитися з базовими структурами даних (список,черга, стек) та отримати навички програмування алгоритмів, що їх обробляють. 1.1 Методичні вказівки Стеки і черги - це динамічні множини, в яких елемент, що видаляється з множини операцією Delete, що не задається довільно, а визначається структурою множини. Саме, зі стеку (stack) можна видалити тільки той елемент, який був у нього доданий останнім: стек працює за принципом «останнім прийшов - першим пішов» (last-in, first-out - LIFO). З черги (queue), навпаки, можна видалити тільки той елемент, який знаходився в черзі довше всього: працює принцип «першим прийшов - першим пішов» (first-in, first-out — FIFO).У зв'язаному списку (або просто списку; linked list) елементи лінійно впорядковані, але порядок визначається не номерами, як у масиві, а покажчиками, що входять до складу елементів списку. Списки є зручним способом реалізації динамічних множин.Якщо кожен стоїть у черзі запам'ятає, хто за ним стоїть, після чого все безладно розсядуться на лавочці, вийде однобічно пов'язаний список; якщо він запам'ятає ще й того, хто попереду, буде двобічно зв'язаний список. Іншими словами, елемент двобічно зв'язаного списку (doubly linked list) - це запис, що містить три поля: key (ключ) і два покажчика next (наступний) і prev (попередній). Крім цього, елементи списку можуть містити додаткові дані. У різних ситуаціях використовуються різні види списків. В одне сторін незв'язаному (singly linked) списку відсутні поля prev. У впорядкованому (sorted) списку елементи розташовані в порядку зростання ключів, так що у голови списку ключ найменший, а у хвоста списку - найбільший, на відміну від неврегульованого (unsorted) списку. У кільцевому списку (circularlist) поле prev голови списку вказує на хвіст списку, а поле next хвоста списку вказує на голову списку. 1.2 Завдання Розробити програму, яка читає з клавіатури послідовність N цілих чисел (1 < N < 256), жодне з яких не повторюється, зберігає їх до структури даних (згідно завданню) та видає на екран наступні характеристики: кількість елементів; середнє арифметичне збережених елементів; мінімальний та максимальний елемент; четвертий елемент послідовності; елемент, що йде перед мінімальним елементом. Наголосимо, що всі характеристики потрібно визначити із заповненої структури даних. Дозволено використовувати лише ті операції, що притаманні заданій структурі, наприклад, заборонено отримувати доступ до елементу із довільною позицією у черзі, яку реалізовано на базі масиву. Використовувати готові реалізації структур даних (наприклад, STL) заборонено. 1.3 Варіанти завдань Використати наступні структури даних. 1 Черга. 2 Стек. 3 Однобічно зв’язний список. 4 Двобічно зв’язний список. 5 Кільцевий список. 6 Масив із довільним доступом. Варіант: 6. Програмний код: #include using namespace std; int main(int argc, char* argv[]) { int N, i; double Sym = 0; cout << "Enter the number of elements in the array: "; cin >> N; while (N < 1 || N>256) { cout << "Error,enter a number from 1 to 256" << endl; cin >> N; } int a[N]; for (i = 0; i < N; i++) { cout << "Enter the number a[" << i << "]="; cin >> a[i]; } for (i = 0; i < N; i++) { cout << "a[" << i << "]=" << a[i] << endl; } for (i = 0; i < N; i++) { Sym += a[i]; } int max = a[0]; for (int i = 0; i < N; ++i) { if (a[i] > max) { max = a[i]; } } int min = a[0]; for (int i = 0; i < N; ++i) { if (a[i] < min) { min = a[i]; } } int c; c = min - 1; cout << "Amount of elements: " << N << endl; cout << "Average = " << Sym / N << endl; cout << "Minimum element: " << min << endl; cout << "Maximum element: " << max << endl; if (N < 4) { cout << "The fourth element of the sequence is missing" << endl; } else { cout << "The fourth element of the sequence: " << a[3] << endl; } cout << "Element preceding the minimum element: " << c << endl; return 0; } Приклад правильного виконання програми:  N вводиться некорректно, програма пропонує спробувати ввести ще раз,поки не введеш число від 1 до 256.Також картинка демонструє,що буде,якщо четвертий елемент послідовності відсутній.  ВИСНОВКИ Виконавши лабораторну роботу, було закріплено ряд знань щодо реалізації масиву із довільним доступом у мові програмування С ++. Отримано практичні навички створення та використання базових структур даних (однобічно зв’язний список) та вдосконалено навички програмування алгоритмів, що їх обробляють.У процесі виконання лабораторної роботи виконано ряд завдань на реалізацію функції очищення пам’яті, у якій зберігалися елементи списку. СПИСОК ВИКОРИСТАНИХ ДЖЕРЕЛ Методичні вказівки по виконанню лабораторних робіт за курсом «Основи теорії алгоритмів» для студентів, які навчаються спеціальністю “Інженерія програмного забезпечення ” Укладач: Стратієнко Н.К. |