《数据结构与算法》课程设计-括号匹配的实现.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 算法描述42.4 程序流程图64 测试114.1 测试数据114.2 测试结果分析115 总结136参考文献141 课程设计目标与任务1.1 课程设计目标（1）了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力。（2）初步掌握软件开发过程的问题分析、系统设计、程序编码、测试等基本方法和技能。（3）提高综合运用所学的理论知识和方法独立分析和解决问题的能力。（4）训练用系统的观点和软件开发一般规范进行软件开发，培养软件工作者所应具备的科学的工作方法和作风。1.2 课程设计任务 设计括号匹配的相关函数库，以便在程序设计中调用，要求：（1）输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号，这三种括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正确配对。（2）能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来。（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 课程设计的基本要求严格按照题意要求，独立进行设计，不能随意更改。若确因条件所限，必须要改变课题要求时，应在征得指导教师同意的前提下进行。学生应制定设计工作计划，认真完成设计的各个环节，并在老师的指导下认真组织设计工作，撰写设计报告，做好设计总结。2 分析与设计2.1 括号匹配的概述假设表达式中允许包含两种括号：圆括号和方括号，其嵌套的顺序随意，即( ( ) )或 ( ) 等为正确的格式， ( 或 ( ) 或( ( ) 均为不正确的格式。检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号排序： ( ) 12345678当计算机接受了第一个括号后，它期待着预期匹配的第八个括号的出现，然而等来的确实第二个括号，此时的第一个括号只能暂时等待。第二个括号期待着第七个括号的出现，然而等来的确实第三个括号，第二个括号仍然需要让先。第三个括号出现之后期待着第四个括号的出现，匹配完成之后第二个括号继续开始期待，依此类推，即可完成对括号的匹配。可见这个处理过程恰好和栈的特点相吻合。由此，在算法中设置一个栈，每读入一个括号，如是右括号，则或者使置于栈顶的最迫切的期待得以消解，或者是不合法的情况；若是左括号，则作为一个新的更迫切的期待压入栈，自然使原有的在栈中的左右未消解的急迫性都降了一级。另外，在算法的开始和结束时，栈都是空的。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，否则返回FALSEint StackEmpty(SqStack S)if(S.base=S.top)return 1;else return 0;将栈清空，以用来进栈void ClearStack(SqStack &S)S.base=NULL;S.top=S.base;栈的销毁void DestoryStack(SqStack *&S)if(StackEmpty(*S)!=1)ClearStack(*S);free(S); 若栈不空，则用e返回S的栈顶元素，并返回OK；否则返回ERRORint GetTop(SqStack S,SElemType &e)if(S.top=S.base)return 0;e=*(S.top-1);return 1;2.3 算法描述构造一个算法，用来确定什么样的情况括号匹配是正确的。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(右括号多余); 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;2.4程序流程图匹 配左括号入栈左括号出栈指向下一个指针栈 空?完全匹配错误位置结 束左括号开 始输 入括号？程序开始后先判断是否为括号，如果是括号，再判断是左括号还是右，如果左，则入栈，如果右括号则进行匹配，只向下一个指针；否则栈空；再判断是否匹配，结束。如图2-4： N Y Y N N Y N图2-4 程序流程图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(请输入一串括号：);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(右括号多余); 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）左括号多余。（2）右括号多余。（3）匹配正确4.2 测试结果分析当输如（）时，输出结果将会是：左括号多余。如图4.2-1：图4.2-1 左括号多余当输如（）时，输出结果将会是：右括号多余。如图4.2-2：图4.2-2 右括号多余当输如（）时，输出结果将会是：括号匹配正确。如图4.2-3：图4.2-3 括号匹配正确5 总结通过这次课程的学习，我越发觉得数据结构的重要性。这次课程设计是运用 c 语言以及这学期所学习的数据结构的只是完成的。数据结构是有某一数据元素的集合和该集合中的数据元素之间的关系组成。此 次数据结构实验，我做的是判别括号配对。我深刻得体会到了设计程序的困 难,设计程序是一个全盘思维的过程.在进行源程序的编写前,一定要对程序怎样 运行,程序的原理有一个大致的了解,只有这样,在编写时才能做到纵观全局,不会 只局限于某一个特定的模块,但是,这正是我们初学者最容易犯的错误.开始，急于 求成，没有仔细考虑就直接写程序，结果出现好多错误，由于没有一个明确的逻 辑思维，没有认真的分析实验而导致的。后来，静下心来慢慢思考，终于写出了，但在程序编写过程中仍有不足，调试能力仍有欠缺，程序还有很的改善空间。6参考文献1.严蔚敏，吴伟民编著，数据结构（C语言版），清华大学出版社，2005 2 严蔚敏，陈文博编著，数据结构及应用算法教程，清华大学出版社，2006 3 李云清，杨庆红，揭安全编著，数据结构（C语言版），人民邮电出版社2006 4、谭浩强，张基温，唐永炎编著，C语言程序设计教程（第二版）高等教育出版社，2005 5 苏仕华等编著，数据结构课程设计，上海；机械工业出版社，2004#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+