C语言二叉树家谱管理系统.doc

摘 要本文设计了一个对数据输入，输出，储存，查找的多功能软件，本文需要保存家族的基本信息，包括姓名及它们的关系，但是由于家族信息很巨大而且关系很复杂所以采用二叉树来表示它们的关系。并且具有保存文件的功能，以便下次直接使用先前存入的信息。家谱的功能是查询家族每个人的信息，并且输出它们的信息，还要具有查询输出功能。本文采用二叉树来存取家族的基本信息，头结点作为父亲节点，他的左孩子为他的妻子，妻子结点的右孩子为他的孩子，依次存储每个家庭的信息。可以查找每个父亲的孩子和每个人的所有祖先。关键词： 二叉树 家谱 结点目录1 系统功能概述11.1 系统功能1图2 成员二叉树功能模块图41.2 总体功能模块42 系统各功能模块的详细设计42.1功能选择42.2信息输入62.3信息输出72.4信息存盘72.5信息清盘82.6信息查询82.7源程序103设计结果与分析163.1菜单函数功能测试164.2输入功能函数测试163.3输出功能函数测试173.4清盘功能函数测试173.5存盘功能函数测试173.6查询功能函数测试18总结19参考文献201 系统功能概述1.1 系统功能实现的方法是先定义一个二叉树，该二叉树上的每个结点由三个元素组成：姓名、指向它左孩子的指针、以及指向它右孩子的指针构成。该家谱管理系统将信息用文件的方法进行存储管理，再从文件中将成员信息以递归的方法创建二叉树。该输入成员信息的方法是将父亲结点存上父亲的信息，然后父亲结点的左孩子存上母亲的信息，母亲结点的右孩子存上孩子的信息。(1)定义结构体结构体为表示一个对象的不同属性提供了连贯一致的方法，结构体类型的说明从关键词struct开始，成员可以由各种数据类型混合构成，成员甚至还可以是数组或者其他类型的结构，但是，结构体中不能包含自身定义类型的成员。本文定义了两个结构体，分别是家族成员和二叉树结点的结构体。代码如下：typedef struct fnode char fatherNAMEWIDTH; char wifeNAMEWIDTH;char sonNAMEWIDTH;FamType;typedef struct tnode char nameNAMEWIDTH;struct tnode *lchild,*rchild;BTree;(2) 二叉树的建立二叉树的结点有三个域，数据域和两个指针域，数据域用来存放数据，两个指针域分别存放指向该结点左右孩子的指针。并且还有个root结点，称二叉树的根节点。代码如下：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(in & strcmp(fami.father,root)!=0)i+;if(ilchild=p-rchild=NULL;strcpy(p-name,fami.wife);bt-lchild=p;for(j=0;jrchild=CreatBTree(famj.son,fam,n);p=p-rchild;return(bt);(3)家族成员信息的输入依次输入一个家庭的父亲、母亲和孩子的姓名。并将它们保存在相应的文件里。(4)家族成员信息的输出依次输出每个家庭的父亲、母亲和孩子的姓名。(5) 查找某人的儿子 首先输入父亲的姓名，在二叉树中查找是否有此人，如果没有就输出不存在这样的父亲。如果有就先查看它的左孩子是否存在，不存在就输出这个父亲没有妻子，如果存在就查找左孩子的右孩子，没有右孩子就输出这个父亲没有孩子，存在就输出右孩子的姓名，即为查找到的儿子。(6)查找某人的祖先采用后序非递归遍历方法输入从根结点到*s结点的路径，首先输入一个成员的姓名，用一个栈存入查找的路径，当找到时栈中的元素即为它的所有祖先。该家谱管理系统将各个家庭的信息以文件的形式存储，具体步骤如下图：文件输入输入父亲、母亲和儿子的姓名保存 图1 文件存储功能模块图 该家谱管理系统还将各个成员的信息以及成员之间的关系存储在二叉树上，具体存储方式如下图：父亲 母亲儿子2儿子1图2 成员二叉树功能模块图1.2 总体功能模块家谱管理系统家谱的建立家谱的插入家谱的删除家谱的查找家谱的显示图3 总体功能模块图2 系统各功能模块的详细设计2.1功能选择功能选择模块函数，主要提供1：文件 2：家谱 两个功能模块让用户选择。输入数字1的时候，出现界面1：输入 2：输出 9：清盘 0：存盘返回。返回后输入数字2，出现界面1：找某人的所有儿子 2：找某人所有祖先 。用户根据自己的需求选择void main()BTree *bt;FamType famMaxSize;int n,sel,sell;ReadFile(fam,n);doprintf(1.文件操作2.家谱操作0.退出 请选择：);scanf(%d,&sel);switch(sel) case 1:doprintf(1：输入2：输出9：全清0：存盘返回 请选择：);scanf(%d,&sell);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(f1,fam,n);doprintf(1.找某人所有儿子 2.找某人所有祖先 0:返回 请选择：);scanf(%d,&sell);switch(sell)case 1: FindSon(bt);break;case 2: printf( );Ancestor(bt);break;while(sell!=0);break;while(sel!=0);2.2信息输入信息输入模块函数，出现界面请输入父亲、母亲和儿子的姓名让用户输入信息。代码如下：void InputFam(FamType fam,int &n)printf( 输入父亲、母亲和儿子姓名：);scanf(%s%s%s,famn.father,famn.wife,famn.son);n+;2.3信息输出信息输出模块函数，自动输出数据的信息及它们之间的家谱关系。按顺序输出父亲，母亲，儿子。代码如下：void OutputFile(FamType fam,int n)int i;if(n没有任何记录n);return;for(i=0;i%10s%10s%10sn,fami.father,fami.wife,fami.son);2.4信息存盘信息存盘模块函数，将用户输入的信息存盘，下次要用时自动调用。代码如下：void SaveFile(FamType fam,int n)int i;FILE *fp;if(fp=fopen(fam.dat,wb)=NULL)printf( 数据家谱文件不能打开n);return;for(i=0;i不能打开家谱文件n);return;n=0;fclose(fp);2.6信息查询信息查询模块函数，查询用户输入数据的信息及家谱关系。具有的功能是1：找某人所有儿子2：找某人所有祖先。用户根据需要操作。找某人所有儿子的代码：void FindSon(BTree *bt)char xmNAMEWIDTH;BTree *p;printf( 父亲姓名：);scanf(%s,xm);p=FindNode(bt,xm);if(p=NULL)printf( 不存在%s的父亲！n,xm);elsep=p-lchild;if(p=NULL)printf( %s没有妻子n,xm);elsep=p-rchild;if(p=NULL) printf( %没有儿子！n,xm);elseprintf( %s的儿子：,xm);while(p!=NULL)printf(%10s,p-name);p=p-rchild;printf(n);找某人所有祖先的代码：void Ancestor(BTree *bt)BTree *p;char xmNAMEWIDTH;printf( 输入姓名:);scanf(%s,xm);p=FindNode(bt,xm);if(p!=NULL)Path(bt,p);elseprintf( 不存在%sn,xm);void DelAll(FamType fam,int &n)FILE *fp;if(fp=fopen(fam.dat,wb)=NULL)printf( 不能打开家谱文件n);return;n=0;fclose(fp);2.7源程序#include #include #include #define MaxWidth 40#define MaxSize 30#define NAMEWIDTH 10typedef struct fnode char fatherNAMEWIDTH; char wifeNAMEWIDTH;char sonNAMEWIDTH;FamType;typedef struct tnode char nameNAMEWIDTH;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(in & strcmp(fami.father,root)!=0)i+;if(ilchild=p-rchild=NULL;strcpy(p-name,fami.wife);bt-lchild=p;for(j=0;jrchild=CreatBTree(famj.son,fam,n);p=p-rchild;return(bt);BTree *FindNode(BTree *bt,char xm)BTree *p=bt;if(p=NULL) return(NULL);elseif(strcmp(p-name,xm)=0)return(p);elsebt=FindNode(p-lchild,xm);if(bt!=NULL)return(bt);elsereturn(FindNode(p-rchild,xm);void FindSon(BTree *bt)char xmNAMEWIDTH;BTree *p;printf( 父亲姓名：);scanf(%s,xm);p=FindNode(bt,xm);if(p=NULL)printf( 不存在%s的父亲！n,xm);elsep=p-lchild;if(p=NULL)printf( %s没有妻子n,xm);elsep=p-rchild;if(p=NULL) printf( %没有儿子！n,xm);elseprintf( %s的儿子：,xm);while(p!=NULL)printf(%10s,p-name);p=p-rchild;printf(n);int Path(BTree *bt,BTree *s)BTree *StMaxSize;BTree *p;int i,flag,top= -1;dowhile(bt)top+;Sttop=bt;bt=bt-lchild;p=NULL;flag=1;while(top!=-1 & flag)bt=Sttop;if(bt-rchild=p)if(bt=s)printf( 所有祖先：);for(i=0;iname);printf(n);return 1;elsetop-;p=bt;elsebt=bt-rchild;flag=0;while(top!=-1);return 0;void Ancestor(BTree *bt)BTree *p;char xmNAMEWIDTH;printf( 输入姓名:);scanf(%s,xm);p=FindNode(bt,xm);if(p!=NULL)Path(bt,p);elseprintf( 不存在%sn,xm);void DelAll(FamType fam,int &n)FILE *fp;if(fp=fopen(fam.dat,wb)=NULL)printf( 不能打开家谱文件n);return;n=0;fclose(fp);void ReadFile(FamType fam,int &n)FILE *fp;long length;int i;if(fp=fopen(fam.dat,rb)=NULL)n=0;return;fseek(fp,0,2);length=ftell(fp);rewind(fp);n=length/sizeof(FamType);for(i=0;i数据家谱文件不能打开n);return;for(i=0;i输入父亲、母亲和儿子姓名：);scanf(%s%s%s,famn.father,famn.wife,famn.son);n+;void OutputFile(FamType fam,int n)int i;if(n没有任何记录n);return;for(i=0;i%10s%10s%10sn,fami.father,fami.wife,fami.son);void main()BTree *bt;FamType famMaxSize;int n,sel,sell;ReadFile(fam,n);doprintf(1.文件操作2.家谱操作0.退出 请选择：);scanf(%d,&sel);switch(sel) case 1:doprintf(1：输入2：输出9：全清0：存盘返回 请选择：);scanf(%d,&sell);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(f1,fam,n);doprintf(1.找某人所有儿子 2.找某人所有祖先 0:返回 请选择：);scanf(%d,&sell);switch(sell)case 1: FindSon(bt);break;case 2: printf( );Ancestor(bt);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后系统自动保存所有的数据并