括号匹配的实现-数据结构报告.doc
文本预览下载声明
河南工程学院《数据结构与算法》课程设计
成果报告
括号匹配的实现
2014 年 12 月 29 日
题 目
括号匹配的实现
考核项目
考核内容
得分
平时考核
(30分)出勤情况、态度、效率;知识掌握情况、基本操作技能、知识应用能力、获取知识能力
系统设计
(20分)分析系统的功能模块
编程调试
(20分)实现系统的各个功能模块,并完成调试
回答问题
(15分)回答老师针对课程设计提出的问题
课程设计报告撰写
(10分)严格按照规范要求完成课程设计报告
源代码
(5分)按照规范要求完成课程设计源代码的排版
总 评 成 绩
指导教师评语:
日期: 年 月 日
目 录
TOC \o 1-3 \h \z \u 1 课程设计目标与任务 1
1.1 课程设计目标 1
1.2 课程设计任务 1
1.3 课程设计的基本要求 1
2 分析与设计 2
2.1 括号匹配的概述 2
2.2 存储结构设计 2
2.3 算法描述 4
2.4 程序流程图 6
4 测试 11
4.1 测试数据 11
4.2 测试结果分析 11
5 总结 13
6参考文献 14
PAGE 6
1 课程设计目标与任务
1.1 课程设计目标
(1)了解并掌握数据结构与算法的设计方法,具备初步的独立分析和设计能力。
(2)初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。
(3)提高综合运用所学的理论知识和方法独立分析和解决问题的能力。
(4)训练用系统的观点和软件开发一般规范进行软件开发,培养软件工作者所应具备的科学的工作方法和作风。
1.2 课程设计任务
设计括号匹配的相关函数库,以便在程序设计中调用,要求:
(1)输入一个算术表达式,式中包含三种括号:圆括号、方括号和花括号,这三种括号可以按任意次序嵌套使用,要求编写程序判断给定表达式中的括号是否正确配对。
(2)能借助语言环境实现图形显示功能,以便将抽象的数据结构以图形方式显示出来,将复杂的运行过程以动态方式显示出来。
(3)给出若干例程,演示通过调用自己所缩写程序来实现相关问题的求解。
1.3 课程设计的基本要求
严格按照题意要求,独立进行设计,不能随意更改。若确因条件所限,必须要改变课题要求时,应在征得指导教师同意的前提下进行。学生应制定设计工作计划,认真完成设计的各个环节,并在老师的指导下认真组织设计工作,撰写设计报告,做好设计总结。
2 分析与设计
2.1 括号匹配的概述
假设表达式中允许包含两种括号:圆括号和方括号,其嵌套的顺序随意,即( [ ]( ) )或[ ( [ ][ ] ) ]等为正确的格式,[ ( ]或[ ( ) 或( ( ) ]均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号排序:
[ ( [ ] [ ] ) ]当计算机接受了第一个括号后,它期待着预期匹配的第八个括号的出现,然而等来的确实第二个括号,此时的第一个括号只能暂时等待。第二个括号期待着第七个括号的出现,然而等来的确实第三个括号,第二个括号仍然需要让先。第三个括号出现之后期待着第四个括号的出现,匹配完成之后第二个括号继续开始期待……,依此类推,即可完成对括号的匹配。可见这个处理过程恰好和栈的特点相吻合。由此,在算法中设置一个栈,每读入一个括号,如是右括号,则或者使置于栈顶的最迫切的期待得以消解,或者是不合法的情况;若是左括号,则作为一个新的更迫切的期待压入栈,自然使原有的在栈中的左右未消解的急迫性都降了一级。另外,在算法的开始和结束时,栈都是空的。
2.2 存储结构设计
构造一个空栈S,
int InitStack(SqStack S){
S.base=(SElemType * )malloc(sizeof(SElemType));
if(!S.base)exit(0); //存储分配失败
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return 1;
}
判断构造的若栈S是否为空栈,用于主函数中对于括号出栈是否为空作为判断。若为空则返回TRUE,否则返回FALSE
int StackEmpty(SqStack S){
if(S.base==S.top)return 1;
else return 0;
}
将栈清空,以用来进栈
void ClearStack(SqStack S){
S.base=NULL;
S.top=S.base;
}
栈的销毁
void DestorySt
显示全部