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

《数据结构-括号匹配课程设计报告》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、p所指节点的值与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-〉next-〉next-

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

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

6、ructlist{charnode;/*数据域*/structlist*next;/*指针域*/}list,*linklist;/*节点类型*/voidinitlist(linklist);/*函数声明*/intisempty(linklist);intcreatlist_node(linklist,char);Textlist(linklist);voidmain()/*主函数*/{chartest[LEN];inti;lista,b;linklistp,q=&b;/*设立P为list结点指针*/p=&a;/

7、*使P指向头结点a*/initlist(p);/*使p为第一个节点*/-7-printf("Plieaseinputtheexpression:");scanf("%80s",test);for(i=0;inext){switch(q->node){case'[':case']':case'{':case'}':case'(':case')':creat

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