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

1、安徽三联学院 数据结构课程设计班级： 计 算 机 科 学 与 技 术 系计算机科学与技术专业2008级（2）班组别： 第 八 组 组长： 徐 恒 组员：何洋洋、枉林然、魏世捷、王煜、戴文强 完成日期：2010.1.20题目：括号匹配检验一、问题描述：假设一个算术表达式可以包含3种括号：圆括号“（”和“）”，方括号“”和“”，和花括号“”和“”且这三种括号可按照任意次序嵌套使用（如：（）。设计一个程序，判别所给定表达式中所含括号是否匹配。二、 要求：1 将算术表达式保存在带头结点的单链表中；2 在1中建立的单链表上实现括号匹配问题的求解。三、 解决问题思路：1、 首先建立带头结点的单链表，单链表

2、的数据域存储字符数据，指针域为结点型指针。设立字符型数组先将算术表达式输入到数组当中，通过插入节点函数将数组中字符全部插入到单链中1中。2、 建立单链表2,通过switch，case语句将单链表1中的括号字符全部插入到单链表2中。3、 调用括号匹配函数将，单链表2的头节点调入函数当中，设立标志位has。当has取1时，说明找到一组匹配括号；当has取0时，当前一组括号不匹配。设立temp指向当前所要判断节点，将temp所指节点的值与temp-next节点的值相比较，利用匹配括号ASCII值相差1或2，相同则相差0；或不相同差值不为1、2或0。当temp与temp-next的差值为1或2时，说明

3、找到一组匹配括号。Temp=temp-next；进行新的判断。当temp与temp-next的差值不为1或2时，将temp赋为temp-next；进行新一轮的判断。若temp-next-next与temp-next-next-next匹配时，此时将temp-next-next与temp-next-next-next全部值为空值。且temp-next未找到匹配字符时将temp重新赋为temp->next，进行新的判断。4、 最后，若单链表p为空则则说明表达式中括号匹配；若p不为空，则说明算术表达式中括号不匹配。四、 运行环境：1、 编辑主要环境为microsoft visualC+6.0。

4、2、 调试运行环境为Turbo C2.0。五、 组员分工情况：1、 何洋洋、汪林然负责单链表相关函数的编写；2、 王煜、洪小龙负责收集相关材料和参考资料；3、 徐恒、戴文强负责整理、编译和调试。/六、 遇到的困难及解决问题的办法：1、 最后在调试程序时发现许多错误，例如函数类型不匹配、没有合适的指针、未定义变量、句法错误、函数声明错误、不合法的指针、有未使用的变量、定义不正确等。先是找同学帮助，然后自己学着改错。慢慢的自己学会改错，并找到相关资料来找出的修改方法。2、 遇到实在不懂的地方，就找组员和同学一起讨论，找到问题的根本原因，然后加以纠正。七、 源代码及注释：括号匹配源程序代码及注释#i

5、nclude <stdio.h> /*头文件*/#include <string.h>#include <stdlib.h>#define LEN 80typedef struct listchar node; /*数据域*/struct list *next; /*指针域*/list,*linklist; /*节点类型*/ void initlist(linklist); /*函数声明*/int isempty(linklist);int creatlist_node(linklist,char);Textlist(linklist);void main(

6、) /*主函数*/char testLEN; int i;list a,b; linklist p,q=&b; /*设立P为list结点指针*/p=&a; /*使P指向头结点a*/initlist(p); /*使p为第一个节点*/ printf("Pliease input the expression:n");scanf("%80s",test);for(i=0;i<LEN;i+) creatlist_node(q,testi); /*将数组中算术表达式存入单链表q中*/for(i=0;i<LEN;i+,q=q->ne

7、xt)switch(q->node)case '':case '':case '':case '':case '(':case ')':creatlist_node(p,q->node);/*将q中括号插入单链表p中*/break;default : continue; /*若节点中字符不为括号则进入下一次循环*/ Testlist(p); /*调用判断括号匹配函数,用P链表作为实参*/if(isempty(p) /*判断P是否为空，p为空则表达式中括号匹配*/printf("

8、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 isem

9、pty(linklist aplist) /*判断头结点是否为空函数*/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)malloc(

10、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*/return 0;while(has

11、) 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个节点

12、字符值减去第2个节点字符值为1或2则条件成立进入if语句*/temp->next=temp->next->next->next; /*将节点1赋值为节点3*/has=1; /*标志has重置为1*/elsetemp=temp->next;/*若第3个节点字符值减去第2个节点字符值为0则将temp置为下一个节点*/else temp=temp->next; /*若第三个节点为空则将temp置为下一个节点*/if(!has) /*判断has的值若为1则退出内while循环*/break;return 0; /*当has值为0时则函数返回0*/八、 运行结果：运行结果如下：1、 输入表达式2x+6y-3y+2z*4z+(45-2x)*13-32结果如下：2、 输入表达式2x+2y+2z-(2x-3y)*5+43*5z-32*12结果如下：3、 输入表达式结果如下：4、 输入表达式纯括号类型如：则输出结果为错误，与实际状况不符。九、 讨论部分：1、 在单链表之后，从数组中提取字符输入到单链表中时，无法正确输进去，后来找同学查看，发现指针有些错误。经过修改之后，可将字符成功插入到单链表中。经过讨论后得知指针未正确指向头结