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

河南工程学院数据结构与算法课程设计成果报告括号匹配算法设计的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目括号匹配检验的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计内容11.3 课程设计思想12 分析与设计22.1 题目分析22.2 算法描述22.3 程序流程图33 程序清单44 测试94.1 测试数据94.2 测试结果分析95 总结12参考文献131 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。1.2 课程设计内容设计括号匹配的相关函数库，以便在程序设计中调用，要求：（1）输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号，这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正确配对。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 课程设计思想利用栈来判断括号是否匹配时，遇到左括号就进栈，遇到右括号则左括号出栈，代表这对括号匹配，如果右括号进栈时，栈为空，则说明缺少左括号，若表达式扫描完栈为空，则说明表达式的括号匹配，否则说明表达式缺少左括号。最内层（最迟出现）的左括号必须与最内层（最早出现）的同类右括号匹配，它最期待着急迫的配对。配对之后，期待得以消除。因此为左括号设置一个栈，置于栈顶的左括号期待配对的急切程度最高。另外，在算法的开始和结束时，栈都应该是空的。例如：()、() 、(2 分析与设计2.1 题目分析设计一个程序可以判断给定表达式中所含的括号是否正确配对出现。给定表达式可包含：圆括号，方括号和花括号这三种括号。本程序用C+编写，完成圆括号、方括号和大括号（选作）的匹配检验，即当输入一串括号后能够判断出此串括号匹配是否合法。（1）每一个左括号，等待与之匹配的右括号出现；（2）多个左括号排成一队，新出现的排在前面；（3）若出现了右括号，看是否有相应的左括号且是排在第一位，是则匹配上，消掉该左括号和右括号，继续（1）；（4）如果左括号没有找到与之匹配的右括号，或右括号没有找到与之匹配的左括号，则出错。括号匹配问题的处理过程与栈的先进先出（后出现的左括号先匹配）特点相吻合，所以可以在算法中设置栈，每读入表达式中的左括号，入栈，每读到右括号，将栈顶元素出栈并和左括号匹配，若能匹配上则继续读表达式中的下一个元素。程序正确执行结束的条件是：表达式读完，栈空；程序不正确结束的条件是：（1） 左，右括号不匹配；（2） 表达式中还有未读完的右括号，栈已空，说明右括号多于左括号；（3） 表达式已读完，栈不为空，说明左括号多于右括号。2.2 算法描述假设一个算术表达式可以包含3种括号：圆括号“（”和“）”，方括号“”“”，和花括号“”和“”且这三种括号可按照任意次序嵌套使用（如：（）。设计一个程序，判别所给定表达式中所含括号是否匹配。在任意个表达式中，判断括号类型及其对数是否匹配。可以将表达式看做一个字符串，当此字符串为左括号时，将其入栈，当此字符串为右括号时，与栈顶元素比较，若不匹配则显示失败，若匹配，循环比较个字符与栈内元素是否匹配，直到栈为空且括号对数及类型相同，则该表达式的括号匹配，否则匹配失败。2.3 程序流程图 流程图如图2.1所示 不匹配是否开始输入字符串，存入str,flag=1字符非#？为左括号？为右括号且匹配？将左括号入栈指向下一个字符将左括号出栈栈不为空？匹配结束否是是是否 图2.1程序流程图3 程序清单#include#include#include#include #define STACK_INIT_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10typedef char Status; typedef char SElemType ;/建立栈的首节点typedef structSElemType *base; /在栈构造前和销毁后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack;/构造一个空栈Sint 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，否则返回FALSEint StackEmpty(SqStack S)if(S.base=S.top)return 1;else return 0;/把S置为空栈void ClearStack(SqStack &S)S.base=NULL;S.top=S.base; /销毁栈S，S不在存在void DestoryStack(SqStack *&S)if(StackEmpty(*S)!=1)ClearStack(*S);free(S); /返回S的元素个数，即栈的长度int StackLength(SqStack S)return S.stacksize;/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORint GetTop(SqStack S,SElemType &e)if(S.top=S.base)return 0;e=*(S.top-1);return 1;/插入元素e为新的栈顶元素Status Push(SqStack &S,SElemType &e)if(S.top-S.base=S.stacksize)/判断是否栈满，是则追加存储空间S.base=(SElemType * )realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ =e;return 1; /若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERRORStatus Pop(SqStack &S,SElemType &e)if(StackEmpty(S)=1)return 0;elsee=*-S.top;return 1; /括号匹配int Comp(char a,char b)if(a=(&b!=)|(a=&b!=)|(a=&b!=)return 0;else return 1;/Status GetCount(SqStack *S)char eSTACK_INIT_SIZE;char e1;int i=0;InitStack(*S);printf(Please enter a string of parenthesis:);gets(e);if(e0=)|(e0=)|(e0=)printf(括号匹配错误); exit(0);for(i=0;ei!=0;i+)/以/0判断输入是否结束switch(ei)case (:case :case :Push(*S,ei);break; case ):case :case : GetTop(*S,e1); if(GetTop(*S,e1)=0) printf(右括号多余n); exit(0); if(Comp(e1,ei)=1) Pop(*S,e1); /S-top-; else printf(括号匹配错误n); exit(0);if(S-top!=S-base)printf(左括号多余n);else printf(括号匹配正确n);return 0;/主函数void main()SqStack S;InitStack(S);GetCount(&S); 4 测试4.1 测试数据以下是测试结果：（1） 输入“”检测正确性如图4.1：（2） 输入“()”检测正确性如图4.2：（3） 输入“()”检测正确性如图4.3：（4） 输入“()”检测正确性如图4.3：4.2 测试结果分析（1）输入“”检测正确性如图4.1：图4.1 匹配正确（2）输入“()”检测正确性如图4.2：图4.2匹配正确（3）输入“()”检测左括号多余如图4.3：图4.3左括号多余（4）输入“()”检测右括号多余如图4.3：图4.4右括号多余 5 总结我相信只要有付出就一定会有回报，编程虽然是一件很枯燥很无聊的事情，但我要坚持下去，把它变成自己的兴趣，再按照老师的要求，完成任务。这次通过老师说的模块思想化，分部分的进行编写，经过老师耐心的指导，和细心的检查，最终完成了这次实训，学到了很多东西。编程师一件高精度、模范化的事情，稍有疏忽都会影响全局，也可能因为某一处的小错误而导致整个程序无法运行。所以认真仔细就是非常重要。当自己编写的程序运行成功的时候，那种喜悦是无法言语的。那种成就感是无法比拟的。很庆幸我能最终完成这个作业。通过这次课程设计我收获很多，明白了理论知识和实际相结合是很重要的，只有理论知识是远远不够的，只有把所学的理论知识和实践相结合起来，从理论中得到结论，从而提高自己的实际动手能力和独立思考的能力。参考文献1谭浩强著.C语言设计题解与上机指导.清华大学出版社2谭浩强著.C面向对象程序设计 谭浩强.清华大学出版社3朱战立.数据结构（第四版）.电子工业出版社4周海英.马巧梅数据结构与算法设计（第二版）国际工业出版社5吴跃.数据结构和算法.机械工业出版社6严蔚敏.数据结构：C语言版.清华大学出版社#include#include#include#include #define STACK_INIT_SIZE 100/存储空间初始分配量#define STACKINCREMENT 10typedef char Status; typedef char SElemType ;/建立栈的首节点typedef structSElemType *base; /在栈构造前和销毁后，base的值为NULLSElemType *top; /栈顶指针int stacksize; /当前已分配的存储空间，以元素为单位SqStack;/构造一个空栈Sint 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，否则返回FALSEint StackEmpty(SqStack S)if(S.base=S.top)return 1;else return 0;/把S置为空栈void ClearStack(SqStack &S)S.base=NULL;S.top=S.base; /销毁栈S，S不在存在void DestoryStack(SqStack *&S)if(StackEmpty(*S)!=1)ClearStack(*S);free(S); /返回S的元素个数，即栈的长度int StackLength(SqStack S)return S.stacksize;/若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORint GetTop(SqStack S,SElemType &e)if(S.top=S.base)return 0;e=*(S.top-1);return 1;/插入元素e为新的栈顶元素Status Push(SqStack &S,SElemType &e)if(S.top-S.base=S.stacksize)/判断是否栈满，是则追加存储空间S.base=(SElemType * )realloc(S.base,(S.stacksize+STACKINCREMENT) * sizeof(SElemType);if(!S.base)exit(0);S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;*S.top+ =e;return 1; /若栈不空，则删除S的栈顶元素，用e返回其值，并返回OK，否则返回ERRORStatus Pop(SqStack &S,SElemType &e)if(StackEmpty(S)=1)return 0;el