C语言二叉树家谱管理系统南京廖华答案网

C语言二叉树家谱管理系统下载本文

文章发布时间 : 2024/11/8 11:38:05星期五

摘要

本文设计了一个对数据输入，输出，储存，查找的多功能软件，本文需要保存家族的基本信息，包括姓名及它们的关系，但是由于家族信息很巨大而且关系很复杂所以采用二叉树来表示它们的关系。并且具有保存文件的功能，以便下次直接使用先前存入的信息。家谱的功能是查询家族每个人的信息，并且输出它们的信息，还要具有查询输出功能。

本文采用二叉树来存取家族的基本信息，头结点作为父亲节点，他的左孩子为他的妻子，妻子结点的右孩子为他的孩子，依次存储每个家庭的信息。可以查找每个父亲的孩子和每个人的所有祖先。

关键词：二叉树家谱结点

1 系统功能概述...................................................... 1

1.1 系统功能 ................................................... 1 图2 成员二叉树功能模块图........................................ 4 1.2 总体功能模块 ............................................... 4 2 系统各功能模块的详细设计.......................................... 4

2.1功能选择..................................................... 4 2.2信息输入..................................................... 6 2.3信息输出..................................................... 7 2.4信息存盘..................................................... 7 2.5信息清盘..................................................... 8 2.6信息查询..................................................... 8 2.7源程序...................................................... 10 3设计结果与分析 ................................................... 16

3.1菜单函数功能测试............................................ 16 4.2输入功能函数测试............................................ 16 3.3输出功能函数测试............................................ 17 3.4清盘功能函数测试............................................ 17 3.5存盘功能函数测试............................................ 17 3.6查询功能函数测试............................................ 18 总结............................................................... 19 参考文献........................................................... 20

1 系统功能概述

1.1 系统功能

实现的方法是先定义一个二叉树，该二叉树上的每个结点由三个元素组成：姓名、指向它左孩子的指针、以及指向它右孩子的指针构成。该家谱管理系统将信息用文件的方法进行存储管理，再从文件中将成员信息以递归的方法创建二叉树。该输入成员信息的方法是将父亲结点存上父亲的信息，然后父亲结点的左孩子存上母亲的信息，母亲结点的右孩子存上孩子的信息。 (1)定义结构体

结构体为表示一个对象的不同属性提供了连贯一致的方法，结构体类型的说明从关键词struct开始，成员可以由各种数据类型混合构成，成员甚至还可以是数组或者其他类型的结构，但是，结构体中不能包含自身定义类型的成员。本文定义了两个结构体，分别是家族成员和二叉树结点的结构体。代码如下： typedef struct fnode

{ char father[NAMEWIDTH]; char wife[NAMEWIDTH];

char son[NAMEWIDTH];

}FamType; typedef struct tnode {

char name[NAMEWIDTH]; struct tnode *lchild,*rchild;

}BTree;

(2) 二叉树的建立

二叉树的结点有三个域，数据域和两个指针域，数据域用来存放数据，两个指针域分别存放指向该结点左右孩子的指针。并且还有个root结点，称二叉树的根节点。代码如下：

BTree *CreatBTree(char *root,FamType fam[],int n)

{ }

(3)家族成员信息的输入

依次输入一个家庭的父亲、母亲和孩子的姓名。并将它们保存在相应的文件里。

(4)家族成员信息的输出

依次输出每个家庭的父亲、母亲和孩子的姓名。 (5)查找某人的儿子

首先输入父亲的姓名，在二叉树中查找是否有此人，如果没有就输出不存在这样的父亲。如果有就先查看它的左孩子是否存在，不存在就输出这个父亲没有

int i=0,j; BTree *bt,*p;

bt=(BTree *)malloc(sizeof(BTree)); strcpy(bt->name,root); bt->lchild=bt->rchild=NULL;

