实验二  栈和队列

一、实验目的和要求

1、理解栈的存储结构及基本操作实现。

2、掌握应用栈解决问题的方法。

3、掌握队列的存储结构及基本操作实现，并能在相应的应用问题中正确选用它们。

二、实验仪器和设备

微型计算机

三、实验内容与过程

1、验证性实验：实现顺序栈的基本操作

实验内容：编写一个程序sqstack.cpp (或.c)，实现顺序栈的各种基本运算（假设栈中元素类型SElemType为char），并在此基础上设计一个程序exp3-1.cpp (或.c)完成以下功能。

(1)  初始化栈S。

(2)  判断栈是否为空。

(3)  将元素a、b、c、d、e依次进栈。

(4)  输出栈顶元素。

(5)  输出栈的长度。

(6)  将栈中元素依次出栈并输出。

(7)  判断栈是否为空。

(8)  销毁栈。

2、验证性实验：实现链栈的基本操作

实验内容：编写一个程序listack.cpp (或.c)，实现链栈的各种基本运算（假设栈中元素类型SElemType为char），并在此基础上设计一个程序exp3-2.cpp (或.c)完成以下功能。

(1)  初始化栈S。

(2)  判断栈是否为空。

(3)  将元素a、b、c、d、e依次进栈。

(4)  输出栈顶元素。

(5)  输出栈的长度。

(6)  将栈中元素依次出栈并输出。

(7)  判断栈是否为空。

(8)  销毁栈。

3、验证性实验：实现循环队列的基本操作

实验内容：编写一个程序sqqueue.cpp (或.c)，实现循环队列的各种基本运算（假设队中元素类型QElemType为char），并在此基础上设计一个程序exp3-3.cpp (或.c)完成以下功能。

(1)  初始化队列Q。

(2)  判断队列是否为空。

(3)  将元素a、b、c依次入队。

(4)  出队一个元素并输出。

(5)  输出队列的长度。

(6)  将元素d、e、f依次入队。

(7)  将队中元素依次出队并输出。

(8)  销毁队列。

4、验证性实验：实现链队列的基本操作

实验内容：编写一个程序liqueue.cpp (或.c)，实现链队列的各种基本运算（假设队中元素类型QElemType为char），并在此基础上设计一个程序exp3-4.cpp (或.c)完成以下功能。

(1)  初始化队列Q。

(2)  判断队列是否为空。

(3)  将元素a、b、c依次入队。

(4)  出队一个元素并输出。

(5)  输出队列的长度。

(6)  将元素d、e、f依次入队。

(7)  将队中元素依次出队并输出。

(8)  销毁队列。

5、设计性实验：括号匹配的检验

实验内容：编写程序exp3-5.cpp (或.c)实现以下功能：判断一个算术表达式中的花括号、方括号和圆括号是否配对，若能够全部配对则返回逻辑真，否则返回逻辑假。

6、设计性实验：判断是否为回文单词

实验内容：编写程序exp3-6.cpp (或.c)判定给定的字符序列是否为回文。回文是指正读、反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。

实验提示：通过将一个待判断的字符序列按照从前往后的顺序依次进栈后，再将栈内元素逐一出栈并与待判断字符序列的字母依次比较。

7、（选做题）设计性实验：兔子繁殖问题

实验内容：编写程序exp3-7.cpp (或.c)实现以下功能：使用循环顺序队列的基本操作来计算某个月的兔子总数。

实验背景：在700多年前，意大利著名数学家斐波那契 (Fibonacci) 在他的《算盘全集》提出了有趣的兔子繁殖问题：如果一开始有一对小兔，每一个月都生下一对小兔，而所生下的每一对小兔在出生的第三个月也都生下一对小兔。他对各个月的兔子对数进行了仔细观察，从中发现了一个十分有趣的规律，就是后面一个月份的兔子总对数，恰好等于前面两个月份兔子总对数的和，如果再把原来兔子的对数重复写一次，于是得到了1,2,3,5,8,13,21,34，…。

