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

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

姓名 学号

实验名称

专业班级 计算机类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;

if(S->top==NULL) {

printf(\链式栈为空！\ return(0); }

else printf(\该链式栈从栈顶到栈底数据如下：\\n\ for(p=S->top;p!=NULL;p=p->next) {

printf(\ } }

int *Pop(LinkStack *S) {

StackNode *p; int item; char k; p=S->top;

if(S->top==NULL) {

printf(\链式栈为空！\ return(0); } else {

item=p->data;

printf(\出栈数据为%d\\n\ S->top=p->next; free(p); view(S); }

printf(\是否继续出栈（y/n）：\ scanf(\ if(k=='y') {

Pop(S); }

else return(S); }

int StackTop(LinkStack *S) {

if(S->top==NULL)

{

printf(\该链式栈为空！\

}

return(S->top->data); }

2.

#include #define MAXSIZE 30 typedef int elemtype; typedef struct {

elemtype data[MAXSIZE]; int front,rear; }seqqueue;

int a=0;//全局变量

int InitQueue(seqqueue *Q);//初始化队列函数 int view(seqqueue *Q);//输出函数 int EnQueue(seqqueue *Q);//入队函数 int DeQueue(seqqueue *Q);//出队函数

main() {

seqqueue *Q; Q=InitQueue(Q);

if(Q->front==Q->rear) {

printf(\该队列为空！\ }

EnQueue(Q);

printf(\按任意键开始出栈！\ getchar(); getchar(); DeQueue(Q);

printf(\程序运行完毕,是否重新运行（y/n）：\ }

int InitQueue(seqqueue *Q) {