《算法与数据结构》实验报告实验3__栈与队列的应用

1、算法与数据结构实验报告姓名学号专业班级计算机类1301指导教师实验名称实验3栈与队列的应用实验目的 了解并掌握栈与队列的概念与定义能够实现并运用栈与队列熟练运用栈与队列的基木操作使用栈实现回溯算法实验环境 个人计算机一台，cpu主频1ghz以上，1gb以上内存，2gb以上硬盘 剩余空间。 windows2000> windows xp 或 win 7 操作系统 code:blocks（版木12.11或近似版本，英文版），或vc+ 6.0实验内容1一基本部分（妙徴）1. 链式栈的创建与操作设链式栈屮元素的数据类型为整型，编写函数实现以下操作：（1）链式栈的初始化（2）链式栈的输出（从栈顶到

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

3、dfsd(fdsd)dfd)dfd是符号平衡的。adx(df)ds)不是符号平衡的o源代码：ds8.c实验代码:1.#include<stdio.h>#define maxsize maxlentypedef int elemtype;typedef struct stacknodeelemtype data;struct stacknode *next;jstacknode;typedef structstacknode *top; linkstack;int *initstack(linkstack *s);初始化链式栈 int *push(linkstack *s);入栈函数

4、 int *view(linkstack *s);输出函数 int *pop(linkstack *s);出栈函数 int stacktop(linkstack *s);取栈顶函数main()linkstack *s;int a;char k;s=initstack(s);if(s->top=null)printf(“该链式栈为空！ ”);push(s);printfc*按任意键开始出栈！ ”)；getchar();getchar();pop(s);a=stacktop(s);printfc栈顶元素为%d”,a);printfc*程序运行完毕，是否重新运行(y/n)： ”); scanf

5、("%s",&k);if(k=,y,)main();int *initstack(linkstack *s)s=(linkstack*)malloc(sizeof(linkstack);s->top=null;return(s);int *push(linkstack *s)int n,i,item;stacknode *p;printfc*请输入即将入栈的数据个数：”)； scanf("%d",&n);for(i=0;i<n;i+)printf(“请输入第d个数:”,i+1); scanf(h%d",&it

6、em);p=(linkstack*)malloc(sizeof(stacknode); p> data=item;p->next=null;p->next=s->top;s->top=p;view(s);return(s);int *view(linkstack *s)stacknode *p;if(s->top=null)printfc链式栈为空！ ”); return(o);else printf(n该链式栈从栈顶到栈底数据如h： n"); for(p=s->top;p!=null;p=p->next) printf("%

7、dn",p->data);int *pop(linkstack *s)stacknode *p;int item;char k;p=s->top;if(s->top=null)printf(“链式栈为空！ ”); return(o);elseitem=p > data;printf(h 出栈数据为 %dnh,item); s->top=p->next;free(p); view(s);printfc'是否继续出栈(y/n)： n);scanf("%s”,&k);if(k=y)pop(s);else return(s);in

8、t stacktop(linkstack *s)if(s->top=null)printf（“该链式栈为空！ ”）;return(s > top->data);2.#include<stdio.h>#define maxsize 30typedef int elemtype;typedef structelemtype datamaxsize;int front,rear;jseqqueue;int a=0;/全局变量int initqueue(seqqueue *q);初始化队列函数int view(seqqueue *q);输岀函数int enqueue(se

9、qqueue *q);入队函数int dequeue(seqqueue *q);出队函数main()seqqueue *q;q=initqueue(q); if(q->front=q->rear) printf(“该队列为空! ”);enqueue(q);printf(“按任意键开始出栈! ”)； getchar();getchar();dequeue(q);printfc*程序运行完毕，是否重新运行(y/n)： ”);int initqueue(seqqueue *q)q=(seqqueue*)malloc(sizeof(seqqueue);q->front=q >

10、rear=o;return(q);int enqueue(seqqueue *q)int n,i,item;printfc*请输入即将入队的数据个数：”)； scanf(h%dh,&n);if(a>maxsize) printf(“该队列已满! ”); return(o);else for(i=();i<n&&av=3();i+)printfc'i#输入第d 个数:”,i+1); scanf("%d",&item);q> dataq > rear=item;q->rear=(q->rear+1 )%

11、maxsize;a+;view(q); return(q);int view(seqqueue *q)seqqueue *r;int i,j；if(a=o) printfc*该队列为空！ ”)； return(o);else printf("该队列从栈顶到栈底数据如t： n*'); for(i=0,j=q->front;i<a;i4-4-,j=(j+1 )%maxsize) printf("%dn",q->dataj);return(q);int dequeue(seqqueue *q)elemtype item;char k;if(a=

12、o)printf(“该队列为空! ”); return(o);else item=q->dataq > front; q->front=(q->front+1 )%maxsize; printfc* 出队数据为 %dn”,item);； view(q);printf(n是否继续出栈(y/n)： n); scanf("%s",&k);if(k=,y,) dequeue(q);else return(q);3-#include "stdio.h"include ”stdlib.h”#define maxsize 100 typ

13、edef structchar datamaxsize;int top; stack;stack *initstack(stack *s)s=(stack *)malloc(sizeof(stack); s->top=-1;return s;int f(stack *s)int i=o,flag=l;char strmaxsize; printf("请输入表达式：”)； scanf("%s'str);for(i=0;stri!=,0,;i+)if(stri=,(,llstri=,'llstri=,)s->top+； s->data s> top=stri;if(stri=<rilstri=tllstri='')if(s->top>=0)if(s->datas->top=stri) s->top;elseflag=o;break;elseflag=o;break;if(s->top!