实验提示：要求某个月的兔子总数，借助于开始的小兔数目和第一个月的小兔总数目，可以求出第二个月的小兔总数目；然后由第一个月的小兔总数和第二个月的总数，可以求出第三个月的小兔总数。依次类推，最终可以求出第n个月的小兔总数。本题要求采用循环顺序队列的基本操作来求某个月的小兔总数，可以把第n-2个月和第n-1个月的小兔总数依次放入队列中，将队首元素（即第n-2个月的小兔总数）出队并记下其值，获取队首元素（即第n-1个月的小兔总数）并记下其值，将两次记下的值相加即为第n个月的小兔总数，然后将第n个月的小兔总数放入队列中。在求第n+1个月的小兔总数时，就可以再将当前队首元素（即第n-1个月的小兔总数）出队并记下其值，获取当前队首元素（即第n个月的小兔总数）并记下其值，将记下的两个值相加即得到第n+1个月的小兔总数。据此，就可以计算任意一个月的小兔总数。

四、实验结果与分析（程序运行结果及其分析）

1. exp3-1

#include<stdio.h>

#include <stdlib.h>

#include<malloc.h>

#define MAX 100

#define overflow -2

#define error 0

#define ok 1

typedef char SElemType;//定义栈的类型

typedef char status;

typedef struct {

SElemType *base;

SElemType *top;

int stacksize;

}sqstack;

status initstack(sqstack &S) //栈的初始化

{

 S.base=new SElemType[MAX];

 if(!S.base) exit(overflow);

 S.top=S.base;

 S.stacksize=MAX;

  return ok;

}

status YON(sqstack &S)//判断栈是否为空

{

if(S.top==S.base)

return error;

else return ok;

 }

status push(sqstack &S,SElemType e)//入栈

{

if(S.top-S.base==S.stacksize) return error;

*S.top++=e;

return ok;

}

status pop(sqstack &S,SElemType &e)//出栈

{

if(S.top==S.base) return error;

e=*--S.top;

return e;

 }

SElemType gettop(sqstack S)//取栈

{

if(S.top!=S.base)

return *(S.top-1);

 }

 length(sqstack &S)//栈长

 {

    int l;

    l=S.top-S.base;

return l;

  }

sqpop(sqstack &S)//逐个输出栈内元素

{

if(YON(S)==error) exit(error);

while(S.top!=S.base)

{

   char n;

   n=pop(S,n);

   printf("%c",n);

}

 }

void DestroyStack(sqstack S)

{

  delete S.base;

}

main()

{

int a,lengt;

char Top;

sqstack S;

initstack(S);

a=YON(S);

printf("(1)初始化栈S。n") ;

printf("(2)初始时判断，空栈为0，非空栈为1，此时此栈为：%dn",a);

printf("(3)将元素a、b、c、d、e依次进栈。n") ;

push(S,'a');

push(S,'b');

push(S,'c');

push(S,'d');

push(S,'e');

printf("(4)输出栈顶元素：") ;

Top=gettop(S);

printf("%c",Top);

lengt=length(S);

printf("n(5)此表长为：%d",lengt);

a=YON(S);

printf("n(6)进栈后判断，空栈为0，非空栈为1，此时此栈为：%d",a);

printf("n(7)将栈中元素依次出栈并输出:") ;

sqpop(S);

a=YON(S);

printf("n(8)现在栈的状态，空栈为0，非空栈为1，此时此栈为：%d",a);

DestroyStack(S);

printf("n(9)释放栈。");

}

（2）3-2

#include<stdio.h>

#include <stdlib.h>

#include<malloc.h>

#define MAX 100

#define overflow -2

#define error 0

#define ok 1

typedef char QElemType;

typedef struct stacknode//链栈的存储结构

