数据结构_实验三_栈和队列及其应用(27页).doc

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

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

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

3、创建一个存放字符型的栈 elect;cout endl;switch (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;elsecout 栈未空 endl;break;case 4:GetTop(S, e);cout e is e endl; break;case 5:StackLength(S);break;case 0:break;DestroyStack(S);r

4、eturn OK;/SStack.cpp:#includeSStack.h/输出菜单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) exi

5、t(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; coutpop succeedendl;return OK;/判栈空Status StackEmpty(SqStack S)if (S.top = S.base)return ERROR;return OK;/销毁栈Status DestroyStac

6、k(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#includeusing namespace std;const int STACK_INIT_SIZE = 100;const int STACKINCREMENT = 10;const int ERROR = 0;const int OK = 1;typ

7、edef char SElemType;typedef int Status;typedef struct SElemType *base;SElemType *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 St

8、ackEmpty(SqStack S);/判断栈是否为空Status DestroyStack(SqStack &S);/销毁栈int StackLength(SqStack S);/计算栈的长度 运行结果：B. 链式储存： 代码部分：/Main.cpp#includeLstack.hint 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 *)mal

9、loc(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 *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 ERRO

10、R;e=L-next-data;return OK;Status StackEmpty(Lq_Stack L)/判断栈是否为空if(L-next=NULL)return ERROR;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;

11、while(select)coutendl;cout请选择功能endl;cout1.入栈endl;cout2.出栈endl;cout3.得到顶部数据endl;cout4.判断栈是否为空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 fa

12、iledendl;break;case 3:if(GetTop(L,e)couthead data e is popendl;else coutGet failedendl;break;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#includeusing namespace std;const int OK=1;const in

13、t ERROR=0;typedef int SElemType;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 S

14、tackEmpty(Lq_Stack L);/判断栈是否为空int StackLength(Lq_Stack L);/计算栈的长度Status DestroyStack(Lq_Stack &L);/销毁栈void Menu(Lq_Stack &L,SElemType e);/输出菜单选择执行的功能 运行结果：（2）应用栈的基本操作，实现数制转换（任意进制）； 代码部分：/Main.cpp#includeSStack.hint main()int number;coutnumber;conversion(number);return 0;SStack.cpp#includeSStack.hSta

15、tus 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.dase = S.stacksize)/栈满追加空间S.dase=(ElemType *)realloc(S.dase,(STACK_INIT_SIZE+STACKINCREM

16、ENT) * 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.top;return OK;Status StackEmpty(SStack &S)/判断栈是否为空if(S.dase=S.top) return ERROR;return OK;void convers

17、ion(int number)/转换为e进制并输出SStack S;int N,e;if(InitStack(S)cout栈创建成功endl;coutN;while(N)push(S,N%number);N=N/number;while(StackEmpty(S)pop(S,e);coute;coutendl;/SStack.h#ifndef SSTACK_H#define SSTACK_H#include#includeusing namespace std;const int STACK_INIT_SIZE=100;const int STACKINCREMENT=10;const int

18、 OK=1;const int ERROR=0;typedef int Status;typedef int ElemType;typedef struct ElemType *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)

19、;/转换为number进制并输出#endif 运行结果：（3）编程实现队列在两种存储结构中的基本操作（队列的初始化、判队列空、入队列、出队列）。 代码部分：A:链式储存：/Main.cpp:#includeQNode.hint main()LinkQueue Q;InitQueue(Q);Menu(Q);DestroyQueue(Q);return 0;/QNode.cpp:#includeQNode.hStatus InitQueue(LinkQueue &Q)/构造空队列Q.front=Q.rear=(QueuePrt)malloc(sizeof(QNode);if(!Q.front) e

20、xit (ERROR);Q.front-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-ne

21、xt=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.rear)return ERROR;return OK;void

22、Menu(LinkQueue &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:cout输入入队数据e;if(EnQueue(Q,e)cout入队成功endl;break;case 2:if(DeQueue(Q,e)coute出队endl;break;case 3:if(QueueEmp

23、ty(Q) cout此队不为空endl;else cout此队为空endl;break;/QNode.h#ifndef QNODE_H#define QNODE_H#include#includeusing namespace std;const int OK=1;const int ERROR=0;typedef int QElemType;typedef int Status;typedef struct QNodeQElemType data;struct QNode * next;QNode,*QueuePrt;typedef struct QueuePrt front;QueuePr

24、t rear;LinkQueue;Status InitQueue(LinkQueue &Q);/构造空队列Status DestroyQueue(LinkQueue &Q);/销毁队列QStatus 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顺序存储: 代

25、码部分：/main.cpp:#includeSqQueue.hint main()SqQueue Q;if(InitQueue(Q)cout创建队成功endl; Menu(Q); DestroyQueue(Q);return 0;/SqQueue.cpp:#includeSqQueue.hStatus InitQueue(SqQueue &Q)/创建空队列Q.base=(QElemType *)malloc(MAXSIZE * sizeof(QElemType);if (!Q.base) exit(ERROR);Q.front=Q.rear=0;return OK;Status EnQueue

26、(SqQueue &Q,QElemType e)/插入元素e为Q的新队尾元素if(Q.rear+1)% MAXSIZE) = Q.front) 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(

27、SqQueue Q)/判断Q是否为空if(Q.front=Q.rear) return ERROR;return OK; 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，出队endl;cout 3，判断是否为空endl;cout 0，退出程序endl;coutsele

28、ct;switch (select)case 0:break;case 1:coute;if(EnQueue(Q,e)cout入队成功endl;else cout队满endl;break;case 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#includeusing namespace std;const int

29、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);/创建空队列Status EnQueue(SqQueue &Q,QElemType e);/插入元素e为Q的新队尾元素Status DeQueue(SqQueue &Q,QElemType &e);/删除Q的对头元素

30、，用e返回其值。Status SqQueueEmpty(SqQueue Q);/判断Q是否为空Status DestroyQueue(SqQueue &Q);/销毁栈void Menu(SqQueue &Q);/输出选择菜单#endif 运行结果：（4） 利用栈实现任一个表达式中的语法检查（括号的匹配）。 代码部分：/SqStack.h#include#includeusing namespace std;const int STACK_INIT_SIZE=100;const int STACKINCREMENT=10;const int ERROR=0;const int OK=0;type

31、def char SElemType;typedef int Status;typedef structSElemType *base;SElemType *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);/出栈/SqStack.cpp#includeSqStack.h/创建栈

32、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; /得到顶部数据 Status GetTop(SqStack S,SElemType &e) if(S.base=S.top) return ERROR; e=*(S.top-1); return OK; /入栈 Status Push (SqStack

33、&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) 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) r

34、eturn ERROR;e=*-S.top;return OK;/main.cpp#includeSqStack.hint 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);if (e=)Pop(S,

35、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#includeusing namespace std;typedef int Status;typedef char SElemType;typedef struct SqStackSElemType data;struct S

36、qStack * next;SqStack,*LinkStack;const int OK=1;const int ERROR=0;Status InitStack(LinkStack &S);/创建栈Status Push(LinkStack &S,SElemType e);/入栈Status 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#includeSqStack.hStatus InitStack(LinkStack &S)