数据结构实验三栈和队列及其应用

1、实验编号：3 四川师大数据结构实验报告 2016年10月29日实验三 栈和队列及其应用_一 实验目的及要求（1） 掌握栈和队列这两种特殊的线性表，熟悉它们的特性，在实际问题背景下灵活运用它们；（2） 本实验训练的要点是“栈”的观点及其典型用法；（3） 掌握问题求解的状态表示及其递归算法，以及由递归程序到非递归程序的转化方法。二 实验内容（1） 编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；（2） 应用栈的基本操作，实现数制转换（任意进制）；（3） 编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）；（4） 利用栈实现任一个表达式中的语法

2、检查（括号的匹配）。（5） 利用栈实现表达式的求值。注：（1）（3）必做，（4）（5）选做。三 主要仪器设备及软件（1）PC机（2）Dev C+ ,Visual C+, VS2010等四 实验主要流程、基本操作或核心代码、算法片段（该部分如不够填写，请另加附页）（1） 编程实现栈在两种存储结构中的基本操作（栈的初始化、判栈空、入栈、出栈等）；A.顺序储存：Ø 代码部分：/Main.cpp:#include"SStack.h"int main()SqStack S;SElemType e;int elect=1;InitStack(S);cout <<

3、"已经创建一个存放字符型的栈" << endl;while (elect)Muse();cin >> elect;cout << endl;switch (elect)case 1:cout << "input data:"cin >> e;Push(S, e);break;case 2: if(Pop(S, e)cout << e <<" is pop"<< endl; elsecout<<"blank"&

4、lt;<endl;break;case 3:if (StackEmpty(S)cout << "栈空 " << endl;elsecout << "栈未空 " << endl;break;case 4:GetTop(S, e);cout << "e is " << e << endl; break;case 5:StackLength(S);break;case 0:break;DestroyStack(S);return OK;/SStack.

5、cpp:#include"SStack.h"/输出菜单void Muse()cout << "请选择功能：" << endl;cout << " 1.入栈" << endl;cout << " 2.出栈" << endl;cout << " 3.判栈空" << endl;cout << " 4.返回栈顶部数据" << endl;cout << &

6、quot; 5.栈长" << endl;cout << " 0.退出系统" << endl;cout << "你的选择是：" ;/创建栈 Status InitStack(SqStack &S)S.base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType);if (!S.base) exit(ERROR);S.top = S.base;S.stacksize = STACK_INIT_SIZE;return OK;/得到顶部

7、数据 Status GetTop(SqStack S, SElemType &e)if (S.base = S.top) return ERROR;e = *(S.top - 1);return OK;/入栈Status Push(SqStack &S, SElemType &e)if (S.top - S.base >= STACK_INIT_SIZE)S.base = (SElemType *)realloc(S.base, (STACK_INIT_SIZE + STACKINCREMENT) * sizeof(SElemType);if (!S.base)

8、exit(ERROR);S.top = S.base + S.stacksize;S.stacksize += STACKINCREMENT;*S.top+ = e;return OK;/出栈Status Pop(SqStack &S, SElemType &e)if (S.base = S.top)return ERROR;e = *-S.top; cout<<"pop succeed"<<endl;return OK;/判栈空Status StackEmpty(SqStack S)if (S.top = S.base)return

9、 ERROR;return OK;/销毁栈Status DestroyStack(SqStack &S)free(S.base);S.top=NULL;S.stacksize = 0;cout << "栈已销毁" << endl;return OK;int StackLength(SqStack S)cout << "StackLength is "<<S.top-S.base << endl;return OK;/SStack.h:#include<iostream>#in

10、clude<stdlib.h>using namespace std;const int STACK_INIT_SIZE = 100;const int STACKINCREMENT = 10;const int ERROR = 0;const int OK = 1;typedef char SElemType;typedef int Status;typedef struct SElemType *base;SElemType *top;int stacksize;SqStack;Status InitStack(SqStack &S);/创建顺序存储的栈Status G

11、etTop(SqStack S, SElemType &e);/得到栈顶数据Status Push(SqStack &S, SElemType &e);/入栈Status Pop(SqStack &S, SElemType &e);/出栈void Muse();/输出菜单界面Status StackEmpty(SqStack S);/判断栈是否为空Status DestroyStack(SqStack &S);/销毁栈int StackLength(SqStack S);/计算栈的长度Ø 运行结果：B. 链式储存：Ø 代码部分

12、：/Main.cpp#include"Lstack.h"int main()Lq_Stack L;if(InintStack (L)cout<<"build stack succeed"<<endl;else exit (ERROR);int e=0;Menu(L,e);DestroyStack(L);return 0;/Lstack.cpp#include"Lstack.h"Status InintStack(Lq_Stack &L)/创建栈L=(LqStack *)malloc(sizeof(LqS

13、tack);if(!L) exit(ERROR);L->data=0;L->next=NULL;return OK;Status push (Lq_Stack &L,SElemType e)/入栈LqStack *p;p=(LqStack *)malloc(sizeof(LqStack);if(!p) exit(ERROR);p->data=e;L->data+;p->next=L->next;L->next=p;return OK;Status pop (Lq_Stack &L,SElemType &e)/出栈LqStack

14、*p;if(L->next=NULL) return ERROR;p=L->next;e=p->data;L->next=p->next;L->data-;free(p);return OK;Status GetTop(Lq_Stack L, SElemType &e)/得到栈顶数据if(L->next=NULL) return ERROR;e=L->next->data;return OK;Status StackEmpty(Lq_Stack L)/判断栈是否为空if(L->next=NULL)return ERROR;el

15、se return OK;int StackLength(Lq_Stack L)/计算栈的长度return L->data;Status DestroyStack(Lq_Stack &L)/销毁栈LqStack *p;while(!L)L=p;L=L->next;free(p);return OK;void Menu(Lq_Stack &L,SElemType e)/输出菜单选择执行的功能int select=1;while(select)cout<<""<<endl;cout<<"请选择功能&quo

16、t;<<endl;cout<<"1.入栈"<<endl;cout<<"2.出栈"<<endl;cout<<"3.得到顶部数据"<<endl;cout<<"4.判断栈是否为空"<<endl;cout<<"5.输出栈的长度"<<endl;cout<<"0.退出程序"<<endl;cout<<"你的选择是：

17、"cin>>select;switch (select)case 0:break;case 1:cout<<"push data:"cin>>e;if(push(L,e)cout<<"push succeed"<<endl;else cout<<"push failed"<<endl;break;case 2:if(pop(L,e)cout<<"data "<<e<<" is

18、pop"<<endl;else cout<<"pop failed"<<endl;break;case 3:if(GetTop(L,e)cout<<"head data "<<e<<" is pop"<<endl;else cout<<"Get failed"<<endl;break;case 4:if(StackEmpty(L)cout<<"stack is not NULL

19、"<<endl;else cout<<"stack is NULL"<<endl;break;case 5:cout<<"this stack length is "<<StackLength(L)<<endl;break;/Lstack.h#include<iostream>#include<stdlib.h>using namespace std;const int OK=1;const int ERROR=0;typedef int SElem

20、Type;typedef int Status;typedef struct LqStackSElemType data;struct LqStack *next;LqStack,*Lq_Stack;Status InintStack (Lq_Stack &L);/创建栈Status push (Lq_Stack &L,SElemType e);/入栈Status pop (Lq_Stack &L,SElemType &e);/出栈Status GetTop(Lq_Stack L, SElemType &e);/得到栈顶数据Status StackEmp

21、ty(Lq_Stack L);/判断栈是否为空int StackLength(Lq_Stack L);/计算栈的长度Status DestroyStack(Lq_Stack &L);/销毁栈void Menu(Lq_Stack &L,SElemType e);/输出菜单选择执行的功能Ø 运行结果：（2）应用栈的基本操作，实现数制转换（任意进制）；Ø 代码部分：/Main.cpp#include"SStack.h"int main()int number;cout<<"要将数值转换为多少进制 "cin>

22、>number;conversion(number);return 0;SStack.cpp#include"SStack.h"Status InitStack(SStack &S)/创建栈S.dase=(ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType);if (!S.dase) exit(ERROR);S.top=S.dase;S.stacksize=STACK_INIT_SIZE;return OK;Status push(SStack &S,ElemType e)/入栈if(S.top-S.

23、dase >= S.stacksize)/栈满追加空间S.dase=(ElemType *)realloc(S.dase,(STACK_INIT_SIZE+STACKINCREMENT) * sizeof(ElemType);if(!S.dase) exit(ERROR);S.top=S.dase+STACK_INIT_SIZE;S.stacksize+=STACKINCREMENT;*S.top+=e;return OK;Status pop(SStack &S,ElemType &e)/出栈if(S.top= S.dase) return ERROR;e=*-S.to

24、p;return OK;Status StackEmpty(SStack &S)/判断栈是否为空if(S.dase=S.top) return ERROR;return OK;void conversion(int number)/转换为e进制并输出SStack S;int N,e;if(InitStack(S)cout<<"栈创建成功"<<endl;cout<<"输入待转换的数："cin>>N;while(N)push(S,N%number);N=N/number;while(StackEmpty

25、(S)pop(S,e);cout<<e;cout<<endl;/SStack.h#ifndef SSTACK_H#define SSTACK_H#include<iostream>#include<stdlib.h>using namespace std;const int STACK_INIT_SIZE=100;const int STACKINCREMENT=10;const int OK=1;const int ERROR=0;typedef int Status;typedef int ElemType;typedef struct El

26、emType *dase;ElemType *top;int stacksize;SStack;Status InitStack(SStack &S);/创建栈Status push(SStack &S,ElemType e);/入栈Status push(SStack &S,ElemType &e);/出栈Status StackEmpty(SStack &S);/判断栈是否为空void conversion(int number);/转换为number进制并输出#endifØ 运行结果：（3）编程实现队列在两种存储结构中的基本操作（队列的初

27、始化、判队列空、入队列、出队列）。Ø 代码部分：A:链式储存：/Main.cpp:#include"QNode.h"int main()LinkQueue Q;InitQueue(Q);Menu(Q);DestroyQueue(Q);return 0;/QNode.cpp:#include"QNode.h"Status InitQueue(LinkQueue &Q)/构造空队列Q.front=Q.rear=(QueuePrt)malloc(sizeof(QNode);if(!Q.front) exit (ERROR);Q.front-&

28、gt;next=NULL;return OK; Status DestroyQueue(LinkQueue &Q)/销毁队列Qwhile(Q.front)Q.rear=Q.front->next;free(Q.front);Q.front=Q.rear;return OK;Status EnQueue (LinkQueue &Q,QElemType e)/插入元素a为Q的新的队尾元素QNode *p;p=(QueuePrt)malloc(sizeof(QNode);if(!p) exit(ERROR);p->data=e;p->next=NULL;Q.rear

29、->next=p;Q.rear=p;return OK;Status DeQueue (LinkQueue &Q,QElemType &e)/删除Q的队头元素，用e返回其值QNode *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;free(p);return OK;Status QueueEmpty(LinkQueue Q)/判断对是否为空if(Q.front=Q.re

30、ar)return ERROR;return OK;void Menu(LinkQueue &Q)/输出选择界面int select=1;QElemType e;while(select)cout<<"-"<<endl;cout<<"请选择以下功能："<<endl;cout<<"-1,入队"<<endl;cout<<"-2,出队"<<endl;cout<<"-3,判断队空"<

31、<endl;cout<<"-0,退出程序"<<endl;cout<<"请输入你的选择"cin>>select;switch (select)case 0:break;case 1:cout<<"输入入队数据"<<endl;cin>>e;if(EnQueue(Q,e)cout<<"入队成功"<<endl;break;case 2:if(DeQueue(Q,e)cout<<e<<&q

32、uot;出队"<<endl;break;case 3:if(QueueEmpty(Q) cout<<"此队不为空"<<endl;else cout<<"此队为空"<<endl;break;/QNode.h#ifndef QNODE_H#define QNODE_H#include<iostream>#include<stdlib.h>using namespace std;const int OK=1;const int ERROR=0;typedef int

33、QElemType;typedef int Status;typedef struct QNodeQElemType data;struct QNode * next;QNode,*QueuePrt;typedef struct QueuePrt front;QueuePrt rear;LinkQueue;Status InitQueue(LinkQueue &Q);/构造空队列Status DestroyQueue(LinkQueue &Q);/销毁队列QStatus EnQueue (LinkQueue &Q,QElemType e);/插入元素a为Q的新的队尾元素

34、Status DeQueue (LinkQueue &Q,QElemType &e);/删除Q的队头元素，用e返回其值Status QueueEmpty(LinkQueue Q);/判断对是否为空void Menu(LinkQueue &Q);/输出选择界面#endifØ 运行结果：B顺序存储:Ø 代码部分：/main.cpp:#include"SqQueue.h"int main()SqQueue Q;if(InitQueue(Q)cout<<"创建队成功"<<endl; Menu(Q

35、); DestroyQueue(Q);return 0;/SqQueue.cpp:#include"SqQueue.h"Status InitQueue(SqQueue &Q)/创建空队列Q.base=(QElemType *)malloc(MAXSIZE * sizeof(QElemType);if (!Q.base) exit(ERROR);Q.front=Q.rear=0;return OK;Status EnQueue(SqQueue &Q,QElemType e)/插入元素e为Q的新队尾元素if(Q.rear+1)% MAXSIZE) = Q.fr

36、ont) return ERROR;Q.baseQ.rear=e;Q.rear=(Q.rear+1)%MAXSIZE;return OK;Status DeQueue(SqQueue &Q,QElemType &e)/删除Q的对头元素，用e返回其值。if(Q.front = Q.rear) return ERROR;e=Q.baseQ.front;Q.front=(Q.front+1)%MAXSIZE;return OK;Status SqQueueEmpty(SqQueue Q)/判断Q是否为空if(Q.front=Q.rear) return ERROR;return OK

37、; Status DestroyQueue(SqQueue &Q)/销毁栈Q.front=Q.rear=0;free(Q.base);return OK;void Menu(SqQueue &Q)/输出选择菜单int select=1;QElemType e;while (select)cout<<"-"<<endl;cout<<"请选择一下功能:"<<endl;cout<<" 1，入队"<<endl;cout<<" 2，出队

38、"<<endl;cout<<" 3，判断是否为空"<<endl;cout<<" 0，退出程序"<<endl;cout<<"你的选择是："cin>>select;switch (select)case 0:break;case 1:cout<<"输入插入的数据:"cin>>e;if(EnQueue(Q,e)cout<<"入队成功"<<endl;else co

39、ut<<"队满"<<endl;break;case 2:if(DeQueue(Q,e)cout<<e<<"出队"<<endl;else cout<<"队空"<<endl;break;case 3:if(SqQueueEmpty(Q)cout<<"队未空"<<endl;else cout<<"队空"<<endl;break;/SqQueue.h:#ifndef SQQ

40、UEUE_H#define SQQUEUE_H#include<iostream>#include<stdlib.h>using namespace std;const int MAXSIZE=100;const int MORE=100;const int OK=1;const int ERROR=0;typedef int QElemType;typedef int Status;typedef structQElemType *base;int front ;int rear;SqQueue;Status InitQueue(SqQueue &Q);/创建

41、空队列Status EnQueue(SqQueue &Q,QElemType e);/插入元素e为Q的新队尾元素Status DeQueue(SqQueue &Q,QElemType &e);/删除Q的对头元素，用e返回其值。Status SqQueueEmpty(SqQueue Q);/判断Q是否为空Status DestroyQueue(SqQueue &Q);/销毁栈void Menu(SqQueue &Q);/输出选择菜单#endifØ 运行结果：（4） 利用栈实现任一个表达式中的语法检查（括号的匹配）。Ø 代码部分：/SqS

42、tack.h#include<iostream>#include<stdlib.h>using namespace std;const int STACK_INIT_SIZE=100;const int STACKINCREMENT=10;const int ERROR=0;const int OK=0;typedef char SElemType;typedef int Status;typedef structSElemType *base;SElemType *top;int stacksize;SqStack;Status InitStack (SqStack

43、&S); /创建栈Status GetTop(SqStack S,SElemType &e);/得到栈顶元素Status Push (SqStack &S,SElemType &e);/入栈Status Pop (SqStack &S,SElemType &e);/出栈/SqStack.cpp#include"SqStack.h"/创建栈 Status InitStack (SqStack &S) S.base=(SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType

44、); if(!S.base) exit(ERROR); S.top=S.base; S.stacksize=STACK_INIT_SIZE; return OK; /得到顶部数据 Status GetTop(SqStack S,SElemType &e) if(S.base=S.top) return ERROR; e=*(S.top-1); return OK; /入栈 Status Push (SqStack &S,SElemType &e) if (S.top-S.base>=STACK_INIT_SIZE) S.base=(SElemType *)real

45、loc(S.base,(STACK_INIT_SIZE+STACKINCREMENT) * sizeof(SElemType); if(!S.base) exit(ERROR); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e; return OK; /出栈Status Pop (SqStack &S,SElemType &e) if(S.base=S.top) return ERROR;e=*-S.top;return OK;/main.cpp#include"SqStack.h&qu

46、ot;int main()char c; SElemType e;SqStack S;InitStack(S);while(c=getchar()!='#')switch(c)case '(':case '':case '':Push (S,c); break;case ')': if (S.top=S.base) break;GetTop(S,e);if (e='(')Pop(S,e);break;case '':if (S.top=S.base) break;GetTop(S,e

47、);if (e='')Pop(S,e); break;case '':if (S.top=S.base) break;GetTop(S,e);if (e='')Pop(S,e); break;if (S.base=S.top)cout<<"括号完全匹配"<<endl; elsecout<<"括号不完全匹配"<<endl; return OK; Ø 运行结果：（5） 利用栈实现表达式的求值。Ø 代码部分：/SqStack.h#include&

48、lt;iostream>#include<stdlib.h>using namespace std;typedef int Status;typedef char SElemType;typedef struct SqStackSElemType data;struct SqStack * next;SqStack,*LinkStack;const int OK=1;const int ERROR=0;Status InitStack(LinkStack &S);/创建栈Status Push(LinkStack &S,SElemType e);/入栈Stat

49、us Pop(LinkStack &S,SElemType &e);/出栈SElemType GetTop(LinkStack &S);/得到顶部数据SElemType EvaluateExpression();/表达式求值Status In(char c,char *OP);/判断C是否是数SElemType Precede(char x,char y);/判断优先关系SElemType Operate(char a,char thate,char b);/运算返回结果/SqStack.cpp#include"SqStack.h"Status In

50、itStack(LinkStack &S)/创建栈S=(LinkStack)malloc(sizeof(SElemType);if (!S) exit (ERROR);S->next=NULL;return OK;Status Push(LinkStack &S,SElemType e)/入栈SqStack *p;p=(LinkStack)malloc(sizeof(SElemType);if (!p) exit (ERROR);p->data=e;p->next=S->next;S->next=p;return OK;Status Pop(Lin

51、kStack &S,SElemType &e)/出栈SqStack *p;if(S->next=NULL) return ERROR;p=S->next;e=p->data;S->next=p->next;return OK;SElemType GetTop(LinkStack &S)/得到顶部数据return S->next->data;SElemType EvaluateExpression()/表达式求值LinkStack OPTR,OPND;char a,b,c,x,thate;char OP10='0'

52、,'1','2','3','4','5','6','7','8','9'InitStack(OPTR);Push(OPTR,'#');InitStack(OPND);c=getchar();while(c!='#'|GetTop(OPTR)!='#')if(!In(c,OP)Push(OPND,c);c=getchar();elseswitch (Precede(GetTop(OPTR),c)case '<':Push(OPTR,c);c=getchar();break;case '=':Pop(OPTR,x);c=getchar();break;case '>':Pop(OPTR,thate);Pop(OPND,b);Pop(OPND,a);Push(OPN