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

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

Государственное образовательное учреждение высшего профессионального образования

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

Кафедра ПМт

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

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

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

Группа: ПМ - 92

Студент:   Санин И. А.

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

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

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

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

1.  Анализ задачи:

      Дано:  LINE = {a_i | a_i  – символ, i=1, 2, …}

      Результат:  LINE2 = {b_i | b_i  – символ, i=1, 2, …}

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

·  создание пустой очереди i = 0

·  добавление элемента ”b” в очередь 

a_i+1 = b;i = i + 1

·  удалить элемент из очереди

еслиi ≠ 0, то

b = a₁;

a_j-1 = a_j, j = 2, 3, …

вывод b

иначе вывести сообщениео том, что очередь пуста

·  вывод элементов очереди на экран

j = 1;

повторять

|         вывод a_j;

|         j = j + 1;

пока j ≤ i

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

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

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

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

Ø  создание очереди

Ø  помещение элемента в очередь

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

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

Ø  вывод содержимого очереди на экран

2.  Структуры данных:

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

  В файле – последовательность чисел(в свою очередь – последовательность цифр), разделенных пробелом.

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

  Последовательность чисел(в свою очередь – последовательность цифр), разделенных пробелом.

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

  Динамическая очередь представлена линейным однонаправленным ациклическим списком без фиктивного звена с двумя указателями. Элемент списка представлен структурой

       struct dline

              {int v; dline *next;};

указатели представлены структурой

             struct del{dline *beg, *end;};

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

   Получена последовательность действительных чисел, представленная линейным однонаправленным списком без фиктивного звена (аналогично).

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

#include <stdio.h>

#include <conio.h>

#include <math.h>

#include <stdlib.h>

#include "line.h"

void clean (del *A)

{    

      A->beg=NULL;

      A->end=A->beg;

}

bool pystota(del *A)

{

  if (A->beg==NULL && A->end==NULL)

      return true;

     else return false;

}

int vzat_eiem(del *A, int *x)

{

      int k=0;

      if (A->beg==NULL && A->end==NULL)

        k=0;

      *x=A->beg->v;  

      if (A->beg==A->end)

          { 

                  k=1;

                  A->beg=NULL;

                  A->end=NULL;

          }

             else {

                  A->beg=A->beg->next;

                      k=2;

                   }

             return k;

}

void input (del *A, int m)

{

      if (A->beg==NULL && A->end==NULL)

         {

               A->beg=new dline;

               A->beg->v=m;

               A->beg->next=NULL;

               A->end=A->beg;

         }

      else

           {

                   A->end->next=new dline;

                   A->end->next->v=m;

                   A->end->next->next=NULL;

                   A->end=A->end->next;

           }

}

void print(del *A)

{

      printf("Soderzhimoe ocheredy:\n");

      dline *t=A->beg;

      do

      {

            printf ("%d",t->v);

            t=t->next;

      }

      while (t!=NULL);

      printf("\n");

}

void main()

{

      int  k=0, f=0, chislo,x;

      char c;

      FILE* fp = fopen("data.txt", "r");

      if (fp != NULL)

      {

            del A;

            clean(&A);

            while (fscanf(fp, "%d", &chislo) != -1)

            {

                  input (&A, chislo);

            }

            if(!pystota(&A))

            {

                  print(&A);

                  k=vzat_eiem (&A, &x);

                  printf("Vzjali element: %d\n",x);

                  if(!pystota(&A)&& k!=1)

                  {

                        print(&A);

                        printf("\n Ochistit' ochered'? (Y,N)\n");

                        scanf("%c",&c);

                        if(c=='y')

                        {

                              clean(&A);

                              bool a = pystota(&A);

                              if(!a)

                                    printf("\nNe pusta!!! \n ");

                              else

                                    printf("\nOchered' ochishena!!!\n");

                        }

                        else

                        {

                              printf("Ochered ne ochisena!\n");

                              print(&A); getch ();

                        }

                  }

                  else

                        printf("Ochered' stala pusta!!!"); getch ();

            }

            else

                  printf("\n Ne mozhem vzjat' element, tk ochered' pusta!");

    }

}

line.h

struct dline

{

      int v; dline *next;

};

struct del

{

      dline *beg, *end;

};

6. Тесты на работоспособность программы:

№	Дано	Результат	Примечание
1.		A->beg==NULL  A->end==NULL	создание очереди
2.	содержимое исходной очереди: 1 2 3	A->beg==NULL  A->end==NULL	очистка очереди
3.	добавляемый элемент: 9	9	добавление элемента в пустую очередь
4.	содержимое исходной очереди: 5 6 7 8 9 добавляемый элемент: 10	5 6 7 8 9 10	добавление элемента в непустую очередь
5.		Ne mozhem vzjat' element, tk ochered' pusta! Sorry...	взятие элемента из пустой очереди
6.	содержимое исходной очереди: 77	Vzjali element:77 Ochered' stala pusta!!!	взятие элемента из очереди, содержащей один элемент
7.	содержимое исходной очереди: 77 66 55	Vzjali element:77 Soderzhimoe ocheredy: 66 55	взятие элемента из очереди, содержащей более одного элемента
8.		true	проверка пустой очереди на пустоту
9.	содержимое исходной очереди: 13 15 22 43 18 109	false	проверка непустой очереди на пустоту

7. На всех тестах программа работает корректно.