{

   QElemType data;

   struct stacknode *next;

}stacknode,*linkstack;

initstack(linkstack &S)//初始化链栈

{

   S=NULL;

   return ok;

}

push(linkstack &S,QElemType e)//链栈的入栈

{

   stacknode *p;

  

   p=new stacknode;

   p->data=e;

   p->next=S;

   S=p;

   return ok;

}

yon(linkstack &S)

{

   if(S==NULL) return error;

   else return ok;

}

pop(linkstack &S,QElemType &e)//链栈的出栈

{

   stacknode *p;

   if(S==NULL) return error;

   e=S->data;

   p=S;

   S=S->next;

   delete p;

   return ok;

}

char gettop(linkstack &S)//取栈顶元素

{

   if(S!=NULL)

   return S->data;

}

int LengthStack(linkstack S)             //栈的长度

{

   stacknode *p;

   int count=1;

    for(p=S->next;p!=NULL;p=p->next)

    {

     count++;

    }

 return count;

}

   listpop(linkstack &S)

   {

      while(S!=NULL)

      {

         char a;

         pop(S,a);

         printf("%c ",a);

        

      }

    }

    destorystack(linkstack &S)

    {

      delete S;

    }

main()

{

   int a,l;

   char b;

   printf("(1)初始化链栈Sn");

   linkstack S;

   initstack(S);

   a=yon(S);

  printf("(2)判断此链栈是否为空，空则返回0，非空则返回1：%dn",a);

   printf("(3)将a、b、c、d、e依次进栈n");

   push(S,'a') ;

   push(S,'b') ;

   push(S,'c') ;

   push(S,'d') ;

   push(S,'e') ;

   b=gettop(S);

   printf("(4)输出栈顶元素：%cn",b);

   l=LengthStack(S);

   printf("(5)输出栈的长度%dn",l);

   printf("(6)将栈中元素依次出栈并输出:");

   listpop(S);

   a=yon(S);

   printf("n(7)判断栈是否为空:%d",a);

   printf("n(8)销毁栈。");

   destorystack(S);

}

（3）exp3-3  #include<stdio.h>

#include <stdlib.h>

#define MAX 100

#define overflow -2

#define error 0

#define ok 1

typedef char QElemType;

typedef struct        //队列的顺序结构

{

   QElemType *base;

   int front;

   int rear;

}sqqueue;

initque(sqqueue &Q)//循环队列的初始化

{

   Q.base=new QElemType[MAX];

   if(!Q.base) exit(overflow);

   Q.front=Q.rear=0;

   return ok;

 }

int queuelength(sqqueue Q)//求循环队列的长度

{

   return (Q.rear-Q.front+MAX)%MAX;

 }

yon(sqqueue Q)//判断此循环队列是否为空

{

   if(Q.front==Q.rear) return error;

   else return ok;

 }

enqueue(sqqueue &Q,QElemType e)//循环队列的入队

{

   if((Q.rear+1)%MAX==Q.front)

   return error;

   Q.base[Q.rear]=e;

   Q.rear=(Q.rear+1)%MAX;

   return ok;

 }

dequeue(sqqueue &Q,QElemType &e)//循环队列的出队

{

   if(Q.front==Q.rear) return error;

   e=Q.base[Q.front];

   Q.front=(Q.front+1)%MAX;

}

gethead(sqqueue Q)//去出循环队列的队头元素

{

   if(Q.front!=Q.rear)

   return Q.base[Q.front];

 }

sqoutput(sqqueue Q)

{

   while(Q.front!=Q.rear)

   {

      char a;

      dequeue(Q,a);

      printf("%c",a);

     

   }

}

destory(sqqueue &Q)

