Задание 3 построение приоритетных очередей и обработка данных на их основе
Текст задания
Необходимо реализовать очередь на базе списков, применяя комбинированный алгоритм для ее обслуживания. Затем продемонстрировать выполнение основных операций с элементами очереди: поиск, добавление, удаление.
Реализация программы
#include <vcl.h>
#include <iostream>
#include <stdlib.h>
#include <windows.h>
using namespace std;
#pragma hdrstop
#pragma argsused
struct link {
char* data;
int priority;
struct link *next;
};
void PrintQueue(struct link*);
struct link *InitQueue(struct link*); // инициализация очереди
int GetPriority(char*); // определяет приоритет элемента в очереди
struct link *PredElQueue(struct link *head,struct link *queue); // поиск указателя на предыдущий элемент
struct link *AddElQueue(struct link *queue,char *data); // вставка элемента, с учетом приоритета
void DeletElQueue(struct link *); // удаление элемента
int main()
{
struct link *queue; // адрес, указывающий на голову стека
queue = (struct link *)malloc(sizeof(struct link));
queue = NULL;
cout << "Elementy slovara - iznachalno:" << endl;
queue=InitQueue(queue);
system("pause");
return 0;
}
void PrintQueue(struct link *p)
{
int kol=0;
while (p!=NULL)
{
if (!kol) cout << p->data;
else cout << " > " << p->data;
kol++;
p=p->next;
}
cout << endl;
}
struct link *InitQueue(struct link *queue)
{
struct link *head; // адрес, указывающий на голову стека
head = (struct link *)malloc(sizeof(struct link));
if (queue==NULL)
head->next = queue;
char a[50][5];
for(int i=0;i<50;i++)
{
for(int j=0;j<4;j++)
a[i][j] = 97+rand() % 26;
a[i][4] = '\0';
if(i==0)
cout <<a[i];
else
cout << " > " << a[i];
}
head->data=a[0];
head->priority=GetPriority(a[0]);
for (int i=1;i<50;i++)
{
head=AddElQueue(head,a[i]);
}
cout << "\n\nElementy slovara v ocheredy s prioritetom \n";
PrintQueue(head);
int n = 0;
cout << "\n Elementov udalit? n= ";
cin >> n;
cout << "\n\n Udalim " << n << " elementov: \n";
for(int i=1;i<n;i++)
DeletElQueue(head);
PrintQueue(head);
return head;
}
int GetPriority(char *data)
{
return data[0]-97;
}
struct link *PredElQueue(struct link *head,struct link *queue)
{
while (head!=NULL)
{
if (head==queue)
{
return NULL;
break;
}
if (head->next==queue)
{
return head;
break;
}
head=head->next;
}
}
struct link *AddElQueue(struct link *queue,char *data)
{
struct link *element; // указатель на новую структуру
element = (struct link *)malloc(sizeof(struct link)); // выделяем память
element->priority = GetPriority(data);
element->data = data;
struct link *head; // адрес, указывающий на голову стека
head = (struct link *)malloc(sizeof(struct link));
head = queue;
while (queue!=NULL)
{
if (GetPriority(data)<=queue->priority)
{
// вставка элемента перед текущим указателем
if (!(PredElQueue(head,queue)==NULL)) // предыдущий элемент - не конец очереди
{
element->next=queue;
PredElQueue(head,queue)->next=element;
}
else // конец очереди
{
element->next=queue;
head=element;
}
break;
}
if (queue->next==NULL) // элемент последний и не вставили, тогда вставляем в начало очереди
{
queue->next=element;
element->next=NULL;
break;
}
queue=queue->next;
}
return head;
}
void DeletElQueue(struct link *p)
{
while (p!=NULL)
{
if (p->next->next==NULL)
{
p->next=NULL;
break;
}
p=p->next;
}
}
Контрольные вопросы:
Дайте определение абстрактному типу данных «очередь».
Очередь – это специальный тип списка. Очередью называют упорядоченный набор элементов, где элементы удаляются с одного его конца, который называется началом, а вставляются с другого, который называется концом очереди.
Перечислите основные операторы, которые определены для работы с очередью.
MAKENULL(Q) очищает очередь Q, делая ее пустой
FRONT(Q) – функция, возвращающая первый элемент очереди Q.
ENQUEUE(x, Q) вставляет элемент х в конец очереди Q.
DEQUEUE (Q) удаляет первый элемент очереди Q.
Дайте определение многопоточной очереди.
Многопоточные очереди -элементы в нее, как обычно, добавляются в конец очереди, но очередь имеет несколько потоков или голов
4. Назовите особенности циклической очереди и приведите пример способа ее организации.
Циклическая очередь – очередь, в которую можно добавлять и удалять из нее любое число элементов. Такая очередь называется циклической, поскольку массив используется не как линейный список, а как циклический