数据结构家谱课程设计报告

1、精选文档 家谱管理系统 姓名：田鑫磊学号：1514020421(1)功能部分：本程序共实现了6个功能分别为：1. 读出家谱并显示 2. 确定指定成员在家族中的辈份3. 输出指定辈的所有成员4. 在家谱中添加新成员，并追加到文件中5. 输出指定家庭的所有成员6. 退出本系统(2)各功能的算法思想：1. 读出家谱并显示 存储结构用栈，按照先显示双亲，然后显示其所有孩子的顺序显示所有的家庭成员。2. 确定指定成员在家族中的辈份用求成员所在的二叉树中的层数（按层遍历二叉树）来确定，这里采用的是递归算法3. 输出指定辈的所有成员此处定义了一个新的结构体类型（增加存储节点所在的层数），定义如下： stru

2、ct BTNode *q; int loc; /存结点所在的层数qu10; 并用一个队列来比较显示同辈分的所有成员。4. 在家谱中添加新成员，并追加到文件中首先，输入一个新成员的名字；然后，输入其双亲；之后，再添加到整个存储二叉链表中。然后，再将新的存储结构写回到文件中。二叉链表的结点类型为：typedef struct node ElemType data10; /存放成员的名字 struct node *child; /其孩子指针 struct node *brother; /其兄弟指针 BTNode;5. 输出指定家庭的所有成员首先，设一个栈，并设一个标记位，先置1；然后，找到输入的要待

3、显示的成员，将标记位置0；再次，显示其孩子和兄弟，依次下去直到显示完其所有的亲戚。6. 退出本系统通过一个输入字符q来控制，每完成一个功能，系统提示是否要继续操作：当q为“Y”或者“y”时，显示菜单，程序继续执行；当q为其他字符时，程序执行结束，退出本系统。三、详细设计：通过一个do-while语句来控制各个模块的选择和实现。1. 读出家谱并显示void display(BTNode *b) BTNode *q10; /定义一个栈 int front,rear; int k; BTNode *p; p=b;k=0; front=-1;rear=0; qrear=p; /头结点先入栈 while

4、(front<rear) front+; p=qfront; printf("%s",p->data ); /头结点出栈，并显示 printf("("); disbr(p->child); printf(")n"); if(p->child!=NULL) /显示其孩子 rear+;qrear=p->child; if(p->brother!=NULL) /显示其兄弟 rear+;qrear=p->brother; 2. 确定指定成员在家族中的辈分int generation(BTNode *b

5、,int h,ElemType x)/用递归的思想 int i; if(b=NULL) return(0); i=strcmp(b->data,x); /比较是否相等 if(i=0) return(h); int L=generation(b->child,h+1,x); if(L=0) L=generation(b->brother,h,x); return(L);3.输出指定辈的所有成员void layer(BTNode *t,int m) struct /定义一个新的结点类型，在孩子兄弟存储结构的基础上添加一个数据域存其所在层数 BTNode *q; int loc;q

6、u10; int front,rear; BTNode *p; p=t;k=0; front=-1;rear=0; qurear.q=p; qurear.loc=1; if( qurear.loc=m) /找到m辈的即输出 printf("%c",p->data); while(front<rear) /通过站查找所有m辈的结点并输出 front+; p=qufront.q; if(p->child!=NULL) rear+;qurear.q=p->child; qurear.loc=qufront.loc+1; if(m= qurear.loc)

7、printf("%s ",p->child->data); if(p->brother!=NULL) rear+;qurear.q=p->brother; qurear.loc=qufront.loc; if( qurear.loc=m) printf("%s ",p->brother->data); 4.在家谱中添加新成员，并追加到文件中void add(BTNode *&b,ElemType y,ElemType x)char filename20=" "FILE *fp;BTNode

8、*p,*q;int i;p=FindNode(b,y);q=(BTNode *)malloc(sizeof(BTNode);for(i=0;xi!='0'i+)q->datai=xi;q->datai='0'q->child=q->brother=NULL;if(p->child =NULL)p->child=q;else p=p->child;while(p->brother!=NULL)p=p->brother ; p->brother=q; display(b);printf("向文件中

9、读入新家谱n"); printf("n input a filename:"); scanf("%s",&filename);if(fp=fopen(filename,"w")=NULL) puts("n can't open the file.");exit(0);else DispBTNode(b,fp);fclose (fp);void DispBTNode(BTNode *b,FILE *fp)char a10;int i=0;if(b!=NULL) while(b->dat

10、ai!='0') ai=b->datai; i+; ai='0' fputs(a,fp); /写入文件if(b->child!=NULL | b->brother!=NULL)fputs(s,fp);DispBTNode(b->child,fp); /递归写入其孩子if (b->brother!=NULL) fputs(p,fp); DispBTNode(b->brother,fp); /递归写入其兄弟fputs(t,fp); 5.输出指定家庭的所有成员void dispfamily(BTNode *b,ElemType x)

11、 BTNode *p;BTNode *qMaxSize;int top=-1,tap=1;if(b!=NULL) top+; qtop=b; while(top>-1) p=qtop; top-; if(strcmp(p->data,x)=0) /查找此人 top=-1; tap=0; if(p->child!=NULL) top+; qtop=p->child; if(tap=0) display(p->child); /显示其孩子 return ; if(p->brother!=NULL) top+; qtop=p->brother; if(tap

12、=0) display(p->brother); /显示其兄弟 return ; 6.退出本系统此处通过一个输入字符q来控制，当q为“Y”或者“y”时，显示菜单，程序继续执行，当q为其他字符时，程序执行结束，退出本系统。此时q=N。四：调试分析1首先，将已有家谱存储文件写在一个txt文档里，内容为：输出结果为：2调试时遇到的问题：（1）当选择功能3（添加新成员），添加完成员后，写回文件时出现了错误，原本添加的为其中一个结点的孩子，结果写回文件时却成了该结点的孙子，也就是本是要添加为此结点的孩子的兄弟，结果却成了其孩子的孩子。最后经过单步跟踪发现写入文件的函数编写错误，缺少判断条件，经过修改后，此问题得到了解决。（2）当选择功能0（显示此家谱），没有按照事先存储在txt中的文件显示，通过认真检查程序中显示成员的函数（按层遍历）、不断调试，发现并不是该显示函数的错误，因为在功能4（输出指定家庭的所有成员）中，也是通过调用该函数实现输出功能，于是，检查txt文件中事先存储的家谱成员，发现是由于“（”与“）”没有匹配好，导致没有按照预期想法创建二叉树造成的错误，通过修改txt文件，使得错误得以解决。五、课程设计总结 通过本次课程设计，我觉得自己最大的收获就是：由于对二叉链表的存储比较感兴趣，我选做的是家谱，开始觉得无从下手，但是经过仔细分析后