数据结构课程设计_括号嵌套问题.doc

《数据结构》 课程设计报告 （括号嵌套问题） 目 录 TOC \o 1-3 \h \z \u HYPERLINK \l _Toc 一、需求分析 PAGEREF _Toc \h 3 HYPERLINK \l _Toc 二、概要设计 PAGEREF _Toc \h 4 HYPERLINK \l _Toc 三、详细设计 PAGEREF _Toc \h 6 HYPERLINK \l _Toc 四、调试分析 PAGEREF _Toc \h 8 HYPERLINK \l _Toc 五、用户手册 PAGEREF _Toc \h 10 HYPERLINK \l _Toc 六、测试结果 PAGEREF _Toc \h 11 HYPERLINK \l _Toc 七、附录 PAGEREF _Toc \h 12 一、需求分析 1、本程序中，输入为字符串和整形数字； 2、以数字和字符串输出； 3、本括号嵌套问题要实现判断任意给定的圆括号序列，是否是一个深度为k的序列；输出括号对数为n，嵌套深度为k的所有序列；输出括号对数为n，嵌套深度为k的序列的总数的功能，具体为： （1）判断任意给定的圆括号序列，是否是一个深度为k的序列； （2）输出括号对数为n，嵌套深度为k的所有序列； （3）输出括号对数为n，嵌套深度为k的序列的总数； 4、测试数据： （1）判断任意给定的圆括号序列，是否是一个深度为k的序列； 3 ((()()()))()(())2 ((()()()))()(()) 5 (()()()))()((((())))) （2）?输出括号对数为n，嵌套深度为k的所有序列； 1:? ?((()()()))?? 2:? ?((()())()) 3:? ?((()()))()? ?4:? ?((())(()))?? 5:? ?((())()()) ??6:? ?((())())()?? 7:? ?((()))(())?? 8:? ?((()))()()? ?9:? ?(()(()())) 10:? (()(())()) 11:? (()(()))() 12:? (()()(())) 13:? (())((())) 14:? ()((()())) 15:? ()((())()) 16:? ()((()))() 17:? ?()(()(())) 18:? ?()()((())) （3）输出括号对数为n，嵌套深度为k的序列的总数； 3? ?2 15 3 20? ?11 二、概要设计 1、程序包括以下几个模块： 每个模块的算法设计说明如下： （1）判断任意给定的圆括号序列，是否是一个深度为k的序列； 输入n和k，若k0，则执行下一功能，若k0则分别计算左括号和右括号的总数，若不相等则括号不配对，若相等，再比较括号嵌套深度是否和输入的k值相等，再若相等，则输出YES，反之输出NO。 （2）输出括号对数为n，嵌套深度为k的所有序列； 输入n和k，若nk则执行下一功能，反之则输出相应的圆括号所有序列。 （3）输出括号对数为n，嵌套深度为k的序列的总数； 输入n和k，若kn，输出对应序列的总数，反之则跳出循环。 流程图 判断圆括号序列深度 判断圆括号序列深度 输出括号对数为n，嵌套深度为k的所有序列 输出括号对数为n，嵌套深度为k的序列的总数 查看航班信息 括号嵌套 主函数流程图 输入n和圆括号序列，判断k=0,调用函数，判断圆括号序列深度是否为k输入n和k，判断 输入n和圆括号序列，判断k=0,调用函数，判断圆括号序列深度是否为k 输入n和k，判断kn,调用函数，输出括号对数为n深度为k的所有序列 输入n和k，判断kn,调用函数，输出相应的括号序列的总数 NO NO YES YES NO 三、详细设计 1、请编程判断任意给定的圆括号序列，是否是一个深度为k的序列。 for(i=0;a[i]!=\0;i++)//用于做一个圆括号序列的循环 { if(a[i]==()//当a[i]等于左括号时counta加一 counta++ ; if(a[i]==))//当a[i]等于右括号时加countb加一 countb++; } if( countb==counta )//括号配对的情况 { for(i=0;a[i]!=\0;i++)//用于做一个圆括号序列的循环 { if(a[i]==)) //用于计