《算法与数据结构》实验报告实验3

1、算法与数据结构实验报告姓名学号专业班级计算机类1301指导教师实验名称实验3栈与队列的应用实验目的了解并掌握栈与队列的概念与定义 能够实现并运用栈与队列 熟练运用栈与队列的基本操作 使用栈实现回溯算法实验环境个人计算机一台，CPU主频1GHz以上，1GB以上内存，2GB以上硬盘 剩余空间。Windows2000、Windows XP 或 Win 7 操作系统Code:Blocks(版本12.11或近似版本，英文版)，或VC+ 6.0实验内容1基本部分(必做)1 链式栈的创建与操作设链式栈中元素的数据类型为整型，编写函数实现以下操作：(1) 链式栈的初始化(2) 链式栈的输出(从栈顶到栈底)(3

2、) 链式栈的判空操作(4) 链式栈入栈操作(5) 链式栈的出栈操作6)取栈顶元素的值注：链式栈可不带头节点源代码：ds6.c2 循环队列的创建与操作设循环队列中元素的数据类型为整型，编写函数实现以下操作：1)循环队列的初始化(2) 循环队列的入栈(3) 循环队列的出栈(4) 取循环队列的栈顶元素(5) 循环队列的输出(从栈顶到栈底)源代码：ds7.c3 符号平衡问题在语言中往往需要判断一些符号是否是成对出现的，比如、()。如何让判断符号的对称也是很多语言的语法检查的首要任务。设计一个函数来检查表达式中的符号()、是否平衡。若平衡，返回1； 若不平衡返回0。例如：a(dda)dfsafddfsd

3、(fdsd)dfd)dfd是符号平衡的。adx(df)ds)不是符号平衡的。源代码：ds8.c实验代码：1.#in clude#defi ne MAXSIZE maxle ntypedef int elemtype;typedef struct stack nodeelemtype data; struct stack node *n ext;StackNode;typedef structStackNode *top;Lin kStack;int *InitStack(LinkStack *S); 初始化链式栈 int *Push(Li nkStack *S); 入栈函数 int *view

4、(LinkStack *S); 输出函数 int *Pop(LinkStack *S); 出栈函数 int StackTop(Li nkStack *S); 取栈顶函数mai n()Lin kStack *S;int a;char k;S=I ni tStack(S); if(S-top=NULL) printf(该链式栈为空!);Push(S);printf(按任意键开始出栈！);getchar();getchar();Pop(S);a=StackTop(S);printf(栈顶元素为%d,a);printf(程序运行完毕，是否重新运行(y/n)：); sca nf(%s,&k);if(k=

5、y)mai n();in t *In itStack(Li nkStack *S)S=(Li nkStack*)malloc(sizeof(L in kStack);S-top=NULL; return(S);int *Push(L in kStack *S)int n ,i,item;StackNode *p;printf(请输入即将入栈的数据个数：);sca nf(%d,&n);for(i=0;i data=item;p-n ext=NULL;p-n ext=S-top;S-top=p;view(S);return(S);int *view(L in kStack *S)StackNode

6、 *p;if(S-top=NULL)printf(链式栈为空!); return(O);n);else printf(该链式栈从栈顶到栈底数据如下:for(p=S-top;p!=NULL;p=p-n ext)prin tf(%dn,p-data);int *Pop(Li nkStack *S)StackNode *p;int item;char k;p=S-top;if(S-top=NULL)printf(链式栈为空!); return(O);elseitem=p-data;printf(出栈数据为 %dn,item); S-top=p-n ext;free(p);view(S);printf

7、(是否继续出栈(y/n)：);sca nf(%s,&k);if(k=y)Pop(S);else return(S);int StackTop(Li nkStack *S) if(S-top=NULL)printf（该链式栈为空！）; return(S-top-data);2.#in clude#defi ne MAXSIZE 30typedef int elemtype;typedef structelemtype dataMAXSIZE;int fron t,rear;seqqueue;int a=0;全局变量int Ini tQueue(seqqueue *Q);/初 始化队列函数 in

8、t view(seqqueue *Q);/输出函数int En Queue(seqqueue *Q);/入 队函数int DeQueue(seqqueue *Q);/出 队函数mai n()seqqueue *Q;Q=I ni tQueue(Q);if(Q-fr on t=Q-rear)printf(该队列为空！);En Queue(Q);printf(按任意键开始出栈！); getchar();getchar();DeQueue(Q);printf(程序运行完毕，是否重新运行(y/n)：);int In itQueue(seqqueue *Q) Q=(seqqueue*)malloc(siz

9、eof(seqqueue);Q-fro nt=Q-rear=O;return(Q);int En Queue(seqqueue *Q)int n ,i,item;printf(请输入即将入队的数据个数：); sca nf(%d,&n);if(aMAXSIZE)printf(该队列已满！); return(O);else for(i=0;i n&adataQ-rear=item;Q-rear=(Q-rea 叶1)%MAXSIZE;a+; view(Q); return(Q);int view(seqqueue *Q)seqqueue *r;int i,j;if(a=0)printf(该队列为空！

10、);return(0);n);else prin tf(该队列从栈顶到栈底数据如下: for(i=0,j=Q-fro nt;idataj);return(Q);int DeQueue(seqqueue *Q)elemtype item;char k;if(a=0)printf(该队列为空！); return(O);elseitem=Q-dataQ-fr on t;Q-fro nt=(Q-fro nt+1)%MAXSIZE; printf(出队数据为 %dn,item); a_； view(Q);printf(是否继续出栈(y/n)：);sca nf(%s,&k);if(k=y) DeQueue

11、(Q);else return(Q);3#i nclude stdio.h#i nclude stdlib.h#defi ne MAXSIZE 100typedef structchar dataMAXSIZE;int top; stack;stack *lni tStack(stack *s)s=(stack *)malloc(sizeof(stack);s-top=-1;return s;int f(stack *s)int i=0,flag=1;char strMAXSIZE;printf(请输入表达式：);sca nf(%s,str);for(i=0;stri!=0;i+)if(stri=(|stri=|stri=)s-top+; s-datas-top=stri; if(stri=)|stri=|stri=)if(s-top=0)if(s-datas-top=stri) s-top-; elseflag=0;break;elseflag=0;break;if(s-top!=-1)flag=0;return flag;int