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

数据结构与算法课程设计成果报告括号配对的程序设计与实现学生学号： 学生姓名： 学 院： 计算机学院 专业班级： 软件工程1341 专业课程： 数据结构与算法 指导教师： 2014 年 12 月 29 日题 目括号配对的程序设计与实现考核项目考核内容得分平时考核（30分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20分）分析系统的功能模块编程调试（20分）实现系统的各个功能模块，并完成调试回答问题（15分）回答老师针对课程设计提出的问题课程设计报告撰写（10分）严格按照规范要求完成课程设计报告源代码（5分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语： 日期： 年 月 日目 录1 课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计内容12 分析与设计22.1 题目分析22.2 存储结构设计32.3 算法描述32.4 程序流程图42.5 测试程序说明63 程序清单94 测试124.1 测试数据124.2 测试结果分析125 总结13参考文献141 课程设计目标与任务1.1 课程设计目标通过本课程设计，使学生在数据结构的选择和应用、算法的设计与实现方面得到训练，加深对数据结构基本内容的理解和灵活应用，同时，在程序设计方法及上机操作方面受到比较系统严格的训练，培养软件工作所需要的动手能力。1.2 课程设计任务数据结构课程设计是在学完数据结构课程之后的实践教学环节。该实践教学是软件设计的综合训练,包括问题分析，总体结构设计用户界面设计，程序设计基本技能和技巧。要求学生在设计中逐步提高程序设计能力培养科学的软件工作方法学生通过数据结构课程设计各方面得到锻炼：（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的存储结构，并能设计出解决问题的有效算法；（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改；（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平；（4）尽可能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来，获得算法的直观感受。1.3 课程设计内容（1）输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号，这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正确配对。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。2 分析与设计2.1 题目分析假设表达式中允许包括三种括号：圆括号、方括号和花括号，其嵌套的顺序随意，即（()）或()等为正确的格式，()或()或()均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而等来的却是第二个括号，此时第一个括号“”只能靠边，而迫切等待与第二个括号相匹配的、第七个括号“)”的出现，类似地，因等来的是第三个括号“”，其期待匹配的程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然第二个括号的期待急迫性高于第一个括号；在接受了第四个括号之后，第三个括号的期待得到满足，消解之后，第二个括号的期待匹配就成为当前最急迫的任务了，依次类推。可见这个处理过程恰与栈的特点相吻合。在算术表达式中，右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点。 因此首先建立一个空的堆栈，依次读入字符直到文件的末尾。我们可以利用一个栈结构保存每个出现的左括号，当遇到右括号时，从栈中弹出左括号，检验匹配情况。输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号，这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正确配对。算术表达式中各种括号的使用规则为：出现左括号，必有相应的右括号与之匹配，并且每对括号之间可以嵌套，但不能出现交叉情况。否则，括号匹配不正确，则该算数表达式无效；程序结束。2.2 存储结构设计本程序用的是顺序栈，用地址连续的存储空间依次存储栈在中的元素，并记录当前栈顶数据元素的位置，这样的栈称为顺序栈。同顺序表的存储结构类似，顺序栈也可以用向量来实现。由于入栈和出栈运算都是在栈顶进行的，而栈底位置是固定不变的，可以将栈底位置设置在向量的起始处；栈顶位置是随入栈和出栈操作而变化的，故需要用一个整型变量TOP来记录当前栈顶元素在向量中的为何子。类似顺序表的类型定义，顺序栈的类型可定义如下：typedef struct StackElementType elemStack_Size; int top; SeqStack; 2.3 算法描述首先建立一个空的堆栈，依次读入字符直到文件的末尾。在算术表达式中，右括号和左括号匹配的次序正好符合后到的括号要最先被匹配的“后进先出”堆栈操作特点，因此可以借助一个堆栈来进行判断。 括号匹配共有以下4种情况： （1）括号匹配不正确左括号多于右括号；右括号多于左括号；左右括号配对次序不正确； （2）左右括号配对正确； 具体方法如下：顺序扫描算术表达式，若该表达式中无括号时，则为空栈，此时结束。当遇到3种类型括号的左括号时，让该括号进栈。当扫描到某一种类型的右括号时，比较当前栈顶括号是否与之匹配，若匹配，则退栈继续进行判断；若当前栈顶括号与当前扫描的括号不相同，则左、右括号配对次序不正确；若字符串当前为某种类型右括号而堆栈已空，则右括号多于左括号；字符串循环扫描结束时，若堆栈非空，则说明左括号多于右括号；以上三种情况均为括号匹配不正确，则输出不匹配括号的位置。如果上述三种情况都没有出现，则说明左、右括号匹配正确。2.4 程序流程图运行程序，用键盘输入算是表达式，判断读入的字符是否为括号，若不是括号，则不入栈继续读取；若是括号，则入栈，在判断该括号是左还是右括号，若是左括号则等待下一个括号的读入，如果读入的下一个括号是右括号，判断该右括号是否与上一个左括号匹配，若匹配，则栈顶元素出栈，继续读取，若不匹配，则输出错误；如果读入的下一个括号为左括号，则入栈成为栈顶元素；重复该步骤。读取完结束后，判断栈是否为空，如果为栈空，则该表达式书写正确，括号完全匹配正确；如果栈非空，则表达式无效，括号匹配不正确。 开始输入读取下一个括号？N左括号？YN匹配？配？YYY左括号入栈左括号出栈N指向下一个指针栈空？Y不匹配完全匹配N结束图2-22.5 测试程序说明一、算法用到的抽象数据类型定义 1、ADT Stack 数据对象D=ai|aiElemSet,i=1,2n, n0 数据关系R1=|ai-1,aiD,i=2, ,n 约定an端为栈顶a1端为栈底 基本操作： （1） InitStack(&S) 操作结果构造一个空栈S。 （2） StackEmpty(S) 初始条件栈S已存在。 操作结果若栈S为空栈则返回TURE否则FALUSE。 （3） StackFull(S) 初始条件栈S已存在。 操作结果若栈S为满则返回TURE,否则FALUSE. （4） GetTop(S,&e) 初始条件栈S已存在且非空。 操作结果用e返回S的栈顶元素。（5） Push(&S,e) 初始条件栈S已存在。 操作结果插入元素e为新的栈顶元素。 （6） Pop(&S,&e) 初始条件栈S已存在且非空。 操作结果删除S的栈顶元素 算法中函数编号及功能要求： （1） voidInitStack(SeqStack*S)初始化构造一个空栈S （2） IsEmpty(SeqStack *S)判断栈S为空栈时返回值为真反之为假 （3） IsFull(SeqStack *S)判断栈S为满栈时返回值为真反之为假 （4） Push(SeqStack *S,StackElementType x)插入元素x为新的栈顶元素 （5） Pop(SeqStack *S,StackElementType *x)将栈S的栈顶元素弹出放 到x所指的存储空间中 （6） GetTop(SeqStack *S,StackElementType *x)将栈S的栈顶元素弹出放到x所指的存储空间中但栈顶指针保持不变 （7） Match(char ch,char str)进行括号的匹配 （8） BracketMatch(char *str) str中为输入的字符串利用堆栈技术来检查该字符串中的括号是否匹配二、核心代码判断括号是否匹配：str中为输入的字符串，利用堆栈技术来检查该字符串中的括号是否匹配，使用for循环对字符串中的字符逐一扫描，用Match判断两个括号是否匹配，已匹配的左括号出栈，如果不匹配输出其结果结束；若匹配，则输出匹配。 void BracketMatch(char *str) SeqStack S; int i; char ch; InitStack(&S); for(i=0; stri!=0; i+) switch(stri) case (: case : case : Push(&S,stri); break; case ): case : case : if(IsEmpty(&S) printf(n右括号多余!n); return; else GetTop(&S,&ch); if(Match(ch,stri) Pop(&S,&ch); else printf(n对应的左右括号不同类!n); return; /*switch*/ /*for*/ if(IsEmpty(&S) printf(n括号匹配!n); else printf(n左括号多余!n); 3 程序清单 #define TRUE 1 #define FALSE 0 #define Stack_Size 50 #define StackElementType char #include stdio.h typedef struct StackElementType elemStack_Size; int top; SeqStack; void InitStack(SeqStack *S) S-top = -1; int IsEmpty(SeqStack *S) return(S-top=-1?TRUE:FALSE); int IsFull(SeqStack *S) return(S-top=Stack_Size-1?TRUE:FALSE); int Push(SeqStack *S,StackElementType x) if(S-top=Stack_Size-1) return(FALSE); S-top+; S-elemS-top = x; return(TRUE); int Pop(SeqStack *S,StackElementType *x) if(S-top = -1) return(FALSE); else *x = S-elemS-top; S-top-; return(TRUE); int GetTop(SeqStack *S,StackElementType *x) if(S-top = -1) return(FALSE); else *x = S-elemS-top; return(TRUE); int Match(char ch,char str) if(ch=( & str=) return TRUE; else if(ch= & str=) return TRUE; else if(ch= & str=) return TRUE; else return FALSE; void BracketMatch(char *str) SeqStack S; int i; char ch; InitStack(&S); for(i=0; stri!=0; i+) switch(stri) case (: case : case : Push(&S,stri); break; case ): case : case : if(IsEmpty(&S) printf(n右括号多余!n); return; else GetTop(&S,&ch); if(Match(ch,stri) Pop(&S,&ch); else printf(n对应的左右括号不同类!n); return; /*switch*/ /*for*/ if(IsEmpty(&S) printf(n括号匹配!n); else printf(n左括号多余!n); void main() char str100; printf( *括号匹配的检验*n); printf(n); printf(请输入算数表达式: ); gets(str); BracketMatch(str); printf(谢谢使用!n); 4 测试4.1 测试数据（1）a*(b+c)*(b-d)=（2）a*(b+c)*(b-d)=4.2 测试结果分析输入的表达式为：a*(b+c)*(b-d)=，图4-1为程序运行后的表达式中括号匹配正确的结果，表达式正确；图4-1 输入的表达式为：a*(b+c)*(b-d)=，图4-2为程序运行后的表达式中括号的左括号多余的结果，即括号匹配错误，表达式有错误；图4-2 5 总结这次课程设计是运用c语言以及这学期所学习的数据结构完成的。数据结构是有某一数据元素的集合和该集合中的数据元素之间的关系组成。我做的课题是：编一个程序判断括号是否匹配。通过这次的编程实训，让我受益较多，更进一步的了解和掌握顺序栈的类型定义方法，顺序栈的操作和应用以及栈先进后出操作原则在解决实际问题中的应用；也认识到了自己在数据结构方面的漏缺之处，同时也增强了自我学习的能力，相信我通过这次的实训可以让我在以后更好的学习编程！参考文献1严蔚敏等.数据结构（C语言版）清华大学出版社2朱战立.数据结构-使用C语言（第四版）.电子工业出版社3吴跃.数据结构和算法.机械工业出版社4周海英等.数据结构与算法设计（第二版）.国际工业出版社#define TRUE 1 #define FALSE 0 #define Stack_Size 50 #define StackElementType char #include stdio.h typedef struct StackElementType elemStack_Size; int top; SeqStack; void InitStack(SeqStack *S) S-top = -1; int IsEmpty(SeqStack *S) return(S-top=-1?TRUE:FALSE); int IsFull(SeqStack *S) return(S-top=Stack_Size-1?TRUE:FALSE); int Push(SeqStack *S,StackElementType x) if(S-top=Stack_Size-1) return(FALSE); S-top+; S-elemS-top = x; return(TRUE); int Pop(SeqStack *S,StackElementType *x) if(S-top = -1) return(FALSE); else *x = S-elemS-top; S-top-; return(TRUE); int GetTop(SeqStack *S,StackE