数据结构实验报告3————栈和队列及其应用_栈和队列的应用实验报告

1. 栈的定义、基本操作的实现，以及典型应用

（1）编程实现顺序栈的基本操作

核心代码：

①comdef.h

#include <stdio.h>
   #include <iostream> 
   using namespace std;
   #define OK 1
   #define ERROR 0
   #define OVERFLOW -1
   typedef int Status;
   

②spstackdef.H

#define MAXSIZE 100  
typedef int SElemType;
typedef struct{
        SElemType *base;//栈底指针 
        SElemType *top;//栈顶指针 
        int stacksize;//栈可用的最大容量 
}SqStack;
 

③spstackapp.H

//栈的初始化 
Status InitStack(SqStack &S)
{
    //构造一个空栈 
    S.base=new SElemType[MAXSIZE];//为顺序栈动态分配一个最大容量为MAXSIZE的数组空间 
    if(!S.base)//存储分配失败 
    exit (OVERFLOW);
    S.top=S.base;//top初始为base,空栈 
    S.stacksize=MAXSIZE;
    return OK;
}
//判断栈空 
Status StackElemType(SqStack S)
{
    return (S.base==S.top);
}
//求栈的长度 
int StackLength(SqStack S)
{
    return S.top-S.base;
    
}
//取栈顶 
SElemType GetTop(SqStack S)
{
    if(S.top!=S.base)
    return *(S.top-1);
}
//出栈 
Status Pop(SqStack &S,SElemType &e)
{
    //删除栈顶元素，用e返回其值 
    if(S.top==S.base)
    return ERROR;
    else
    {
        e=*--S.top; 
        return OK;
    }
}
//入栈 
Status Push(SqStack &S,SElemType e)
{
    if(S.top-S.base>=S.stacksize)//栈满 
    return ERROR;
    else
    {
        *S.top++=e; //元素e压入栈顶，栈顶指针加一 
        return OK;
    }
}
//输出栈 
void StackTraverse(SqStack S)
{
    SElemType *p=S.top-1;
    while(p>=S.base)
    {
        cout<<"\n        "<<*p;
        p--; 
    }
}

//清空栈 
void ClearStack(SqStack &S)
{
    S.base=S.top;
}
//栈的销毁 
bool DestroyStack(SqStack &S)
{
    delete []S.base;
    S.base=NULL;
    S.top=NULL;
    S.stacksize=0;        
    return true;
}
④main.CPP

#include "comdef.h"
#include "sqstackdef.h"
#include "sqstackapp.h"
int main(){
    SqStack S;
    SElemType e;
    int choice,n,i;    
    cout<<"\n建立顺序栈：";
    if (InitStack(S)==OVERFLOW){
          cout<<"顺序栈空间分配失败,程序退出！";
         return 0;
         }
    else{
        cout<<"\n数据个数=";
          cin>>n;
          cout<<"\n输入"<<n<<"个数据: "; 
          for(int j=0;j<n;j++)
          {
              cin>>i;
              Push(S,i);    
        }
          cout<<"顺序栈建立成功，顺序栈为：";
        StackTraverse(S);    
    } 
    do { 
        cout<<"\n\n===================================";
        cout<<"\n        顺序栈的基本操作           ";
        cout<<"\n===================================";
        cout<<"\n           1:判断栈空" ;
        cout<<"\n           2:求栈的长度" ;
        cout<<"\n           3:取栈顶" ;
        cout<<"\n           4:出栈" ;         
        cout<<"\n           5:入栈" ;
        cout<<"\n           6:输出栈" ;    
        cout<<"\n           7:清空栈" ;            
        cout<<"\n           0:操作结束" ;
        cout<<"\n===================================";
        cout<<"\n请输入你的选择:"; 
        cin>>choice;
        switch (choice)
        {
            case 1:    if(StackElemType(S))
                    cout<<"\n数据表为空表";
                    else
                    cout<<"\n数据表为非空表"; 
                       break;         
            case 2:    cout<<"\n数据栈的长度为："<<StackLength(S);
                       break;
            case 3:    if(StackElemType(S)) 
                    cout<<"\n栈为空，栈顶元素不存在！";
                    else
                    {
                        cout<<"\n栈顶元素为："<<GetTop(S);
                    } 
                       break;           
            case 4:    if(!Pop(S,e))
                    {
                        cout<<"\n栈为空，栈顶元素不存在！";
                    }
                    else
                    {
                    cout<<"\n栈顶出栈成功！"<<"\n出栈后的栈为：";
                    StackTraverse(S);
                    }
                    break;
            case 5:    cout<<"入栈元素为：";
                    cin>>e;
                    Push(S,e);
                    cout<<"\n入栈成功！"<<"\n入栈后的栈为：";
                    StackTraverse(S); 
                    break;
            case 6: cout<<"顺序栈为：";
                    StackTraverse(S);
                    break;
            case 7: ClearStack(S);
                       cout<<"成功清空！"<<"\n栈中无元素：";
                    StackTraverse(S);    
                    break;  
            case 0:    break; 
            default:cout<<"\n输入错误,重新输入！";            
        }
    } while (choice) ;    
    DestroyStack(S);
    return 0; 
}

