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

家谱管理系统

姓名：田鑫磊 学号：1514020421

(1)功能部分：

本程序共实现了6个功能分别为： 1. 读出家谱并显示

2. 确定指定成员在家族中的辈份 3. 输出指定辈的所有成员

4. 在家谱中添加新成员，并追加到文件中 5. 输出指定家庭的所有成员 6. 退出本系统

(2)各功能的算法思想：

1. 读出家谱并显示

存储结构用栈，按照先显示双亲，然后显示其所有孩子的顺序显示所有的家庭成员。

2. 确定指定成员在家族中的辈份

用求成员所在的二叉树中的层数（按层遍历二叉树）来确定，这里采用的是递归算法

3. 输出指定辈的所有成员

此处定义了一个新的结构体类型（增加存储节点所在的层数），定义如下： struct

{ BTNode *q;

int loc; //存结点所在的层数 }qu[10];

并用一个队列来比较显示同辈分的所有成员。

4. 在家谱中添加新成员，并追加到文件中

首先，输入一个新成员的名字； 然后，输入其双亲；

之后，再添加到整个存储二叉链表中。 然后，再将新的存储结构写回到文件中。 二叉链表的结点类型为：typedef struct node {

ElemType data[10]; //存放成员的名字 struct node *child; //其孩子指针 struct node *brother; //其兄弟指针 }BTNode;

5. 输出指定家庭的所有成员

首先，设一个栈，并设一个标记位，先置1；

然后，找到输入的要待显示的成员，将标记位置0；

再次，显示其孩子和兄弟，依次下去直到显示完其所有的亲戚。

6. 退出本系统

通过一个输入字符q来控制，每完成一个功能，系统提示是否要继续操作：

当q为“Y”或者“y”时，显示菜单，程序继续执行； 当 q为其他字符时，程序执行结束，退出本系统。

三、详细设计：

通过一个do-while语句来控制各个模块的选择和实现。 1. 读出家谱并显示

void display(BTNode *b) {

BTNode *q[10]; //定义一个栈 int front,rear; int k; BTNode *p; p=b;k=0;

front=-1;rear=0;

q[rear]=p; //头结点先入栈 while(frontprintf(\"%s\头结点出栈，并显示 printf(\"(\"); disbr(p->child); printf(\")\\n\");

if(p->child!=NULL) //显示其孩子 {

rear++;q[rear]=p->child; }

if(p->brother!=NULL) //显示其兄弟 {

rear++;q[rear]=p->brother; } } }

2. 确定指定成员在家族中的辈分

int generation(BTNode *b,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 //定义一个新的结点类型，在孩子兄弟存储结构的基础上添加一个数据域存其所在层数

{

int loc; }qu[10]; BTNode *q;

int front,rear; BTNode *p; p=t;k=0;

front=-1;rear=0; qu[rear].q=p; qu[rear].loc=1;

if( qu[rear].loc==m) //找到m辈的即输出 printf(\"%c\

while(frontchild!=NULL)

{

rear++;qu[rear].q=p->child; qu[rear].loc=qu[front].loc+1; if(m== qu[rear].loc)

printf(\"%s \ }

if(p->brother!=NULL)

{

rear++;qu[rear].q=p->brother;

qu[rear].loc=qu[front].loc; if( qu[rear].loc==m)

printf(\"%s \ } }

}

4.在家谱中添加新成员，并追加到文件中

void add(BTNode *&b,ElemType y[],ElemType x[]) {

char filename[20]=\" \"; FILE *fp; BTNode *p,*q; int i;

p=FindNode(b,y);

q=(BTNode *)malloc(sizeof(BTNode)); else

{ p=p->child; }

printf(\"向文件中读入新家谱\\n\"); scanf(\"%s\

if((fp=fopen(filename,\"w\"))==NULL) else

fclose (fp); }

while(p->brother!=NULL)

p=p->brother ; for(i=0;x[i]!='\\0';i++)

q->data[i]=x[i]; q->data[i]='\\0';

q->child=q->brother=NULL;

p->child=q;

if(p->child ==NULL)

p->brother=q;

display(b);

printf(\"\\n input a filename:\");

{puts(\"\\n can't open the file.\");exit(0);} DispBTNode(b,fp);

void DispBTNode(BTNode *b,FILE *fp) {

char a[10]; int i=0; if(b!=NULL) {

while(b->data[i]!='\\0')

{ }

a[i]='\\0';

if(b->child!=NULL || b->brother!=NULL) {

a[i]=b->data[i]; i++;

fputs(a,fp); //写入文件

} }

fputs(s,fp);

DispBTNode(b->child,fp); //递归写入其孩子 if (b->brother!=NULL) {

fputs(p,fp); }

fputs(t,fp);

DispBTNode(b->brother,fp); //递归写入其兄弟

}

5.输出指定家庭的所有成员

void dispfamily(BTNode *b,ElemType x[]) { BTNode *p;

BTNode *q[MaxSize]; int top=-1,tap=1; if(b!=NULL) { top++; q[top]=b; while(top>-1) {

p=q[top]; top--;

if(strcmp(p->data,x)==0) //查找此人 {

top=-1; tap=0; }

if(p->child!=NULL) { top++;

q[top]=p->child; if(tap==0)

{

display(p->child); //显示其孩子 return ;

} }

if(p->brother!=NULL) { top++;

q[top]=p->brother; if(tap==0) {

display(p->brother); //显示其兄弟 return ; } } }

} }

6.退出本系统

此处通过一个输入字符q来控制，当q为“Y”或者“y”时，显示菜单，程序继续执行，当 q为其他字符时，程序执行结束，退出本系统。此时q=‘N’。 四：调试分析

1．首先，将已有家谱存储文件写在一个txt文档里，内容为：

输出结果为：

2．调试时遇到的问题：

（1）当选择功能3（添加新成员），添加完成员后，写回文件时出现了错误，原本添加的为其中一个结点的孩子，结果写回文件时却成了该结点的孙子，也就是本是要添加为此结点的孩子的兄弟，结果却成了其孩子的孩子。最后经过单步跟踪发现写入文件的函数编写错误，缺少判断条

件，经过修改后，此问题得到了解决。

（2）当选择功能0（显示此家谱），没有按照事先存储在txt中的文件显示，通过认真检查程序中显示成员的函数（按层遍历）、不断调试，发现并不是该显示函数的错误，因为在功能4（输出指定家庭的所有成员）中，也是通过调用该函数实现输出功能，于是，检查txt文件中事先存储的家谱成员，发现是由于“（”与“）”没有匹配好，导致没有按照预期想法创建二叉树造成的错误，通过修改txt文件，使得错误得以解决。

五、课程设计总结

通过本次课程设计，我觉得自己最大的收获就是：

由于对二叉链表的存储比较感兴趣，我选做的是家谱，开始觉得无从

下手，但是经过仔细分析后，渐渐找到一点思路（首先创建，然后分别实现各个功能，最后利用菜单实现选择功能并输出结果）。

本次编写家谱程序的过程中，我体验到了编程的酸甜苦辣：开始，由

于即将运用所学知识设计实际问题而激动兴奋；后来编写程序过程中，在想不出算法如何实现或者追求空间、时间上高效率的算法时会比较纠结；以及遇到BUG时，追踪数据的痛苦；当然，还有解决问题后的激动与自豪。所有这些都增强了我对编程的热爱、提高了我对计算机专业的兴趣。