数据结构实例应用(3)

strcat(fname,\ fp=fopen(fname,\ /* 以读取方式打开文件 */ if(fp) /* 文件已存在 */ { fclose(fp); printf(\的家族关系已存在！重新建立请按“Y”,直接打开请按“N”\\n\ ch=getchar(); getchar(); /* 接收回车 */ if(ch=='N'||ch=='n') { t=Open(familyname);/* 直接打开 */ return t; } } if(!fp||ch=='Y'||ch=='y') /* 重新建立，执行以下操作 */ { fp=fopen(fname,\ /* 以写入方式打开文件，不存在则新建 */ 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\ return t; /* 返回树 */ } }

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

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)); } }

/* 添加一个新成员 */ 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; /* 将新结点添加到所有孩子之后 */ } 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数组行下标归0 */ while(family[i][0]!='#') { if(family[i][0]=='@') /* 查找“@”的个数，第一个不计 */ count++; /* count累加个数 */ if(count==parpos) /* 说明此“@”与其前一个“@”之前为par的孩子 */ curpos=i; /* curpos计当前位置 */ i++; /* family数组行下标后移 */ } if(count=curpos;j--) /* 当前位置到数组最后的全部信息后移一行 */ strcpy(family[j+1],family[j]); strcpy(family[curpos],chi); /* 将新结点存储到“@”的前一行 */ } if(end==1) /* 若end为1，则数组末尾下标后移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\ } }

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

void Ancesstor(TriTree *t) /* 返回树的根结点信息 */ { printf(\该家族的祖先为 %s\\n\}

/* 查找一个成员的所有祖先 */ void AncesstorPath(TriTree *t) { if(t->parent==NULL) /* 若该成员为祖先，则直接输出 */ printf(\无祖先！\\n\ else /* 否则继续查找祖先 */ { printf(\所有祖先路径：%s\ while(t->parent!=NULL)/* 若当前成员的双亲不是祖先，则继续查找 */ { printf(\/* 访问当前成员的双亲 */ t=t->parent; /* 继续循环查找 */ } printf(\ } }

/* 查找一个成员的双亲 */ void Parent(TriTree *t) { if(t->parent!=NULL) /* 若该成员为祖先，则无双亲 */ printf(\的双亲为 %s\\n\ else printf(\无双亲！\\n\}

/* 确定一个成员是第几代 */ void Generation(TriTree *t) { int count=1; /* 计数 */

DataType str[MAXNUM]; strcpy(str,t->data); /* 存储当前信息 */ while(t->parent!=NULL)/* 查找其双亲 */ { count++; /* 累加计数 */ t=t->parent; } printf(\是第 %d 代！\\n\}

/* 查找一个成员的兄弟 */

void Brothers(TriTree *t,DataType str[]) /* 查找兄弟 */ { if(t->parent!=NULL) /* 若该结点是祖先，则无兄弟 */ { t=t->parent; /* 该结点的兄弟即为其双亲除该成员以外的所有孩子 */ if(t->lchild&&t->lchild->rchild) /* 当前结点的左孩子及其右孩子都存在 */ { printf(\的所有兄弟有：\ t=t->lchild; while(t) /* 遍历当前成员左孩子的右子树 */ { if(strcmp(t->data,str)!=0) /* 遍历右子树，选择输出 */ printf(\ \访问当前结点 */ t=t->rchild; } printf(\ } else printf(\无兄弟！\\n\ } else printf(\无兄弟！\\n\}

/* 查找一个成员的堂兄弟 */ void Consin(TriTree *t) { int flag=0; TriTree *ch=t; TriTree *temp; if(t->parent&&t->parent->parent)/* 当前结点的双亲及其双亲都存在 */ {