C語言二叉樹家譜管理系統(tǒng)

1、 摘 要本文設(shè)計(jì)了一個(gè)對數(shù)據(jù)輸入，輸出，儲存，查找的多功能軟件，本文需要保存家族的基本信息，包括姓名及它們的關(guān)系，但是由于家族信息很巨大而且關(guān)系很復(fù)雜所以采用二叉樹來表示它們的關(guān)系。并且具有保存文件的功能，以便下次直接使用先前存入的信息。家譜的功能是查詢家族每個(gè)人的信息，并且輸出它們的信息，還要具有查詢輸出功能。本文采用二叉樹來存取家族的基本信息，頭結(jié)點(diǎn)作為父親節(jié)點(diǎn)，他的左孩子為他的妻子，妻子結(jié)點(diǎn)的右孩子為他的孩子，依次存儲每個(gè)家庭的信息?？梢圆檎颐總€(gè)父親的孩子和每個(gè)人的所有祖先。關(guān)鍵詞： 二叉樹 家譜 結(jié)點(diǎn)目錄1 系統(tǒng)功能概述11.1 系統(tǒng)功能1圖2 成員二叉樹功能模塊圖41.2 總體功能模

2、塊42 系統(tǒng)各功能模塊的詳細(xì)設(shè)計(jì)42.1功能選擇42.2信息輸入62.3信息輸出72.4信息存盤72.5信息清盤82.6信息查詢82.7源程序103設(shè)計(jì)結(jié)果與分析163.1菜單函數(shù)功能測試164.2輸入功能函數(shù)測試163.3輸出功能函數(shù)測試173.4清盤功能函數(shù)測試173.5存盤功能函數(shù)測試173.6查詢功能函數(shù)測試18總結(jié)19參考文獻(xiàn)201 系統(tǒng)功能概述1.1 系統(tǒng)功能實(shí)現(xiàn)的方法是先定義一個(gè)二叉樹，該二叉樹上的每個(gè)結(jié)點(diǎn)由三個(gè)元素組成：姓名、指向它左孩子的指針、以及指向它右孩子的指針構(gòu)成。該家譜管理系統(tǒng)將信息用文件的方法進(jìn)行存儲管理，再從文件中將成員信息以遞歸的方法創(chuàng)建二叉樹。該輸入成員信息的

3、方法是將父親結(jié)點(diǎn)存上父親的信息，然后父親結(jié)點(diǎn)的左孩子存上母親的信息，母親結(jié)點(diǎn)的右孩子存上孩子的信息。(1)定義結(jié)構(gòu)體結(jié)構(gòu)體為表示一個(gè)對象的不同屬性提供了連貫一致的方法，結(jié)構(gòu)體類型的說明從關(guān)鍵詞struct開始，成員可以由各種數(shù)據(jù)類型混合構(gòu)成，成員甚至還可以是數(shù)組或者其他類型的結(jié)構(gòu)，但是，結(jié)構(gòu)體中不能包含自身定義類型的成員。本文定義了兩個(gè)結(jié)構(gòu)體，分別是家族成員和二叉樹結(jié)點(diǎn)的結(jié)構(gòu)體。代碼如下：typedef struct fnode char fatherNAMEWIDTH; char wifeNAMEWIDTH;char sonNAMEWIDTH;FamType;typedef struct t

4、node char nameNAMEWIDTH;struct tnode *lchild,*rchild;BTree;(2) 二叉樹的建立二叉樹的結(jié)點(diǎn)有三個(gè)域，數(shù)據(jù)域和兩個(gè)指針域，數(shù)據(jù)域用來存放數(shù)據(jù)，兩個(gè)指針域分別存放指向該結(jié)點(diǎn)左右孩子的指針。并且還有個(gè)root結(jié)點(diǎn)，稱二叉樹的根節(jié)點(diǎn)。代碼如下：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;whi

5、le(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)家族成員信息的輸入依次輸入一個(gè)家庭的父親、母親和孩子的姓名。并將它們保存在相應(yīng)的文件里。(4)家族成員信息的輸出依次輸出每個(gè)家庭的父親、母親和孩子的姓名。(5) 查找某人的兒子 首先輸入父親的姓名，在二叉樹中查找是否有此人，如果沒有就輸出不存在這樣的父親。如果有

