数据结构-括号匹配课程设计报告

《数据结构-括号匹配课程设计报告》由会员分享，可在线阅读，更多相关《数据结构-括号匹配课程设计报告（7页珍藏版）》请在金锄头文库上搜索。

1、- 1 -安徽三联学院数据结构课程设计班级：班级： 计计 算算 机机 科科 学学 与与 技技 术术 系系计算机科学与技术专业计算机科学与技术专业 20082008 级（级（2 2）班）班组别：组别： 第 八 组 组长：组长： 徐 恒 组员组员：何洋洋、枉林然、魏世捷、王煜、戴文强完成日期：2010.1.202010.1.20- 2 -题目：括号匹配检验题目：括号匹配检验一、问题描述一、问题描述：假设一个算术表达式可以包含 3 种括号：圆括号“（”和“） ” ，方括号“”和“” ，和花括号“”和“”且这三种括号可按照任意次序嵌套使用（如：（） 。设计一个程序，判别所给定表达式中所含括号是否匹配。

2、二、二、要求：要求：1将算术表达式保存在带头结点的单链表中； 2在 1 中建立的单链表上实现括号匹配问题的求解。 三、三、解决问题思路：解决问题思路：1、首先建立带头结点的单链表，单链表的数据域存储字符数据，指针域为结点型指针。设立字符型数组先将算术表达式输入到数组当中，通过插 入节点函数将数组中字符全部插入到单链中 1 中。2、建立单链表 2,通过 switch，case 语句将单链表 1 中的括号字符全部插入到单链表 2 中。3、调用括号匹配函数将，单链表 2 的头节点调入函数当中，设立标志位has。当 has 取 1 时，说明找到一组匹配括号；当 has 取 0 时，当前一组 括号不匹配

3、。设立 temp 指向当前所要判断节点，将 temp 所指节点的值 与 temp-next 节点的值相比较，利用匹配括号 ASCII 值相差 1 或 2，相 同则相差 0；或不相同差值不为 1、2 或 0。当 temp 与 temp-next 的差 值为 1 或 2 时，说明找到一组匹配括号。Temp=temp-next；进行新的 判断。当 temp 与 temp-next 的差值不为 1 或 2 时，将 temp 赋为 temp-next；进行新一轮的判断。若 temp-next-next 与 temp-next-next-next 匹配时，此时将 temp-next-next 与 temp

4、-next-next-next 全部值为空值。且 temp-next 未找到匹配字符时将 temp 重新赋为 temp-next，进行新的判断。4、最后，若单链表 p 为空则则说明表达式中括号匹配；若 p 不为空，则说明算术表达式中括号不匹配。- 3 -四、四、 运行环境：运行环境：1、编辑主要环境为 microsoft visualC+6.0。 2、调试运行环境为 Turbo C2.0。五、五、 组员分工情况：组员分工情况：1、何洋洋、汪林然负责单链表相关函数的编写； 2、王煜、洪小龙负责收集相关材料和参考资料； 3、徐恒、戴文强负责整理、编译和调试。/六、六、 遇到的困难及解决问题的办法：

5、遇到的困难及解决问题的办法：1、最后在调试程序时发现许多错误，例如函数类型不匹配、没有合适的指 针、未定义变量、句法错误、函数声明错误、不合法的指针、有未使用 的变量、定义不正确等。先是找同学帮助，然后自己学着改错。慢慢的 自己学会改错，并找到相关资料来找出的修改方法。 2、遇到实在不懂的地方，就找组员和同学一起讨论，找到问题的根本原因， 然后加以纠正。七、七、 源代码及注释：源代码及注释：括号匹配源程序代码及注释括号匹配源程序代码及注释kuohaopipei.c#include /*头文件*/ #include #include #define LEN 80 typedef struct l