while(i

i++;

if(i

p=(BTree *)malloc(sizeof(BTree)); p->lchild=p->rchild=NULL; strcpy(p->name,fam[i].wife); bt->lchild=p; for(j=0;j

if(strcmp(fam[j].father,root)==0) { }

p->rchild=CreatBTree(fam[j].son,fam,n); p=p->rchild;

妻子，如果存在就查找左孩子的右孩子，没有右孩子就输出这个父亲没有孩子，存在就输出右孩子的姓名，即为查找到的儿子。 (6)查找某人的祖先

采用后序非递归遍历方法输入从根结点到*s结点的路径，首先输入一个成员的姓名，用一个栈存入查找的路径，当找到时栈中的元素即为它的所有祖先。

该家谱管理系统将各个家庭的信息以文件的形式存储，具体步骤如下图：

文件

图1 文件存储功能模块图

保存

输入父亲、母亲和儿子的姓名

输入

该家谱管理系统还将各个成员的信息以及成员之间的关系存储在二叉树上，具体存储方式如下图：

儿子1

母亲

父亲

儿子2

图2 成员二叉树功能模块图

1.2 总体功能模块

家谱管理系统家谱的建立家谱的插入家谱的删除图3 总体功能模块图

家谱的查找家谱的显示 2 系统各功能模块的详细设计

2.1功能选择

功能选择模块函数，主要提供1：文件 2：家谱两个功能模块让用户选择。输入数字1的时候，出现界面1：输入 2：输出 9：清盘 0：存盘返回。返回后输入数字2，出现界面1：找某人的所有儿子 2：找某人所有祖先。用户根据自己的需求选择 void main()

{

BTree *bt;

FamType fam[MaxSize]; int n,sel,sell; ReadFile(fam,n); do {

printf(\文件操作2.家谱操作0.退出请选择：\scanf(\switch(sel) {

case 1:

do {

printf(\：输入2：输出9：全清0：存盘返回请选择：\scanf(\switch(sell) {

case 9:DelAll(fam,n);

break;

case 1:InputFam(fam,n);

break;

case 2:OutputFile(fam,n);

break;

case 0:SaveFile(fam,n); }

break;

}while (sell!=0); break; case 2:

bt=CreatBTree(\

}

do {

printf(\找某人所有儿子 2.找某人所有祖先 0:返回请选择：\scanf(\switch(sell) { case 1:

FindSon(bt);

break;

case 2:

printf(\ }

break;

}while(sell!=0); break;

}while(sel!=0);

2.2信息输入

信息输入模块函数，出现界面请输入父亲、母亲和儿子的姓名让用户输入信息。代码如下：

void InputFam(FamType fam[],int &n) { }

printf(\输入父亲、母亲和儿子姓名：\

scanf(\n++;

2.3信息输出

信息输出模块函数，自动输出数据的信息及它们之间的家谱关系。按顺序输出父亲，母亲，儿子。代码如下： void OutputFile(FamType fam[],int n) {

int i; if(n<0) { }

for(i=0;i

printf(\printf(\没有任何记录\\n\return;

}

2.4信息存盘

信息存盘模块函数，将用户输入的信息存盘，下次要用时自动调用。代码如下：

void SaveFile(FamType fam[],int n) {

int i; FILE *fp;

if((fp=fopen(\{ }

for(i=0;i

fwrite(&fam[i],sizeof(FamType),1,fp); printf(\数据家谱文件不能打开\\n\return;

}

fclose(fp);

2.5信息清盘

信息清盘模块函数，将用户输入的信息全部清盘。代码如下： void DelAll(FamType fam[],int &n) { }

FILE *fp;

if((fp=fopen(\{ } n=0; fclose(fp);

printf(\不能打开家谱文件\\n\return;

2.6信息查询

信息查询模块函数，查询用户输入数据的信息及家谱关系。具有的功能是1：找某人所有儿子2：找某人所有祖先。用户根据需要操作。

找某人所有儿子的代码： void FindSon(BTree *bt) {

char xm[NAMEWIDTH]; BTree *p;

printf(\父亲姓名：\scanf(\p=FindNode(bt,xm); if(p==NULL)

printf(\不存在%s的父亲！\\n\

}

else { }

找某人所有祖先的代码：

p=p->lchild; if(p==NULL)

printf(\没有妻子\\n\

else { }

p=p->rchild; if(p==NULL)

printf(\没有儿子！\\n\else { }

printf(\的儿子：\while(p!=NULL) { }

printf(\

printf(\p=p->rchild;

void Ancestor(BTree *bt) {

BTree *p;

char xm[NAMEWIDTH]; printf(\输入姓名:\scanf(\p=FindNode(bt,xm);

}

if(p!=NULL)

Path(bt,p);

else

printf(\不存在%s\\n\

void DelAll(FamType fam[],int &n) { }

FILE *fp;

if((fp=fopen(\{ } n=0; fclose(fp);

printf(\不能打开家谱文件\\n\return;

2.7源程序

#include #include #include #define MaxWidth 40 #define MaxSize 30

#define NAMEWIDTH 10 typedef struct fnode

{ char father[NAMEWIDTH]; char wife[NAMEWIDTH]; char son[NAMEWIDTH]; }FamType;

typedef struct tnode {

char name[NAMEWIDTH]; struct tnode *lchild,*rchild; }BTree;

BTree *CreatBTree(char *root,FamType fam[],int n) {

int i=0,j;

BTree *bt,*p;

bt=(BTree *)malloc(sizeof(BTree)); strcpy(bt->name,root);

bt->lchild=bt->rchild=NULL;

while(ilchild=p->rchild=NULL; strcpy(p->name,fam[i].wife); bt->lchild=p; for(j=0;jrchild=CreatBTree(fam[j].son,fam,n); p=p->rchild; } }

return(bt); }

BTree *FindNode(BTree *bt,char xm[]) {

BTree *p=bt; if(p==NULL)

return(NULL); else { if(strcmp(p->name,xm)==0) return(p); else { bt=FindNode(p->lchild,xm); if(bt!=NULL) return(bt); else return(FindNode(p->rchild,xm)); } } }

void FindSon(BTree *bt) {

char xm[NAMEWIDTH];

BTree *p;

printf(\父亲姓名：\ scanf(\ p=FindNode(bt,xm); if(p==NULL) printf(\不存在%s的父亲！\\n\ else { p=p->lchild; if(p==NULL) printf(\没有妻子\\n\ else { p=p->rchild; if(p==NULL) printf(\没有儿子！\\n\ else { printf(\的儿子：\ while(p!=NULL) { printf(\ p=p->rchild; } printf(\ } } } }

int Path(BTree *bt,BTree *s) {

BTree *St[MaxSize]; BTree *p;

int i,flag,top= -1; do { while(bt) { top++; St[top]=bt; bt=bt->lchild; } p=NULL; flag=1;

while(top!=-1 && flag) { bt=St[top]; if(bt->rchild==p) { if(bt==s) { printf(\所有祖先：\ for(i=0;irchild; flag=0; } }

}while(top!=-1); return 0; }

void Ancestor(BTree *bt) {

BTree *p;

char xm[NAMEWIDTH]; printf(\输入姓名:\ scanf(\ p=FindNode(bt,xm); if(p!=NULL) Path(bt,p); else printf(\不存在%s\\n\}

void DelAll(FamType fam[],int &n) {

FILE *fp;

if((fp=fopen(\

{ printf(\不能打开家谱文件\\n\ return; } n=0;

fclose(fp); }

void ReadFile(FamType fam[],int &n) {

FILE *fp; long length; int i;

if((fp=fopen(\ { n=0; return; }

fseek(fp,0,2); length=ftell(fp); rewind(fp);

n=length/sizeof(FamType); for(i=0;i

fread(&fam[i],sizeof(FamType),1,fp); fclose(fp); }

void SaveFile(FamType fam[],int n) {

int i;

FILE *fp;

if((fp=fopen(\ { printf(\数据家谱文件不能打开\\n\ return; }

for(i=0;i

void InputFam(FamType fam[],int &n) {

printf(\输入父亲、母亲和儿子姓名：\

scanf(\ n++; }

void OutputFile(FamType fam[],int n) {

int i; if(n<0) { printf(\没有任何记录\\n\ return; }

for(i=0;i

void main() {

BTree *bt;

FamType fam[MaxSize]; int n,sel,sell; ReadFile(fam,n); do { printf(\文件操作2.家谱操作0.退出请选择：\ scanf(\ switch(sel) {

case 1: do { printf(\：输入2：输出9：全清0：存盘返回请选择：\ scanf(\ switch(sell) { case 9:DelAll(fam,n); break; case 1:InputFam(fam,n); break; case 2:OutputFile(fam,n); break; case 0:SaveFile(fam,n); break; } }while (sell!=0); break; case 2: bt=CreatBTree(\ do

}

{ printf(\找某人所有儿子 2.找某人所有祖先 0:返回请选择：\ scanf(\ switch(sell) { case 1: FindSon(bt); break; case 2: printf(\ break; } }while(sell!=0); break; }

}while(sel!=0);

3设计结果与分析

3.1菜单函数功能测试

系统运行后就会自动显示如图3-1的主菜单，选项包括：1、文件，2、家谱，0、退出，。当用户选择相应的代号就进入相应的功能模块。

图3-1 主菜单函数功能检测

4.2输入功能函数测试

系统运行后就会自动显示如图3-2的输入功能模块，界面出现1：输入>>输入父亲、母亲和儿子的姓名，用户输入信息。

图3-2输入功能函数测试

3.3输出功能函数测试

系统运行后就会自动显示如图3-3的输出功能模块，界面出现2：输出。用户输入数字2后系统自动输出数据信息。

图3-3输出功能函数测试

3.4清盘功能函数测试

系统运行后就会自动显示如图3-4的清盘功能模块，界面出现9：全清。用户输入数9后自动系统清除所有的数据并返回。

图3-4清盘功能函数测试

3.5存盘功能函数测试

系统运行后就会自动显示如图3-5的存盘功能模块，界面出现0：存盘返回。

用户输入数0后系统自动保存所有的数据并返回。

图3-5存盘功能函数测试

3.6查询功能函数测试

系统运行后就会自动显示如图3-6的查询功能模块，界面出现1：找某人的

所有儿子

图3-6查询某人儿子功能函数测试

系统运行后就会自动显示如图

3-7的查询功能模块，界面出现2：找某人的

所有祖先

图3-7查询某人祖先功能函数测试

总结

程序的关键是掌握二叉树的相关操作、二叉树的创建和运用、结点的查找、祖宗结点的查找等。在编程的过程中，出现了很多问题，如二叉树无法建立、程序内存读取不了、忘了添加头文件等错误。在单步调试和添加提示输出的情况下修改程序运行正确。

查找首先要判断该结点是否为空，再与查找到的结点比较，否则会内存无法读取，强行结束程序。

祖宗结点的查找一直是个大问题，在参考书的帮助下想到了后续遍历，是可以从孩子往上找到。

家谱的功能是查询家族每个人的信息，并且输出它们的信息，还要具有查询输出功能。这样复习了一下查询、插入、删除函数的应用。并复习了上学期c语言的文件储存及调用功能，子函数和递归调用功能，熟练运用这些函数。

参考文献

[1]王敬华,林萍，陈静. C语言程序设计[M]. 北京：清华大学出版社，2005.10： [2] 赵文静. 数据结构与算法[M].北京：科学出版社,2005.8:41-57

[3] 海,童伟.C语言精彩编程百例[M]. 北京：水利水电出版社, 2005.7：228-234 [4] 严蔚敏,吴伟民.数据结构(C语言版)[M]. 北京:清华大学出版社, 39-43 [5]朱若愚 . 张秋璞数据结构（C语言版）[M]. 北京：电子工业出版社, 2004.9 [6]徐孝凯，魏荣《数据结构》,机械工业出版社，1996年 [7]徐孝凯《数据结构简明教程》，清华大学出版社，1995年 [8] 陈文博，朱青《数据结构与算法》，机械工业出版社，1996年

Word文档下载：C语言二叉树家谱管理系统.doc

搜索更多:C语言二叉树家谱管理系统