6、就先查看它的左孩子是否存在，不存在就輸出這個(gè)父親沒有妻子，如果存在就查找左孩子的右孩子，沒有右孩子就輸出這個(gè)父親沒有孩子，存在就輸出右孩子的姓名，即為查找到的兒子。(6)查找某人的祖先采用后序非遞歸遍歷方法輸入從根結(jié)點(diǎn)到*s結(jié)點(diǎn)的路徑，首先輸入一個(gè)成員的姓名，用一個(gè)棧存入查找的路徑，當(dāng)找到時(shí)棧中的元素即為它的所有祖先。該家譜管理系統(tǒng)將各個(gè)家庭的信息以文件的形式存儲，具體步驟如下圖：文件輸入輸入父親、母親和兒子的姓名保存 圖1 文件存儲功能模塊圖 該家譜管理系統(tǒng)還將各個(gè)成員的信息以及成員之間的關(guān)系存儲在二叉樹上，具體存儲方式如下圖：父親 母親兒子2兒子1圖2 成員二叉樹功能模塊圖1.2 總體功能

7、模塊家譜管理系統(tǒng)家譜的建立家譜的插入家譜的刪除家譜的查找家譜的顯示圖3 總體功能模塊圖2 系統(tǒng)各功能模塊的詳細(xì)設(shè)計(jì)2.1功能選擇功能選擇模塊函數(shù)，主要提供1：文件 2：家譜 兩個(gè)功能模塊讓用戶選擇。輸入數(shù)字1的時(shí)候，出現(xiàn)界面1：輸入 2：輸出 9：清盤 0：存盤返回。返回后輸入數(shù)字2，出現(xiàn)界面1：找某人的所有兒子 2：找某人所有祖先 。用戶根據(jù)自己的需求選擇void main()BTree *bt;FamType famMaxSize;int n,sel,sell;ReadFile(fam,n);doprintf(1.文件操作2.家譜操作0.退出 請選擇：);scanf(%d,&sel);sw

8、itch(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,&se

9、ll);switch(sell)case 1: FindSon(bt);break;case 2: printf( );Ancestor(bt);break;while(sell!=0);break;while(sel!=0);2.2信息輸入信息輸入模塊函數(shù)，出現(xiàn)界面請輸入父親、母親和兒子的姓名讓用戶輸入信息。代碼如下：void InputFam(FamType fam,int &n)printf( 輸入父親、母親和兒子姓名：);scanf(%s%s%s,famn.father,famn.wife,famn.son);n+;2.3信息輸出信息輸出模塊函數(shù)，自動輸出數(shù)據(jù)的信息及它們之間的家譜關(guān)系

10、。按順序輸出父親，母親，兒子。代碼如下：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信息存盤信息存盤模塊函數(shù)，將用戶輸入的信息存盤，下次要用時(shí)自動調(diào)用。代碼如下：void SaveFile(FamType fam,int n)int i;FILE *fp;if(fp=fopen(fam.dat,wb)=NULL)printf( 數(shù)據(jù)家譜文件不能打開n);return;for(i=0;i不能打開家譜文件n)

11、;return;n=0;fclose(fp);2.6信息查詢信息查詢模塊函數(shù)，查詢用戶輸入數(shù)據(jù)的信息及家譜關(guān)系。具有的功能是1：找某人所有兒子2：找某人所有祖先。用戶根據(jù)需要操作。找某人所有兒子的代碼：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)

12、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=fope

13、n(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,*

14、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.so

15、n,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);

16、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

17、(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

18、,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

19、);n=length/sizeof(FamType);for(i=0;i數(shù)據(jù)家譜文件不能打開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;Re

20、adFile(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

21、(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設(shè)計(jì)結(jié)果與分析3.1菜單函數(shù)功能測試系統(tǒng)運(yùn)行后就會自動顯示如圖3-1的主菜單，選項(xiàng)包括：1、文件，2、家譜，0、退出，。當(dāng)用戶選擇相應(yīng)的代號就進(jìn)入相應(yīng)的功能模塊。圖3-1 主菜單函數(shù)功能檢測4.2輸入功能函數(shù)測試系統(tǒng)運(yùn)行后就會自動顯示如圖3-2的輸入功能模塊，界面出現(xiàn)1：輸入輸入父親、母親和兒子的姓名，用戶輸入信息。圖3-2輸入功能函數(shù)測試3.3輸出功能函數(shù)測試系統(tǒng)運(yùn)行后就會自動顯示如圖3-3的輸出功能模塊，界面出現(xiàn)2：輸出。用戶輸入數(shù)字2后系統(tǒng)自動輸出數(shù)據(jù)信息。圖3-3輸出功能函數(shù)測試3.4清盤功能函數(shù)測試系統(tǒng)運(yùn)行后就會自動顯示如圖3-4的清盤功能模塊，界面出現(xiàn)9：全清。用戶輸入數(shù)9后自動系統(tǒng)清除所有的數(shù)據(jù)并返回。圖3-4清盤功能函數(shù)測試3.5存盤功能函數(shù)測試系統(tǒng)運(yùn)行后就會自動顯示如圖3-5的存盤功能模塊，界面出現(xiàn)0：存盤返回。用戶輸入數(shù)0后系統(tǒng)自動保存所有的