Результаты работы программы




Условие задачи

Написать операции работы с заданной структурой данных, включив их в один модуль (файл). К основным операциям добавить операцию, показывающую содержимое структуры после выполнения какого-либо действия с ней. Эту операцию реализовать на основе базовых операций над динамической очередью (вид очереди: линейный двусвязный циклический список с одним указателем)

 

Анализ задачи

Дано:

а) проверка очереди на пустоту:

б) вывод элементов очереди

в) добавление элемента в очередь

г) взятие элемента из очереди

Результат:

а) проверка очереди на пустоту:

б) вывод элементов очереди

в) добавление элемента в очередь

г) взятие элемента из очереди

Метод решения:

а) проверка очереди на пустоту:

если указатель на начало очереди нулевой то

k = 1

иначе

beg
k = 0

 
 

 

 


б) вывод элементов очереди

если очередь не пуста то

пусть t – указатель на первый элемент очереди

| повторять

| вывод значения элемента на который указывает t

| 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


Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-04-12 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: