数据结构实验报告(实验3,实验4)

肇庆学院 计算机学院/软件学院

实 验 报 告

专业 15物联网工程 班级 1班 姓名 林忠杰 学号 201524134151 课程名称 数据结构 学年2015—2016 学期 1? / 2□ 课程类别 专业必修? 限选□ 任选□ 实践□ 评分： 批阅老师： 2016年 12 月 6 日

实验3 栈的基本操作

? 实验目的

（1）熟悉栈的定义和栈的基本操作。

（2）掌握顺序存储栈和链接存储栈的基本运算。

（3）加深对栈结构的理解，逐步培养解决实际问题的编程能力。 ? 实验内容 （一）基础题

（1）编写栈的基本操作函数。

（2）调用栈的基本操作函数完成栈的基本操作：建立栈、读取栈顶函数、从栈中删除元素、输出栈中的所有元素。 （二）提高题

编写一个判定表达式中的括号是否正确匹配的函数。 ? 实验结果

1、基础题

（1）画出数据结构基本运算的流程图

调用OutputStack函数 输出操作结果 调用push函数 调用pop函数 1 进栈 2 出栈 0 退出 输入操作选择op 主函数 （2）程序运行主要结果截图

测试用例：依次输入元素34，43，56，45进栈，程序运行结果如下图

测试用例：让元素45,56出栈，程序运行结果如下图

（3）程序源代码

#include #define max 10

int push(int *stack,int maxn,int *toppt,int x) { if(*toppt>=maxn) return 1; stack[*toppt]=x; ++(*toppt); return 0; }

int pop(int *stack,int *toppt,int *cp) { if(toppt==0) return 1; --(*toppt);

*cp=stack[*toppt]; return 0; }

void OutputStack(int *stack,int toppt) { int i; for(i=toppt-1;i>=0;i--) printf(\ printf(\}

void main() { int s[max],i; int top=0; int op; while(1) { printf(\请选择操作，1:进栈；2:出栈；0:退出\\n\ fflush(stdin); scanf(\ switch(op) { case 0: return; case 1: printf(\请输入进栈元素：\ scanf(\ if(push(s,max,&top,i)==0) { printf(\进栈成功，栈内元素为：\\n\ OutputStack(s,top); } else printf(\栈满\\n\ break; case 2: if(pop(s,&top,&i)==0) { printf(\出栈元素为：[%d],栈内元素为：\\n\ OutputStack(s,top); } else printf(\栈空\\n\ break; } } }

2、提高题

（1）画出数据结构基本运算的流程图

（2）程序运行主要结果截图

测试用例：输入表达式 ([][](())) ，程序运行结果如图

Strcmp(exp,”0”)=0? 主函数 gets(exp)读取表达式 否 调用correct函数 输出结果 是 退出

测试用例：输入表达式 [][[]() ，程序运行结果如图

（3）程序源代码 #include #include #include #define MAX 100

int push(int *stack,int maxn,int *toppt,char x) {

if(*toppt>=maxn) return 1; stack[*toppt]=x; ++(*toppt); return 0; }

int pop(int *stack,int *toppt,char *cp) {

if(toppt==0) return 1; --(*toppt);