《算法与数据结构》实验报告
姓名 学号
实验名称
专业班级 计算机类1301
指导教师
实验3 栈与队列的应用
实验目的
? ? ? ?
了解并掌握栈与队列的概念与定义 能够实现并运用栈与队列 熟练运用栈与队列的基本操作 使用栈实现回溯算法
实验环境
? 个人计算机一台，CPU主频1GHz以上，1GB以上内存，2GB以上硬盘
剩余空间。
? Windows2000、Windows XP或Win 7操作系统
? Code::Blocks(版本12.11或近似版本，英文版)，或VC++ 6.0
实验内容
1 基本部分(必做)
1．链式栈的创建与操作
设链式栈中元素的数据类型为整型，编写函数实现以下操作： （1）链式栈的初始化
（2）链式栈的输出（从栈顶到栈底） （3）链式栈的判空操作 （4）链式栈入栈操作 （5）链式栈的出栈操作 （6）取栈顶元素的值 注：链式栈可不带头节点
源代码：ds6.c
2．循环队列的创建与操作
设循环队列中元素的数据类型为整型，编写函数实现以下操作： （1）循环队列的初始化 （2）循环队列的入栈 （3）循环队列的出栈
（4）取循环队列的栈顶元素
（5）循环队列的输出（从栈顶到栈底）
源代码：ds7.c
3．符号平衡问题
在语言中往往需要判断一些符号是否是成对出现的，比如{}、[]、()。如何让判断符号的对称也是很多语言的语法检查的首要任务。
设计一个函数来检查表达式中的符号()、[]、{}是否平衡。若平衡，返回1；若不平衡返回0。
例如：
a(dda){[dfsafd[dfsd]](((fdsd)dfd))dfd}是符号平衡的。 {ad[x(df)ds)]}不是符号平衡的。
源代码：ds8.c
实验代码 ：
1.
#include
#define MAXSIZE maxlen typedef int elemtype; typedef struct stacknode {
elemtype data;
struct stacknode *next; }StackNode; typedef struct {
StackNode *top; }LinkStack;
int *InitStack(LinkStack *S);//初始化链式栈 int *Push(LinkStack *S);//入栈函数 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);
printf(\按任意键开始出栈！\ getchar(); getchar(); Pop(S);
a=StackTop(S);
printf(\栈顶元素为 %d\
printf(\程序运行完毕,是否重新运行（y/n）：\ scanf(\ 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;
printf(\请输入即将入栈的数据个数：\ scanf(\ for(i=0;i printf(\请输入第%d个数：\ scanf(\ 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;