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

Страницы работы

Содержание работы

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

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

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

Кафедра ПМт

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

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

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

Группа: ПМ - 92

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

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

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

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

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

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

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

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

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

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

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

ai+1 = b;i = i + 1

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

еслиi ≠ 0, то

b = a1;

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

вывод b

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

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

j = 1;

повторять

|         вывод aj;

|         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. На всех тестах программа работает корректно.

Похожие материалы

Информация о работе