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

河南工程学院数据结构与算法课程设计成果报告括号匹配算法设计的实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1342 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目括号匹配算法设计的实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计内容及要求11.3 课程设计思想12 分析与设计22.1 题目设计分析22.2概要设计和数据结构的选择22.3 算法描述32.4 程序流程图43 程序清单54 测试84.1 测试数据84.2测试结果及分析95 总结101 课程设计目标与任务1.1 课程设计目标通过对括号匹配的检验的程序设计编写，深入了解和掌握栈的使用，了解栈先进后出的特点，掌握栈的表示和实现。通过本课程设计，提高在数据结构的选择和应用、算法的设计与实现等方面的能力。加深对数据结构基本内容的理解和灵活应用，同时，培养软件工作所需要的动手能力。在程序设计方法及上机操作方面得到比较严格的全面的锻炼。1.2 课程设计内容及要求输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号，这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正确配对。最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 课程设计思想匹配思想：从左至右扫描一个字符串(或表达式)，则每个右括号将与最近遇到的那个左括号相匹配。则可以在从左至右扫描过程中把所遇到的左括号存放到堆栈中。每当遇到一个右括号时，就将它与栈顶的左括号(如果存在)相匹配，同时从栈顶删除该左括号。算法思想：设置一个栈，利用栈来判断括号是否匹配时，遇到左括号就进栈，遇到右括号则左括号出栈，代表这对括号匹配，如果右括号进栈时，栈为空，则说明缺少左括号，若表达式扫描完栈为空，则说明表达式的括号匹配，否则说明表达式缺少左括号。最内层（最迟出现）的左括号必须与最内层（最早出现）的同类右括号匹配，它最期待着急迫的配对。配对之后，期待得以消除。因此为左括号设置一个栈，置于栈顶的左括号期待配对的急切程度最高。另外，在算法的开始和结束时，栈都应该是空的。例如：()、() 、(2 分析与设计2.1 题目设计分析设计一个程序可以判断给定表达式中所含的括号是否正确配对出现。给定表达式可包含：圆括号，方括号和花括号这三种括号。本程序用C+编写，完成圆括号、方括号和大括号（选作）的匹配检验，即当输入一串括号后能够判断出此串括号匹配是否合法。一、输入形式和输入范围括号以字符串形式输入，只输入圆括号、方括号和大括号三种括号，三种括号可以随意嵌套。二、输出形式及功能当输入任意一字符串后，都会做出判断，输出输入的括号串是否合法。三、测试数据输入（），结果“匹配”输入（），结果“此串括号匹不合法。2.2概要设计和数据结构的选择一、概要设计（1）定义抽象数据类型存储编号、密码指针： using namespace std; #define stacksize 100 /定义栈的空间大小 struct stack /定义栈的结构体 char strstackstacksize;/定义栈的存储格式为字符型 int top; ; /定义栈的栈顶变量（2）程序流程：在屏幕上显示：“请您输入一个字符串”。输入一串字符串（表达式）。进行get()操作。进行bracket()操作。输出结果，是否匹配。二、数据结构的选择本题目设计选择的数据结构为栈。因为栈的特点是先进后出，使用栈使括号匹配问题简易化。多项式中的括号对数是成对出现的，可以将它抽象为一个对称的字符串，字符串的前一半看做连续出现的左括号字符，后一半看做连续出现的右括号字符，与栈顶元素比较，若匹配则栈顶指针下移，即删除栈顶元素，继续比较。当栈内元素为空时，说明左右的左括号与右括号匹配，则匹配成功。2.3 算法描述括号匹配问题是指要匹配一个字符串的左，右括号。括号问题可以用来解决C语言中的“”和“”的匹配问题，可以观察到，如果从左至右扫描一个字符串，那么每个右括号将于最近遇到的那个未匹配的左括号相匹配，在从左至右的扫描工程中把所遇到的左括号存放到堆栈内，每当遇到一个右括号时，就将它与栈顶的左括号（如果存在）相匹配，同时从栈顶删除该左括号。即假设一个算术表达式可以包含3种括号：圆括号“（”和“）”，方括号“”“”，和花括号“”和“”且这三种括号可按照任意次序嵌套使用（如：（）。设计一个程序，判别所给定表达式中所含括号是否匹配。在任意个表达式中，判断括号类型及其对数是否匹配。可以将表达式看做一个字符串，当此字符串为左括号时，将其入栈，当此字符串为右括号时，与栈顶元素比较，若不匹配则显示失败，若匹配，循环比较个字符与栈内元素是否匹配，直到栈为空且括号对数及类型相同，则该表达式的括号匹配，否则匹配失败。2.4 程序流程图 流程图如图2.1所示。对括号出现的情况进行判断，如果是、（则元素进栈，如果是、）则与出栈元素进行比较。继续匹配，直到读完。若不匹配则进行标示，最后输出结果。 开始 输入字符串串 否字符串没结束，匹配标示 是判断括号()与出栈元素比较括号进栈是是否匹配否输出结果返回1结束图2.1括号匹配算法设计流程图 3 程序清单#includestdafx.h #include #include #include using namespace std; #define stacksize 100 /定义栈的空间大小 struct stack /定义栈的结构体 char strstackstacksize;/定义栈的存储格式为字符型 int top; /定义栈的栈顶变量 ; void InitStack(stack &s) /定义一个新栈s，初始化栈顶为-1 s.top = -1; char Push(stack &s, char a) /入栈操作，将字符a入栈s if(s.top = stacksize - 1) /当栈顶为栈的空间大小-1，栈满 return 0; s.top +;/入栈操作一次，栈顶+1 s.strstacks.top = a;/此时，栈顶元素为字符a return a; char Pop(stack &s ) /出栈操作 if(s.top = -1) /当栈顶为-1时，栈空 return 0; char a = s.strstacks.top;/将栈顶元素赋予字符a，并返回字符a，完成出栈操作 s.top-; return a; int Empty(stack &s,int re) /定义判断栈是否为空的函数 if(s.top=-1) return 1; /栈为空时返回值为1 else return 0; /栈不为空时返回值为0 int Check(char* str) /检验括号是否匹配的函数 stack s; InitStack(s); int strn = strlen(str); /定义字符串长度为strn for(int i=0;istrn;i+) char a=stri; switch (a)/对输入的字符a进行判断 case(: case: case: Push(s,a);/若是左括号，则进行入栈操作 break; /若是右括号，则进行出栈操作，若出栈元素不是与输入相对应的左括号，则字符串括号中不匹配，返回case): if(Pop(s)!=() return 0; break; case: if(Pop(s)!=) return 0; break; case: if(Pop(s)!=) return 0; break; int re=0; /定义并初始化判空函数的返回值 re=Empty(s,re); /返回判空函数的返回值 if(re=1) return 1; /栈为空 else return 0; /栈不为空，有左括号，即存在(或或未匹配 void main() /主函数 char str100; /定义一个单字符型数组以储存键盘输入的字符串。 cout请您输入一个长度小于的字符串：str; /从键盘输入字符存储到字符数组中，有输入则继续。 int re=Check(str); if (re=1) cout您输入的字符串中的括号完全匹配！endl; else if (re=0) cout您输入的字符串中的括号不匹配！endl; 4 测试4.1 测试数据算法设计完成后，输入几组表达式进行测试。输入表达式 2x+6y-3y+2z*4z+(45-2x)*13-32.运行结果如图4.1。图4.1 表达式的运行结果输入表达式2x+3y+3y-4z)+4z-2y-(2x-3z)*5+2z,运行结果如图4.2。图4.2 表达式的运行结果输入表达式65+x*z-(x+y/z+78*2,运行结果如图4.3。图4.3 表达式的运行结果4.2测试结果及分析 第一个表达式中左括号和右括号相互匹配，所以显示您输入的字符串中的括号完全匹配。第二个表达式括号类型不匹配，即“”和“）”不匹配，所以显示您输入的字符串中的括号不匹配。 第三个表达式中括号个数不匹配，即缺少一个“）”，所以显示您输入的的字符串的括号不匹配。5 总结通过一个星期的上机实训，我发现了自己的很多不足之处。我做的题目是括号匹配的算法设计。题目很简单，但是我却花了一个星期仍然没有自己想象中做的成功。期间老师不断地给予指导，我也在改进过程中不断地学习。我感觉要想做好编程，不仅需要丰富的理论知识，还要有定期的上机实践。只凭自己的一点书上学到的理论就想熟练的编程序是几乎不可能的。在以后的学习中，还要不断地加强自己的上机实践能力。参考文献1朱战立.数据结构使用C语言（第四版）电子工业出版社20092周海英.马巧梅数据结构与算法设计（第二版）国际工业出版社20053吴跃.数据结构和算法机械工业出版社20104严蔚敏.吴伟民数据结构：C语言版清华大学出版社2007#include #include #include using namespace std; #define stacksize 100 /定义栈的空间大小 struct stack /定义栈的结构体 char strstackstacksize;/定义栈的存储格式为字符型 int top; /定义栈的栈顶变量 ; void InitStack(stack &s) /定义一个新栈s，初始化栈顶为-1 s.top = -1; char Push(stack &s, char a) /入栈操作，将字符a入栈s if(s.top = stacksize - 1) /当栈顶为栈的空间大小-1，栈满 return 0; s.top +;/入栈操作一次，栈顶+1 s.strstacks.top = a;/此时，栈顶元素为字符a return a; char Pop(stack &s ) /出栈操作 if(s.top = -1) /当栈顶为-1时，栈空 return 0; char a = s.strstacks.top;/将栈顶元素赋予字符a，并返回字符a，完成出栈操作 s.top-; return a; int Empty(stack &s,int re) /定义判断栈是否为空的函数 if(s.top=-1) return 1; /栈为空时返回值为1 else return 0; /栈不为空时返回值为0 int Check(char* str) /检验括号是否匹配的函数 stack s; InitStack(s); int strn = strlen(str); /定义字符串长度为strn for(int i=0;istrn;i+) char a=stri; switch (a)/对输入的字符a进行判断 case(: case: case: Push(s,a);/若是左括号，则进行入栈操作 break; /若是右括号，则进行出栈操作，若出栈元素不是与输入相对应的左括号，则字符串括号中不匹配，返回case): if(Pop(s)!=() return 0; break; case: if(Pop(s)!=) return 0; break; case: if(Pop(s)!=) return 0; break; int re=0; /定义并初始化判空函数的返回值 re=Emp