6、ist char node; /*数据域*/ struct list *next; /*指针域*/ list,*linklist; /*节点类型*/ void initlist(linklist); /*函数声明*/ int isempty(linklist); int creatlist_node(linklist,char); Textlist(linklist);void main() /*主函数*/ char testLEN; int i; list a,b; linklist p,q= /*设立 P 为 list 结点指针*/ p= /*使 P 指向头结点 a*/ initlist(

7、p); /*使 p 为第一个节点*/printf(“Pliease input the expression:n“);- 4 -scanf(“%80s“,test); for(i=0;inext) switch(q-node) case : case : case : case : case (: case ): creatlist_node(p,q-node);/*将 q 中括号插入单链表 p 中*/ break; default : continue; /*若节点中字符不为括号则进入下一次循 环*/ Testlist(p); /*调用判断括号匹配函数,用 P 链表作为实 参*/ if(is

8、empty(p) /*判断 P 是否为空，p 为空则表达 式中括号匹配*/ printf(“Truen“);printf(“the kuo hao in expression is pipein“); else /*P 不为空，则表达式中 括号不匹配*/ printf(“Falsen“);printf(“the kuo hao in expression is not pipein“); void initlist(linklist aplist) /*构造头结点函数*/ struct list *next; aplist-next=NULL; aplist-node=0; int isemp

9、ty(linklist aplist) /*判断头结点是否为空函数*/- 5 - linklist next; return aplist-next=NULL?1:0; /*头结点不为空侧返回 0*/ int creatlist_node(linklist aplist,char a) /*插入字符节点函数*/*建立 list 型 anode 节点，将 字符 a 插入*/ linklist bplist=aplist,anode; /*设立 bplist 作为中间变量用于添加节点 */ while(bplist-next) bplist=bplist-next; anode=(linklist

10、)malloc(sizeof(list); /*构造一个 list 型节点并分配空间 */ if(!anode) exit(-1); anode-node=a; anode-next=NULL; bplist-next=anode; return 0; int Testlist(linklist aplist) /*判断算术表达式中括号是否匹配函数*/ linklist temp; /*设立 list 型节点 temp 作为临时变量*/ int has=1; /*作为标志,当一对括号匹配时，则 has 置 为 0，否则置为 1*/ if(isempty(aplist) /*P 为空则返回 0*

11、/ return 0; while(has) linklist next; /*设立 next 为 linklist 型变量，用于指向 新的节点*/ has=0; temp=aplist; /*使 temp 指向第一个节点*/ while(temp-next) /*若第 2 个节点不为空，进入 while 循 环*/ if(temp-next-next) /*若第 3 个节点不为空，继续判断*/ if(temp-next-next-node-temp-next-node=1)|(temp-next- next-node-temp-next-node=2) /*若第 3 个节点字符值减去第 2

12、个节点字符值为 1 或 2 则条件成立进入 if 语句 */- 6 - temp-next=temp-next-next-next; /*将节点 1 赋值为节 点 3*/ has=1; /*标志 has 重置为 1*/ else temp=temp-next;/*若第 3 个节点字符值减去第 2 个节点字 符值为 0 则将 temp 置为下一个节点*/ else temp=temp-next; /*若第三个节点为空则将 temp 置为下一个节 点*/ if(!has) /*判断 has 的值若为 1 则退出内 while 循环 */ break; return 0; /*当 has 值为 0

13、时则函数返回 0*/ 八、 运行结果：运行结果：运行结果如下：1、输入表达式2x+6y-3y+2z*4z+(45-2x)*13-32 结果如下：2、输入表达式2x+2y+2z-(2x-3y)*5+43*5z-32*12 结果如下：3、输入表达式结果如下：- 7 -4、输入表达式纯括号类型如：则输出结果为错误，与实际 状况不符。九、九、 讨论部分：讨论部分：1、在单链表之后，从数组中提取字符输入到单链表中时，无法正确输进去， 后来找同学查看，发现指针有些错误。经过修改之后，可将字符成功插 入到单链表中。经过讨论后得知指针未正确指向头结点。 2、在创建单链表过程中，发现许多问题，指针转换错误经常出现，定义变 量，调用函数方面也经常出现错误。后来只能查看C 程序设计教程 ， 来检查错误。分析原因很可能是因为长时间未接触 C 语言，有些生疏， 以致于经常出错。 3、在最初编写程序时感到无从下手，思路有些不清晰，可能主要是原因平 时上课时没有认真听讲，没有系统的掌握编写一个算法的基本方法、步 骤。应从平时上课中打好基础，学会分析问题、解决问题。