{

   delete Q.base;

}

 main()

 {

   int a,l;

   QElemType b;

   sqqueue Q;

   initque(Q);

   printf("(1)初始化队列Q。n");

   a=yon(Q);

   printf("(2)判断队列是否为空。空则返回0，非空则返回1：%dn",a);

   printf("(3)将元素a、b、c依次入队。n");

   enqueue(Q,'a');

   enqueue(Q,'b');

   enqueue(Q,'c');  

   dequeue(Q,b);

   printf("(4)出队一个元素并输出。元素为：%cn",b);

   l=queuelength(Q);

   printf("(5)输出队列的长度:%dn",l);

   printf("(6)将元素d、e、f依次入队。n");

   enqueue(Q,'d');

   enqueue(Q,'e');

   enqueue(Q,'f');

   printf("(7)将队中元素依次出队并输出:");

   sqoutput(Q);

   printf("n(8)销毁队列。");

   destory(Q);

  }

 （4）exp3-4  #include<stdio.h>

#include <stdlib.h>

#define overflow -2

#define error 0

#define ok 1

typedef char QElemType;

typedef struct qnode//队列的链式存储结构

{

   QElemType data;

   struct qnode *next;

  

}qnode,*queueptr;

typedef struct

{

   queueptr front;

   queueptr rear;

}linkqueue;

initqueue(linkqueue &Q)//链队的初始化

{

   Q.front=Q.rear=new qnode;

   Q.front->next=NULL;

   return ok;

 }

enqueue(linkqueue &Q,QElemType e)//链队的入队

{

   queueptr p;

   p=new qnode;

   p->data=e;

   p->next=NULL;Q.rear->next=p;

   Q.rear=p;

   return ok;

}

yon(linkqueue Q)//判断队是否为空

{

   if(Q.front==Q.rear)

   return error;

   else return ok;

}

dequeue(linkqueue &Q,QElemType &e)//链队的出队

{

   queueptr p;

   if(Q.front==Q.rear) return error;

   p=Q.front->next;

   e=p->data;

   Q.front->next=p->next;

   if(Q.rear==p) Q.rear=Q.front;

   delete p;

   return ok;

}

gethead(linkqueue Q)//取链队的队头元素

{

   if(Q.front!=Q.rear)

   return Q.front->next->data;

}

queuelength(linkqueue Q)//返回链队的长度

{

   qnode *p;

   int l=0;

   if(Q.front==Q.rear)

   return error;

   else

   p=Q.front->next;

   while(p)

   {

      p=p->next;

      l++;

     

   }

   return l;

}

destory(linkqueue &Q)//销毁链队

{

   delete Q.front;

   delete Q.rear;}

sqput(linkqueue &Q)

{

   char a;

   while (Q.front!=Q.rear)

   {

   dequeue(Q,a);

   printf("%c",a);}

}

main()

{

  

   linkqueue Q;

   char b;

   int l;

   printf("(1)  初始化队列Q。n");

   initqueue(Q);

   int a=yon(Q);

   printf("(2)  判断队列是否为空。如果为空，返回0，非空返回1：%dn",a);

   printf("(3)  将元素a、b、c依次入队。n");

   enqueue(Q,'a');

   enqueue(Q,'b');

   enqueue(Q,'c');

   dequeue(Q,b);

   printf("(4)  出队一个元素并输出:%cn",b);

   queuelength(Q);

   printf("(5)  输出队列的长度:%dn",queuelength(Q));

   printf("(6)  将元素d、e、f依次入队。n");

   enqueue(Q,'d');

   enqueue(Q,'e');

   enqueue(Q,'f');

   printf("(7)  将队中元素依次出队并输出:");

   sqput(Q);

   printf("n(8)  销毁队列。");

   destory(Q);

  

}

（5）exp3-5 #include<stdio.h>

#include<malloc.h>

typedef struct{                  

   char *base;

   char *top;

   int size;

}snode;

