《广义表的应用》由会员分享，可在线阅读，更多相关《广义表的应用（41页珍藏版）》请在金锄头文库上搜索。
1、软件综合课程设计广义表的应用图书借阅管理系统二一四年六月广义表的应用一、问题陈述由于广义表在结构上较线性表复杂得多， 因此，广义表的运算也不如线性表简单。本设计要求实现的广义表的建立、查找、输出、取表头和取表尾以及求深度、求逆表等。本设计用一个主控菜单程序控制，共分为6 个子系统。（1）建立广义表（2）输出广义表（3）结点的查找（4）求广义表表头（5）求广义表表尾（6）求广义表的深度二、需求分析1. 菜单函数使用数字 0-6 来选择菜单项，超出此范围时，提示输入错误，并重新输入。运行程序时，先输入一个广义表，回车后，调用各功能函数，则出现功能菜单，输入的一个数字，该数字用 sn 存储，使用 c
2、hoose（）接受数字输入，该函数的返回值提供给主函数； 则主函数使用 while 循环实现重复选择， 以实现不同的广义表菜单功能。2. 主函数包含的功能函数有：输出广义表、广义表深度、广义表表头、广义表表尾、广义表查找、广义表逆置6 个函数。运行程序时，首先执行主函数，根据提示，建立广义表，广义表中的元素应单独输入，每输入一个字符，回车，广义表输入完成时，应再次输入“）”，表示输入结束，这是由于CreateGList函数递归的原因，回车，此时调用choose（）函数，出现功能菜单，提示用户进行相关操作，进入任一操作，通过switch （ choose（）对用户所输入的信息进行匹配，匹配后调用
3、相关的子函数，从而实现各项函数的功能。3. 创建广义表函数函数中，先定义一个整型数据i=0 和一个数组 a10 ，构建时，先输入一个字符，如果输入字符的是 #，则广义表为空，否则输出第一个左括号。接下来的元素项如果是子表，则递归调用CreateGList()，若是原子，则直接输出，并将输入的数据保存在数组ai中，同时 i+ ，然后继续输入保存用户所输入的数据，若是，则递归调用 CreateGList （）函数，继续执行第一步， 当遇到 ）时，结束。4. 广义表的输出此函数实现的是输出功能，它直接关联到后面的取表头、表尾运算。函数中，分为原子和子表，若是子表，则利用头结点指针，递归输出子表。若是
4、原子，则直2接输出该原子的数值。然后判断下一结点是否为空，不为空则输出“， ”，继续递归输出，执行上一步的操作。5. 结点的查找运行时，输入要查找的元素，将该元素与数组中的元素进行比较，若相等，则查找成功，输出此元素的位置信息，当查找超出范围时，输出查找失败信息。6求广义表的表头表头分为子表和原子。当表头为子表时，先输出左括号，再通过递归调用依次输出表头，最后输出右括号。当表头为原子时，直接输出原子数值。7. 求广义表的表尾若广义表非空，则广义表中除去表头后其余元素构成的子表为表尾。函数中，定义指针 p、q，q 用于指向广义表表头， q-next 为广义表表尾，并赋值给 p，因 p 也是广义表
5、，则可调用广义表输出函数 PrintGList （），输出表尾。8. 广义表的逆置逆置即将表头和表尾倒置，因此算法中，先后调用取表尾函数和取表头函数，先输出表尾，再输出表头，以此实现逆置功能。9. 广义表的深度广义表深度的递归定义式： 它等于所有子表中表的最大深度加 1。若一个表为空，则深度为 1。定义 dep 表示任一子表的深度， max为所有子表中的最大深度， 则广义表的深度为 max+1。函数中，当广义表 L 为空表或由单元素组成时， 不进行递归调用， 返回 1；否则，当广义表含有子表时，利用头结点指针，递归求出深度，将最大深度的子表的 dep 赋值给 max，返回 max+1即为广义表
6、深度。三、概要设计程序的开始，先定义广义表的结点类型，采用枚举类型区分原子 ATOM和子表 LIST。采用联合体定义原子结点的值域 atom 和表头指针域 hp。再输入一个广义表，在程序中可以定义一个数组用来存放广义表中的关键字。 编写各个功能函数时，先了解算法的思想，绘出流程图，根据流程图进一步编写。之后编写一个功能选择函数 choose（），并在此函数中打印运行界面，通过输入代码，来进行不同功能的操作。在运行界面中，通过一个 while 循环，能让用户进行循环操作，直至退出系统。3mainCreateGListchoosePrintGListLocateGListHeaGListTailT
7、raversGListdelistDepth四、详细设计1. 菜单函数int choose()cout-endl;int sn;cout请输入代码0 6： endl;cout-for( ; ; )-endl;coutsn;endl;if( sn 6)cout1.广义表输出2.coutendl输 入 错结点的查找endl;误，重选0 6： endl;cout3.广义表表头4.else广义表表尾endl;break;cout5.广义表逆置6.广义表深度endl;return sn;cout0.退出系统endl;2. 主函数int main()PrintGList(L);coutendl;GList
8、 *L;break;char ch;case 2: coutch;CreateGList(&L); /创建广义表Locate(L, ch);while(1)coutendl;break;switch(choose()case 3: cout广义表取表头： ;case 1: cout输 出 广 义GListHead(L);表： ;coutendl;4break;度为： ;case 4: cout广义表取表尾： ;couthp)endl;cout(;break;GListTail(L);case 0: cout退出！cout)endl;endl;break;exit(0);case 5: prin
9、tf(广 义 表 的break;逆表： );TraverseList(L);coutendl;return 0;break;case 6: coutch;/此处输char ch;入的必为逗号或者右括cinch;/输if(ch=,)入数据/ 如果是逗号就递归构建下一个子表if(ch=#)CreateGList(&(*L)-next);/ 如果输入的是#表示为空elseif(ch=)*L = NULL;/ 如果是右括号就结束elseif(ch=()(*L)-next =NULL;/ 如果是左括号就递归构建子表4. 广义表输出函数PrintGList（）*L=(GListvoid PrintGLis
10、t(GList *L)*)malloc(sizeof(GList);/ 输出广义表(*L)-tag=1;/ 广义表的标志量为LISTif(L-tag=1)CreateGList(&(*L)-hp);/ 广义表标志量为LIST/ 建立此广义表的表头指针所指的元素couthp=NULL)/ 表头指针为空*L=(GListcouttag=0;PrintGList(L-hp);/ 广义表标志量为ATOM/ 递归打印子表(*L)-atom=ch;coutatom;else2/ 标志量为ATOMcout, ;coutatom;/输出PrintGList(L-next); /调用此此元素函数，输出广义表下一个元素if(L-next !=NULL)5. 广义表查找函数 Locate （）void Locate(GList *L,char ch) /广义表cout查 找 成功 ，位 置查找为 :j+1ch; /输入要查找关键字for (j=0;ji)cout 查找失败 , 元素不存在此广义if(aj=ch)/如果找到表中 !hp;/p指向广义
