数据结构实训报告

1、题目括号匹配实现考核项目考核内容得分平时考核（30 分）出勤情况、态度、效率；知识掌握情况、基本操作技能、知识应用能力、获取知识能力系统设计（20 分）分析系统的功能模块编程调试（20 分）实现系统的各个功能模块，并完成调试回答问题（15 分）回答老师针对课程设计问题课程设计撰写（10 分）严格按照规范要求完成课程设计源代码（5 分）按照规范要求完成课程设计源代码的排版总 评 成 绩指导教师评语：日期：年月日目录1课程设计目标与任务11.1 课程设计目标11.2 课程设计任务11.3 课程设计. 12分析与设计22.1题目分析22.2结构设计22.3算法描述32.4程序流程43程序. 64测试

2、84.1测试数据84.2分析84.3分析105总结11参考文献121 课程设计目标与任务1.1 课程设计目标（1）能根据实际问题的具体情况结合数据结构课程中的基本理论和基本算法，正确分析出数据的逻辑结构，合理地选择相应的结构，并能设计出解决问题的有效算法。（2）通过上机实习,验证自己设计的算法的正确性，学会有效利用基本调试方法，迅速找出程序代码中的错误并且修改。（3）培养算法分析能力，分析所设计算法的时间复杂度和空间复杂度，进一步提高程序设计水平。1.2 课程设计任务设计括号匹配的相关函数库，以便在程序设计中调用，要求：（1）输入一个算术表达式，式中包含三种括号：圆括号、方括号和花括号，这三种

