Написание операций работы с заданной структурой данных, в том числе операции, показывающей содержимое структуры после выполнения какого-либо действия с ней (Лабораторная работа № 3)

Министерство Образования Российской Федерации.

Новосибирский Государственный Технический Университет.

Факультет Прикладной Математики и Информатики.

Лабораторная работа №3.

По дисциплине: Структуры данных и алгоритмы.

Группа: ПМИ-31

Выполнил:

Проверила: Шапошникова Т.А.

г.Новосибирск

2003г.

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

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

®  операция “принадлежит ли заданный элемент ” динамической  очереди (вид очереди: а, б);

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

Структура: динамическая очередь, реализованная в виде двунаправленного кольцевого списка с заглавным звеном.

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

Двунаправленным кольцевым списком с заглавным звеном называется структура следующего типа

            С учетом такого типа реализации очереди и определения самой очереди, как структуры для хранения данных в которой возможно только брать элементы слева, а помещать справа, распишем алгоритмы работы с очередью.

            Прежде всего, определим возможные состояния очереди:

®  Пустая очередь: состоит только из заглавного элемента и его ссылочные поля указывают на него самого

®  Непустая очередь: состоит из более чем одного элемента

Тогда алгоритм добавления элемента в очередь будет таким:

Q- заглавное звено очереди

N – новый элемент очереди

N->пред=Q->пред

Q->пред->след=N

N->след=Q

Алгоритм удаления элемента из очереди:

Если очередь пуста – удалить элемент из нее невозможно.

ИНАЧЕ

P=Q->след

Q->след=Q->след->след

Q->след->пред=Q

Вывод всех элементов очереди.

Для того чтобы вывести элемент из очереди q необходимо его оттуда извлечь, а затем положить обратно, чтобы не нарушить состояния очереди. Таким образом, нам понадобится дополнительная очередь, которая будет содержать все уже выведенные элементы.

ПОКА Q не пуста

            X=взять элемент из Q

            Вывод Х

            Положить Х в Р

ПОКА P Не пуста

            X=взять элемент из Р

            Положить X в Q

Поиск элемента в очереди будет производиться алогично выводу, за исключением того, что элемент будет не выводиться, а сравниваться с искомым.

Алгоритм

Текст программы

Файл queue.cpp

#include <stdio.h>

//Структура очереди

struct queue {

      char value;

      queue * next;

      queue * prev;

};

//Функция для создания пустой очереди

queue * create() {

      //Создаем новую очередь

      queue * x = new queue;

      //Ссылаем ее указатели сами на себя

      x->next=x->prev=x;

      return x;

}

//Функция добавления элемента в очередь

void addElement(queue * q, char x) {

      //Создаем новый элемент очереди

      queue * n = new queue;

      //Записываем в него данные

      n->value=x;

      //Перенаправляем ссылочные поля

      n->next=q;

      q->prev->next=n;

      q->prev=n;

}

//Функция получения элемента из очереди

//Возвращает 0, если очередь пуста и 1 - иначе

int getElement(queue * q,char *x) {

      //Если очередь пуста – возвращаем 0

      if(q->next==q) return 0;

      //Иначе

      else {

            //Записываем данные элемента

            *x=q->next->value;

            //Запоминаем его

            queue * s = q->next;

            //Перенаправляем ссылки

            q->next=q->next->next;

            q->next->prev=q;

            //Удаляем старый элемент

            delete s;

            //Возвращаем 1

            return 1;

      }

}

//Проверка на пустоту очереди

int isEmpty(queue *q) {

      if(q->next==q)return 1;

      return 0;

}

//Распечатка очереди

int printQueue(queue *q) {

      //если очередь пуста – вернем 0

      if(isEmpty(q))return 0;

      //Создаем временную очередь

      queue *p=create();

      char c;

      printf("--------\n");

      //Пока не кончатся элементы в q

      while(!isEmpty(q)) {

            //Достаем элемент