《数据结构与算法》课程设计-括号匹配的程序设计与实现.doc

河南工程学院数据结构与算法课程设计成果报告括号匹配的程序设计与实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程 1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目括号匹配的的程序设计与实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3课程设计思想22 分析与设计32.1 题目分析32.2 存储结构设计32.3 算法描述32.4程序流程图42.5 测试程序说明52.5.1主要的数据结构52.5.2课程设计的方法和原理52.5.3主要代码及解释53 程序清单74 测试104.1 测试数据104.2 测试结果分析105 总结13参考文献141 课程设计目标与任务1.1 课程设计目标1.能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法。2通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。3培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。1.2 课程设计任务假设表达式中允许包括两种括号:圆括号和方括号,其嵌套的顺序随意,即()或()等为正确的格式，()或()）均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号只能暂时靠边，而迫切等待与第二个括号相匹配的，期待第七个括号的出现，类似的，因等来的第三个括号，其期待的匹配程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配成了当前最急迫的任务了，依次类推。可见，这个处理过程恰与栈的特点相吻合。试利用栈的运算，编写判定给定表达式所含括号是否正确配对出现的算法。此程序要完成如下要求；表达式中有三种括号；圆括号，方括号和花括号，嵌套顺序任意。实现程序需要解决： 用什么数据结构； 怎样实现判断括号是否匹配； 括号匹配与否有几种情况； 输出与输入数据的形式；怎么判断括号是否匹配时程序的难点。1.3课程设计思想最内层（最迟出现）的左括号必须与最内层（最早出现）的同类右括号匹配，它最期待着急迫的配对。配对之后，期待得以消除。因此为左括号设置一个栈，置于栈顶的左括号期待配对的急切程度最高。另外，在算法的开始和结束时，栈都应该是空的。例如：()、 ()、(2 分析与设计2.1 题目分析（1） 输入形式和输入值的范围：从键盘上以字符串的形式输入括号序列。（2） 输出的形式：括号匹配或是括号不匹配。（3） 程序所达到的功能：检验括号是否匹配。输入一个算术表达式，式中包含三种括号：圆括号、方括号、花括号，这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正确匹配。而括号的就近匹配正好跟栈的先进先出的特点相吻合，借助栈的特点，利用栈的入栈和出栈等基本操作，来实现表达式中括号是否匹配的检验。2.2 存储结构设计根据题目需求，本题需设计一个顺序栈的存储结构，即利用一组地址连续的存储单元依此存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置。在初始化设空栈时不限定栈的最大容量。现设定两个常量:STACK_INIT_SIZE(存储空间分配量)和STACKINCREMENT（储储空间分配增量），并以下述类型说明作为顺序栈的定义：typedef char SElemType ;/建立栈的首节点typedef structSElemType *base; /在栈构造前和销毁后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack;2.3 算法描述在检验算法中可设置一个栈，每读入一个括号，若是左括号，则直接入栈，等待相匹配的同类右括号；若读入的是右括号，且与当前栈顶的左括号同类，则二者匹配，将栈顶的左括号出栈，否则不合法。另外，当输入序列已读尽，而栈中仍有左括号，或读入一个右括号，而栈中无左括号，均属于不合法。当输入序列和栈同时为空，说明所有括号完全匹配。2.4程序流程图首先要先判断从键盘中输入的是否是括号，如果不是则直接返回输入界面；反之则直接进入判断界面。如果判断有括号，直接入栈；否则，进行匹配让左括号出栈。当栈空的时候，说明括号已经完全匹配了；若栈不空，则输出错误位置。具体如图3-1开始输入括号？ N Y左括号 Y N 匹配左括号入栈 Y N左括号出栈 指向下一个指针栈空? Y N完全匹配错误位置结束图3-1程序流程图2.5 测试程序说明2.5.1主要的数据结构栈类包括如下数据成员和成员函数top;/指向栈顶的指针LinkStack();/构造函数 boolisEmpty(); /判断栈是否为空voidPush(Tx); /x进栈，top指向x TPop();/栈顶元素出栈TGetPop(); /读取栈顶元素boolSearch(Tx); /搜素栈中是否有x这个元素voidOutPut(); /输出栈内所有元素 2.5.2课程设计的方法和原理1）定义三个栈s1,s2,s3分别用来判断圆括号，方括号和花括号是否匹配2）对s1,s2,s3均有如下操作：a.利用动态指针p依次对输入的（字符串）表达式进行扫描： I.若为左括号，则进栈； II.若有括号，则先取栈顶元素。若栈顶元素为空，则缺少左括号；若不为空，则栈顶元素出栈；b.当字符串扫描完，检验栈是否为空。若为空，则括号正确匹配。否则表示缺少右括号。2.5.3主要代码及解释以上是栈的基本操作，定义一个栈和初始化一个新栈，出栈和入栈操作，以及判断栈是否为空的情况。接下来检查字符串的每个字符，左括号则进行入栈操作，右括号则进行出栈操作看其是否匹配，最后判断是否为空以判定是否匹配。 定义栈的结构体并初始化一个新栈：status creat(list &L)L.data=(elemtype*)malloc(2*sizeof(elemtype);if(!L.data)return ERROR;L.top=L.data;L.length=1;return OK;出栈和入栈的操作：status push(list &L,elemtype e)elemtype *dat;dat=(elemtype*)realloc(L.data,(L.length+1)*sizeof(elemtype);if(!dat)return ERROR;L.data=dat;L.length+;*(L.top)=e;L.top+;return OK;status pop(list &L,elemtype &e)if(L.top=L.data)printf(n已是堆低无数据元素n);return ERROR;判断栈是否为空：int Empty(stack &s,int re)if(s.top=-1)return 1;Else return 0; 3 程序清单#include#include#define OK 1#define ERROR 0typedef int status;typedef char elemtype;typedef structelemtype *data;int length;elemtype *top;list;status creat(list &L)L.data=(elemtype*)malloc(2*sizeof(elemtype);if(!L.data)return ERROR;L.top=L.data;L.length=1;return OK;status push(list &L,elemtype e)elemtype *dat;dat=(elemtype*)realloc(L.data,(L.length+1)*sizeof(elemtype);if(!dat)return ERROR;L.data=dat;L.length+;*(L.top)=e;L.top+;return OK;status pop(list &L,elemtype &e)if(L.top=L.data)printf(n已是堆低无数据元素n);return ERROR;L.top-;e=*(L.top);return OK;int main()list L;creat(L);char a20,b;int i=0,m=0;printf(请输入括号序列：n);while(i20)scanf(%c,&ai);if(ai=n)break;if(ai=(|ai=)|ai=|ai=|ai=|ai=|ai=)i+;m=i;i=0;while(im)if(ai=|ai=)|ai=)if(L.top=L.data)break;elsepop(L,b);if(ai-b)!=2&(ai-b)!=1)break;elsepush(L,ai);i+;if(m=0)printf(无数据元素n);return ERROR;if(i=m)if(L.data!=L.top)printf(配对出错多出左括号%cn,*(L.top);elseprintf(配对成功n);elseprintf(配对出错);if(L.data!=L.top)printf(多出左括号 %c 且,*(L.top);printf(多出右括号 %c n,ai);return 0;4 测试4.1 测试数据1）a*(b+c)*(b-d)2)b/a*(a+b)*(b-d)3)(b+d)/a4)a+b*d+e4.2 测试结果分析如图4-1 ，输入a*(b+c)*(b-d)，可知括号不匹配。图4-1 程序测试结果匹配图如图4-2，输入b/a*(a+b)*(b-d)，结果匹配。图4-2程序测试结果匹配图如图4-3，输入(b+d)/a，结果匹配。图4-3程序测试结果匹配图如图4-4，输入a+b*d+e，结果匹配。图4-4程序测试结果匹配图5 总结这次课程设计是运用语言以及这学期所学习的数据结构的知识完成的。数据结构是有某一数据元素的集合和该集合中数据元素之间的关系组成。此次数据结构实验，我做的是判别括号配对。我深刻得体会到了设计程序的困难,设计程序是一个全盘思维的过程。在进行源程序的编写前,一定要对程序怎样行程序的原理有一个大致的了解,只有这样,在编写时才能做到纵观全局,不会只局限于某一个特定的模块，但是,这正是我们初学者最容易犯的错误。开始，急于求成，没有仔细考虑就直接写程序，结果出现好多错误，由于没有一个明确的逻辑思维，没有认真的分析实验而导致的。后来，静下心来慢慢思考，终于写出了一个还比较满意的程序。通过这个实验，我了解到了自己语言知识的匮乏，缺乏独立设计程序的能力，容易产生思维定式。我也懂得了数据结构课程的巨大作用,它教给我们全局策划的思想,这正是我们所缺乏的,对我们来说也是最重要的。在今后的学习中，一定把语言学号，基础打捞，多进行实践，自己动手，独立思考，取得进步。参考文献1 严蔚敏等.数据结构（C语言版），清华大学出版社2 徐子珊.算法设计、分析与实现（第三版），人民邮电出版3 张乃孝.算法与数据结构（第二版），高等教育出版社4 杨勇虎.数据结构（C语言版），东软电子出版社#include#include#define OK 1#define ERROR 0typedef int status;typedef char elemtype;typedef structelemtype *data;int length;elemtype *top;list;status creat(list &L)L.data=(elemtype*)malloc(2*sizeof(elemtype);if(!L.data)return ERROR;L.top=L.data;L.length=1;return OK;status push(list &L,elemtype e)elemtype *dat;dat=(elemtype*)realloc(L.data,(L.length+1)*sizeof(elemtype);if(!dat)return ERROR;L.data=dat