数据结构_实验三_栈和队列和应用32362.pdf

《数据结构_实验三_栈和队列和应用32362.pdf》由会员分享，可在线阅读，更多相关《数据结构_实验三_栈和队列和应用32362.pdf（33页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

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:#includeSStack.h int main()SqStack S;SElemType e;.int elect=1;InitStack(S);cout 已经创建一个存放字符型的栈 elect;cout endl;swi

3、tch(elect)case 1:cout e;Push(S,e);break;case 2:if(Pop(S,e)cout e is pop endl;elsecoutblankendl;break;case 3:if(StackEmpty(S)cout 栈空 endl;else cout 栈未空 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.cpp:#includeSStack.h

4、/输出菜单 void Muse()cout 请选择功能：endl;cout 1.入栈 endl;cout 2.出栈 endl;cout 3.判栈空 endl;cout 4.返回栈顶部数据 endl;cout 5.栈长 endl;cout 0.退出系统 endl;cout=STACK_INIT_SIZE)S.base=(SElemType*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT)*sizeof(SElemType);if(!S.base)exit(ERROR);S.top=S.base+S.stacksize;S.stacksize+=ST

5、ACKINCREMENT;*S.top+=e;return OK;/出栈 Status Pop(SqStack&S,SElemType&e).if(S.base=S.top)return ERROR;e=*-S.top;coutpop succeedendl;return OK;/判栈空 Status StackEmpty(SqStack S)if(S.top=S.base)return ERROR;return OK;/销毁栈 Status DestroyStack(SqStack&S)free(S.base);S.top=NULL;S.stacksize=0;cout 栈已销毁 endl;

6、return OK;int StackLength(SqStack S)cout StackLength is S.top-S.base endl;return OK;./SStack.h:#include#include 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;SElem

7、Type*top;int stacksize;SqStack;Status InitStack(SqStack&S);/创建顺序存储的栈 Status GetTop(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

8、(SqStack S);/计算栈的长度 运行结果：.B.链式储存：代码部分：/Main.cpp#includeLstack.h int main()Lq_Stack L;if(InintStack(L)coutbuild stack succeeddata=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;retur

9、n OK;Status pop(Lq_Stack&L,SElemType&e)/出栈 LqStack*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 ERR

10、OR;else 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).coutendl;cout请选择功能endl;cout1.入栈endl;cout2.出栈endl;cout3.得到顶部数据endl;cout4.判断

11、栈是否为空endl;cout5.输出栈的长度endl;cout0.退出程序endl;coutselect;switch(select)case 0:break;case 1:coute;if(push(L,e)coutpush succeedendl;else coutpush failedendl;break;case 2:if(pop(L,e)coutdata e is popendl;else coutpop failedendl;break;case 3:if(GetTop(L,e)couthead data e is popendl;else coutGet failedendl;b

12、reak;.case 4:if(StackEmpty(L)coutstack is not NULLendl;else coutstack is NULLendl;break;case 5:coutthis stack length is StackLength(L)endl;break;/Lstack.h#include#include using namespace std;const int OK=1;const int ERROR=0;typedef int SElemType;typedef int Status;typedef struct LqStack SElemType da

13、ta;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 StackEmpty(Lq_Stack L);/判断栈是否为空.int StackLength(Lq_Stack L);/计算栈的长度 Status DestroyStack(Lq_S

14、tack&L);/销毁栈 void Menu(Lq_Stack&L,SElemType e);/输出菜单选择执行的功能 运行结果：（2）应用栈的基本操作，实现数制转换（任意进制）；代码部分：/Main.cpp#includeSStack.h int main()int number;coutnumber;conversion(number);return 0;SStack.cpp#includeSStack.h Status InitStack(SStack&S)./创建栈 S.dase=(ElemType*)malloc(STACK_INIT_SIZE*sizeof(ElemType);if

15、(!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.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+=STACKINC

16、REMENT;*S.top+=e;return OK;Status pop(SStack&S,ElemType&e)/出栈 if(S.top=S.dase)return ERROR;e=*-S.top;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;coutN;while(N)push(S,N%numb

17、er);N=N/number;while(StackEmpty(S)pop(S,e);coute;coutendl;/SStack.h#ifndef SSTACK_H#define SSTACK_H#include#include 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 ElemType*dase;Ele

18、mType*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）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）。代码部分：A:链式储存：/Main.cpp:#in

19、cludeQNode.h int main()LinkQueue Q;InitQueue(Q);.Menu(Q);DestroyQueue(Q);return 0;/QNode.cpp:#includeQNode.h Status InitQueue(LinkQueue&Q)/构造空队列 Q.front=Q.rear=(QueuePrt)malloc(sizeof(QNode);if(!Q.front)exit(ERROR);Q.front-next=NULL;return OK;Status DestroyQueue(LinkQueue&Q)/销毁队列 Q while(Q.front)Q.r

20、ear=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-next=p;.Q.rear=p;return OK;Status DeQueue(LinkQueue&Q,QElemType&e)/删除 Q 的队头元素，用 e 返回其值 QNode*p;if(

21、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.rear)return ERROR;return OK;void Menu(LinkQueue&Q)/输出选择界面 int select=1;QElemType e;while(select)cout-endl;cout请选择以下功能：endl;cout-1,入

22、队endl;cout-2,出队endl;cout-3,判断队空endl;cout-0,退出程序endl;.coutselect;switch(select)case 0:break;case 1:cout输入入队数据e;if(EnQueue(Q,e)cout入队成功endl;break;case 2:if(DeQueue(Q,e)coute出队endl;break;case 3:if(QueueEmpty(Q)cout此队不为空endl;else cout此队为空endl;break;/QNode.h#ifndef QNODE_H#define QNODE_H#include#include

23、using namespace std;.const int OK=1;const int ERROR=0;typedef int QElemType;typedef int Status;typedef struct QNode QElemType data;struct QNode*next;QNode,*QueuePrt;typedef struct QueuePrt front;QueuePrt rear;LinkQueue;Status InitQueue(LinkQueue&Q);/构造空队列 Status DestroyQueue(LinkQueue&Q);/销毁队列 Q Sta

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

25、stroyQueue(Q);return 0;/SqQueue.cpp:#includeSqQueue.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.front)return ERROR;Q.baseQ.rea

26、r=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;Status DestroyQueue(SqQueue&Q)/销毁栈

27、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，出队endl;cout 3，判断是否为空endl;cout 0，退出程序endl;coutselect;switch(select)case 0:break;case 1:coute;if(EnQueue(Q,e)cout入队成功endl;else cout队满endl;break;cas

28、e 2:if(DeQueue(Q,e)coute出队endl;else cout队空endl;break;case 3:if(SqQueueEmpty(Q)cout队未空endl;else cout队空endl;break;./SqQueue.h:#ifndef SQQUEUE_H#define SQQUEUE_H#include#include using namespace std;const int MAXSIZE=100;const int MORE=100;const int OK=1;const int ERROR=0;typedef int QElemType;typedef i

29、nt Status;typedef struct QElemType*base;int front;int rear;SqQueue;Status InitQueue(SqQueue&Q);/创建空队列 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

30、 Menu(SqQueue&Q);/输出选择菜单 .#endif 运行结果：（4）利用栈实现任一个表达式中的语法检查（括号的匹配）。代码部分：/SqStack.h#include#include 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 struct SElemType*base;.SElemType*top;int

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

32、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*)realloc(S.base,(STACK_INIT_SIZE+STACKINCREMENT

33、)*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#includeSqStack.h int main()char c;SElemType e;SqStack S;InitStack(S);while(c=getchar()!=

34、#)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);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;else cout括号不完全匹配endl;return OK;运行结果：（5）利用栈

35、实现表达式的求值。代码部分：/SqStack.h#include#include using namespace std;.typedef int Status;typedef char SElemType;typedef struct SqStack SElemType data;struct SqStack*next;SqStack,*LinkStack;const int OK=1;const int ERROR=0;Status InitStack(LinkStack&S);/创建栈 Status Push(LinkStack&S,SElemType e);/入栈 Status Pop

36、(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#includeSqStack.h Status InitStack(LinkStack&S)/创建栈 S

37、=(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(LinkStack&S,SElemType&e)/出栈 SqStack*p;if(S-next=NULL)return ERRO

38、R;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,1,2,3,4,5,6,7,8,9;InitStack(OPTR);Push(OPTR,#);InitStack(OPND);.c=getchar();while(c!=#|GetTop(OPTR)!=#)if(!In(c,

39、OP)Push(OPND,c);c=getchar();else switch(Precede(GetTop(OPTR),c)case:Pop(OPTR,thate);Pop(OPND,b);Pop(OPND,a);Push(OPND,Operate(a,thate,b);break;return GetTop(OPND);Status In(char c,char*OP)/判断 C 是否是数 for(int i=0;i,=;/优先关系表 for(i=0;i7;i+)if(ai=x)break;for(j=0;j7;j+)if(aj=y)break;return bij;SElemType O

40、perate(char x,char thate,char y)/运算返回结果 char a4=+,-,*,/;/运算符 int i,j,k;for(i=0;i4;i+)if(ai=thate)break;x-=48;.y-=48;switch(i)case 0:return x+y+48;case 1:return x-y+48;case 2:return x*y+48;case 3:return x/y+48;return ERROR;/main.cpp#includeSqStack.h int main()cout请输入十以的表达式(以#号结束)endl;cout该表达式的值是：(int)EvaluateExpression()-48endl;return 0;运行结果：五实验结果的分析与评价（该部分如不够填写，请另加附页）1.栈先入后出,利用这一特性可以解决很多问题,但是也有很多弊端 2.表达式求值比较麻烦涉及到的知识有点多,函数也比较复杂.不过用工程将文件分类后还是清晰简单了些.也方便修改.注：实验成绩等级分为（90100 分）优，（8089 分）良，(70-79 分)中，（6069 分）及格，（59 分）不及格。