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

家族关系查询系统

}

}

family[i][j]='\\0'; /* 字符串结束标志*/ i++; /* family数组行下标后移*/ j=0; /* family数组列下标归零*/ } ch=fgetc(fp); /* 继续读取文件信息*/ }

fclose(fp); /* 关闭文件*/

t=TriTreeCreate(family); /* 调用函数建立三叉链表*/ printf(\家族关系已成功打开！\\n\); return t;

2.4在家族关系中查找一个成员是否存在

用递归算法实现。如果树空，返回NULL。如果根节点就是要查找的成员，返回根节点；否则，递归查找它的左右子树。

/* 查找一个成员是否存在*/

TriTree *Search(TriTree *t,DataType str[]) {

TriTree *temp;

if(t==NULL) /* 如果树空则返回NULL */ return NULL;

else if(strcmp(t->data,str)==0) /* 如果找到返回该成员指针*/ return t;

else /* 如果没找到遍历左右子树进行查找*/ { temp=Search(t->lchild,str); /* 递归查找*/ if(temp) /* 结点不空则查找*/ return(Search(t->lchild,str)); else return(Search(t->rchild,str)); } }

2.5 向家族中添加一个新成员

11

家族关系查询系统

基本思想：添加的新成员要根据其双亲确定其在家族中的位置。首先判断该双亲是否在此家族关系中，若存在则查找其双亲，将新结点插入其双亲的最后一个孩子之后；若没有孩子，则直接作为左孩子插入。以写入的方式打开文件，如果成功打开，则更新family数组中的信息，并查找新成员的双亲所在位置和其对应的“@”个数，如果“@”个数小于双亲位置，则添加“@”实质相等，新成员不插入到最后“@”之前。最后将family数组中信息写入文件保存，关闭文件。

/* 添加一个新成员*/ void Append(TriTree *t) {

int i=0,j,parpos=1,curpos,num,end=0,count=-1;

DataType chi[MAXNUM],par[MAXNUM];/* 存储输入的孩子和其双亲结点*/

TriTree *tpar,*temp; FILE *fp;

printf(\请输入要添加的成员和其父亲，以回车分隔！\\n. \); gets(chi);

printf(\); /* 以点提示符提示继续输入*/ gets(par);

tpar=Search(t,par); /* 查找双亲结点是否存在*/ if(!tpar) printf(\该成员不存在！\\n\);

else /* 存在则添加其孩子*/ { temp=(TriTree *)malloc(sizeof(TriTree));/* 申请空间*/ temp->parent=tpar; strcpy(temp->data,chi); temp->lchild=NULL; /* 新结点左右孩子置空*/ temp->rchild=NULL; if(tpar->lchild) /* 成员存在左孩子*/ { tpar=tpar->lchild; /* 遍历当前成员左孩子的右子树*/ while(tpar->rchild) /* 当前结点右孩子存在*/ tpar=tpar->rchild; /* 继续遍历右孩子*/ tpar->rchild=temp; /* 将新结点添

12

家族关系查询系统

加到所有孩子之后*/ } else /* 没有孩子则直接添加*/ tpar->lchild=temp; fp=fopen(fname,\); /* 以写入方式打开文件*/ if(fp) { while(strcmp(par,family[i])!=0&&family[i][0]!='#') { if(family[i][0]!='@') /* 查找双亲在数组中位置*/ parpos++; /* parpos计数*/ i++; /* family数组行下标后移*/ } i=0; /* family数组行下标归*/ while(family[i][0]!='#') { if(family[i][0]=='@') /* 查找“@”的个数，第一个不计*/ count++; /* count累加个数*/ if(count==parpos) /* 说明此“@”与其前一个“@”之前为par的孩子*/ curpos=i; /* curpos计当前位置*/ i++; /* family数组行下标后移*/ } if(count

13

家族关系查询系统

{ for(j=i;j>=curpos;j--) /* 当前位置到数组最后的全部信息后移一行*/ strcpy(family[j+1],family[j]); strcpy(family[curpos],chi); /* 将新结点存储到“@”的前一行*/ } if(end==1) /* 若end为，则数组末尾下标后移num位*/ i=i+num; for(j=0;j<=i+1;j++) /* 将数组所有信息写入文件*/ { fputs(family[j],fp); fputc('\\n',fp); /* 一个信息存一行*/ } fclose(fp); /* 关闭文件*/ printf(\添加新成员成功！\\n\); } else printf(\添加新成员失败！\\n\); } }

2.6 家族成员关系的相关查询

2.6.1 查找一个家族的鼻祖

判断输入的姓名是否在该家族中存在，如果存在，则返回该家族的根节点信息。

/* 查找一个家族的祖先*/

void Ancesstor(TriTree *t) /* 返回树的根结点信息*/ {

printf(\该家族的祖先为%s\\n\,t->data); }

14

家族关系查询系统

2.6.2 查找一个成员的所有祖先路径

查找一个成员的所有祖先路径，需要从它的双亲一直向上查找到根结点。

基本思想：对与结点t，先判断它是否是根结点（根节点的双亲是NULL），如果是根结点，直接输出它本身；如果不是，查找它的双亲指针指向的结点，将双亲信息输出。继续查找，直到找到根结点。

/* 查找一个成员的所有祖先*/ void AncesstorPath(TriTree *t) {

if(t->parent==NULL) /* 若该成员为祖先，则直接输出*/ printf(\无祖先！\\n\,t->data);

else /* 否则继续查找祖先*/ { printf(\所有祖先路径：%s\,t->data,t->data); while(t->parent!=NULL)/* 若当前成员的双亲不是祖先，则继续查找*/ { printf(\,t->parent->data); /* 访问当前成员的双亲*/ t=t->parent; /* 继续循环查找*/ } printf(\); } }

2.6.3 查找一个成员的双亲

基本思想：先判断结点t是否是根结点，过不是根结点，

直接输出该结点双亲指针的结点信息；若是根结点，输出提示信息，结点无双亲。

15

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库数据结构课程设计（家族关系查询系统）(3)在线全文阅读。