数据结构课程设计(家族关系查询系统)

家族关系查询系统11课程设计介绍1.1课程设计项目简介家谱是一种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书载体。家谱是中国特有的文化遗产，是中华民族的三大文献之一，属珍贵的人文资料，对于历史学，民俗学，人口学，社会学和经济学的深入研究，均有不可替代的重要功能。本项目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员等功能。1.2课设题目分析本程序的实质是完成对家谱成员信息的建立、查找、插入等功能。可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。本程序包含以下几个模块（1）建立家族关系树。此模块将构建一个家族关系，对数据初始化，构造关系树并录入数据一遍后续程序使用。（2）添加新成员。此模块将添加一个新成员，实现对家族关系的修改。（3）家族关系的查询。此模块将实现对家族不同关系的查询（4）主程序模块。此模块实现整个程序的进入和进出，以及各种初始化处理。（5）1.3课程题目原理与数据结构因为家族的成员之间存在一个对多个的层次结构关系，所以不能用线性表来表示和实现。家谱从形状上看像一颗倒长的树，所以用树结构来表示比较合适。树形结构是一类非常重要的非线性数据结构，直观看来树是以分支关系定义的层次结构。因此本课程设计可以采用的数据结构有树状结构和队列。树状结构采用三叉链表来实现，队列采用链式队列实现。家族关系查询系统21.4功能分析说明图家族关系查询系统建立一个家族关系打开一个家族关系添加一个家庭成员按关系查找各个家庭成员退出系统查找一个成员的祖先查找成员的子孙后代查找成员祖先路径查找成员是第几代查找一个成员双亲查找一个成员的兄弟查找成员的堂兄弟查找一个成员的孩子家族关系查询系统32分析与实现2.1基本数据结构和栈队的操作2.1.1结点基本数据结构和链队的定义/*家族关系树实现*/#includestring.h#includemalloc.h#includelimits.h#includestdio.h#includestdlib.h#includeio.h#includemath.h#includeprocess.h#defineTRUE1#defineFALSE0#defineOK1#defineERROR-1#defineINFEASIBLE-1typedefcharDataType;#defineMAXNUM20typedefstructTriTNode/*树的三叉链表存储结构*/{DataTypedata[MAXNUM];structTriTNode*parent;/*双亲*/structTriTNode*lchild;/*左孩子*/structTriTNode*rchild;/*右孩子*/}TriTree;typedefstructNode/*队列的结点结构*/{TriTree*info;structNode*next;}Node;typedefstruct/*链接队列类型定义*/{structNode*front;/*头指针*/家族关系查询系统4structNode*rear;/*尾指针*/}LinkQueue;DataTypefname[MAXNUM],family[50][MAXNUM];/*全局变量*/2.1.2链队的基本操作LinkQueue*LQueueCreateEmpty()/*建立一个空队列*/{LinkQueue*plqu=(LinkQueue*)malloc(sizeof(LinkQueue));if(plqu!=NULL)plqu-front=plqu-rear=NULL;else{printf(内存不足！\n);returnNULL;}returnplqu;}intLQueueIsEmpty(LinkQueue*plqu)/*判断链接表示队列是否为空队列*/{return(plqu-front==NULL);}voidLQueueEnQueue(LinkQueue*plqu,TriTree*x)/*进队列*/{Node*p=(Node*)malloc(sizeof(Node));if(p==NULL)printf(内存分配失败！\n);else{p-info=x;p-next=NULL;if(plqu-front==NULL)/*原来为空队*/plqu-front=p;elseplqu-rear-next=p;plqu-rear=p;家族关系查询系统5}}intLQueueDeQueue(LinkQueue*plqu,TriTree*x)/*出队列*/{Node*p;if(plqu-front==NULL){printf(队列空！\n);returnERROR;}else{p=plqu-front;x=p-info;plqu-front=plqu-front-next;free(p);returnOK;}}TriTree*LQueueGetFront(LinkQueue*plqu)/*在非空队列中求队头元素*/{return(plqu-front-info);}2.2建立家族关系2.2.1建立家族关系并存入文件基本思想：首先输入家族关系的名称，以此名称为文件名，建立文本文件接下来按层次输入结点信息，输入一个在文件中写入一行同时将输入的信息保存到二位字符数组family中。字符数组family是全局变量，存储临时信息.注意，输入时每个结点信息占一行，一个结点有多个家族关系查询系统6兄弟，以“@”作为兄弟结束标志，结点若无孩子，直接以“@”代替。依次输入各节点信息，以“#”作为结束标志。最后使用函数CreateTriTree建立家族关系树.TriTree*Create(DataTypefamilyname[MAXNUM])/*建立家族关系并存入文件*/{inti=0;/*i控制family数组下标*/DataTypech,str[MAXNUM];/*ch存储输入的y或n，str存储输入的字符串*/TriTree*t;FILE*fp;strcpy(fname,familyname);/*以家族名为文本文件名存储*/strcat(fname,.txt);fp=fopen(fname,r);/*以读取方式打开文件*/if(fp)/*文件已存在*/{fclose(fp);printf(%s的家族关系已存在！重新建立请按“Y”,直接打开请按“N”\n,familyname);ch=getchar();getchar();/*接收回车*/if(ch=='N'||ch=='n')lixianliguoyuliguojunliguoqiangliyongzhiliyongruiliyongmingliwendeliwenjia家族关系查询系统7{t=Open(familyname);/*直接打开*/returnt;}}if(!fp||ch=='Y'||ch=='y')/*重新建立，执行以下操作*/{fp=fopen(fname,w);/*以写入方式打开文件，不存在则新建*/printf(请按层次输入结点，每个结点信息占一行\n);printf(兄弟输入结束以“@”为标志，结束标志为“#”\n.);gets(str);fputs(str,fp);fputc('\n',fp);strcpy(family[i],str);/*将成员信息存储到字符数组中*/i++;/*family数组下标后移*/while(str[0]!='#'){printf(.);/*以点提示符提示继续输入*/gets(str);fputs(str,fp);/*写到文件中，每个信息占一行*/fputc('\n',fp);strcpy(family[i],str);/*将成员信息存储到字符数组中*/i++;/*family数组下标后移*/}fclose(fp);/*关闭文件*/t=TriTreeCreate();/*根据family数组信息创建三叉树*/printf(家族关系已成功建立！\n);returnt;/*返回树*/}}2.2.2建立家族关系树家族关系查询系统8基本思想：采用指针数组作为指针，保存输入的结点地址。队列的尾指针指向当前结点。头指针指向当前结点的双亲结点。输入的结点信息已存储在字符数组family中。将信息复制到字符串数组“ch”中，如果ch不是“@”，则建立一个新结点。若新结点是第一个结点，则它是根结点，将其入队，指针tree指向这个根节点；如果不是根结点，则将当前结点链接到双亲结点上，即当前结点的双亲指针就是队头元素，然后将当前结点入队列。接着判断flag的值，如果flag=0，表示当前结点没有左孩子，那么当前结点就是双亲的左孩子。否则，当前结点就是双亲的右孩子。用指针root指向刚刚入队的结点。继续复制数组family的下个元素。如果“ch”是@。则flag=0（因为“@”后面的第一个孩子为左孩子），同时判断“@”是否是第一次出现，如果是第一次，则令标志star=1；如果不是第一次出现。则出队列，root指向队头元素（实际上root总是指向双亲结点）。继续复制family的下一个元素。知道遇到“#”结束。函数返回指针tree。/*建立家族关系树*/TriTree*TriTreeCreate(){TriTree*t,*x=NULL,*tree,*root=NULL;LinkQueue*q=LQueueCreateEmpty();/*建立一个空的队列，存储指向树的指针*/inti=0,flag=0,start=0;DataTypestr[MAXNUM];/*存放family数组中信息*/strcpy(str,family[i]);/*复制*/i++;/*family数组下标后移*/while(str[0]!='#')/*没遇到结束标志继续循环*/{while(str[0]!='@')/*没遇到兄弟输入结束标志继续*/{if(root==NULL)/*空树*/{root=(TriTree*)malloc(sizeof(TriTree));/*申请空间*/strcpy(root-data,str);家族关系查询系统9root-parent=NULL;root-lchild=NULL;root-rchild=NULL;LQueueEnQueue(q,root);/*将root存入队列*/tree=root;}else/*不为空树*/{t=(TriTree*)malloc(sizeof(TriTree));/*申请空间*/strcpy(t-data,str);t-lchild=NULL;t-rchild=NULL;t-parent=LQueueGetFront(q);/*当前结点的双亲为队头元素*/LQueueEnQueue(q,t);/*入队*/if(!flag)/*flag为，当前结点没有左孩子*/root-lchild=t;else/*flag为，当前结点已有左孩子*/root-rchild=t;root=t;/*root指向新的结点t*/}flag=1;/*标记当前结点已有左孩子*/strcpy(str,family[i]);i++;}if(start!=0)/*标记不是第一次出现“@”*/{LQueueDeQueue(q,x);/*出队*/if(q-front!=NULL)root=LQueueGetFront(q);/*root为队头元素*/}start=1;/*标记已出现过“@”*/flag=0;/*“@”后面的结点一定为左孩子*/strcpy(str,family[i]);家族关系查询系统10i++;}returntree;/*返回树*/}2.3打开一个家族关系首先输入家族关系名，以家族名为文件名打开文件，如果家族关系不存在，返回空；如果存在，文件打开，读取文件。将文件的每行信息依次存储在数组f