Построение операций работы с деком: удаление из начала дека, добавление в начало дека, создание пустого дека и создание дерева (Лабораторная работа № 3)

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

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

Кафедра ПМт.

Лабораторная работа по структурам данных и алгоритмов №3

по предмету : “Структуры данных и алгоритмы” .

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

Группа : ПМ – 75

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

Студент : Рак Б.В.

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

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

Формулу вида :

< формула >::=<терминал>|(<формула><знак><формула>)

<знак >::+|-|*

<терминал>::=0|1|2|3|4|5|6|7|8|9|)|(

Можно представить как двоичное дерево (‘дерево – формулы’):

- формула из одного терминала (цифры) представляется деревом из одной вершины (корнем) с этим терминалом;

- формула вида() – деревом , в котором корень – это знак s , а левое и  правое поддеревья – это соответствующие представления   :

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

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

Дано : < формула >::=<терминал>|(<формула><знак><формула>)

            <знак >::+|-|*

            <терминал>::=0|1|2|3|4|5|6|7|8|9|)|(

Результат :

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

В программе используются следующие операции работы с деком :

удаление из начала дека  

добавление в начало дека

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

создание дерева :

вычисление :

3. Структура основных входных и выходных данных :

Дерево представлено в виде иерархического односвязного списка с элементами типа bintree .

 struct bintree

{

char inf_pole;

bintree *left,*right;

};

 Дек представлен в виде  двусвязного линейного списка , у которого доступны 1 позиция: начало списка .

struct LIST_2_sv1

{

bintree *inf_pole1;

LIST_2_sv1 *next;

LIST_2_sv1 *prev;

};

struct DEK1

{

LIST_2_sv1 *begin,*end;

};

4.  Алгоритм :

 

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

#include <stdio.h>

#include "e:\stek_dlj.cpp"

#include "e:\D3.cpp"

#include <conio.h>

int vych(bintree *d)

{

int c,b,e;

if(d->left)

  {

   c=vych(d->left);

   b=vych(d->right);

   switch(d->inf_pole)

   {

   case '+':e=c+b;break;

   case '-':e=c-b;break;

   case '*':e=c*b;break;

   case '/':e=c/b;break;

   }

   return e;

  }

else

return (d->inf_pole-'0');

}

void main()

{

clrscr();

FILE *fp,*ft;

char ch;

int c;

DEK1 *stek;

bintree *k,*kl,*ks,*qw,*gh,*a,*d;

fp=fopen("e:input.txt","r");

stek=sozdanie_pustogo_deka1();

while(fscanf(fp,"%c",&ch)!=EOF)

 {

   if(ch!='('&&ch!=')')

     {

      kl=new bintree;

      kl->inf_pole=ch;

      kl->right=NULL;

      kl->left=NULL;

      dobavlenie_v_nachalo_DEKa1(stek,kl);

     }

   else

     {

      if(ch==')')

       {

          a=udalenie_start1(stek);

          ks=udalenie_start1(stek);

          gh=udalenie_start1(stek);

          ks->right=a;

          ks->left=gh;

          kl=ks;

          dobavlenie_v_nachalo_DEKa1(stek,kl);

       }

     }

 }

fclose(fp);

ft=fopen("e:output.txt","w");

//pe4at_pre(kl,ft);

//pe4at_inf(kl,ft);

pe4at_post(kl,ft);

fclose(ft);

int w=vych(kl);

printf("%d",w) ;

}

void pe4at_pre(bintree *d,FILE *ft)

{

if(d!=NULL)

   {

    fprintf(ft,"%s ",d->name);

    pe4at_pre(d->left,ft);

    pe4at_pre(d->right,ft);

   }

}

void pe4at_inf(bintree *d,FILE*ft)

{

 if(d!=NULL)

   {

    pe4at_inf(d->left,ft);

    fprintf(ft,"%s ",d->name);

    pe4at_inf(d->right,ft);

   }

}

void pe4at_post(bintree *d,FILE*ft)

{

if(d!=NULL)

  {

   pe4at_post(d->left,ft);

   pe4at_post(d->right,ft);

   fprintf(ft,"%s ",d->name);

  }

}

struct bintree

{

char inf_pole;

bintree *left,*right;

};

struct LIST_2_sv1

{

bintree *inf_pole1;

LIST_2_sv1 *next;

LIST_2_sv1 *prev;

};

struct DEK1

{

LIST_2_sv1 *begin,*end;

};

/**********************************/

bintree* udalenie_start1(DEK1 *d)

{

 LIST_2_sv1 *f;bintree* a;

  if(d->begin!=NULL)

   {a=d->begin->inf_pole1;

    f=d->begin;

    d->begin=d->begin->next;

    d->begin->prev=NULL;

    delete f;

   }

  else

   {a=d->begin->inf_pole1;

    f=d->begin;

    d->begin=NULL;

    d->end=NULL;

    delete f;

   }

return a;

}

/****************************/

/*bintree *udalenie_finish (DEK *d)

{

 LIST_2_sv *f;bintree* a;

  if(d->end!=NULL)

  { a=d->end->inf_pole;

    f=d->end;

    d->end=d->end->prev;

    d->end->next=NULL;

    delete f;

  }

  else

  {

    a=d->begin->inf_pole;

    f=d->begin;

    d->begin=NULL;

    d->end=NULL;

    delete f;

  }

 return a;

}

/*************************************/

void dobavlenie_v_nachalo_DEKa1(DEK1* d,bintree* f)

{

 LIST_2_sv1 *q,*r;

 q=new LIST_2_sv1;

 q->inf_pole1=f;

 r=d->begin;

 d->begin=q;

 q->next=r;

 r->prev=q;

 if(d->end==NULL)d->end=q;

}

//////////////*****************//////////

/*void dobavlenie_v_konec_DEKa(DEK* d,bintree* f)

{

 LIST_2_sv *q,*r;

 q=new LIST_2_sv;

 q->inf_pole=f;

 r=d->end;

 d->end=q;

 q->prev=r;

 r->next=q;

 q->next=NULL;

 if (d->begin==NULL) d->begin=q;

}

/********************************/

/*void vyvod_is_DEKa(DEK *d)

{

  LIST_2_sv *r,*k;

  FILE *fp;

  fp=fopen("f:\output.txt","w");

  r=d->begin;k=d->end;

  if(r!=NULL&&k!=NULL)

   {

     while(r!=NULL)

       {

      if(r->inf_pole=='t')

       {

        printf("true");

        fprintf(fp,"true");

       }

      else

       {

        printf("false");

        fprintf(fp,"false");

       }

       r=r->next;

       }

   }

  else

   {printf("DEK pust");

    fprintf(fp,"DEK PUST");

   }

}*/

DEK1 *sozdanie_pustogo_deka1()

{ DEK1 *d;

  d=new DEK1;

  d->begin=NULL;

  d->end=NULL;

  return d;

}

/*int proverka_na_pustotu(DEK *d)

{

if (d->begin==NULL) return 1;

else return 0;

} */

6. Набор тестов :

дано	результат
1 (2+3)-((1*2)/(2-1))	1 3

7. Результат отладки и анализ :

            На всех тестах программа выдала ожидаемый результат , задача решена правильно

            и полностью.