bool match(char *p){

   snode s;

   int i;

   i=0;

   s.base=(char *)malloc(20 * sizeof(char));             //初始化一个栈

   if(!s.base){

      printf("内存空间不足n");

      return false;

   }

   s.top=s.base;

   s.size=20;

   while(p[i]!=''){                                     //开始循环  “”是字符串的结束标志

      if((p[i]=='{')||(p[i]=='[')||(p[i]=='(')){         //筛选   ‘（’、‘{’、‘[’进栈

         if(s.top-s.base>=s.size){                      //入栈判栈满

            printf("栈满n");

            return false;

         }

         *(s.top)=p[i];

         s.top++;

         i++;

      }else{                                            

            switch(p[i]){

            case ')' : if(s.base==s.top){             //遇到‘）’‘}’‘]’则开始匹配，要是栈顶元素能匹配成功，则继续，否则直接return，里面的一些条件可以自己想想

                           return false;

                     }

                     else if(*(--s.top)=='(')

                     {

                           i++;

                           continue;

                     }

                     else{

                           return false;

                        }

            case '}' : if(s.base==s.top)

                     {

                           return false;

                     }

                     else if(*(--s.top)=='{')

                     {

                           i++;

                           continue;

                     }

                     else{

                           return false;

                        }

            case ']' : if(s.base==s.top)

                     {

                           return false;

                     }

                     else if(*(--s.top)=='['){

                           i++;

                           continue;

                     }

                     else{

                           return false;

                        }

            default : i++;               //剔除其他符号

                    continue;

            }

         }

   }

   if(s.top==s.base)          //匹配成功则最后栈空

      return true;

   else

      return false;

}

int main(){

   char str[50];

   int i=0;

   char *p;

   p=str;

   printf("请输入字符串:");

   gets(str);

   if(match(p))

      printf("匹配成功!n");

   else

      printf("匹配失败……n");

   return 0;

}

（6）exp3-6  #include<stdio.h>

#include <stdlib.h>

#include<malloc.h>

#define MAX 100

#define overflow -2

#define error 0

#define ok 1

typedef char QElemType;

typedef struct stacknode//链栈的存储结构

{

   QElemType data;

   struct stacknode *next;

}stacknode,*linkstack;

initstack(linkstack &S)//初始化链栈

{

   S=NULL;

   return ok;

}

push(linkstack &S,QElemType e)//链栈的入栈

{

   stacknode *p;

  

   p=new stacknode;

   p->data=e;

   p->next=S;

   S=p;

   return ok;

}

yon(linkstack &S)

{

   if(S==NULL) return error;

   else return ok;

}

pop(linkstack &S,QElemType &e)//链栈的出栈

{

   stacknode *p;

   if(S==NULL) return error;

   e=S->data;

   p=S;

   S=S->next;

   delete p;

   return ok;

}

char gettop(linkstack &S)//取栈顶元素

{

   if(S!=NULL)

   return S->data;

}

int LengthStack(linkstack S)//栈的长度

{

   stacknode *p;

   int count=1;

    for(p=S->next;p!=NULL;p=p->next)

    {

     

     count++;

    }

 return count;

}

   listpop(linkstack &S)

   {

      while(S!=NULL)

      {

         char a;

         pop(S,a);

         printf("%c ",a);

        

      }

    }

    destorystack(linkstack &S)

    {

      delete S;

    }

main()

{

   linkstack S;

   initstack (S);

   int length=0,i=0,yo=1;

   printf("请输入一个字符序列以#结束：");

   char a=0,b[100],c;

   scanf("%c",&a);

   while(a!='n')

   {

     

      b[length]=a;

      push(S,a);

      scanf("%c",&a);

      length++;

     

   }

   while(yon(S))

   {

      pop(S,c);

      printf("%c  %cn",c,b[i]);

      if(c!=b[i])

      {

         yo=0;

         break;

      }

      i++;

          

    }

    if(yo==1)

    printf("是回文数。");

    

    else printf("不是回文数。"); 

}

1. exp3-7

#include<stdio.h>

#include <stdlib.h>

