括号匹配算法的设计与实现1.docVIP

河南工程学院《数据结构与算法》课程设计 成果报告 括号匹配算法的设计与实现 2014 年 12 月 29 日 题 目 括号匹配算法的设计与实现 考核项目 考核内容 得分 平时考核 （30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力 系统设计 （20分）分析系统的功能模块 编程调试 （20分）实现系统的各个功能模块，并完成调试 回答问题 （15分）回答老师针对课程设计提出的问题 课程设计报告撰写 （10分）严格按照规范要求完成课程设计报告 源代码 （5分）按照规范要求完成课程设计源代码的排版 总 评 成 绩 指导教师评语： 日期： 年 月 日 目 录 TOC \o 1-3 \h \z \u 30403 1 课程设计目标与任务 1 17456 1.1 课程设计目标 1 24571 1.2 课程设计任务 1 3800 1.3 课程设计的基本要求 1 4152 2 分析与设计 2 25633 2.1 括号匹配的概述 2 6780 2.2 存储结构设计 2 29338 2.3 算法描述 4 1120 2.4程序流程图 6 7575 3 程序清单 7 20362 4 测试 11 17757 4.1 测试数据 11 29581 4.2 测试结果分析 11 25073 5 总结 12 29721 6参考文献 13 PAGE 1 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;