Условие задачи
Написать операции работы с заданной структурой данных, включив их в один модуль (файл). К основным операциям добавить операцию, показывающую содержимое структуры после выполнения какого-либо действия с ней. Эту операцию реализовать на основе базовых операций над динамической очередью (вид очереди: линейный двусвязный циклический список с одним указателем)
Анализ задачи
Дано:
а) проверка очереди на пустоту:
б) вывод элементов очереди
в) добавление элемента в очередь
г) взятие элемента из очереди
Результат:
а) проверка очереди на пустоту:
б) вывод элементов очереди
в) добавление элемента в очередь
г) взятие элемента из очереди
Метод решения:
а) проверка очереди на пустоту:
если указатель на начало очереди нулевой то
k = 1
иначе
|
 |
б) вывод элементов очереди
если очередь не пуста то
пусть t – указатель на первый элемент очереди
| повторять
| вывод значения элемента на который указывает t
| t – указатель на следующий элемент очереди
| пока t ≠ указатель на первый элемент очереди
иначе
операция не определена
|
|
в) добавление элемента в очередь
если очередь не пуста то
создать новый элемент следующий за предыдущим от первого
установить связи между созданным элементом, предыдущим элементом и первым элементом
значению созданного элемента присвоить значение х
иначе
создать первый элемент
указателям на предыдущий и на последующий элементы присвоить адрес этого же элемента
 | |||||
 | |||||
 |
г) взятие элемента из очереди
если очередь не пуста то
если очередь не состоит из одного элемента то
х = значению первого элемента
удалить первый элемент очереди
установить связи: указателя на начало на второй элемент очереди, указателя на предыдущий элемент второго элемента на последний элемент, указателя на следующий элемент последнего элемента на второй элемент
иначе
х = значению первого элемента
удалить первый элемент
указатель на начало = нулевой указатель
иначе
операция не определена
 | |||
 |
 |
использование всех операций осуществляется с помощью меню.
Структуры данных
Внутреннее представление
А - линейный двусвязный циклический список с одним указателем
 |
Входные данные
Меню
[1] print queue to screen -вывод очереди на экран 1 +
[2] check queue is empty -проверка очереди на пустоту 2 +
[3] add item to queue -добавление элемента в очередь 3 +
[4] get item from queue -взятие элемента из очереди 4 +
[5] exit -выход из программы 5 +
при выборе пункта 3 потребуется ввести вещественное число – добавляемый элемент.
Выходные данные
1) вещественные числа с точностью 3 знака после запятой – элементы очереди или "queue empty." если очередь пуста
2) "queue is not empty. " если очередь не пуста или "queue is empty." если очередь пуста
3) вещественные числа с точностью 3 знака после запятой – элементы измененной очереди
4) вещественные числа с точностью 3 знака после запятой – элементы измененной очереди или "queue empty." если очередь пуста, "taken element:" вещественное число с точностью 3 знака после запятой – взятый элемент или "unable to taken." в случае невозможности взять элемент
Алгоритм решения
 |
 |
 |
 |
Текст программы
/* файл queue.h */
#ifndef QUEUE_H
#define QUEUE_H
struct queue
{float data;
queue *next, *prev;};
// проверка на пустоту, 1-пустая, 0-нет
inline int queue_empty(queue **beg)
{
return!(*beg);
}
// вывод на экран очереди
void queue_print(queue **beg);
//добавление элемента к очереди
void queue_add(float x, queue **beg);
//взятие элемента из очереди
int queue_get(float *x, queue **beg);
#endif
/* файл queue.cpp */
#include <stdio.h>
#include "queue.h"
// вывод на экран очереди
void queue_print(queue **beg)
{
if(!queue_empty(beg)) {
queue *t;
t = *beg;
do {
printf("%.3f ", t->data);
t = t->next;
} while(t!= *beg);
printf("\n");
}
else
printf("queue empty.\n");
}
//добавление элемента к очереди
void queue_add(float x, queue **beg)
{
if(!queue_empty(beg)) {//если непустая
(*beg)->prev->next = new queue;
(*beg)->prev->next->prev = (*beg)->prev;
(*beg)->prev = (*beg)->prev->next;
(*beg)->prev->next = *beg;
(*beg)->prev->data = x;
}
else {
(*beg) = new queue;
(*beg)->next = *beg;
(*beg)->prev = *beg;
(*beg)->data = x;
}
queue_print(beg);
}
//взятие элемента из очереди
int queue_get(float *x, queue **beg)
{
if(!queue_empty(beg)) {//если непустая
if((*beg)->next!= *beg) {
queue *t1, *t2;
*x = (*beg)->data;
t1 = (*beg)->next;
t2 = (*beg)->prev;
delete *beg;
*beg = t1;
(*beg)->prev = t2;
(*beg)->prev->next = *beg;
}
else {//если из одного элемента
*x = (*beg)->data;
delete *beg;
*beg = NULL;
}
queue_print(beg);
return 1;
}
else
return 0;
}
/* файл main.cpp */
#include <stdio.h>
#include "queue.h"
int main()
{
queue *beg = NULL;
int i;
do {
printf("[1] print queue to screen\n");//вывести очередь
printf("[2] check queue is empty\n");//проверить на пустоту
printf("[3] add item to queue\n");//добавить элемент
printf("[4] get item from queue\n");//взять элемент
printf("[5] exit\n");//выход
//int i;
scanf("%i", &i);
switch(i) {
case 1: queue_print(&beg); break; //вывести очередь
case 2: {//проверить на пустоту
if(queue_empty(&beg))
printf("queue is empty.\n");
else
printf("queue is not empty.\n");
} break;
case 3: {//добавить элемент
printf("enter new item:");
float x;
scanf("%f", &x);
queue_add(x, &beg);
} break;
case 4: {//взять элемент
float x;
if(queue_get(&x, &beg))
printf("taken element: %.3f.\n", x);
else
printf("unable to taken.\n");
} break;
}
printf("\n");
} while(i!= 5);
return 0;
}
Набор тестов
| № | Входные данные | Назначение теста |
| Проверить на пустоту | Проверка на пустоту пустой очереди | |
| Добавить элемент в очередь | Добавление элемента в пустую очередь | |
| Добавить элемент в очередь | Добавление элемента в непустую очередь | |
| Добавить элемент в очередь | Добавление элемента в непустую очередь с количеством элементов больше 2. Вывод элементов непустой очереди | |
| Проверить на пустоту | Проверка на пустоту непустой очереди | |
| Взять элемент из очереди | Взятие элемента из очереди с количеством элементов больше 2 | |
| Взять элемент из очереди Взять элемент из очереди | Взятие элемента из очереди с количеством элементов 1. Вывод элементов пустой очереди | |
| Взять элемент из очереди | Взятие элемента из пустой очереди |
Результаты работы программы
| № | Входные данные | Выходные данные |
| [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit | ||
| queue is empty. [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit | ||
| 2.369 | enter new item:2.369 2.369 [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit | |
| -8.92 | enter new item:-8.92 2.369 -8.920 [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit | |
| 7.8 | enter new item:7.8 2.369 -8.920 7.800 [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit | |
| queue is not empty. [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit | ||
| -8.920 7.800 taken element: 2.369. [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit | ||
| 7.800 taken element: -8.920. [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit queue empty. taken element: 7.800. [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit | ||
| unable to taken. [1] print queue to screen [2] check queue is empty [3] add item to queue [4] get item from queue [5] exit |