发布时间 : 星期二 文章广义表的应用更新完毕开始阅读6f770d51eff9aef8941e0692
件综合课程 广义表的应用 图书借阅管理系统
二〇一四 年 六 月
设计
软
广义表的应用
一、问题陈述
由于广义表在结构上较线性表复杂得多，因此，广义表的运算也不如线性表简单。本设计要求实现的广义表的建立、查找、输出、取表头和取表尾以及求深度、求逆表等。
本设计用一个主控菜单程序控制，共分为6个子系统。 （1）建立广义表 （2）输出广义表 （3）结点的查找 （4）求广义表表头 （5）求广义表表尾 （6）求广义表的深度
二、需求分析
1.菜单函数
使用数字0-6来选择菜单项，超出此范围时，提示输入错误，并重新输入。运行程序时，先输入一个广义表，回车后，调用各功能函数，则出现功能菜单，输入的一个数字，该数字用sn存储，使用choose（）接受数字输入，该函数的返回值提供给主函数；则主函数使用while循环实现重复选择，以实现不同的广义表菜单功能。
2.主函数
包含的功能函数有：输出广义表、广义表深度、广义表表头、广义表表尾、广义表查找、广义表逆置6个函数。运行程序时，首先执行主函数，根据提示，建立广义表，广义表中的元素应单独输入，每输入一个字符，回车，广义表输入完成时，应再次输入“）”，表示输入结束，这是由于CreateGList函数递归的原因，回车，此时调用choose（）函数，出现功能菜单，提示用户进行相关操作，进入任一操作，通过switch（choose（））对用户所输入的信息进行匹配，匹配后调用相关的子函数，从而实现各项函数的功能。
3.创建广义表函数
函数中，先定义一个整型数据i=0和一个数组a[10]，构建时，先输入一个字符，如果输入字符的是‘#’，则广义表为空，否则输出第一个左括号。接下来的元素项如果是子表，则递归调用CreateGList()，若是原子，则直接输出，并将输入的数据保存在数组a[i]中，同时i++，然后继续输入保存用户所输入的数据，若是‘，’，则递归调用CreateGList（）函数，继续执行第一步，当遇到‘）’时，结束。
4. 广义表的输出
此函数实现的是输出功能，它直接关联到后面的取表头、表尾运算。函数中，分为原子和子表，若是子表，则利用头结点指针，递归输出子表。若是原子，则直
2
接输出该原子的数值。然后判断下一结点是否为空，不为空则输出“，”，继续递归输出，执行上一步的操作。
5. 结点的查找
运行时，输入要查找的元素，将该元素与数组中的元素进行比较，若相等，则查找成功，输出此元素的位置信息，当查找超出范围时，输出查找失败信息。
6．求广义表的表头
表头分为子表和原子。当表头为子表时，先输出左括号，再通过递归调用依次输出表头，最后输出右括号。当表头为原子时，直接输出原子数值。
7. 求广义表的表尾
若广义表非空，则广义表中除去表头后其余元素构成的子表为表尾。函数中，定义指针p、q，q用于指向广义表表头，q->next为广义表表尾，并赋值给p，因p也是广义表，则可调用广义表输出函数PrintGList（），输出表尾。
8. 广义表的逆置
逆置即将表头和表尾倒置，因此算法中，先后调用取表尾函数和取表头函数，先输出表尾，再输出表头，以此实现逆置功能。
9. 广义表的深度
广义表深度的递归定义式：它等于所有子表中表的最大深度加1。若一个表为空，则深度为1。定义dep表示任一子表的深度，max为所有子表中的最大深度，则广义表的深度为max+1。
函数中，当广义表L为空表或由单元素组成时，不进行递归调用，返回1；否则，当广义表含有子表时，利用头结点指针，递归求出深度，将最大深度的子表的dep赋值给max，返回max+1即为广义表深度。
三、概要设计
程序的开始，先定义广义表的结点类型，采用枚举类型区分原子ATOM和子表LIST。采用联合体定义原子结点的值域atom和表头指针域hp。再输入一个广义表，在程序中可以定义一个数组用来存放广义表中的关键字。编写各个功能函数时，先了解算法的思想，绘出流程图，根据流程图进一步编写。之后编写一个功能选择函数choose（），并在此函数中打印运行界面，通过输入代码，来进行不同功能的操作。在运行界面中，通过一个while循环，能让用户进行循环操作，直至退出系统。
3
main CreateGList choose PrintGList Locate GListHead GListTail Traverselist GListDepth
四、详细设计
1.菜单函数
int choose() cout<<\ { -------------\ int sn; cout<<\请输入代码0－6：\ cout<<\ for( ; ; )
-------------\ { cout<<\广义表的应用 cin>>sn; \ if( sn <0||sn>6) cout<<\广义表输出 2. cout< cout<<\ 0.退出系统 } \ 2.主函数 int main() { GList *L; char ch; printf(\建立广义表，结束请多输一个右括号！\\n\ CreateGList(&L); //创建广义表 while(1) { switch(choose()) { case 1: cout<<\输出广义表：\ PrintGList(L); cout< case 2: cout<<\请输入要查找的结点：\ cin>>ch; Locate(L, ch); cout< case 3: cout<<\广义表取表头：\