广义表的应用(共41页).doc

精选优质文档-倾情为你奉上软件综合课程设计 广义表的应用图书借阅管理系统 二一四 年 六 月广义表的应用一、问题陈述由于广义表在结构上较线性表复杂得多，因此，广义表的运算也不如线性表简单。本设计要求实现的广义表的建立、查找、输出、取表头和取表尾以及求深度、求逆表等。本设计用一个主控菜单程序控制，共分为6个子系统。（1）建立广义表（2）输出广义表（3）结点的查找（4）求广义表表头（5）求广义表表尾（6）求广义表的深度二、需求分析1.菜单函数 使用数字0-6来选择菜单项，超出此范围时，提示输入错误，并重新输入。运行程序时，先输入一个广义表，回车后，调用各功能函数，则出现功能菜单，输入的一个数字，该数字用sn存储，使用choose（）接受数字输入，该函数的返回值提供给主函数；则主函数使用while循环实现重复选择，以实现不同的广义表菜单功能。2.主函数 包含的功能函数有：输出广义表、广义表深度、广义表表头、广义表表尾、广义表查找、广义表逆置6个函数。运行程序时，首先执行主函数，根据提示，建立广义表，广义表中的元素应单独输入，每输入一个字符，回车，广义表输入完成时，应再次输入“）”，表示输入结束，这是由于CreateGList函数递归的原因，回车，此时调用choose（）函数，出现功能菜单，提示用户进行相关操作，进入任一操作，通过switch（choose（）对用户所输入的信息进行匹配，匹配后调用相关的子函数，从而实现各项函数的功能。3.创建广义表函数函数中，先定义一个整型数据i=0和一个数组a10，构建时，先输入一个字符，如果输入字符的是#，则广义表为空，否则输出第一个左括号。接下来的元素项如果是子表，则递归调用CreateGList()，若是原子，则直接输出，并将输入的数据保存在数组ai中，同时i+，然后继续输入保存用户所输入的数据，若是，则递归调用CreateGList（）函数，继续执行第一步，当遇到）时，结束。4. 广义表的输出此函数实现的是输出功能，它直接关联到后面的取表头、表尾运算。函数中，分为原子和子表，若是子表，则利用头结点指针，递归输出子表。若是原子，则直接输出该原子的数值。然后判断下一结点是否为空，不为空则输出“，”，继续递归输出，执行上一步的操作。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循环，能让用户进行循环操作，直至退出系统。mainCreateGList choosePrintGListLocateGListHeadGListTailTraverselistGListDepth四、详细设计1.菜单函数专心-专注-专业int choose() int sn;cout<<"-"<<endl;cout<<" 广义表的应用 "<<endl;cout<<" 1.广义表输出 2.结点的查找 "<<endl;cout<<" 3.广义表表头 4.广义表表尾 "<<endl;cout<<" 5.广义表逆置 6.广义表深度 "<<endl;cout<<" 0.退出系统 "<<endl;cout<<"-"<<endl; cout<<"请输入代码06："<<endl; for( ; ; ) cin>>sn;if( sn <0|sn>6)cout<<endl<<"输入错误，重选06："<<endl;elsebreak;return sn;2.主函数int main()GList *L; char ch;printf("建立广义表，结束请多输一个右括号！n");CreateGList(&L); /创建广义表while(1) switch(choose()case 1:cout<<"输出广义表："PrintGList(L);cout<<endl;break;case 2:cout<<"请输入要查找的结点："cin>>ch;Locate(L, ch);cout<<endl;break;case 3:cout<<"广义表取表头："GListHead(L);cout<<endl;break;case 4:cout<<"广义表取表尾："cout<<"("GListTail(L);cout<<")"<<endl;break;case 5:printf("广义表的逆表：");TraverseList(L);cout<<endl;break;case 6:cout<<"广义表的深度为："cout<<GListDepth(L->hp)<<endl;break;case 0:cout<<"退出！"<<endl;exit(0);break;return 0;3.创建广义表函数：CreateGList（）void CreateGList(GList *L)/创建广义表函数 char ch;cin>>ch;/输入数据if(ch = '#') /如果输入的是#表示为空*L = NULL;else if(ch = '(') /如果是左括号就递归构建子表*L = (GList *)malloc(sizeof(GList);(*L)->tag =1; /广义表的标志量为LISTCreateGList(&(*L)->hp); /建立此广义表的表头指针所指的元素else/只有原子的情况下*L = (GList *)malloc(sizeof(GList);(*L)->tag = 0; /广义表标志量为ATOM(*L)->atom = ch; /元素为所输入数值ai=ch; /不能写成ai=(*L)->atom;i+;cin>>ch; /此处输入的必为逗号或者右括if(ch = ',') /如果是逗号就递归构建下一个子表CreateGList(&(*L)->next); else if(ch = ')') /如果是右括号就结束 (*L)->next =NULL;4.广义表输出函数PrintGList（）void PrintGList(GList *L) /输出广义表if(L->tag = 1) /广义表标志量为LIST cout<<"(" /先输出左括号if(L->hp = NULL) /表头指针为空cout<<"#"elsePrintGList(L->hp); /递归打印子表 cout<<")" /结束打印右括号else /标志量为ATOMcout<<L->atom; /输出此元素 if(L->next !=NULL) cout<<", "PrintGList(L->next); /调用此函数，输出广义表下一个元素5. 广义表查找函数Locate（）void Locate(GList *L,char ch) /广义表查找int j;cin>>ch; /输入要查找关键字for (j=0;j<=i;j+)/用for循环查找if(aj=ch) /如果找到cout<<"查找成功，位置为:"<<j+1<<endl;break;if(j>i)cout<<"查找失败,元素不存在此广义表中!"<<endl;6.广义表取表头函数：void GListHead(GList *L) /广义表取表头GList *p;p=L->hp; /p指向广义表表头PrintGListHead(p); /调用表头输出函数7.广义表取表尾函数void GListTail(GList *L)/广义表取表尾GList *p,*q;q=L->hp;/q指向广义表表头p=q->next;/p指向广义表表尾PrintGList(p); 8.广义表逆置函数TraverseList()void TraverseList(GList *L) /广义表逆置 cout<<"(" GListTail(L); /调用取表尾函数 cout<<"," GListHead(L); /调用取表头函数cout<<")"9. 广义表求深度函数int GListDepth(GList *L) /求广义表深度int max, dep;if(!L)/广义表存在return 1;for(max =0; L; L=L->next) /max初值为0，元素地址不为空if(L->tag = 1) /元素标志量为LISTdep = GListDepth(L->hp); /求以L->hp的子表深度if(dep > max)max = dep; return max + 1; /各元素的深度的最大值加一五、程序代码#include <iostream>using namespace std;typedef enumATOM, LISTElemTag; /ATOM=0:原子,LIST=1:子表typedef struct GLNode /广义表结构类型int tag; /标志域,区分原子和表结点union /原子结点和表结点的联合部分char atom; /原子结点的值域 struct GLNode *hp; /表结点表头指针;struct GLNode *next;/下一个元素结点GList;int i=0; /定义变量i，用来作数组下标 int a10; /定义数组用来存储广义表中的关键字void CreateGList(GList *L)/创建广义表函数 char ch;cin>>ch; /输入数据if(ch = '#') /如果输入的是#表示为空*L = NULL;else if(ch = '(') /如果是左括号就递归构建子表*L= (GList *)malloc(sizeof(GList); (*L)->tag=1; /广义表的标志量为LISTCreateGList(&(*L)->hp); /建立此广义表的表头指针所指的元素else/只有原子的情况下*L = (GList *)malloc(sizeof(GList);(*L)->tag = 0; /广义表标志量为ATOM(*L)->atom = ch; /元素为所输入数值ai=ch; /不能写成ai=(*L)->atom;i+;cin>>ch; /此处输入的必为逗号或者右括if(ch = ',') /如果是逗号就递归构建下一个子表CreateGList(&(*L)->next); elseif(ch=')') /如果是右括号就结束 (*L)->next =NULL;void PrintGList(GList *L) /输出广义表if(L->tag=1) /广义表标志量为LIST cout<<"(" /先输出左括号if(L->hp = NULL) /表头指针为空cout<<"#"elsePrintGList(L->hp); /递归打印子表 cout<<")" /结束打印右括号else /标志量为ATOMcout<<L->atom; /输出此元素 if(L->next !=NULL) cout<<", "PrintGList(L->next); /调用此函数，输出广义表下一个元素int GListDepth(GList *L) /求广义表深度int max, dep;if(!L)/广义表存在return 1;for(max = 0; L; L = L->next) /max初值为0，元素地址不为空if(L->tag = 1) /元素标志量为LISTdep = GListDepth(L->hp); /求以L->hp的子表深度if(dep > max)max = dep; return max + 1; /各元素的深度的最大值加一void PrintGListHead(GList *L) /打印广义表表头函数 if(L->tag = 1 ) /子表 cout<<"(" /先输出左括号if(L->hp = NULL) /如果表头为空cout<<"#" elsePrintGListHead(L->hp); /递归打印子表cout<<")" /结束打印右括号else /原子cout<<L->atom;void GListHead(GList *L) /广义表取表头GList *p;p=L->hp; /p指向广义表表头PrintGListHead(p); /调用表头输出函数void GListTail(GList *L)/广义表取表尾GList *p,*q;q=L->hp;/q指向广义表表头p=q->next;/p指向广义表表尾PrintGList(p); void TraverseList(GList *L) /广义表逆置 cout<<"(" GListTail(L);/调用取表尾函数 cout<<"," GListHead(L); /调用取表头函数cout<<")"void Locate(GList *L,char ch) /广义表查找int j;for (j=0;j<=i;j+)/用for循环查找if(aj=ch) /如果找到cout<<"查找成功，位置为:"<<j+1<<endl;break;if(j>i)cout<<"查找失败,元素不存在此广义表中!"<<endl;int choose() int sn;cout<<"-"<<endl;cout<<" 广义表的应用 "<<endl;cout<<" 1.广义表输出 2.结点的查找 "<<endl;cout<<" 3.广义表表头 4.广义表表尾 "<<endl;cout<<" 5.广义表逆置 6.广义表深度 "<<endl;cout<<" 0.退出系统 "<<endl;cout<<"-"<<endl; cout<<"请输入代码06："<<endl; for( ; ; ) cin>>sn;if( sn <0|sn>6)cout<<endl<<"输入错误，重选06："<<endl;elsebreak;return sn; int main()GList *L; char ch;printf("建立广义表，结束请多输一个右括号！n");CreateGList(&L); /创建广义表while(1) switch(choose()case 1:cout<<"输出广义表："PrintGList(L);cout<<endl;break;case 2:cout<<"请输入要查找的结点："cin>>ch;Locate(L, ch);cout<<endl;break;case 3:cout<<"广义表取表头："GListHead(L);cout<<endl;break;case 4:cout<<"广义表取表尾："cout<<"("GListTail(L);cout<<")"<<endl;break;case 5:printf("广义表的逆表：");TraverseList(L);cout<<endl;break;case 6:cout<<"广义表的深度为："cout<<GListDepth(L->hp)<<endl;break;case 0:cout<<"退出！"<<endl;exit(0);break;return 0;六、运行结果与测试1.建立广义表2.输出广义表3.结点的查找4.求广义表表头5. 求广义表表尾6. 求广义表的逆表7. 求广义表的深度8.退出七、设计体会与总结此次课程设计我被分配到的题目是广义表的应用，这对我来说是个熟悉的陌生人，因为前不久才复习过，可是没记住，只能回头再去看，经过多方面参考，总算是勉强执行出来了，不过这中间也遇到了一些问题：1.建立广义表时，把表一次性全部输完再回车，无限循环；经检查，是源程序中输入算法编写的错误。2. 输入代码1，即输出广义表，显示调试错误，经检查，是源程序中输出算法编写的错误。3.查找结点的时候要输入两个结点才会显示第二个结点位置；经检查，是调用的程序中多写了一句输入语句。图书借阅管理系统一、问题陈述  主要分为两大功能：1)图书管理(增加图书、查询图书、删除图书、图书借阅、还书)；2)会员管理(增加会员、查询会员、删除会员、借书信息)；二、需求分析1.主函数分为两个模块：图书信息和会员信息，并显示两个模块的主界面，可将图书信息和会员信息写入和读出。2.图书管理（1）增加图书：只需添加书的编号和书名即可，考虑到图书的信息较多，所以用结构体对其定义，又考虑到图书量大，所以添加后要保存到文件中去。（2）查询图书：可按书名查询、按书的编号查询，也可查询所有图书信息，主要是通过顺序查找法来实现的。（3）删除图书：输入要删除的书的编号即可，主要是把保存到文件中的内容写到链表中去，用链表删除结点的方法来删除，删除时以记录为单位，能一次删除一条记录。（4）图书借阅：输入会员编号和图书编号即可借阅，能对借出的图书作记录信息，能一次借出一本图书。（5）还书：输入要还的书的编号即可还，能将被借出的图书信息还原，能一次借出一本图书。3.会员管理（方法与图书管理类似）（1）增加会员：输入会员编号、姓名、性别即可添加。（2）查询会员：可按姓名查询，也可查询所有会员信息。（3）删除会员：输入会员编号即可删除，主要是通过把保存到文件中的内容写到链表中去，用链表删除结点的方法来删除图书。（4）借书信息：选择“借书信息”即可显示所有读者是否借书三、概要设计图书和会员的信息的存储是建立两个带头结点的单链表，分别用于存储图书和会员。建立这两个链表的联系是在图书结点中设一个借书人编号，在会员结点中设一个数组用于存会员借的书，剩下的只需按链表的操作就可以了。四、详细设计1.主函数void main()FILE *fpb1,*fpb2,*fpm1,*fpm2; /文件指针Book *p1,*p2,*s1;Member *q1,*q2,*s2;H=Init_B();L=Init_M();fpb1=fopen("book.txt","rb"); /读方式打开图书文件if(fpb1!=NULL)p1=(Book *)malloc(sizeof(Book);if(!p1) exit(1);p1->next=NULL;while(fread(p1,sizeof(Book),1,fpb1)=1)if(H->next=NULL)H->next=p1;s1=p1;elses1->next=p1;s1=p1;p1=(Book *)malloc(sizeof(Book);if(!p1) exit(1);p1->next=NULL;fpm1=fopen("member.txt","rb"); /读方式打开会员文件if(fpm1!=NULL)q1=(Member *)malloc(sizeof(Member);if(!q1) exit(1);q1->next=NULL;while(fread(q1,sizeof(Member),1,fpm1)=1)if(L->next=NULL)L->next=q1;s2=q1;elses2->next=q1;s2=q1;q1=(Member *)malloc(sizeof(Member);if(!q1) exit(1);q1->next=NULL;int m,n;while(m!=0)cout<<" 欢迎进入图书借阅管理系统 "<<endl;cout<<" *"<<endl;cout<<" 1.图书管理 "<<endl;cout<<" 2.会员管理 "<<endl;cout<<" 0.退出系统 "<<endl;cout<<"*"<<endl;cout<<" 请在此输入您的选择："cin>>m;cout<<"="<<endl;cout<<endl;if(m=1)cout<<" 图书管理 "<<endl;cout<<"*"<<endl;cout<<" 1.增加图书 3.删除图书 "<<endl;cout<<" 2.查询图书 4.图书借阅 "<<endl;cout<<" 0.退 出 "<<endl;cout<<" *"<<endl;cout<<"请输入您的选择："cin>>n;cout<<"="<<endl;switch(n)case 1:BookAdd(H); break; /增加图书case 2:BookSearch(H); break; /查询图书case 3:BookDel(H); break; /删除图书case 4:BookBorrow(H,L); break; /图书借阅case 0:break; /退出图书管理，返回上一层菜单else if(m=2)cout<<" 会员管理 "<<endl;cout<<" *"<<endl;cout<<" 1.增加会员 3.删除会员 "<<endl;cout<<" 2.查询会员 4.借书信息 "<<endl;cout<<" 0.退 出 "<<endl;cout<<" *"<<endl;cout<<" 请输入您的选择："cin>>n;cout<<"="<<endl;switch(n)case 1:MemberAdd(L); break; /增加会员case 2:MemberSearch(L); break; /查询会员case 3:MemberDel(L); break; /删除会员case 4:BorrowInfo(L); break; /借书信息case 0:break; /退出会员管理，返回上一层菜单else if(m=0)cout<<endl<<"退出系统"<<endl;fpb2=fopen("book.txt","wb");for(p2=H->next;p2!=NULL;p2=p2->next)fwrite(p2,sizeof(Book),1,fpb2);fclose(fpb2);fpm2=fopen("member.txt","wb");for(q2=L->next;q2!=NULL;q2=q2->next)fwrite(q2,sizeof(Member),1,fpm2);fclose(fpm2);exit(0);2. 图书管理（1）增加图书int BookAdd(BookList &H)/建立一个带头结点的链表用来存储图书信息int i=0;/统计要增加的图书量Book *p,*q;p=(Book *)malloc(sizeof(Book);if(!p) exit(1);if(H->next=NULL)cout<<" 输入图书编号："cin>>p->num;if(p->num=0)/退出"增加图书"cout<<" 共计"<<i<<"本图书入库！"<<endl;cout<<"="<<endl;return 1;cout<<" 输入书名："cin>>p->name;p->yes=1;/1表示没有借出p->next=NULL;H->next=p;q=p;+i;cout<<endl;elseq=H;while(q->next!=NULL)q=q->next;p->num=1; /进入循环的条件p->next=NULL;while(p->num!=0)/以图书编号作为判断链表是否结束p=(Book *)malloc(sizeof(Book);if(!p) exit(1);cout<<" 输入图书编号："cin>>p->num;if(p->num=0) /退出"增加图书"cout<<" 共计"<