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

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

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

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

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

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

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

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

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

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

2.1.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);

}