Лабораторная работа № 9. Полустатические структуры данных: очереди
Очередь - одномерная структура данных, для которых загрузка или извлечение элементов осуществляется с помощью указателей начала извлечения ( head ) и конца ( tail ) очереди в соответствии с правилом FIFO (" first-in, first-out " - " первым введен, первым выведен" ), т. е. включение производится с одного, а исключение – с другого конца.
| Задание
| Краткие теоретические сведения
| | 1. В программе, приведенной справа, демонстрируется реализация очереди на основе односвязного списка.
Внести изменения в главную функцию с тем, чтобы выводились различные варианты содержимого очереди.
| #include < iostream>
using namespace std;
struct Queue
{ int val;
Queue *next;
};
void intoFIFO(Queue *ph[], int v)//постановка элемента в конец очереди
{ Queue *p = new Queue;
p-> val = v; p-> next = NULL;
if (ph[0] == NULL)
ph[0] = ph[1] = p; // включение в пустую очередь
else
{ ph[1]-> next = p;
ph[1] = p;
}
}
void scan(Queue *ph[]) //вывод элемента
{ for(Queue* p = ph[0]; p! = NULL; p = p-> next)
cout< < p-> val< < " ";
cout< < " \n";
}
int fromFIFO(Queue *ph[])//извлечение элемента
{ Queue *q;
if (ph[0] == NULL) return -1; // очередь пуста
q = ph[0]; // исключение первого элемента
ph[0] = q-> next;
if (ph[0] == NULL) ph[1] = NULL;
int v = q-> val;
return v;
}
void main()
{ Queue A3 = {7, NULL}, A2 = {5, & A3}, A1 = {1, & A2};
Queue* ph[2];
ph[0] = & A1; ph[1] = & A3;
scan(ph);
intoFIFO (ph, 10);
intoFIFO (ph, 2);
scan(ph);
int vv = fromFIFO (ph);
scan(ph);
}
| | 2. Изучить реализацию очереди на основе односвязного списка с приоритетным включением, выполнив программу, приведенную в правой части.
| При решении некоторых задач возникает необходимость в формировании очередей, порядок включения или выборки элементов из которых определяется приоритетами элементов.
Приоритет в общем случае может быть представлен числовым значением, которое вычисляется на основании значений каких-либо полей элемента, либо на основании внешних факторов.
В данном примере приоритет заключается в том, что каждый элемент при добавлении его в очередь вставляется в нужное место так, чтобы очередь всегда была упорядочена.
#include< iostream>
using namespace std;
struct item
{ int data;
item *next;
};
item *head, *tail;
bool isnull(void)//Проверка на пустоту
{ return (head == NULL);
}
void delet1()//Извлечение элемента из начала
{ if(isnull())
cout< < " Очередь пуста" < < endl;
else
{ item *p = head;
head = head -> next;
delete p;
}
}
void fromhead()//Получение элемента из начала
{ if(isnull()) cout< < " Очередь пуста" < < endl;
else cout< < " Начало = " < < head -> data < < endl;
}
void add(int x)//Добавление элемента в очередь
{ item *p = new item; //новый указатель
p -> data = x; p -> next = NULL;
item *v = new item; //указатель для нового числа
item *p1 = new item;
item *p2 = new item;
int i = 0; // флажок
if (isnull()) head = tail = p;
else
{ p2 = head; p1 = head;
while(p1! = NULL)//пока очередь не закончится
{ if (i == 1)
{ if(x < = p1 -> data )//число меньше, чем в очереди
{ v -> data = x; v -> next = p1;
p2 -> next = v;
return;
}
p2 = p2 -> next; // следующее число
}
else
{ if(x < = p1 -> data )
{ v -> data = x; v -> next = p1;
head = v;
return;
}
}
p1 = p1 -> next; i = 1;
}
if(p1 == NULL) { tail -> next = p; tail = p; }
}
}
void out()//Вывод очереди
{ item *p = new item;
if(isnull())
cout< < " Очередь пуста" < < endl;
else
{ cout< < " Очередь = ";
p = head;
while(! isnull())
{ if (p! = NULL) { cout< < p-> data< < " "; cout< < " -> "; p = p -> next; }
else { cout< < " NULL" < < endl; return; }
}
}
}
void clrscr()//Очистка очереди
{ while(! isnull())
delet1();
}
int main()
{ setlocale (LC_CTYPE, " Russian" );
int i = 1, num = 1, z;
head = NULL;
tail = NULL;
while (num! = 0)
{ cout< < " 1 - добавить элемент" < < endl;
cout< < " 2 - получить элемент с начала" < < endl;
cout< < " 3 - извлечь элемент с начала" < < endl;
cout< < " 4 - вывести элементы" < < endl;
cout< < " 5 - очистить очередь" < < endl;
cout< < " 0 - выход" < < endl;
cout< < " Выберите действие ";
cin> > num;
switch(num)
{ case 1: cout< < " Введите элемент: ";
cin> > z; add(z);
out(); break;
case 2: fromhead(); break;
case 3: delet1(); break;
case 4: out(); break;
case 5: clrscr(); break;
}
}
return 0;
}
| | 3. Изучить реализацию очереди на основе массива, выполнив программу, приведенную в правой части.
| #include < iostream>
using namespace std;
const int N = 4; //размер очереди
struct Queue
{ int data[N]; //массив данных
int last; //указатель на начало
};
void Creation(Queue *Q) //Создание очереди Q
{ Q-> last = 0;
}
bool Full(Queue *Q) //Проверка очереди на пустоту
{ if (Q-> last == 0) return true;
else return false;
}
void Add(Queue *Q) //Добавление элемента
{ if (Q-> last == N)
{ cout < < " \nОчередь заполнена\n\n"; return; }
int value;
cout < < " \nЗначение > ";
cin > > value;
Q-> data[Q-> last++] = value;
cout < < endl < < " Элемент добавлен в очередь\n\n";
}
void Delete(Queue *Q) //Удаление элемента
{ for (int i = 0; i< Q-> last & & i < N; i++) //смещение элементов
Q-> data[i] = Q-> data[i + 1];
Q-> last--;
}
int Top(Queue *Q) //Вывод начального элемента
{ return Q-> data[0];
}
int Size(Queue *Q) //Размер очереди
{ return Q-> last;
}
void main()
{ setlocale(LC_ALL, " Rus" );
Queue Q;
Creation(& Q);
char number;
do
{ cout < < " 1. Добавить элемент" < < endl;
cout < < " 2. Удалить элемент" < < endl;
cout < < " 3. Вывести верхний элемент" < < endl;
cout < < " 4. Узнать размер очереди" < < endl;
cout < < " 0. Выйти\n\n";
cout < < " Номер команды > "; cin > > number;
switch (number)
{ case '1': Add(& Q); break;
case '2': if (Full(& Q)) cout < < endl < < " Очередь пуста\n\n";
else
{ Delete(& Q);
cout < < endl < < " Элемент удален из очереди\n\n";
} break;
case '3': if (Full(& Q)) cout < < endl < < " Очередь пуста\n\n";
else cout < < " \nНачальный элемент: " < < Top(& Q) < < " \n\n";
break;
case '4': if (Full(& Q)) cout < < endl < < " Очередь пуста\n\n";
else cout < < " \nРазмер очереди: " < < Size(& Q) < < " \n\n";
break;
case '0': break;
default: cout < < endl < < " Команда не определена\n\n";
break;
}
} while (number! = '0');
}
| | 4. Изучить реализацию очереди на основе динамического массива, выполнив программу, приведенную в правой части.
Дописать главную функцию, включив операторы добавления, извлечения и вывода различных элементов.
| Главная функция
#include " stdafx.h"
#include " MyQueue.h"
#include < iostream>
using namespace std;
struct str1
{ int a;
char b;
};
struct str2
{ char b;
long a;
};
void PrnQu(Queue& s)// Вывод на экран
{ while (! (s.isEmpty()))
{ cout< < ((str1 *)Peek(s))-> a< < " " < < ((str1 *)Peek(s))-> b< < endl;
Deq(s);
}
}
int _tmain(int argc, _TCHAR* argv[])
{ str1 a1 = {1, 'q'}; str1 a2 = {2, 'w'}; str1 a3 = {3, 'e'};
str2 b1 = {'a', 1}; str2 b2 = {'s', 2}; str2 b3 = {'d', 3};
str2* b4 = new str2; b4-> a = 4; b4-> b = 'f';
str1* a4 = new str1; a4-> a = 4; a4-> b = 'r';
Queue q1=CreateQueue (3);
Enq(q1, & a1);
Enq(q1, & a3);
PrnQu(q1);
...................
str1* x = (str1*)Peek(q1);
x = (str1*)Deq(q1);
...................
Queue q2 = CreateQueue(q1);
Enq(q1, a4);
ClearQueue(q1);
CopyQueue(q1, q2);
return 0;
}
Заголовочная функция MyQueue.h
#define MYQUEUE1_EQE 0x0000// возврат в случае пустоты очереди
struct Queue// блок управления очередью
{ int Head; // голова очереди
int Tail; // хвост очереди
int Size; // размер очереди (макс. колич.+1)
void** Data; // хранилище данных очереди
Queue(int size)// физический размер очереди
{ Head = Tail = 0;
Data = new void*[Size = size+1];
}
bool isFull() const; // очередь заполненa?
bool isEmpty()const; //очередь пустa?
};
Queue CreateQueue(int n); // n – макс. колич.
Queue CreateQueue(const Queue& pq); //создать очередь по образцу
bool Enq(Queue& q, void* x); // добавить x
void* Deq(Queue& q); //удалить элемент
void* Peek(const Queue& q); //получить первый элем.
int ClearQueue(Queue& q); //очистить очередь
void ReleaseQueue(Queue& q); //освободить ресурсы
void AppendQueue(Queue& to, const Queue& from); //добавить одну очередь к другой
void CopyQueue(Queue& to, const Queue& from); // //копировать очередь
void RemoveQueue(Queue& to, Queue& from); ////переместить очередь
Программный модуль MyQueue.cpp
#pragma once
#include " stdafx.h"
#include " MyQueue.h"
#include < string.h>
Queue CreateQueue(int n) //Выделить ресурс для очереди
{ return *(new Queue(n)); };
Queue CreateQueue(const Queue& pq)// Создать очередь по образцу
{ Queue *rc = new Queue(pq.Size-1);
rc-> Head = pq.Head; rc-> Tail = pq.Tail;
for (int i = 0; i < pq.Size; i++)
rc-> Data[i] = pq.Data[i];
return *rc;
}
bool Enq(Queue& q, void* x)// Добавить x
{ bool rc = true;
if (rc =! q.isFull()) { q.Data[q.Tail] = x; q.Tail=(q.Tail+1)%q.Size; }
else rc = false;
return rc;
};
void* Deq(Queue& q) //Удалить элемент
{ void* rc = (void*)MYQUEUE1_EQE;
if (! q.isEmpty()) { rc = q.Data[q.Head]; q.Head = (q.Head + 1) % q.Size; }
else rc = NULL;
return rc;
}
void* Peek(const Queue& q)
{ void* rc = (void*)MYQUEUE1_EQE;
if (! q.isEmpty()) rc = q.Data[q.Head];
else rc=NULL; return rc;
}
int ClearQueue(Queue& q) //Очистить очередь
{ int rc = (q.Tail - q.Head) > = 0? (q.Tail - q.Head): (q.Size - q.Head + q.Tail + 1);
q.Tail = q.Head = 0;
return rc; // колич. элементов до очистки
}
void ReleaseQueue(Queue& q) //Освободить ресурсы очереди
{ delete[] q.Data;
q.Size = 1; q.Head = q.Tail = 0;
}
void AppendQueue(Queue& to, const Queue& from)//Добавить одну очередь к другой
{ for (int i = from.Head; i! = from.Tail; (++i) % from.Size)
Enq(to, from.Data[i]);
}
void CopyQueue(Queue& to, const Queue& from)// Копировать очередь
{ ClearQueue(to); AppendQueue(to, from);
}
void RemoveQueue(Queue& to, Queue& from)// Переместить очередь
{ CopyQueue(to, from); ClearQueue(from);
}
bool Queue:: isFull() const
{ return (Head % Size == (Tail + 1) % Size);
} //очередь заполненa?
bool Queue:: isEmpty()const
{ return (Head % Size == Tail % Size);
} //Очередь пустa?
|
4. Создать проект из нескольких файлов, демонстрирующий работу с очередью. В соответствии со своим вариантом выполнить задание из таблицы, представленной ниже. Реализовать все операции с очередью через функции.
| № варианта
| Задание для выполнения
| | 1, 8
| Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие - подряд из младших адресов (начало очереди). Приоритет: мin значение числового параметра, при совпадении параметров - LIFO.
| | 2, 4
| Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие - подряд из младших адресов (начало очереди). Приоритет: мах значение числового параметра, при совпадении параметров - FIFO
| | 5, 3
| Разработать функцию, которая по одной очереди строит две новых: Queue1 из положительных элементов и Queue2 - из остальных элементов очереди.
| | 6, 7
| Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие - подряд из старших адресов (конец очереди). Приоритет: мin значение числового параметра, при совпадении параметров - LIFO.
| | 9, 12
| Разработать функции работы с приоритетной очередью. Постановка запросов в очередь выполняется по приоритету, снятие - подряд из старших адресов (конец очереди). Приоритет: мin значение числового параметра, при совпадении параметров - LIFO
| | 10, 11
| Разработать функцию, которая в очереди переставляет в обратном порядке все элементы между первыми последним вхождением элемента E, если E входит в L не менее двух раз.
| | 13, 16
| Разработать функцию, которая по одной очереди строит две новых: Queue1 из положительных элементов и Queue2 - из остальных элементов очереди.
| | 14, 15
| Разработать функцию, которая удаляет из очереди первый отрицательный элемент, если такой есть.
|
В начало практикума
Популярное:
|
