Написание операций работы с заданной структурой данных (динамической очередью) (Лабораторная работа № 2)

Министерство образования и науки

Российской Федерации

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

Кафедра ПМт

Лабораторная работа №2

Тема: «Структуры данных и алгоритмы»

Студент: Мерзликин П.В.

Факультет: ПМИ

Группа: ПМ-94

Преподаватель: Еланцева И.Л.

Новосибирск, 2010

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

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

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

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

          Дано:  A= {a_j| a_jсимвол ,j=k,...,i} k,iєZ   k<=i

          Результат: B= {b_j| b_jсимвол j =k,…,i} k,iєZ  k<=i  или текстовое сообщение.

          Решение: 

Очевидно, что при решении задачи выделяются следующие подзадачи:

1.  Создать пустую очередь

2.  Поместить элемент в конец очереди

3.  Поместить элемент в начало очереди

4.  Взять элемент из начала очереди

5.  Взять элемент из конца очереди

6.  Проверить, пуста ли очередь

7.  Вывести содержимое очереди на экран

1.  Создание пустого дека

      i=0

      k=0

2.  Добавление элемента в конец дека

     a=b

     i=i+1;

3.Добавление элемента в начало дека

k=k-1

A_k=b

4.Взятие элемента из начала дека

      если i>0, то

      b=a_k

        k=k+1

       удаление a_k

      иначе вывести сообщение о ошибке

5.Взятие элемента из конца дека

Если i>0 то

 B=a_i

I=i-1

Удаление а_i

Иначе вывести сообщение о ошибке

6.Вывод элементов очереди на экран

c₀=0_, j=1

     повторять

     взятие a_i

     с_j=добавление a_i

     пока    a не пуста

7.Проверка дека на пустоту

     если i>0, то очередь не пуста

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

3.  Структуры  данных

Внешнее представление:

Входные данные: последовательность символов на экране   

  Выходные данные: последовательность символов на экране   

Внутреннее представление:

Входные данные: Динамический дек представлен линейным двунаправленным циклическим списком без заглавного звена. Элемент списка представлен структурой: struct list{int info; list *next; list *prev;};    

Выходные данные: Динамический дек представлена линейным двунаправленным циклическим списком без заглавного звена. Элемент стека представлен структурой: struct list{int info; list *next; list *prev;};    

Представление структуры:

 

4.  Алгоритмы

Алгоритм решения подзадачи создания нового дека:

 

Алгоритм решения подзадачи добавление нового элемента в конец дека:

 

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

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

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

 

Алгоритм решения вывода дека на экран:

 

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

 

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

Заголовочный файл:

struct list

{

       int inf;

       list *next,*prev;

};

list *Create();

list* EAdd(list *p, int x);

list* BAdd(list *p, int x);

list* EDel(list *p, int *x);

list* BDel(list *p, int *x);

int Check (list *p);

list* Clear(list* p);

list* Show(list *p);

   Модуль,содержащий определение подпрограмм:

#include <stdio.h>

#include "queue.h"

list *EAdd(list *p, int x)

{

          list *t;

          if(p==NULL)

          {

                    p=new list;

                    p->inf=x;

                    p->prev=p;

                    p->next=p;

          }

          else

          {

                    t=p->prev;

                    t->next=new list;

                    t->next->prev=t;

                    t->next->inf=x;

                    t->next->next=p;

                    p->prev=t->next;

          }

          return p;

}

list *BAdd(list *p, int x)

{

          list *t;

          if(p==NULL)

          {

                    p=new list;

                    p->inf=x;

                    p->prev=p;

                    p->next=p;