Лабораторна робота 2
Робота з переліками та структурами
1 Завдання на лабораторну роботу
1.1 Перелік для представлення місяців року
Створити перелік для представлення місяців року. Реалізувати та продемонструвати перевантаження операцій ++
і -- так, щоб після грудня йшов січень, а перед січнем – грудень.
1.2 Точки в тривимірному просторі
Створити структуру для опису точки в тривимірному просторі (тип точки). Написати програму, яка обчислює відстань між двома точками. Для обчислення відстані створити функцію з двома параметрами типу структури для представлення точок.
1.3 Представлення й обробка даних про студентів
Створити структуру для представлення даних про студента. Структура повинна містити такі елементи даних:
- номер студентського посвідчення (
unsigned int); - прізвище (рядок у вигляді
масиву символів); - оцінки за останню сесію у вигляді масиву цілих від 0 до 100 (оцінки за предметами).
Реалізувати функцію яка здійснює виведення даних про студента у консольне вікно. Першим параметром функції повинна бути структура, яка описує студента.
Реалізувати функції, які отримують масив вказівників на студентів і довжину масиву і здійснюють
- сортування масиву за ознакою, яка наведена в індивідуальному завданні;
- пошук даних про студентів, які відповідають умові, наведеній в індивідуальному завданні.
- виведення всіх елементів масиву в консольне вікно.
Під час сортування масиву структур замість обміну місцями двох структур здійснювати обмін місцями елементів масиву вказівників.
Створити масив студентів. Створити масив вказівників на студентів, заповнивши його адресами структур з масиву студентів. Продемонструвати сортування й пошук студентів.
Індивідуальні завдання:
| №№ студента у списку | Умова сортування | Умова вибору даних |
|---|---|---|
| 1 | За алфавітом | З середнім балом в інтервалі "64" – "74" |
| 2 | За збільшенням середнього балу | З довжиною прізвища понад 7 літер |
| 3 | За зменшенням довжини прізвища | З середнім балом в інтервалі "90" – "100" |
| 4 | За зменшенням номера студентського посвідчення | Прізвище починається з літери "А" |
| 5 | За зменшенням середнього балу | Прізвище закінчується літерою "а" |
| 6 | За збільшенням суми оцінок | З непарною довжиною прізвища |
| 7 | За збільшенням довжини прізвища | З непарними номерами студентських посвідчень |
| 8 | За алфавітом | З парними номерами студентських посвідчень |
| 9 | За алфавітом у зворотному порядку | Оцінок "A" більше, ніж оцінок "D" |
| 10 | За збільшенням номера студентського посвідчення | Прізвище містить літеру "е" |
| 11 | За зменшенням добутку оцінок | З непарною довжиною прізвища |
| 12 | За збільшенням добутку оцінок | З довжиною прізвища менш ніж 8 літер |
| 13 | За алфавітом | З парною сумою оцінок |
| 14 | За алфавітом у зворотному порядку | З непарними номерами студентських посвідчень |
| 15 | За алфавітом | З середнім балом в інтервалі "75" – "81" |
| 16 | За збільшенням середнього балу | З довжиною прізвища менш ніж 7 літер |
| 17 | За збільшенням довжини прізвища | З середнім балом в інтервалі "82" – "89" |
| 18 | За збільшенням номера студентського посвідчення | Прізвище починається з літери "А" |
| 19 | За збільшенням середнього балу | Прізвище закінчується літерою "а" |
| 20 | За збільшенням суми оцінок | З парною довжиною прізвища |
| 21 | За збільшенням довжини прізвища | З парними номерами студентських посвідчень |
| 22 | За алфавітом у зворотному порядку | З парними номерами студентських посвідчень |
| 23 | За алфавітом | Оцінок "A" більше, ніж оцінок "E" |
| 24 | За збільшенням номера студентського посвідчення | Прізвище містить літеру "о" |
| 25 | За зменшенням добутку оцінок | З парною довжиною прізвища |
| 26 | За зменшенням добутку оцінок | З довжиною прізвища менш ніж 9 літер |
| 27 | За алфавітом у зворотному порядку | З непарною сумою оцінок |
| 28 | За алфавітом | З непарними номерами студентських посвідчень |
1.4 Робота зі зв'язаним списком
Написати програму, яка забезпечує файлове введення та виведення і включає індивідуальне завдання лабораторної роботи № 5 курсу "Основи програмування (частина 1)". Слід реалізувати такі дії:
- визначення константи (
n) яка визначає кількість стовпців двовимірного масиву - відкриття файлу для читання (файл повинен бути підготовлений за допомогою текстового редактора)
- читання цілих чисел до кінця файлу і зберігання їх у зв'язаному списку
- створення двовимірного масиву в динамічній пам'яті; кількість рядків повинна бути обчислена на основі кількості зчитаних з файлу значень та визначеної кількості стовпців
- заповнення двовимірного масиву рядок за рядком; відсутні елементи останнього рядка повинні бути заповнені нулями
- видалення елементів зв'язаного списку з динамічної пам'яті
- реалізація індивідуального завдання лабораторної роботи № 5 курсу "Основи програмування (частина 1)".
- зберігання результатів в новому файлі
- видалення масивів операцією
delete.
2 Методичні вказівки
2.1 Користувацькі типи
Засоби C ++, зокрема, об'єктно-орієнтовані, націлені в першу чергу на створення користувацьких типів. Мова C++ дозволяє створювати власні типи, використання яких може бути не менш зручним і більш виразним, ніж використання стандартних типів, що існують.
У більшості випадків для створення користувацьких типів застосовують класи. Але іноді також можна використовувати інші мовні конструкції – переліки, структури й об'єднання.
2.2 Переліки
Тип переліку визначає набір цілих констант. Перелік може бути визначений за допомогою ключового слова
enum,
після якого у фігурних дужках розміщують список елементів, розділених комами. Перша константа приймає усталене
значення 0, наступна – 1 тощо.
Можна створити безіменні та іменовані переліки. Безіменний перелік фактично є списком констант. Наприклад,
enum { red, green, blue };
Такий перелік еквівалентний визначенню констант:
const int red = 0; const int green = 1; const int blue = 2;
Необхідні значення можна визначити явно. Значення наступних елементів обчислюють шляхом додавання одиниці:
enum { one = 1, three = 3, four, nine = 9, ten };
// four == 4, ten == 10
Іменований перелік у C++ визначає новий тип даних. Цей новий тип може бути використаний для визначення змінних:
enum Colors { red, green, blue };
Colors c = blue;
На відміну від опису typedef, типи даних, які визначає користувач, зокрема перелік, не є синонімами
наявних типів. Наприклад, в нашому випадку не можна присвоїти цілі значення змінним типу Colors, тільки
значення red, green та blue. Але навпаки, присвоєння цілим змінним
значень типу Colors є цілком коректним. Змінні таких типів можна використовувати у виразах.
Colors c; c = 1; // Помилка! c = green; // OK int i = c; // OK i = c + 1; // OK
Для переліків можна перевантажувати деякі операції, наприклад ++ і --.
Перевантаження операцій – це потужний механізм визначення поведінки для об'єктів користувацьких типів. Завдяки
перевантаженню операцій над об'єктами можна виконувати дії з використанням більшості операторів мови С++. Наприклад,
якщо для об'єкта a перевантажена операція додавання до нього цілого значення, у програмі можна
використовувати вираз a + 1. В такий спосіб можна створювати типи об'єктів, робота з якими мало відрізняється
від роботи з примітивними типами. Для класів можна перевантажувати майже всі операції, для переліків – лише деякі.
Для того, щоб операція вважалась перевантаженою, необхідно створити так звану операторну функцію. Ім'я цієї функції
складається зі слова operator, після якого розташовано оператор, який ми хочемо перевантажити.
Аргументи операторної функції – операнди операції. Докладно синтаксис операторних функцій буде розглянуто під
час розгляду синтаксису класів. У прикладі 3.1 перевантаження операцій реалізовано для переліку "День тижня".
Оскільки традиційні переліки додають імена констант у глобальну область видимості, збільшується ймовірність конфліктів імен. Для уникнення таких конфліктів у сучасних версіях C++ для звернення до окремих констант переліку зазвичай використовують префікс (ім'я типу переліку та операція області видимості):
Colors c = Colors::green;
Починаючи з версії C++11, виникла можливість обмеження видимості елементів переліку областю видимості самого переліку.
Створюють спеціальний різновид переліку – перелік з областю видимості (scoped enum), додаючи
ключове слово class або struct після enum:
enum class Colors { red, green, blue };
Тепер до елементів переліку можна звертатися тільки через ім'я переліку, бо тепер елементи не є глобальними константами:
Colors c1 = Colors::green; Colors c2 = green; // Помилка!
2.3 Структури
Структури дозволяють об'єднати кілька елементів даних різних типів. З такою групою можна працювати як з одним цілим. Наприклад:
struct
{
int i;
double d;
} pair;
Змінна pair містить два елементи даних (поля), з якими можна працювати,
використовуючи імена, до яких ми звертаємось через крапку:
pair.d = 1.5; pair.i = 3; double y = pair.d + pair.i;
Аналогічна конструкція присутня у мові C.
Окремі поля – це фактично змінні відповідних типів, над якими можна виконувати всі дії, дозволені для цих типів.
У мові С++ зазвичай спочатку визначають новий тип структури даних і пізніше створювати змінні цього типу. Після
ключового слова struct визначається ім'я типу, яке потім використовується для створення нових
об'єктів типу структури. Наприклад:
struct Pair
{
int i;
double d;
}; // крапка з комою обов'язкова
Можна створити змінну типу Pair:
Pair p;
Мова C не підтримує такого опису типу. У мові C можна створювати типи структур, але для цього застосовують інший синтаксис:
typedef struct
{
int i;
double d;
} Pair;
Цей синтаксис також доступний у C++, але вважається небажаним.
Типи даних окремих елементів можуть бути однаковими, наприклад:
struct Point
{
int x;
int y;
};
В цьому випадку імена елементів даних можна вказувати через кому:
struct Point
{
int x, y;
};
Структура, як і масив – це складений тип даних. Загальною рисою складених типів даних є можливість звернення до групи даних через одне ім'я. Складений тип даних може включати багато елементів. Але різні складені типи передбачають різні шляхи створення змінних і надають різні можливості.
- Усі елементи масиву повинні бути одного типу, елементи структури можуть бути різних типів.
- Масив описується через визначення загальної кількості елементів, тоді як всі елементи структур описуються й іменуються окремо.
- Звертатися до елементів масиву необхідно через визначення індексу, а до елементів структури – через імена.
Наприклад, можна створити змінну типу структури:
struct
{
double x, y;
} point_struct;
Можна виконати типові дії над елементами даних:
point_struct.x = 5; point_struct.y = point_struct.x; std::cout << point_struct.x << point_struct.y;
Альтернативне рішення – створити масив point_arr і виконувати аналогічні дії:
double point_arr[2]; point_arr[0] = 5; point_arr[1] = point_arr[0]; std::cout << point_arr[0] << point_arr[1];
Для забезпечення більшої схожості можна, наприклад, визначити константи x та y:
const int x = 0; const int y = 1; double point_arr[2]; point_arr[x] = 5; point_arr[y] = point_arr[x]; std::cout << point_arr[x] << point_arr[y];
Але розбіжності залишаються. Існує ще багато синтаксичних відмінностей. Головне те, що структури створюють для опису сутності, різні атрибути якої мають різний сенс. Масиви створюють для роботи з великою кількістю однотипних сутностей.
Зазвичай структури використовують для опису сутностей реального світу. Наприклад, можна описати тип структури для представлення країни:
struct Country
{
char name[20];
double area;
long population;
};
Тепер замість роботи з окремими змінними ми створюємо одну змінну. Це забезпечує цілісність даних:
Country France; // France є змінною типу Country
Структури, як і інші визначені користувачем типи даних, зазвичай визначаються в глобальній області видимості. Синтаксис мови C++ дозволяє створювати змінні нового типу безпосередньо після його визначення.
struct Country
{
char name[20];
double area;
long population;
} France; // France є змінною типу Country
Визначення змінних разом з типом (або без імені типу) не рекомендуються у мові C++. Кращий підхід передбачає окреме визначення типів даних і змінних.
Під час створення змінної типу структури можна здійснити її ініціалізацію. Значення елементів ініціалізуються в порядку опису:
Country France = { "France", 551695, 67750000 };
На відміну від масивів, оператор присвоювання виконує поелементне копіювання однієї структури в іншу:
Country someCountry;
someCountry = France; // поелементне копіювання
Можна створювати вказівники на структури. Для того, щоб описати вказівник на структуру, застосовують такий синтаксис:
Country* pCountry = &someCountry; (*pCountry).area = 551695;
Дужки обов'язкові, оскільки пріоритет операцій передбачає спочатку отримання елемента, а потім розіменування:
*pCountry.area = 551695; // Помилка. pCountry - не структура, area - не вказівник
Для спрощення доступу до елементів структур, на які вказує вказівник,
використовується спеціальна операція ->. Наприклад:
Country *pCountry = &someCountry; pCountry->area = 551695;
На відміну від масивів, об'єкти типу структури передаються у функції за значенням. Це означає, що функція
працює з копіями об'єктів. Це також стосується елементів масивів, які розташовані всередині структури. Вони
також копіюються під час присвоєння одній структурі іншої або під час передачі параметрів. Розглянемо такий
приклад. Структура містить масив фіксованої довжини n. Спеціальна допоміжна функція
print() здійснює виведення елементів масиву цілих:
const int n = 4;
struct Array
{
int arr[n];
};
void print(int *arr_n)
{
for (int* p = arr_n; p < arr_n + n; p++) {
cout << *p << " ";
}
cout << endl;
}
Функція tryToModify() отримує структуру як параметр, змінює значення елементів масиву, збільшуючи
їх на одиницю, а потім здійснює виведення значень елементів на екран:
void tryToModify(Array a)
{
for (int i = 0; i < n; i++)
{
a.arr[i]++;
}
print(a.arr); // 2 3 4 5
}
У функції main() здійснюється ініціалізація структури, виклик функції та виведення значень
елементів масиву після виклику:
int main()
{
Array a = { { 1, 2, 3, 4 } }; // вкладені фігурні дужки обов'язкові
tryToModify(a);
print(a.arr); // 1 2 3 4
return 0;
}
Значення елементів не змінилися. Якщо необхідно змінити значення елементів структури всередині тіла функції, слід використовувати аргументи типу посилання:
void tryToModify(Array &a)
{
for (int i = 0; i < n; i++)
{
a.arr[i]++;
}
print(a.arr); // 2 3 4 5
}
int main()
{
Array a = { { 1, 2, 3, 4 } };
tryToModify(a);
print(a.arr); // 2 3 4 5
return 0;
}
Навіть якщо не потрібно змінювати дані всередині функції, можна використовувати посилання на константні типи, що підвищить продуктивність програми через копіювання адреси замість величезного блоку даних:
struct LargeData
{
// Деяка велика структура
};
void someFunc(const LargeData& data)
{
...
};
Структура може містити в собі іншу структуру.
Якщо структура містить низку змінних, які можуть мати лише дуже невелике число можливих значень, можна заощадити пам'ять за допомогою бітових полів, вказавши максимальний розмір поля у бітах. Оголошення бітового поля містить ім'я деякого цілого типу, за яким слідує ім'я поля, а потім двокрапка, а потім розмір бітового поля.
struct Flags
{
unsigned int logical : 1; // один біт
unsigned int tinyInt : 3; // крихітне ціле
};
За допомогою бітових полів кілька значень можна зберігати в одному байті. Це не працює, якщо бітові поля чергуються з небітовими полями. Бітові поля можна також використовувати у визначеннях класів.
На відміну від мови програмування C, структури у C++ можуть мати функції-елементи. Взагалі структури підтримують увесь синтаксис класів. Єдина відмінність полягає в тому, що усталено елементи структури є відкритими, але це можна змінити за допомогою відповідних директив. Оскільки приховування даних є дуже важливим з точки зору об'єктно-орієнтованого програмування, для створення повноцінних користувацьких типів використовують саме класи, а не структури. Структури, як правило, використовуються для групування даних, а не замість класів.
2.4 Об'єднання
Об'єднання (union) – це структура, у якій всі елементи розташовані за однією адресою.
В кожен момент в об'єднанні може зберігатися значення тільки одного з елементів. У наведеному нижче прикладі об'єкт об'єднання
може зберігати дійсне або ціле значення, але не одночасно обидва. Спроба присвоїти значення другому елементу призводить
до псування значення першого елемента, оскільки насправді пам'ять виділена тільки для одного зі значень.
union FloatAndInt
{
float f;
int i;
};
FloatAndInt fi;
fi.i = 2;
fi.f = 100;
cout << fi.i << endl; // 1120403456
fi.i = 3;
cout << fi.f << endl; // 4.2039e-45
Об'єднання може бути використане для створення масивів, елементи яких мають різні типи. Крім того, можна використати об'єднання для кодування інформації, а також для аналізу внутрішнього представлення даних. У наведеному вище прикладі число 1120403456, якщо його перевести у двійкову систему, показує внутрішнє представлення числа 100.0 з рухомою крапкою.
Можна створювати анонімні об'єднання:
union { int a; const char* p; };
a = 1;
p = "name"; // a і p немає сенсу використовувати одночасно
Після використання p значення a буде зіпсоване.
Об'єднання може містити функції-елементи.
Іноді об'єднання використовують як частину даних структур для опису взаємно несумісних даних. Наприклад, можна створити структуру для опису деякого студента. Залежно від форми навчання (контрактна / бюджетна) студент або сплачує за навчання певну суму, або потенційно може отримувати стипендію. Структура може бути такою:
struct Student
{
char name[30];
char surname[30];
bool isContractForm;
union
{
double paymentAmount;
int scholarship;
};
};
Компілятор не в змозі відстежити зв'язок між булевим полем isContractForm і тим, яка з гілок використовується.
Це програміст повинен контролювати сам, і тому такий підхід дуже ймовірно призводить до виникнення логічних помилок
у програмі.
Можливості застосування об'єднань істотно обмежені. Використання поліморфізму надає більш коректний спосіб для зберігання в масивах даних різних типів, тому зараз об'єднання використовують не дуже часто.
2.5 Сортування масивів структур з використанням вказівників
Структури, які описують об'єкти реального світу, можуть бути достатньо великими за розмірами. Відповідно копіювання структури в нову змінну може вимагати багато часу. Якщо в програмі здійснюється, наприклад, сортування масиву структур за певною ознакою, таке копіювання може виконуватися дуже багато разів. Тим більше якщо послідовно сортувати за різними критеріями сортування, це ще збільшить час виконання програми.
Існує спосіб підвищення ефективності виконання програм, які працюють з масивами структур. Ідея полягає в такому:
- створюємо допоміжний масив вказівників, який заповнюємо адресами елементів масиву структур;
- в алгоритмі сортування, або в іншому алгоритмі, пов'язаному з обміном місцями елементів масиву структур здійснюється модифікація масиву вказівників;
- доступ до структур здійснюється через масив указівників, а не безпосередньо.
Цей підхід продемонстровано у прикладі 3.3.
2.6 Використання зв'язаних списків
Одна з найпоширеніших задач, які розв'язуються програмістами, є представлення та обробка послідовностей даних. Більшість задач реального світу може бути розв'язана через використання масивів. Але іноді застосування масивів не є достатнім через такі недоліки:
- додавання нових елементів у кінець масиву не може бути здійснене без додаткових зарезервованих елементів; якщо немає таких елементів, ми повинні створити новий масив і скопіювати вміст старого масиву в новий
- додавання елементів всередину або видалення елементів, як правило, вимагає копіювання багатьох елементів даних.
Інший підхід до подання послідовностей забезпечує так званий зв'язаний список (linked list), або ланцюг. Для реалізації зв'язаного списку необхідно створити структуру, яка містить безпосередньо дані й вказівник на інший елемент цього типу:
struct Link
{
Data data;
Link *next;
};
де Data – це деякий відомий тип даних. Для додавання нового елемента між тими, що існують, слід
створити цей елемент у динамічній пам'яті, а потім змінити значення вказівників у сусідніх елементах.
Наприклад, для зберігання цілих значень слід описати таку структуру (ланку ланцюга):
struct Link
{
int data;
Link *next;
};
Для того, щоб створити зв'язаний список, необхідно створити вказівник на початок списку (першу ланку). Для зручності можна також окремо зберігати вказівник на останню ланку. Крім того, придасться вказівник на певну поточну ланку. Поки ці вказівники ні на що не вказують:
Link* first = 0; Link* last = 0; Link* link = 0;
Тепер до майбутнього списку можна додати перший елемент. Припустимо, необхідно додати значення цілої змінної
k. Створюємо нову ланку в динамічній пам'яті та вказуємо на неї:
int k = 1; link = new Link(); link->data = k; link->next = 0; first = link; last = link;
Далі, якщо треба, додаємо другий та інші елементи в кінець списку:
k = 2; link = new Link(); link->data = k; link->next = 0; last->next = link; last = link;
Вивести значення елементів списку можна за допомогою циклу:
link = first;
while (link != 0)
{
std::cout << link->data << " ";
link = link->next;
}
std::cout << std::endl;
Якщо треба додати елемент всередині списку, не треба переписувати елементи, які вже існують, на нове місце. Достатньо перевизначити вказівники, які зберігаються в елементах списку. Наприклад, ми хочемо додати новий елемент зі значенням 3 після першого:
Link* previous = first; k = 3;
Створюємо новий елемент і змінюємо вказівники:
link = new Link(); link->data = k; link->next = previous->next; previous->next = link;
Можна так зобразити додавання ланки всередині списку:
Аналогічно можна видалити елемент після вказаного. Не слід забувати про необхідність видалення елементу з динамічної пам'яті:
link = previous->next; previous->next = link->next; delete link;
Можна так зобразити видалення ланки:
Наведений нижче цикл дозволяє видалити всі наявні елементи:
while (first)
{
link = first;
first = first->next;
delete link;
}
Приклад 3.4 показує, як працювати зі зв'язаними списками.
Існують також двобічно зв'язані списки – списки, в яких кожен елемент вказує не тільки на наступний, але й на попередній елемент. Крім того, існують циклічні списки (однобічно зв'язані й двобічно зв'язані).
Зв'язаний список – це різновид динамічних структур даних. Іншими прикладами таких структур є черги, стеки й бінарні дерева. Приклад бінарного дерева:
3 Приклади програм
3.1 Перелік для представлення днів тижня
Припустимо, є тип переліку:
enum DayOfWeek {
Sunday,
Monday,
Tuesday,
Wednesday,
Thursday,
Friday,
Saturday
};
Для перевантаження префіксної операції ++ в тому ж просторі імен, де визначено тип
DayOfWeek,
повинна бути реалізована така функція:
// Перевантаження префіксної операції ++
DayOfWeek operator++(DayOfWeek& day)
{
if (day == Saturday) // окремий випадок
{
day = Sunday;
}
else
{
day = (DayOfWeek) (day + 1); // всі інші дні
}
return day;
}
Для перевантаження постфіксної операції ++ необхідно реалізувати функцію з двома параметрами:
// Перевантаження постфіксної операції ++
DayOfWeek operator++(DayOfWeek& day, int)
{
DayOfWeek oldDay = day;// зберігаємо попередній день
operator++(day); // викликаємо попередню функцію
return oldDay; // повертаємо попередній день
}
У списку формальних параметрів int – тип параметра який не використовується, але його
наявність дозволяє компілятору відрізнити постфіксну операцію від префіксної.
Весь код програми буде таким:
#include <iostream>
enum DayOfWeek {
Sunday,
Monday,
Tuesday,
Wednesday,
Thursday,
Friday,
Saturday
};
// Перевантаження префіксної операції ++
DayOfWeek operator++(DayOfWeek& day)
{
if (day == Saturday) // окремий випадок
{
day = Sunday;
}
else
{
day = (DayOfWeek) (day + 1); // всі інші дні
}
return day;
}
// Перевантаження постфіксної операції ++
DayOfWeek operator++(DayOfWeek& day, int)
{
DayOfWeek oldDay = day;// зберігаємо попередній день
operator++(day); // викликаємо попередню функцію
return oldDay; // повертаємо попередній день
}
// Отримання назв днів тижня
const char* getName(DayOfWeek day)
{
switch (day)
{
case Sunday:
return "Неділя";
case Monday:
return "Понеділок";
case Tuesday:
return "Вівторок";
case Wednesday:
return "Середа";
case Thursday:
return "Четвер";
case Friday:
return "П\'ятниця";
default:
return "Субота";
}
}
int main()
{
std::system("chcp 1251 > nul");
// Послідовно виводимо дні від середи до наступного понеділка
for (DayOfWeek d = Wednesday; d != Tuesday; d++)
{
std::cout << getName(d) << std::endl;
}
return 0;
}
3.2 Відстань між точками
У наведеному нижче прикладі, ми створюємо структуру, яка представляє точку на екрані. Програма обчислює відстань між двома точками.
#include <iostream>
#include <cmath>
struct Point
{
int x, y;
};
double sqr(double x)
{
return x * x;
}
double distance(Point p1, Point p2)
{
return std::sqrt(sqr(p1.x - p2.x) + sqr(p1.y - p2.y));
}
int main()
{
Point p1 = {1, 2};
Point p2 = {4, 6};
std::cout << distance(p1, p2);
return 0;
}
3.3 Робота з масивом структур
У програмі, яку ми створимо, описується структура для представлення міста. Місто характеризується назвою, назвою країни, в якій знаходиться, назвою регіону (області), де знаходиться місто та кількістю населення.
У програмі треба створити масив з кількох міст, та реалізувати такі функції:
- сортування міст за кількістю населення;
- пошук міст, які належать до певного регіону (області);
- виведення інформації про міста.
Для кращого розуміння коду та для забезпечення можливості його багаторазового використання окремі дії (сортування, пошук, виведення) доцільно реалізувати у вигляді окремих функцій. Для підвищення ефективності роботи з даними сортування здійснюється не для масиву міст, а для масиву вказівників на міста.
Код програми буде таким:
#include <iostream>
#include <cstring>
// Структура для опису міста
struct City
{
char name[30];
char country[30];
char region[30];
int population;
};
// Сортування за населенням
// Замість модифікації масиву міст, змінюємо масив вказівників
void sortByPopulation(City** arr, int size)
{
bool mustSort; // повторюємо сортування
// якщо mustSort дорівнює true
do
{
mustSort = false;
for (int i = 0; i < size - 1; i++)
{
if (arr[i]->population > arr[i + 1]->population)
// Обманюємо елементи
{
City* temp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = temp;
mustSort = true;
}
}
}
while (mustSort);
}
// Виведення даних про місто.
// Для підвищення ефективності використовуємо посилання
// на константний об'єкт
void printCity(const City& city)
{
std::printf("Мiсто: %s. Країна: %s. Регіон: %s. Населення: %d\n",
city.name, city.country, city.region, city.population);
}
// Виведення даних про всі міста.
// Доступ до міст здійснюємо через масив указівників
void pintCities(City** arr, int size)
{
for (int i = 0; i < size; i++)
{
printCity(*arr[i]);
}
std::cout << "\n";
}
// Виведення даних про міста,
// які знаходяться в певному регіоні
void printIf(City cities[], int size, const char* region)
{
for (int i = 0; i < size; i++)
{
if (std::strcmp(cities[i].region, region) == 0) {
printCity(cities[i]);
}
}
}
int main()
{
std::system("chcp 1251 > nul");
const int n = 4;
// Створюємо і заповнюємо масив міст:
City cities[n] = {
{ "Харкiв", "Україна", "Харкiвська область", 1421125 },
{ "Полтава", "Україна", "Полтавська область", 284942 },
{ "Лозова", "Україна", "Харкiвська область", 54618 },
{ "Суми", "Україна", "Сумська область", 264753 }
};
// Створюємо і заповнюємо масив указівників:
City* pointers[n];
for (int i = 0; i < n; i++)
{
pointers[i] = &cities[i];
}
pintCities(pointers, n);
sortByPopulation(pointers, n);
pintCities(pointers, n);
printIf(cities, n, "Харкiвська область");
return 0;
}
Як видно з коду, під час сортування здійснюється обмін місцями елементів масиву вказівників. У масиві структур нічого не змінюється.
3.4 Зворотний порядок
Наведена нижче програма читає числа з рухомою крапкою з текстового файлу і поміщає ці числа в новий файл у
зворотному порядку. Дані вводяться до кінця файлу. Під час завантаження даних створюється тимчасовий зв'язаний список.
Структура Link використовується
для представлення конкретних елементів списку. Завантажені дані переписуються в новий масив, а потім тимчасові
структури даних знищуються.
#include<iostream>
#include <fstream>
using namespace std;
// Ланка зв'язаного списку:
struct Link
{
double data;
Link *next;
};
// Функція зчитує зі вказаного файлу числа
// та повертає вказівник на нульовий елемент масиву.
// Масив створюється всередині функції, його елементи
// розташовуються в динамічній пам'яті
// Параметр count після завершення функції містить довжину масиву
double *readFromFile(const char *fileName, int &count)
{
// Підготовка зв'язаного списку до роботи та створення файлового потоку:
Link *first = 0;
Link *last = 0;
Link *link;
ifstream in(fileName);
double d;
count = 0; // лічильник чисел, які зчитані з файлу
while (in >> d) // читання до кінця файлу
{
count++;
// Створення нового елемента списку:
link = new Link;
link->data = d;
link->next = 0;
if (last == 0)
{
first = link;
}
else
{
last->next = link;
}
last = link;
}
// Створення й заповнення масиву чисел:
double *arr = new double[count];
link = first;
for (int i = 0; i < count; i++)
{
arr[i] = link->data;
link = link->next;
}
// Видалення з динамічної пам'яті елементів зв'язаного списку:
while (first)
{
link = first;
first = first->next;
delete link;
}
return arr;
}
// Записує елементи масиву arr довжини count
// у вказаний текстовий файл
void outToFile(const char *filename, double *arr, int count)
{
ofstream out(filename);
for (int i = count - 1; i >= 0; i--)
{
out << arr[i] << " ";
}
}
int main()
{
int count = 0;
double *arr = readFromFile("data.txt", count);
outToFile("results.txt", arr, count);
delete [] arr;
return 0;
}
4 Вправи для контролю
- Визначити перелік для представлення сезонів року. Реалізувати та продемонструвати перевантаження операцій
++і--. - Визначити структуру для представлення двох цілих чисел, а потім створити та викликати функцію, яка отримує як аргумент структуру створеного типу та обчислює добуток елементів структури.
- Визначити структуру для представлення навчального закладу. Створити масив навчальних закладів. Здійснити сортування масиву за іменами.
5 Контрольні запитання
- Які синтаксичні конструкції надає C++ для створення користувацьких типів?
- Для чого використовують безіменні переліки?
- Що таке перелік з областю видимості?
- Визначте поняття структури.
- У чому різниця між структурами й масивами?
- Чому слід розташувати крапку з комою після дужки, яка закриває тіло структури?
- Як надіслати структури до функцій?
- Що таке бітові поля?
- У яких випадках бітові поля підвищують ефективність програми?
- У чому полягають особливості об'єднань і для чого їх використовують?
- У чому потенційна небезпека використання об'єднань?
- Чому доцільно використовувати масиви вказівників під час сортування масивів структур?
- Що таке динамічні структури даних?
- Які переваги зв'язаних списків в порівнянні з масивами?
- Які недоліки зв'язаних списків в порівнянні з масивами?