Тип даних лінійної структури. Стек. Черга. Черга пріоритетів

 

 

 

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

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

3. Практична частина 

Висновки

Список використаної літератури

 

 

 

Мета: Ознайомитися з основними алгоритмами обробки типів даних лінійної структури.

1. Вивчити основні принципи обробки типів даних лінійної структури.

2. Реалізувати програмно лінійну структуру даних відповідно до варіанту. Організувати обробку заданої структури відповідно до запиту користувача.

3. Оцінити обчислювальну складність алгоритмів обробки.

 

Реалізувати програмно чергу пріоритетів для візового агентства. Диспетчер вводить ім’я клієнта та країну, яку клієнт хоче відвідати. Для кожної країни задані пріоритети (Країни, в які не потрібна віза мають пріоритет 0; країни ближнього зарубіжжя мають пріоритет 10 і т. д.). Вихід програми – № черги клієнта і день, коли йому можна прийти за візою (путівкою), якщо агентство в день обслуговує N клієнтів.

 

 

Черга – динамічна структура даних, що працює за принципом «перший прийшов – перший пішов» (англ. FIFO – first in, first out).

Черга пріоритетів – це модифікована версія черги, яка із списку видаляє елемент з найвищим пріоритетом. При видаленні елементів з однаковими пріоритетами спочатку видаляється елемент, що надійшов раніше.

Основні операції з чергою:

• англ. еnqueue – «поставити в чергу». Операція додавання елемента в «хвіст» черги. При цьому довжина черги збільшується на одиницю. Якщо відбувається намагання додати елемент у вже заповнену чергу, відбувається її переповнення.
• англ. dequeue – «отримання з черги». Операція, яка повертає елемент з голови та видаляє його з черги, таким чином встановлюючи голову на наступний за видаленим елемент та зменшуючи довжину на одиницю. При намаганні видалити елемент з пустої черги, виникає ситуація «незаповнення».

Додаткові операції з пріоритетною чергою:

• включення елемента в чергу по пріоритету;
• виключення елемента з черги по пріоритету;
• визначення розміру черги;
• очищення черги.

 

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

На рис. 1 наведено результат роботи алгоритму.

Рис. 1

 

 

#include <iostream>

#pragma warning (disable: 4996)

#include <algorithm>

#include <string. h>

#include <time. h>

using namespace std;

struct Element

{

char * data; // данные

int pr; // приоритет

};

class QueuePriority

{

enum { EMPTY = -1, FULL = 999 };

// Массив элементов

Element q[FULL + 1];

// Максимальный размер очереди

int MaxQueueLength;

// Текущий размер очереди

int QueueLength;

public:

// Конструктор

QueuePriority (int m) ;

// Добавление элемента

void Add (const Element & elem) ;

// Очистка очереди

void Clear () ;

// Проверка существования элементов в очереди

bool IsEmpty () ;

// Проверка на переполнение очереди

bool IsFull () ;

// Количество элементов в очереди

int GetCount () ;

//демонстрация очереди

void Show () ;

//сравнение двух слов

int Srav (char*nam) ;

//опредиление приоритета

int Preor (char *MasP) ;

};

void QueuePriority: : Show () {

cout << «\n»; //демонстрация очереди

for (int i = 0; i<QueueLength; i++) {

cout << q[i]. data <<« «<< q[i]. pr << «\n\n»;

}

}

QueuePriority: : QueuePriority (int m)

{//получаем размер

MaxQueueLength = m;

QueueLength = 0;

}

void QueuePriority: : Clear ()

{// Эффективная «очистка» очереди

QueueLength = 0;

}

bool QueuePriority: : IsEmpty ()

{// Пуст?

return QueueLength == 0;

}

bool QueuePriority: : IsFull ()

{ // Полон?

return QueueLength == MaxQueueLength;

}

int QueuePriority: : GetCount ()

{// Количество присутствующих в очереди элементов

return QueueLength;

}

void QueuePriority: : Add (const Element & elem) //добавление елемента в очередь. Очередь с приоритетным включением

{

int i, k = -1;

// поиск позиции

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

if (q[i]. pr > elem. pr) {

k = i;

break;

}

if (k == -1) {

q[QueueLength ] = elem;

}

else

{

for (int j = QueueLength; j>k; j--)

q[j ] = q[j-1];

q[k] = elem;

}

QueueLength++;

}

char* tolower (char*str) {//все букви в нижнем регистре

if (str) {

for (int i = 0; str[i]! = 0; i++) {

str[i] = tolower (str[i]) ;

}

}

return str;

}

