1、 C C 语 言语 言 数 据 结 构数 据 结 构 题题 目：目： 括号匹配的检验括号匹配的检验 班班 级：级： 1 1 1 1 0 0 1 1 学学 号：号： 作者姓名：作者姓名： 指导教师：指导教师： 2012 年 11 月 课 程 设 计 报 告 2 目 录 1 设计题目与要求 3 1.1 实验目的 3 1.2 问题描述 3 1.3 设计要求 3 2 总体设计思想及相关知识 3 2.1 总体设计思想 . 3 2.2 开发环境与工具 4 3 功能设计 4 3.1 抽象数据类型的定义 4 3.2 栈的基本运算 4 3.3 栈的基本操作的实现4 3.4 模块流程图 . 6 4 源程序代码 6
2、 5 测试及结果 9 6 总结 . 11 7 小组成员任务分配 . 11 参考文献. 12 3 1设计题目与要求 1.1 实验目的 通过对括号匹配的检验的程序设计编写，深入了解和掌握栈的使用，了解栈 先进后出的特点，掌握栈的表示和实现。 1.2 问题描述 假设表达式中允许包括两种括号:圆括号和方括号， 其嵌套的顺序随意， 即() 或()等为正确的格式，()或()）均为不正确的格式。检验括号是否匹配的 方法可用“期待的急迫程度”这个概念来描述。例如考虑下列括号序列： ( ) 1 2 3 4 5 6 7 8 当计算机接受了第一个括号后，它期待着与其匹配的第八个括号的出现，然而 等来的却是第二个括号
3、，此时第一个括号只能暂时靠边，而迫切等待与第二个括 号相匹配的，第七个括号的出现，类似的，因等来的第三个括号，其期待的匹配 程度较第二个括号更急迫，则第二个括号也只能靠边，让位于第三个括号，显然 第二个括号的期待急迫性高于第一个括号；在接受了第四个括号后，第三个括号 的期待得到满足，消解之后，第二个括号的期待匹配成了当前最急迫的任务 了， ，依次类推。可见，这个处理过程恰与栈的特点相吻合。 1.3 设计要求 读入圆括号和方括号的任意序列，输出“匹配”或“此串括号匹配不合法” 。 2总体设计思想及相关知识 2.1 总体设计思想 最内层 （最迟出现） 的左括号必须与最内层 （最早出现） 的同类右括
4、号匹配， 它最期待着急迫的配对。配对之后，期待得以消除。因此为左括号设置一个栈， 置于栈顶的左括号期待配对的急切程度最高。另外，在算法的开始和结束时，栈 都应该是空的。例如：()、 () 、( 4 2.2 开发环境与工具 系统平台：Windows 应用程序 实现语言：C 语言 开发工具：VC+6.0 3功能设计 3.1 抽象数据类型的定义 堆栈的定义：栈（Stack）是限定只能在表的一端进行插入和删除操作的线性 表。在表中，允许插入和删除的一端称作“栈顶(top)“，不允许插入和删除的另 一端称作“栈底(bottom)“ 。 3.2 栈的基本运算 （1）栈初始化：Init_Stack(s)。操
5、作结果是构造了一个空栈。 （2）判栈空：Empty_Stack(s)。操作结果是若 s 为空返回 1，否则返回为 0. （3）入栈：Push_Stack(s,x)。操作结果是在栈 s 的顶部插入一个新的元素 x，x 成为新的栈顶元素，栈发生变化。 （4）出栈：Pop_Stack(s)。在栈 s 存在且非空的情况下，操作结果是将栈 s 的顶 部元素从栈中删除，栈中少了一个元素，栈发生变化。 （5）读栈顶元素：Top_Stack(s)。在栈 s 存在且非空的情况下，操作结果是读栈 顶元素，栈不变化。 3.3.3 3 栈的基本操作的实现 (1）置空栈（首先建立栈空间，然后初始化栈顶指针） SeqSt
6、ack * Init_Stack() SeqStack *s; s=( SeqStack *)malloc(sizeof(SeqStack ); s-top=-1;return s; 5 (2)判空栈 int Empty_Stack(SeqStack *s) If(s-top=-1) return 1; Else return 0; (3)入栈 int Push_Stack(SeqStack *s,datatype x) if(s-top=MAXSIZE-1) return 0; /栈满不能入栈 elses-top+; s-datas-top=x; return 1; (4)出栈 int Pop_Stack(SeqStack *s,datatype *x) if (Empty_Sta