#define MAX 100

#define overflow -2

#define error 0

#define ok 1

typedef int QElemType;

typedef struct        //队列的顺序结构

{

   QElemType *base;

   int front;

   int rear;

}sqqueue;

initque(sqqueue &Q)//循环队列的初始化

{

   Q.base=new QElemType[MAX];

   if(!Q.base) exit(overflow);

   Q.front=Q.rear=0;

   return ok;

 }

int queuelength(sqqueue Q)//求循环队列的长度

{

   return (Q.rear-Q.front+MAX)%MAX;

 }

yon(sqqueue Q)//判断此循环队列是否为空

{

   if(Q.front==Q.rear) return error;

   else return ok;

 }

enqueue(sqqueue &Q,QElemType e)//循环队列的入队

{

   if((Q.rear+1)%MAX==Q.front)

   return error;

   Q.base[Q.rear]=e;

   Q.rear=(Q.rear+1)%MAX;

   return ok;

 }

dequeue(sqqueue &Q,QElemType &e)//循环队列的出队

{

   if(Q.front==Q.rear) return error;

   e=Q.base[Q.front];

   Q.front=(Q.front+1)%MAX;

}

gethead(sqqueue Q)//去出循环队列的队头元素

{

   if(Q.front!=Q.rear)

   return Q.base[Q.front];

 }

sqoutput(sqqueue Q)

{

   while(Q.front!=Q.rear)

   {

      int a;

      dequeue(Q,a);

      printf("%c",a);

     

   }

}

destory(sqqueue &Q)

{

   delete Q.base;

}

tutu(int a)

{

   sqqueue Q;

   initque(Q);

   if(a==1)

   return 1;

   else if(a==2)

   return 2;

   else{

      int b=1,c=2,d=1,e=2,sum;

  

      for(int i=2;i<a;i++)

      {

     

         dequeue(Q,d);

         dequeue(Q,e);

         sum=d+e;

         d=e;

         e=sum;

         enqueue(Q,d);

         enqueue(Q,e);

      }

     

  

   printf("%d",sum);

      return sum ;

     

     

   }

}

 main()

 {

   int a,sum;

   printf("请输入你想知道兔子数量的月份：");

  

   scanf("%d",&a);

   sum=tutu(a);

   printf("n兔子数为：%d",sum);

  }

五、实验体会（遇到问题及解决办法，编程后的心得体会）

（至少300字）

本次实验是针对栈和队列进行一些基本处理方法的学习和处理。在此期间我们充分了解了栈和队列的一些特性，栈：先进后出。队列：先进先出。因为对于数据处理方式的不同，所以在实验过程中，所面对的问题也不同。

我想在这里谈论在本次实验中，我所遇到的几个印象深刻的问题，（1）在队列的方法撰写中，本人在c程序的编写往往喜欢使用for循环，所以在编写按顺序输出元素时，本人使用length作为循环截止变量，但是因为人为输入字符时，计数length过于麻烦，而且不易于判定何时结束，for循环存在过于繁琐的步骤，while循环相对于停止循环的条件，更加便于思考和判定。（2）在队列方法的编写中，因为本人使用while循环时，不够纯熟，忘了加{}，使得程序逻辑错误（找了老半天）。（3）本人认为在回文问题的解决上，数组更容易解决此类问题，使用栈方法过于繁琐。（4）最后一个错误是在exp3-7的问题中，没有明白题目要求，导致在函数编写时逻辑发生错误。

以上可见，在我们编写程序时，应该有更加宽拓的思维，了解更多解决问题的方法，程序再小的细节也需要注意，最后要熟知问题需求，对症下药，不可以从起点就发生逻辑上的错误，很浪费时间。

最后

以上就是紧张世界为你收集整理的实验二栈和队列实验二  栈和队列的全部内容，希望文章能够帮你解决实验二栈和队列实验二  栈和队列所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。