int QueuePriority: : Srav (char *nam) {//сравнение двух слов

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

if (strcmp (nam, q[i]. data) == 0) {

return i + 1;

}

}

int QueuePriority: : Preor (char *MasP) {

tolower (MasP) ;

int Prior;

if ((strcmp (MasP, «belarus»)) == 0 || (strcmp (MasP, «russia»)) == 0) {

return Prior = 0; }

else if ((strcmp (MasP, «turkey»)) == 0 || (strcmp (MasP, «moldavia»)) == 0 || (strcmp (MasP, «brazil»)) == 0) { return Prior = 5; }

else if ((strcmp (MasP, «maldives»)) == 0 || (strcmp (MasP, «egypt»)) == 0 || (strcmp (MasP, «thailand»)) == 0) { return Prior = 10; }

else if ((strcmp (MasP, «australia»)) == 0 || (strcmp (MasP, «india»)) == 0 || (strcmp (MasP, «uae»)) == 0) {

return Prior = 15; }

else if ((strcmp (MasP, «germany»)) == 0 || (strcmp (MasP, «greece»)) == 0 || (strcmp (MasP, «france»)) == 0 || (strcmp (MasP, «poland»)) == 0 || (strcmp (MasP, «italy»)) == 0) {

return Prior = 20;

}

else return Prior = 30;

}

void main ()

{

setlocale (LC_ALL, «Russian») ;

QueuePriority q (25) ; //создание очереди

cout << «Введите длину очереди» << endl;

int strok = 0; //Количество строк в массиве

int Nday = 0; int Prior = 0; //приоритет

cin >> strok;

cout << «Введите количество клиентов, обслуживаемых в день» << endl;

cin >> Nday;

int len = 255; //Длина строки

char**Massiv = new char*[strok]; //Выделяем память под количество строк. Массив имен

char**MasP = new char*[strok]; //Выделяем память под количество строк. Массив стран

Element s[200]; //массив структур

for (int i = 0; i < strok; i++) { Massiv[i] = new char[len]; MasP[i] = new char[len];

} //Выделяем память под количество символов в строке для каждой строки в отдельности

cout << «Вводимое количество строк = « << strok << «\n»;

for (int i = 0; i < strok; i++) {

cin >> Massiv[i] >> MasP[i]; //Считываем строки с клавиатуры в массив

Prior = q. Preor (MasP[i]) ;

s[i]. data = Massiv[i];

s[i]. pr = Prior;

q. Add (s[i]) ; //добавление елемента

}

cout << «Введите ваше имя» << endl;

char nam[290];

char nam2[290];

cin >> nam;

tolower (nam) ;

int Flagnal = 0; int inde = 0, Flag = 0, NoFlag = 0, nom = 0;

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

{

if (strcmp (nam, Massiv[i]) == 0) { Flagnal = 1; inde = i; break; }

}

if (Flagnal! =0) {//если вы есть в очереди

cout << endl;

cout << «Страна, которую вы хотите посетить: « << endl;

cout << MasP[inde] << endl;

}

if (NoFlag == 0) {//опредиление дня и номера в очереди

cout << nam;

int k = q. Srav (nam) ; //номер в очереди

// cout << endl;

cout << «, Вы « << k << « в очереди. « << endl;

int day = 0; //день

if ((k% Nday) == 0) { day = k / Nday;

}

else{ day = (k / Nday) + 1;

}

cout << «Прийдите в « << day << « день забрать путевку» << endl;

}

q. Show () ; //показ очереди

q. Clear () ; //очистка

 

}

 

Блок-схема

 

 

На основі проведеної роботи, можна зробити наступні висновки:

Тип даних черга пріоритетів має низку переваг та недоліків.

До переваг можна віднести:

У багатьох мовах програмування є вбудовані засоби організації та обробки черг.

Черга пріоритетів – зручний спосіб організації викликів функцій.

Операції з чергою пріоритетів мають константну складність О (1).

До недоліків віднесемо:

• Не можна отримати доступ до елементів, що знаходяться у середині черги;
• Пошук по черзі відбувається повільно;
• Чергу пріоритетів застосовують в операційній системі, яка записує процеси у список, а потім виконує їх у порядку пріоритетів.

 

1. [Електронний ресурс]:
2. Назва з екрану http: //www. refine. org. ua//
3. Седжвик Р. – Фундаментальные алгоритмы на С++. Части 1-4. с. 159.
4. Вирт Н. – Алгоритмы+структуры данных=программы. с. 198.
5. Ахо Альфред В., Хопкрофт Джон, Ульман Джеффри Д. – Структуры даннях и алгоритмы. с. 60-63.