广义表的应用

二〇一四 年 六 月

设计

软

广义表的应用

一、问题陈述

由于广义表在结构上较线性表复杂得多，因此，广义表的运算也不如线性表简单。本设计要求实现的广义表的建立、查找、输出、取表头和取表尾以及求深度、求逆表等。

本设计用一个主控菜单程序控制，共分为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 CreateGLis choose PrintGList e LocatGListHead GListTail TraverseGList

四、详细设计

1.菜单函数

int choose() cout<<\"-------------------------- { -------------\"<cout<<\" 广义表的应用 { \"<>sn;

cout<<\" 1.广义表输出 2. if( sn <0||sn>6) 结点的查找 \"<cout<<\" 3.广义表表头 4.误，重选0－6：\"<cout<<\" 5.广义表逆置 6. break; 广义表深度 \"<cout<<\" 0.退出系统 return sn; \"<2.主函数

int main()

{ GList *L; char ch; printf(\"建立广义表，结束请多输一个右括号！\\n\");

CreateGList(&L); 建广义表函数：CreateGList（） void CreateGList(GList **L) 义表输出函数PrintGList（） void PrintGList(GList *L) 广义表查找函数Locate（） void Locate(GList *L,char ch) 义表取表头函数： void GListHead(GList *L) 义表取表尾函数

void GListTail(GList *L) 义表逆置函数TraverseList() void TraverseList(GList *L) 广义表求深度函数

int GListDepth(GList *L) 义表输出 2.结点的查找

4

\"<cout<<\" 3.广义表表头 4.广义表表尾 \"<>sn; if( sn <0||sn>6) cout<int main() { GList *L; char ch; printf(\"建立广义表，结束请多输一个右括号！\\n\");

CreateGList(&L); 立广义表

2.输出广义表

5

3.结点的查找

4.求广义表表头

6

5. 求广义表表尾

6. 求广义表的逆表

7

7. 求广义表的深度

8.退出

七、设计体会与总结

此次课程设计我被分配到的题目是广义表的应用，这对我来说是个熟悉的陌生人，因为前不久才复习过，可是没记住，只能回头再去看，经过多方面参考，总算是勉强执行出来了，不过这中间也遇到了一些问题：

1.建立广义表时，把表一次性全部输完再回车，无限循环；经检查，是源程序中输入算法编写的错误。

2. 输入代码1，即输出广义表，显示调试错误，经检查，是源程序中输出算法编写的错误。

3.查找结点的时候要输入两个结点才会显示第二个结点位置；经检查，是调用的程序中多写了一句输入语句。

8

图书借阅管理系统

一、问题陈述

主要分为两大功能：

1)图书管理(增加图书、查询图书、删除图书、图书借阅、还书)； 2)会员管理(增加会员、查询会员、删除会员、借书信息)；

二、需求分析

1.主函数

分为两个模块：图书信息和会员信息，并显示两个模块的主界面，可将图书信息和会员信息写入和读出。

2.图书管理

（1）增加图书：只需添加书的编号和书名即可，考虑到图书的信息较多，所以用结构体对其定义，又考虑到图书量大，所以添加后要保存到文件中去。

（2）查询图书：可按书名查询、按书的编号查询，也可查询所有图书信息，主要是通过顺序查找法来实现的。

（3）删除图书：输入要删除的书的编号即可，主要是把保存到文件中的内容写到链表中去，用链表删除结点的方法来删除，删除时以记录为单位，能一次删除一条记录。

（4）图书借阅：输入会员编号和图书编号即可借阅，能对借出的图书作记录信息，能一次借出一本图书。

（5）还书：输入要还的书的编号即可还，能将被借出的图书信息还原，能一次借出一本图书。

3.会员管理（方法与图书管理类似）

（1）增加会员：输入会员编号、姓名、性别即可添加。

（2）查询会员：可按姓名查询，也可查询所有会员信息。

（3）删除会员：输入会员编号即可删除，主要是通过把保存到文件中的内容写到链表中去，用链表删除结点的方法来删除图书。

（4）借书信息：选择“借书信息”即可显示所有读者是否借书

三、概要设计

图书和会员的信息的存储是建立两个带头结点的单链表，分别用于存储图书和会员。建立这两个链表的联系是在图书结点中设一个借书人编号，在会员结点中设一个数组用于存会员借的书，剩下的只需按链表的操作就可以了。

9

四、详细设计

1.主函数

void main() { FILE *fpb1,*fpb2,*fpm1,*fpm2; 书管理 \"<>m; cout<<\"====================================\"<>n; cout<<\"====================================\"<10

cout<<\" 0.退 出 \"<cout<<\" ***********************************\"<>n;

cout<<\"====================================\"<case 1:MemberAdd(L); break; 图书管理 （1）增加图书

int BookAdd(BookList &H) um==0) break; q->t[i].num=p->num; cout<<\" 成功借出！\"<num) { q->t[k].num=0; q->max--; break; } cout<<\" 还书成功！\"<max==0) q->yes=0;

flag=1; 员管理

cout<<\"==========================

==========\"<} else if(p->num==n&&p->yes==0) { cout<<\" 无借书记录！\"<cout<<\"====================================\"<} } return 1; }

（1）增加会员

int MemberAdd(MemberList &L) um=0; p->max=0; um=0; p->max=0; um!=0) { k++; if(flag==0) cout<<\"本数\"<cout<t[j].num<flag=1; } }

五、程序代码

#include <>

11

#include <>

#include #include #include <> #include <> #include <>

#define MAX 10书名查询 3.查询所有图书信息 \"<>m; cout<<\"====================================\"<t[i].num=p->num; cout<<\" 成功借出！\"<num) { q->t[k].num=0; q->max--; break; } cout<<\" 还书成功！\"<max==0) q->yes=0; flag=1; um=0; p->max=0; um=0; p->max=0; 姓名查询 2. 查询所有会员信息\"<>m; cout<<\"====================================\"<12

cout<t[j].num<num==n&&p->yes==0) { cout<<\" 无借书记录！\"<>m; cout<<\"====================================\"<>n; cout<<\"====================================\"<>n; cout<<\"====================================\"<13

{

case 1:MemberAdd(L); break; 菜单

1-1增加图书

14

1-2查询图书：可查询所有图书，也可按书名或编号查询

查询所有按书名按书号

15

1-3删除图书

1-4图书借阅

1-5还书

2-1增加会员

16

2-2查询会员：可查询所有会员或按姓名查询

查询所有按姓名

2-3删除会员

2-4借书信息

17

七、设计体会与总结

由于之前其他的课程设计做的都是图书管理系统，对这个比较熟悉，所以这次就选了差不多的图书借阅管理系统。不过在做的过程中还是不免出现了这样那样的问题，最主要的还是文件写不进去，经检查，头文件中少了几个语句：

#include <> #include using namespace std;

同时通过这几天的程序及报告编写，我也发现了自己的很多不足，自己知识的很多漏洞，看到了自己的实践经验还是比较缺乏，理论联系实际的能力还是比较脆弱。尤其是编写大型的程序所要拥有的知识和技能比较缺乏。程序编好了，还要经过调试和修改，这步也很关键，好的程序是经过了无数次的修改和调试才产生的。

这个程序基本上能够满足要求，但还有一些地方需要改进，比如图书编号不可以重复，显示借书信息时可以把书名显示出来，而不仅仅是显示是否借书等。

18