3、括号可以按任意次序嵌套使用，要求编写程序判断给定表达式中的括号是否正确配对。（2）最好能借助语言环境实现图形显示功能，以便将抽象的数据结构以图形方式显示出来，将复杂的运行过程以动态方式显示出来；（3）给出若干例程，演示通过调用自己所缩写程序来实现相关问题的求解。1.3 课程设计最内层（最迟出现）的左括号必须与最内层（最早出现）的同类右括号匹配，它最期待着急迫的配对。配对之后，期待得以消除。因此为左括号设置一个栈，置于栈顶的左括号期待配对的急切程度最高。另外，在算法的开始和结束时，栈都应该是空的。例如：()、 ()、(。2 分析与设计2.1 题目分析1、问题：一个算术表达式含圆括号、中括号、花括

4、号,且它们可任意嵌套使用。写一程序，判断任一算术表达式中所含括号是否正确配对。2、要求：（1）表达式从键盘输入。（2）利用栈求解此问题。（3）测试用例自己设计。3、说明：检验表达式中的括号匹配情况。假设在一个算术表达式中，可以包含三种括号：圆括号（和），方括号和，以及花括号和。并且这三种括号可以按任意的次序嵌套使用。比如，.(.).。现在需要设计一个算法，用来检验在输入的算术表达式中所使用括号的。2.2结构设计根据题目需求，本题需设计一个顺序栈的结构，即利用一组地址连续的单元依此存放自栈底到栈顶的数据元素，同时附设指针 top 指示栈顶元素在顺序栈中的位置。在初始化设空栈时不限定栈的最大容量。

5、现设定两个常量:STACK_INIT_SIZE(空间分配量)和 STACKINCREMENT（空间分配增量），并以下述类型说明作为顺序栈的定义：typedef char SElemType ;/建立栈的首节点typedef structSElemType*base;/在栈构造前和销毁后，base 的值为 NULLSElemType*top;/栈顶指针stacksize;/当前已分配的空间，以元素为SqStack;2.3 算法描述完整的顺序栈包含很多的函数，不过根据本题的需要，只写出下列几个操作函数：（1）构造一个空栈 S（2）判断栈是否为空栈，若栈 S 为空栈，则返回 OK，否则返回 ERRO

6、R。（3）返回 S 的元素个数。（4）若栈不空，则用 e 返回 S 的栈顶元素，并返回 OK；否则返回 ERROR，此函数用来获得栈顶元素来判断是否与读入的右括号相匹配。（5）元素 e 为新的栈顶元素，本题中只有左括号进栈，右括号不进栈。（6）若栈不空，则删除 S 的栈顶元素，用 e 返回其值，并返回 OK，否则返回 ERROR；此函数返回的栈顶元素（即一个左括号）若与读入的右括号匹配，则使下个元素成为最急迫的期待置于栈顶。（7）括号匹配，此函数包含两个字符变量，a 代表的是左括号，b 代表的是右括号，通过判断 a 对应的左括号与 b 对应的右括号是否匹配，来完成判断。（8）此函数是针对括号匹

7、配中的几种错误， 依赖函数判断，在窗体中返回不同的内容，大致的错误分为以下两种：右括号多余左括号多余2.4 程序流程程序开始后先判断是否为括号，如果是括号，再判断是左括号还是右，如果左，则入栈，如果右括号则进行匹配，只向下一个指针；否则栈空；再判断是否开始匹配，结束。如图 2-1：Y表达式空N栈空N括号Y左括号NYN栈空YNY匹配YN匹配成功匹配失败结束图 2-1 程序流程图左括号出栈指向下一个指针左括号入栈指向下一输入表达2.5 测试程序说明该程序是将数据结构中用栈的基本操作判断括号是否匹配的程序。程序开始后先输入表达式，然后计算机会根据所编写的程序，自动为数据分配空间，并将数据分配到括号相

8、应的结点位置，然后从左到右开始判断是否为括号。如果是括号，再判断是左括号还是右括号。如果左括号，则入栈，如果右括号则进行匹配，匹配成功则指向下一个指针，否则返回匹配失败。指向下一个指针后判断表达式是否为空，如果为空则继续判断是否栈空，栈空则返回匹配成功否则返回左括号多余。将程序运行结果和预期结果相比较，分析程序、错误，发现问题所在，致力改良程序。使程序更加合理，更加简便。3程序#include#include#include#define NULL 0typedef struct nodechar ch;struct node *next;snode,*stack;main()/主函数stac

9、k s,top,p;char *string,ch100=;/栈的空间初始分配量s=(stack)malloc(sizeoode);/空间初始分配s-ch=0;/构造一个空栈 Ss-next=NULL;top=s;/建立栈的首节点prf(输入一个含括号的四则运算表达式：n);scanf(%s,&ch);/输入含括号的四则运算表达式getchar();string=ch;while(*string!=0)if(*string=(|*string=|*string=)/遇到左括号，入栈p=(stack)malloc(sizeoode);/分配空间p-ch=*string;p-next=top;to

10、p=p;if(*string=)|*string=|*string=)/遇到右括号，匹配if(*string=)&top-ch=()|(*string=&top-ch=)|(*string=&top-ch=)/匹配成功，左括号出栈。top=top-next;elsebreak;/匹配失败，结束循环。string+;if(*string!=0)/判断右括号是否为空。prf(多出右括号n);if(top-ch!=0)/判断栈是否为空。prf(多出左括号n);if(*string=0)&(top-ch=0)/如果都为空输出匹配成功。prf(配对成功n);return 0;4 测试4.1 测试数据(1

11、).左括号多余：3+2+(2+3)(2).右括号多余：(2+5)+1+2+(2+3)(3).匹配成功：(3+3)+(6+7)4.2分析当输入3+2+(2+3)时，左括号多余。如图 4-1：图 4-1当输入(2+5)+1+2+(2+3)时，右括号多余。如图 4-2：图 4-2当输入(3+3)+(6+7)时，匹配成功。如图 4-3：图 4-34.3分析程序经过测试之后，主要的功能可以实现，可以完成实验的要求，并仿照教科书的例子在求值中运算符栈、运算数栈、输入字符和主要操作的变化过程进行四则混合运算。但是也存在一些小问题，就是在计算完一个表达式之后，不可以直接进行下一运算，必须再一次启动程序进行计算

12、。但它的优点是，用户输入方便，没有过多的输入要求，直接输入想计算的表达式即可，没有过多的格式要求。以字符列的形式从终端输入语法正确的、不含变量的整数表达式。利用已知的运算符优先关系，实现对算术四则混合运算表达式的求值。5 总结行,程序的原理有一个大致的了解,在编写时才能做到纵观全局,不会 只局限于某一个特定的模块,但是,这正是初学者最容易犯的错误.开始，急于 求成，没有仔细考虑就直接写程序，结果出现好多错误，由于没有一个明确的逻 辑思维，没有认真的分析实验而导致的。后来，静下心来慢慢思考，终于写出了，但在程序编写过程中仍有，调试能力仍有欠缺，程序还有很的改善空间。这次课程设计是运用 c 语言以及这学期所学习的数据结构的只是完成的。数 据结构是有某一数据元素的集合和该集合中的