2. 队列的定义、基本操作的实现

编程实现循环队列的基本操作

核心代码：

• comdef.h
•  #include <stdio.h>
     #include<stdlib.h>
     #include <iostream> 
     using namespace std;
     #define OK 1
     #define ERROR 0
     #define OVERFLOW -1
     typedef int Status;
     
• SqQueuedef.h
• typedef int QElemType;
  //队列的顺序存储结构 
  #define MAXQSIZE 100
  typedef struct {
      QElemType *base; //存储空间的基地址 
      int front;  //头指针 
      int rear;  //尾指针 
  }SqQueue;
   
• SqQueueapp.h

• //初始化空队列
  Status InitQueue(SqQueue &Q)
  {
      //构造空队列
      Q.base=new QElemType[MAXQSIZE]; //为队列分配一个最大容量为MAXQSIZE的数组空间 
      if(!Q.base) exit(OVERFLOW);
      Q.front=Q.rear=0;  //头指针和尾指针置空，队列为空 
      return OK;
   } 
  //打印队列
  void OutputQueue(SqQueue Q,int n)
  {
      if(Q.front==Q.rear) cout<<"队列为空"; 
      while(Q.front!=Q.rear)
      {
          cout<<Q.base[Q.front]<<"  ";
          Q.front=(Q.front+1)%(n+1); 
      }
      
  } 
  //判断队空
  Status QueueEmpty(SqQueue Q)
  {
      return (Q.front==Q.rear);
  }

  //求队列的长度
  int QueueLength(SqQueue Q)
  {
      return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
  }

  //取队首
  Status GetHead(SqQueue Q,QElemType &e)
  {
      if(Q.front==Q.rear) return ERROR;
      e=Q.base[Q.front]; //返回队头元素的值，队头元素不变 
      return OK;
  }

  //出队列
  Status DeQueue(SqQueue &Q,QElemType &e)
  {
      if(Q.front==Q.rear) return ERROR;
      e=Q.base[Q.front];  //保存队头元素 
      Q.front=(Q.front+1)%MAXQSIZE; //队头指针加一 
      return OK;
  }

  //入队列
  Status EnQueue(SqQueue &Q,QElemType e)
  {
      //插入e为新的队尾元素 
      if((Q.rear+1)%MAXQSIZE==Q.front)
      //尾指针在循环意义上加一，表明存储空间已满 
      return ERROR;
      Q.base[Q.rear]=e; //新元素为队尾 
      Q.rear=(Q.rear+1)%MAXQSIZE; //队尾指针加一 
      return OK;
  }

  //队列的销毁
  Status DestoryQueue(SqQueue &Q)
  {
      free(Q.base);
      Q.base=NULL;
      Q.front=Q.rear=0;
      
      return OK;
  }
   

• main.CPP

• #include "comdef.h"
  #include "SqQueuedef.h"
  #include "SqQueueapp.h"
  int main(){
      SqQueue Q;
      QElemType e;
      int choice,n,i;    
      cout<<"\n建立循环队列：";
      if (InitQueue(Q)==OVERFLOW){
            cout<<"队列空间分配失败,程序退出！";
           return 0;
           }
      else{
          cout<<"\n元素个数=";
            cin>>n;
            cout<<"\n输入"<<n<<"个队列元素: "; 
            for(int j=0;j<n;j++)
            {
                cin>>i;
                EnQueue(Q,i);    
          }
            cout<<"顺序队列建立成功，队列为：";
          OutputQueue(Q,n);    
      } 
      do { 
          cout<<"\n\n===================================";
          cout<<"\n        循环队列的基本操作           ";
          cout<<"\n===================================";
          cout<<"\n           1:判断队列空" ;
          cout<<"\n           2:求队列的长度" ;
          cout<<"\n           3:取队首" ;
          cout<<"\n           4:出队列" ;         
          cout<<"\n           5:入队列" ;    
          cout<<"\n           6:打印队列" ;    
          cout<<"\n           0:操作结束" ;
          cout<<"\n===================================";
          cout<<"\n请输入你的选择:"; 
          cin>>choice;
          switch (choice){
              case 1:    if(!QueueEmpty)
                      cout<<"此队列为空队列！";
                      else
                      cout<<"此队列非空！";
                         break;
              case 2:    cout<<"此队列的长度为"<<QueueLength(Q);
                         break;
              case 3:    GetHead(Q,e);
                      cout<<"队首为："<<e; 
                         break;           
              case 4:    DeQueue(Q,e);
                      cout<<"出队列的元素为："<<e<<"\n当前队列为：";
                      OutputQueue(Q,n); 
                      break;
              case 5:    cout<<"需要入队列的元素为：";
                      cin>>e; 
                      EnQueue(Q,e);                
                      cout<<"\n当前队列为："; 
                      OutputQueue(Q,n+1); 
                      break;
              case 6:    
                      cout<<"\n队列为：";
                      OutputQueue(Q,n);
                      break;
              case 0:    break; 
              default:cout<<"\n输入错误,重新输入！";            
          }
      } while (choice) ;    
      DestoryQueue(Q);    
      return 0; 
  }