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

实验编号：3 四川师大数据结构实验报告 2016年10月29日实验三 栈与队列及其应用_一 实验目得及要求（1） 掌握栈与队列这两种特殊得线性表，熟悉它们得特性，在实际问题背景下灵活运用它们；（2） 本实验训练得要点就是“栈”得观点及其典型用法；（3） 掌握问题求解得状态表示及其递归算法，以及由递归程序到非递归程序得转化方法。二 实验内容（1） 编程实现栈在两种存储结构中得基本操作（栈得初始化、判栈空、入栈、出栈等）；（2） 应用栈得基本操作，实现数制转换（任意进制）；（3） 编程实现队列在两种存储结构中得基本操作（队列得初始化、判队列空、入队列、出队列）；（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 已经创建一个存放字符型得栈 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);return 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) 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; 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;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;typedef 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 StackEmpty(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 *)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 *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;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、判断栈就是否为空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;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 int 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 StackEmpty(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、hStatus 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+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、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%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 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);/转换为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) exit (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-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、rear)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,判断队空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#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;QueuePrt 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顺序存储: 代码部分：/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(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(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;coutselect;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 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得对头元素，用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;typedef 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/创建栈 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 &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) return 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,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 SqStack * next;SqStack,*LinkStack;const int OK=1;const int ERROR=0;Status