Робота з масивом структур

Після визначення структури можна оголосити масив структур. Наприклад, щоб оголосити масив з 30 елементів типу name_struct, досить записати:

name_struct elem[30];

Для одержання доступу до конкретного елемента масиву структур потрібно проіндексувати ім'я структури. Наведемо приклад створення масиву структур, Введення даних у структури й відображення даних на екрані:

#include <iostream.h>

//Константна змінна зберігає розмір масиву

const int size=10;

//----Визначення структури---------

struct person {

char name[20];

int age;

} osob[size]; //Оголошення масиву структур

//-------Функція Введення даних у структуру------

void enter(int k){

cout<<"Enter name: ";

cin>>osob[k].name;

cout<<"Enter age: ";

cin>>osob[k].age; }

//-----Функція виведення даних структури----------

void display(int k) {

cout<<'\n'<<osob[k].name<<" "<<osob[k].age; };

//-------Головна функція------

int main(){

//Ініціалізація масиву структур - запис 0 у поле name

for (int i=0; i<size; i++)

*osob[i].name='\0';

int opt = 0;

//Меню вибору операції

for(;;) {

cout << "0. Exit the program" << endl;

cout << "1. Enter data" << endl;

cout << "2. Display data" << endl;

cin >> opt;

int flag=0;

switch (opt) {

case 1:

for (i=0; i<size; i++){

//Якщо знайдено перший вільний елемент

if(!*osob[i].name &&!flag) {

enter(i);

//Встановлюється прапорець, щоб не зробити ще один запис

flag=1;

break;

};

};

//Якщо вільних елементів немає (масив повний)

if(i==size) cout<<"Array is full!\n";

break;

case 2:

for (i=0; i<size; i++)

//Виведення тільки ненульових елементів

if(*osob[i].name) display(i);

cout<<endl;

break;

case 0:

return(0);

default:

cout << "I do not know how to do it!" << endl; }

};

}

1.2. Постановка задачі

Скласти програму, що створює масив структур і дозволяє вводити дані в масив, виводити дані на екран і виконувати інші дії. Управління структурами повинне здійснюватися за допомогою меню. У меню присутні опції:

– вихід із програми

– введення даних

– виведення даних,

а також додаткові опції, зазначені у варіанті завдання (див. наступний розділ).

1.3. Варіанти

