Постановка задачі, Теоретичні відомості - Алгоритм обробки типів даних лінійної структури
Тема: Тип даних лінійної структури. Стек. Черга. Черга пріоритетів.
Мета: Ознайомитися з основними алгоритмами обробки типів даних лінійної структури.
Завдання:
- 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
{
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 << " ";//демонстрация очереди
For (int i = 0; i<QueueLength; i++){
Cout << q[i].data <<" "<< q[i].pr << " ";
} лінійний пріоритетний черга операційний
}
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 << " ";
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();//очистка
}
Блок-схема
Похожие статьи
-
Відомі два підходи до організації інформаційних масивів: файлова організація та організація у вигляді бази даних. Файлова організація передбачає...
-
ПОСТАНОВКА ЗАДАЧИ - Структуры и алгоритмы обработки данных
Хранящуюся в файле базу данных загрузить в оперативную память компьютера и построить индексный массив, упорядочивающий данные По дням рождения и ФИО ,...
-
Програмна реалізація алгоритмів лінійної структури Алгоритм (латинізов. Algorithmi за араб. ім'ям узб. математека аль-Хороезмі) -- набір інструкцій, які...
-
У цей час існують різні системи керування запасами, кожна з яких характеризується певними особливостями планування запасів. Розглянемо основні з даних...
-
Постановка задачи, Описание программы, Алгоритм работы - Алгоритм кодировки RSA
Реализовать клиент серверное приложение для пересылки закодированной информации. В качестве алгоритма реализовать алгоритм RSA. Описание программы...
-
Составьте программу для реализации графического редактора линий, изображенного на рисунке 1.1.: Рисунок 1.1. - Пример работы Целью данной работы является...
-
Постановка задачи Необходимо разработать программу для поиска автобусных маршрутов. В качестве среды разработки должна использоваться Delphi 7. В...
-
Постановка задачи на разработку программного обеспечения Для того чтобы предлагаемая схема была интегрирована в САПР, который не имеет функции интеграции...
-
ОПИСАНИЕ ПОДПРОГРАММ - Структуры и алгоритмы обработки данных
Процедуры начальной обработки базы данных: 1. void Read() - считывает базу данных и формирует индексный массив. 2. void PrintMas(void) - осуществляет...
-
Програмний код для алгоритму ЕЦП ЕЦП DSS/DSА - Розробка електронного цифрового підпису
#include "stdafx. h" Extern "C" { #include "miracl. h" } #include <ctime> #include <cstring> #include <iostream> Class DSA { Public: Big p, q,...
-
Створення бази даних слід починати з її проектування. У результаті проектування має бути визначена структура бази, тобто склад таблиць, їхня структура та...
-
Постановка задачи Имеющаяся база данных SQL имеет недостаточное количество полей и таблиц, не имеет упорядоченной структуры пользователей для работы с...
-
Постановка задачи Магазин "Растения для сада", который занимается реализацией продажи растений, содержит информацию о растениях и их характеристиках:...
-
Призначення централізованої промислової КМ підприємства з виробництва сільськогосподарських кормів Проектована система призначена головним чином...
-
Цель работы. В городе имеется четыре АТС со свободной номерной емкостью (1,2,3,4). Известно количество свободных телефонных номеров на каждой станции....
-
МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ - Анализ потерь рабочего времени сорудников предприятия
Постановка задачи Имеется смета на выполнение проекта монтажа охранной сигнализации, в которой расписаны этапы выполнения работ, подбор специалистов на...
-
Сучасні вимоги до ІС "ГППР" надає адміністрації та співробітникам унікальну можливість отримувати повну і достовірну інформацію про наявне устаткування,...
-
Постановка задачи - Написание игры на Java
Требуется создать игру, в которой пользователь для победы должен найти спрятанный на карте объект. Построение алгоритма задачи. Приложение имеет меню...
-
Транспортная задача (Т. З.) является одной из распространенных задач линейного программирования специального вида. Эта задача такого наиболее...
-
Постановка задачи - Расчет трудоемкости средствами Ms Excel
Необходимо рассчитать нормативную трудоемкость квартальной и месячной производственной программы цеха по деталям. Для этого необходимо перемножить...
-
У відповідності до технічного завдання програма "Телефонний довідник" повинна забезпечувати облік даних про користувачів телефонами і можливість...
-
Постановка задачі - Інформаційна система адміністратора готелю "Венеціанська ніч"
У цій курсовій роботі повинна бути розроблена інформаційна система адміністратора готелю "Венеціанська ніч" у середовищі Access. У базі даних міститься...
-
В рамках данной работы по разработке схемотехнического метода повышения сбоеустойивости ПЛИС поставлены следующие задачи: 1. Создание сбоеустойчивой...
-
Для того щоб спроектувати реляційну БД потрібно виділити певну сукупність таблиць, які містять потрібну інформацію, і встановити зв'язки між цими...
-
В данном курсовом проекте в качестве исследуемой организации рассматривается институт, который предоставляет выбор факультативов студентами. Институт...
-
Програма - це опис розв'язання деякої задачі. Практично в кожній задачі можна виділити окремі допоміжні підзадачі. Деякі підзадачі доводиться...
-
ОСОБЕННОСТИ РЕАЛИЗАЦИИ АЛГОРИТМОВ - Структуры и алгоритмы обработки данных
В ходе выполнения курсовой работы, помимо основных алгоритмов, потребовалось реализовать также несколько вспомогательных, необходимых для корректной...
-
Програмний код для алгоритму ЕЦП по Ель Гамалю #include "stdafx. h" #include "ElGamal. h" #include <ctime> #include <iostream> Inline void...
-
Технические требования Техническое задание данной работы требует разработать программу для визуального редактирования HTML-кода. Программа должна быть...
-
Характеристики ЛВС Используемый стандарт: IEEE 802.3ab -- стандарт, использующий витую пару категорий 5e. 1000BASE-T, стандарт Gigabit Ethernet....
-
Задача данной выпускной квалификационной работы состоит в программной и аппаратной разработке комплекса, оповещающего адресата о поступлении...
-
Теоретичні відомості - Виробничо-транспортна задача
Транспортна задача - один із спеціальних видів задачі лінійного програмування, для розв'язування якої використовують спеціальні методи. Класична...
-
Анализ предметной области Организация 'ОБЩЕСТВО С ОГРАНИЧЕННОЙ ОТВЕТСТВЕННОСТЬЮ "СЕРВИС ПАРТНЕР" зарегистрирована по адресу г. Краснодар, ул. им Федора...
-
Постановка задачі - Розробка гри в С# "Корови та бики"
Етап 1 . Визначення цілей програми . На даному етапі творець програми повинен: - чітко визначити, які функції повинна виконувати програма; - обміркувати...
-
Постановка задачи нечеткого управления Была рассмотрена задача по прогнозированию износа (в микрометрах) тормозных дисков автомобилей. Входные данные:...
-
Постановка задач на проектирование Мотивация: В настоящее время есть возможность улучшить эффективность управлением временем и коммуникацией между...
-
Построение модели сердца, Постановка задачи, Создание нового проекта - Построение модели сердца
Постановка задачи Мы рассмотрим простейшую математическую модель, описывающую процессы, похожие на биение сердца. Эта модель описана двумя...
-
Постановка задачи, выбор предметной области Предметная область: "Автомобиль". Создание автомобиля будет состоять из трех этапов: выбор кузова, выбор...
-
Разработать и создать аналог системной утилиты "Диспетчер задач" по дисциплине "Системное программирование". "Диспетчер задач" должен содержать следующие...
-
Постановка задачи, Подход к реализации - Обьекто-ориентированное программирование
Создать класс Triangle для представления треугольника. Поля класса - длины сторон. Требуется реализовать операции: вычисления углов треугольника,...
Постановка задачі, Теоретичні відомості - Алгоритм обробки типів даних лінійної структури