№	Структура (поля)	Додаткові опції меню (наступні операції)
	"Абітурієнт" (прізвище, ім'я, рік народження, оцінки вступних іспитів (5 ісп.))	- Пошук за прізвищем (–> введення прізвища –> виведення даних по абітурієнту, а також середнього бала й результату «прийнято/не прийнято»)
	"Абітурієнт" (прізвище, ім'я, рік народження, оцінки вступних іспитів (3 ісп.))	- Пошук за роком народження (–> введення року –> виведення знайдених записів)
	"Абітурієнт" (прізвище, ім'я, рік народження, оцінки вступних іспитів (3 ісп.))	- Зміна даних (–> введення прізвища –> введення нових даних)
	"Абітурієнт" (прізвище, ім'я, рік народження, оцінки вступних іспитів (3 ісп.))	- Фільтрація за роком народження (–> введення року –> виведення знайдених записів)
	"Студент" (прізвище, ім'я, номер групи, середній бал сесії)	- Упорядкувати за номером групи (–>виведення даних)
	"Студент" (прізвище, ім'я, номер групи, оцінки іспитів)	- Упорядкувати за середнім балом (–>виведення даних)
	"Студент" (прізвище, ім'я, номер групи, середній бал сесії)	- Студенти із середнім балом > 4.2 (–>виведення прізвищ і номерів груп)
	"Студент" (прізвище, ім'я, номер групи, оцінки іспитів)	- Студенти з оцінками 4 і 5 (–>виведення прізвищ і номерів груп, а також кількості таких студентів)
	"Студент" (прізвище, ім'я, номер групи, оцінки іспитів)	- Студенти з оцінками 2 (–> виведення прізвищ) - Кількість «двієчників» у кожній групі
	"Співробітник" (прізвище, ініціали, посада, стаж роботи, оклад)	- Додати співробітника
	"Співробітник" (прізвище, ініціали, посада, стаж роботи, оклад)	- Співробітники зі стажем більше…(–>введення числа із клавіатури –> виведення прізвищ співробітників)
	"Співробітник" (прізвище, ініціали, посада, стаж роботи, оклад)	- Виведення даних (поля структури, а також виплачена сума: оклад за винятком податку 20%) - Змінити дані (-> запит на введення прізвища -> введення нових даних)
	"Співробітник" (прізвище, ініціали, посада, стаж роботи, оклад)	- Співробітники з окладом в інтервалі… (–>введення границь діапазону –> виведення прізвищ співробітників)
	"Поїзд" (пункт призначення, номер поїзда, час відправлення)	- Поїзда після…(–>введення часу –> виведення поїздів, що відправляються пізніше уведеного часу)
	"Поїзд" (пункт призначення, номер поїзда, час відправлення)	- Пункт призначення …(–> введення назви пункту –> виведення інформації про поїзди в даний пункт)
	"Поїзд" (пункт призначення, номер поїзда, час відправлення)	- Номер поїзда …(–> введення номера поїзда –> виведення інформації про поїзд)
	"Поїзд" (пункт призначення, номер поїзда, час відправлення)	- Зміна в розкладі (–> введення номера поїзда –> введення нового часу відправлення)
	"Поїзд" (пункт призначення, номер поїзда, час відправлення)	- Зміна в розкладі (–> введення номера поїзда –> введення нового пункту призначення)
	"Блокнот" (прізвище, ім'я, телефон, день народження)	- Пошук телефону (–> введення прізвища –> виведення номера телефону)
	"Блокнот" (прізвище, ім'я, телефон, день народження)	- У кого сьогодні день народження? (–> введення поточної дати –> виведення прізвищ персон із зазначеною датою народження)
	"Блокнот" (прізвище, ім'я, телефон, день народження)	- Змінити номер телефону (–> введення прізвища –> введення нового номера)
	"Накладна" (назва товару, ціна, кількість, вартість)	- Введення даних (товар, ціна, кількість) - Виведення даних (товар, ціна, кількість, вартість) - Загальна сума
	"Накладна" (назва товару, ціна, кількість, вартість)	- Введення даних (товар, ціна, кількість) - Виведення даних (товар, ціна, кількість, вартість) - Додати товар
	"Накладна" (назва товару, ціна, кількість, вартість)	- Введення даних (товар, ціна, кількість) - Виведення даних (товар, ціна, кількість, вартість) - Внести зміни ((-> введення назви товару -> введення нових дані)

1.4. Методичні вказівки

Дані, що вводить користувач, розміщуються в масиві структур - записах. Інтерфейс програми повинен бути побудований у вигляді меню з опціями: введення, відображення, пошук, зміна записів і іншими. Введення даних передбачає додавання даних у перший вільний запис.

1.5. Зміст звіту

1. Постановка задачі.

2. Код програми.

3. Скріншот з результатами роботи програми.

4. Пояснення результатів і висновки.

2. Лабораторна робота 2
"Динамічні структури даних"

Ціль роботи: Вивчення створення структур даних змінної довжини: списків, черг і стеків. Складання програм, що дозволяють оперувати з динамічними структурами.

2.1. Теоретичні відомості

Списки

Слідом за масивами найпоширенішими структурами даних у програмуванні є списки, які являють собою логічно зв'язані елементи. Доступ до кожного елемента не обмежений. Будь-який елемент списку може бути вилучений, і його значення можуть бути обчислені або змінені. Крім цього, у будь-яке місце списку може бути вставлений новий елемент.

Динамічна реалізація списку називається зв'язним списком. Кожний елемент списку називається вузлом і містить дві величини: дані й покажчик на наступний вузол списку (покажчик останнього вузла має значення NULL).

Розглянемо приклад зв'язного списку, побудованого на основі наступної структури:

struct node {

char name[20];

long tel;

node *nxt;// Покажчик на наступний елемент

};

Список таких структур може являти собою телефонний довідник, що складається з полів name (ім'я абонента) і tel (номер телефону). Вузли списку послідовно зв'язані між собою покажчиком nxt.

Наведемо основні функції для маніпуляцій зі списками. У цих функціях будуть використані глобальні змінні:

node *pstart = NULL; //Покажчик початку списку

node *curr; //Поточний покажчик для переміщення уздовж списку

char key[20]; //Ключ, по якому виконується пошук вузла

Функція введення значень вузла:

node *input(){

node *temp;

temp = new node; //Тимчасовий вузол

cout << "Enter the name of the person: "; cin >> temp->name;

cout << "Enter the telephon: "; cin >> temp->tel;

return temp;

}

Функція додавання вузла:

void add(){

node *temp=input(); //Введення даних у новий вузол

temp->nxt = NULL; //Оскільки temp - останній вузол

//Зв'язування вузла зі списком

if (pstart == NULL){

pstart = temp;

curr = pstart;

}

else {

node *temp2; //Тимчасовий покажчик

temp2 = pstart; //Встановлення покажчика на початок списку

while (temp2->nxt!= NULL) // Поки не кінець списку,

temp2 = temp2->nxt;// перемістити покажчик

temp2->nxt = temp; //Прив'язати до списку новий вузол

}

}

Функція пошуку вузла за ключем:

node *find(char *key){

node *temp=new node; //Тимчасовий покажчик

temp=pstart; //Сполучення покажчика з початком списку

for(; temp->name!=NULL; temp=temp->nxt) //Пошук елемента

if (strcmp(key, temp->name)== 0) break;

return temp; //Повернення покажчика на знайдений елемент

}

Функція видалення вузла із заданим значенням:

void remove (char *key){

node *previous; //Покажчик на попередній вузол

int f1=0;

if (node *fkey=find(key)){ //Якщо за ключем key знайдений вузол

if (fkey==pstart){ //Якщо вузол на початку списку

pstart=pstart->nxt; //Початком вважати наступний вузол

}

else {

//Установка покажчика на попередній вузол

previous = pstart;

while (previous->nxt!= fkey)

previous = previous->nxt;

previous->nxt = fkey->nxt;

//Якщо видаляється вузол, що розташований наприкінці списку

if (fkey->nxt == NULL) previous->nxt=NULL;

}

delete fkey;

}

else cout<<"Element "<<key<<" not found"<<endl;

}

Функція вставки елемента після вузла із заданим значенням:

void insert (char *key){

int f1=0;

if (node *fkey=find(key)){ //Якщо за ключем key знайдений вузол

node *temp=input(); //Введення значень нового вузла

//Якщо вставлено вузол, що попадає в кінець списку

if (fkey->nxt==NULL){

fkey->nxt = temp;

temp->nxt = NULL; }

else {

//Вузол після вставленого вузла:

node *after=fkey->nxt;

//Зв'язування вставленого вузла із сусідами

fkey->nxt = temp;

temp->nxt=after;

}

;}

else cout<<"Element "<<key<<" not found"<<endl;

}

Функція виведення списку на екран:

void display() {

node *temp;

temp = pstart;

cout << endl;

if (temp == NULL) //Якщо список порожній

cout << "The list is empty!" << endl;

else {

while (temp!= NULL) {//Поки не досягнуто кінець списку

cout << "Name: " << temp->name << " ";

cout << "tel: " << temp->tel << " ";

cout << endl;

temp = temp->nxt;

}

cout << "End of list!" << endl;

}

}

Функція виведення одного елемента списку:

void display1(node *temp) {

cout << "Name: " << temp->name << " ";

cout << "tel: " << temp->tel <<endl;

}

Роботу зі списком зручно організовувати за допомогою меню, з якого викликається та або інша функція:

void main() {

int opt = 0;

pstart = NULL;

do {

cout << "0. Exit the program" << endl;

cout << "1. Add a node" << endl;

cout << "2. Find element" << endl;

cout << "3. Remove element" << endl;

cout << "4. Insert element" << endl;

cout << "5. Display list" << endl;

cout << endl << ">> ";

cin >> opt;

switch (opt) {

case 1: add(); break;

case 2: cout<<"Name? "; cin>>key; curr=find(key);

if (curr) display1(curr);

else cout<<"Element "<<key<<" not found"<<endl; break;

case 3: cout<<"Name? "; cin>>key; remove (key);break;

case 4: cout<<"After? "; cin>>key; insert (key); break;

case 5: display();

}

}

while (opt!= 0);

}

Стеки

Стек – це спеціальний вид списку, додавання вузлів у який і видалення вузлів з якого здійснюються тільки з одного кінця – вершини. Нові вузли записуються в структуру стека через вершину. У вершині виявляється останній записаний вузол. Видалення вузлів із стека здійснюється також через вершину, але у зворотному порядку, тобто реалізується принцип обслуговування «останнім прийшов, першим вийшов». Видалити перший записаний вузол можна тільки після того, як будуть видалені із стека всі інші вузли. Основними функціями для маніпуляцій із стеками є наступні:

push – додавання (проштовхування) нового вузла. Ця функція вставляє новий вузол у вершину стека й встановлює покажчик вершини на цей новий вузол.

pop – видалення (виштовхування) вузла. Ця функція видаляє вузол з вершини стека, повертає його значення й встановлює покажчик вершини на наступний вузол стека.

Розглянемо реалізацію стека на прикладі структури:

struct node {

int data;

node *nxt; //Покажчик на наступний вузол

};

У програмі також знадобиться змінна – покажчик на вершину стека:

node *top;

Функція додавання нового вузла:

void push() {

node *temp=new node; //Створити новий вузол

cout<<"Element>> ";

cin>> temp->data; //Записати дані в новий вузол

temp->nxt=top; //Поставити вузол перед вихідною вершиною

top=temp; //Зробити новий вузол вершиною

}

Функція видалення вузла із стека:

int pop() {

if (top==NULL) {//Якщо стек порожній

cout<<"Stack is empty!";

return NULL; }

else {

int item=top->data; //Записати дані із стека в змінну

node *temp=top; //Створити новий вузол у вершині стека

top=top->nxt; // Перемістити вершину на наступний вузол

delete temp; //Видалити вузол з пам'яті

return item;

}

}

Приведемо також функцію очищення стека clear, що видаляє всі вузли стека й звільняє пам'ять.

void clear() {

node *temp;

while(top!= NULL) { //Цикл для кожного вузла стека

temp = top; // Перезапис вершини

top = top->nxt; // Перемістити вершину на наступний вузол

delete temp; // Видалити вершину

};

}

Черги

Ще одним спеціальним типом списку є черги. Новий вузол може бути вставлений тільки в «хвіст» черги, а вибирається вузол тільки з «голови» черги. Таким чином, за допомогою черги реалізується принцип обслуговування «першим прийшов, першим вийшов». Основними функціями для маніпуляцій із чергами є наступні:

enqueue() – додавання нового вузла. Ця функція вставляє вузол у кінець черги й установлює покажчик хвоста черги на цей новий вузол. Алгоритм додавання вузла трохи видозмінюється, якщо черга була порожня.

denqueue() – видалення вузла. Ця функція видаляє вузол з голови черги, повертає його значення й установлює покажчик голови черги на наступний вузол.

Розглянемо реалізацію черги на прикладі структури node (див. розд. «2.1.2. Стеки»). У програмі також потрібні будуть змінні:

node *front; // Покажчик на голову черги

node *back; // Покажчик на хвіст черги

int len=0; //Довжина черги

Функція додавання вузла в чергу:

void enqueue(){

int item;

cout<<">> "; cin>>item; //Введення даних у вузол

if(len!= 0) {//Якщо черга не порожня

back->nxt = new node; //Створити новий вузол у хвості

back = back->nxt; //Зробити новий вузол хвостом черги

back->data = item; //Записати дані в створений вузол

back->nxt = NULL; //Установити покажчик на NULL

}

else {

back = new node; //Створити новий вузол

back->data = item; //Записати дані

back->nxt = NULL;

front = back; //Установити «голову» там же, де «хвіст»

}

len++; //Інкрементувати число вузлів

}

Функція видалення вузла із черги:

int dequeue() {

assert(!(front==NULL)); //Перервати, якщо черга порожня

int item = front->data; //Зберегти дані з першого вузла

node *temp = front; //Тимчасовий покажчик на голову черги

front = front->nxt; //Наступний вузол зробити головою черги

delete temp; //Видалити вихідний перший вузол

if(front == NULL) //Якщо черга порожня

back = NULL;

len-і; //Декрементувати число вузлів

return item; //Повернути значення першого вузла

}

Приведемо також функцію очищення черги:

void clear() {

node *temp;

while(front!= NULL) { //Поки покажчик голови не дійде

//до хвоста

temp = front; // Тимчасовий покажчик на голову

front = front->nxt; //Перемістити голову на один вузол

delete temp; //Видалити вихідний перший вузол

};

}

2.2. Постановка задачі

Скласти програму, що реалізує динамічну структуру відповідно до варіанта завдання, а також забезпечує виконання операцій над даними.

2.3. Варіанти завдань

1. Створити список "Блокнот" (прізвище, ім'я, телефон, день народження). Реалізувати операції додавання елемента в список, внесення змін, виведення списку на екран.

2. Створити список "Блокнот" (прізвище, ім'я, телефон, день народження). Реалізувати операції додавання елемента в початок списку, видалення елемента, виведення списку на екран.

3. Створити список "Студент" (прізвище, ім'я, група, середній бал). Реалізувати операції додавання елемента в початок списку, виведення списку на екран, а також визначення кількості студентів у кожній групі.

4. Створити список "Студент" (прізвище, ім'я, група, оцінки з 4 дисциплін). Реалізувати операції додавання елемента в початок списку, виведення списку на екран, а також визначення числа студентів з оцінками не нижче 4.

5. Створити список "Студент" (прізвище, ім'я, група, оцінки з 4 дисциплін). Реалізувати операції додавання елемента в початок списку, виведення списку на екран, а також упорядкування списку по прізвищах.

6. Створити список "Файли на диску" (ім'я файлу, розмір, дата створення, кількість звернень). Скласти програму, що забезпечує початкове формування каталогу файлів, виведення каталогу файлів, видалення файлів, дата створення яких менше заданої.

7. Створити список "Файли на диску" (ім'я файлу, розмір, дата створення, кількість звернень). Скласти програму, що забезпечує початкове формування каталогу файлів, виведення каталогу файлів, видалення файлів, число звернень до яких менше заданого числа, а також виведення списку вилучених файлів.

8. Створити список "Предметний покажчик" (назва теми, номер сторінки). Скласти програму, що забезпечує початкове формування предметного покажчика, виведення покажчика на екран, а також пошук теми й виведення відповідних номерів сторінок.

9. Створити список "Предметний покажчик" (назва теми, номер сторінки). Скласти програму, що забезпечує початкове формування предметного покажчика, виведення предметного покажчика на екран, а також виведення всіх тем на заданій сторінці, які цитуються у покажчику.

10. Створити чергу "Стоянка таксі" (номер машини, кількість місць, пункт призначення). Скласти програму, що забезпечує початкове формування черги таксі, видаляє із черги відправлену машину (із вказівкою пункту призначення), а також виводить список відправлених машин.

11. Створити чергу "Стоянка таксі" (номер машини, кількість місць, пункт призначення). Скласти програму, що забезпечує початкове формування черги таксі, видаляє із черги відправлену машину (із вказівкою пункту призначення й фактичного числа пасажирів), а також виводить список відправлених машин і кількість пасажирів, що виїхали.

12. Створити чергу "Стоянка таксі" (номер машини, кількість місць, пункт призначення). Скласти програму, що забезпечує початкове формування черги таксі, видаляє із черги відправлену машину (із вказівкою пункту призначення й фактичного числа пасажирів), а також виводить список машин, відправлених у заданий пункт.

13. Створити чергу "Аеропорт" (номер рейса, місце призначення, час відправлення). Скласти програму, що дозволяє додавати в чергу новий політ, видаляти із черги відправлений рейс, вносити зміни в рейс, упорядковувати рейси за часом відправлення.

14. Створити чергу "Аеропорт" (номер рейса, місце призначення, час відправлення). Скласти програму, що дозволяє додавати в чергу новий політ, видаляти із черги відправлений рейс, упорядковувати рейси за часом відправлення, міняти місцями рейси.

15. Створити чергу "Аеропорт" (номер рейса, місце призначення, час відправлення). Скласти програму, що дозволяє додавати в чергу новий політ, видаляти із черги відправлений рейс, формувати список рейсів, відправлених після заданого часу.

16. Створити чергу "Аеропорт" (номер рейса, місце призначення, час відправлення за розкладом, час затримки рейсу). Скласти програму, що дозволяє додавати в чергу новий політ, видаляти із черги відправлений рейс, формувати список рейсів, які будуть відправлені протягом найближчої години.

17. Створити стек, що моделює платформу для перевезення нових автомобілів (поля структури: марка автомобіля, колір кузова). Платформа має один з'їзд. Тому, щоб витягти потрібну машину, доводиться викотити всі попередні машини й потім повернути їх на платформу у вихідному порядку. Скласти програму, що забезпечує початкове завантаження платформи, моделює процес вилучення першої машини потрібної марки, показуючи на екрані, які машини потрібно викотити із платформи.

18. Створити стек, що моделює платформу для перевезення нових автомобілів (див. варіант 17). Скласти програму, що забезпечує початкове завантаження платформи, а також моделює процес вилучення машин заданого кольору. Показати новий порядок машин на платформі.

19. Створити стек, що моделює платформу для перевезення нових автомобілів (див. варіант 17). Скласти програму, що забезпечує початкове завантаження платформи, а також моделює процес вилучення машин заданої марки. Показати новий порядок машин на платформі й сформувати список вилучених машин.

20. Створити стек, що моделює платформу для перевезення нових автомобілів (див. варіант 17). Скласти програму, що забезпечує початкове завантаження платформи, а також моделює процес послідовного вилучення машин заданої марки (після викочування кожної машини, всі інші машини повертаються на платформу). Підрахувати, скільки разів кожна машина викочується із платформи, щоб забезпечити виїзд потрібній машині.

21. Створити стек, що моделює платформу для перевезення нових автомобілів (див. варіант 17). Скласти програму, що забезпечує початкове завантаження платформи й моделює процес послідовного вилучення машин заданих кольорів (після викочування кожної машини, всі інші машини повертаються на платформу). Підрахувати, скільки разів кожна машина викочувалась із платформи й скільки разів водієві доводилося сідати за кермо.

22. Створити стек "Маневровий тупик" (платформа/вагон, найменування вантажу, вантажопідйомність). Скласти програму, що дозволяє додавати в стек новий вагон, видаляти із стека вагон, формувати окремий стек для вагонів з певним типом вантажу.

23. Створити стек "Маневровий тупик" (платформа/вагон, найменування вантажу, вантажопідйомність). Скласти програму, що дозволяє додавати в стек новий вагон, видаляти із стека вагон, формувати окремий стек для вагонів з певним вантажем.

24. Скласти програму, що здійснює формування поїзду з певним вантажем. Використається три стеки типу "Маневровий тупик" (платформа/вагон, найменування вантажу, вантажопідйомність). В одному із стеків перебуває вихідний поїзд, в іншому – вагони поїзду, який формується, а третій стік - допоміжний. Програма повинна виводити на екран вихідний і отриманий поїзди.

2.4. Методичні вказівки

1. Управління програмою здійснюється за допомогою меню.

2. Передбачити виведення повідомлень у випадку, якщо список (черга, стік) порожній.

2.5. Зміст звіту

1. Постановка завдання.

2. Код програми.

3. Скриншот з результатами роботи програми.

4. Пояснення результатів і висновки.

3. Лабораторна робота 3
"Класи. Черги й стеки на основі масивів"

Ціль роботи: Навчитися створювати класи, визначати й застосовувати функції-члени класів. Освоїти роботу із класами на прикладах черг і стеків,

3.1. Теоретичні відомості