工程名稱：家譜系統的設計與實現學生姓名：學號：班級：指導教師：2011年12月23日目錄TOC\o"1-2"\u1系統需求分析 11.1問題分析 11.2任務意義 12設數據結構設計及用法說明 23詳細設計和編碼 33.1初始化 33.2功能選擇 43.3信息輸入 73.4信息輸出 73.5信息存盤 83.6信息清盤 93.7信息查詢 104實驗結果 134.1菜單函數功能測試 134.2輸入功能函數測試 134.3輸出功能函數測試 134.4清盤功能函數測試 134.5存盤功能函數測試 144.6查詢功能函數測試 15致謝 17參考文獻 18附錄：源代碼 191系統需求分析1.1問題分析從課程設計的題目要求可以知道，我需要設計一個對數據輸入，輸出，儲存，查找的多功能軟件，我選擇用二叉樹來保存家族的根本信息，包括姓名及它們的關系，但是由于家族信息很巨大而且關系很復雜所以采用二叉樹來儲存它們的信息及輸出它們的關系。并且具有保存文件的功能，以便下次直接使用先前存入的信息。1.2任務意義家譜的功能是查詢家族每個人的信息，并且輸出它們的信息，還要具有查詢輸出功能。這樣復習了一下查詢。插入。刪除函數的應用。并復習了上學期c語言的文件儲存及調用功能，子函數和遞歸調用功能，熟練運用這些函數。

2系統數據結構設計及用法說明采用文件保存信息，并且從文件中輸出原先保存的信息，用結構體fnode來儲存家族的信息，采用遞歸的方法從fam中創立一個空二叉樹，然后初始化二叉樹。采用InputFam函數添加信息，OutputFam函數輸出信息，DelAll函數刪除家族的全部記錄，SaveFile函數保存添加的信息，FindNode函數查找節點。文件1：輸入輸入父親、母親和兒子的姓名0：存盤返回文件1：輸入輸入父親、母親和兒子的姓名0：存盤返回圖2數據存儲結構圖相應的存儲結構代碼為：typedefstructfnode{ charfather[NAMEWIDTH]; charwife[NAMEWIDTH]; charson[NAMEWIDTH]; charbrother[NAMEWIDTH];}FamType;typedefstructtnode{ charname[NAMEWIDTH]; structtnode*lchild,*rchild;}BTree;3詳細設計和編碼3.1初始化圖3-1為初始化函數的流程圖，主要是對二叉樹中數據域置空，對二叉樹中的數據進行初始化。代碼如下：BTree*CreatBTree(char*root,FamTypefam[],intn)//從fam中〔含n個記錄〕遞歸創立一棵二叉樹{ inti=0,j; BTree*bt,*p; bt=(BTree*)malloc(sizeof(BTree));//創立父親結點 strcpy(bt->name,root); bt->lchild=bt->rchild=NULL; while(i<n&&strcmp(fam[i].father,root)!=0) i++; if(i<n)//找到該姓名的記錄 { p=(BTree*)malloc(sizeof(BTree));//創立母親結點 p->lchild=p->rchild=NULL; strcpy(p->name,fam[i].wife); bt->lchild=p; for(j=0;j<n;j++)//找所有兒子 if(strcmp(fam[j].father,root)==0)//找到一個兒子 { p->rchild=CreatBTree(fam[j].son,fam,n); p=p->rchild; } } return(bt);}圖3-1初始化函數流程圖3.2功能選擇圖3-2為功能選擇模塊函數的流程圖，主要提供1：文件2：家譜兩個功能模塊讓用戶選擇。輸入數字1的時候，出現界面1：輸入2：輸出9：清盤0：存盤返回。返回后輸入數字2，出現界面1：找某人的所有兒子2：找某人所有祖先3：找某人所有兄弟。用戶根據提示操作。代碼如下：voidmain(){ BTree*bt; BTree*p,*father; FamTypefam[MaxSize]; intn,sel,sell; charxm[NAMEWIDTH]; ReadFile(fam,n); do { cout<<"1.文件2:家譜0:退出請選擇:"; cin>>sel; switch(sel) { case1: do { cout<<"1:輸入2:輸出9:全清0:存盤返回請選擇:"; cin>>sell; switch(sell) { case9: DelAll(fam,n); break; case1: InputFam(fam,n); break; case2: OutputFile(fam,n); break; case0: SaveFile(fam,n); break; } }while(sell!=0); break; case2: bt=CreatBTree("f1",fam,n); do { cout<<"1:找某人所有兒子2:找某人所有祖先3:查找某人所有兄弟0:返回請選擇:"; cin>>sell; switch(sell) { case1: FindSon(bt); break; case2: cout<<">>"; Ancestor(bt); cout<<endl; break; case3: cout<<">>"; FindBrother(bt); cout<<endl; break; } }while(sell!=0); break; } }while(sel!=0);}圖3-2功能選擇模塊函數流程圖3.3信息輸入圖3-3為信息輸入模塊函數的流程圖，出現界面請輸入父親、母親和兒子的姓名讓用戶輸入信息。代碼如下：voidInputFam(FamTypefam[],int&n)//添加一個記錄{ cout<<">>輸入父親、母親和兒子姓名:"; cin>>fam[n].father>>fam[n].wife>>fam[n].son; n++;}圖3-3信息輸入模塊函數流程圖3.4信息輸出圖3-4為信息輸出模塊函數的流程圖，自動輸出數據的信息及它們之間的家譜關系。按順序輸出父親，母親，兒子。代碼如下：voidOutputFile(FamTypefam[],intn)//輸出簡樸文件的所有記錄{ inti; if(n<0) { cout<<">>沒有任何記錄!"<<endl; return; } for(i=0;i<n;i++) cout<<fam[i].father<<fam[i].wife<<fam[i].son;}圖3-4信息輸出模塊函數流程圖3.5信息存盤圖3-5為信息存盤模塊函數的流程圖，將用戶輸入的信息存盤，下次要用時自動調用。代碼如下：voidSaveFile(FamTypefam[],intn)//將fam數組存入數據家譜文件{ inti; FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>數據家譜文件不能翻開"<<endl; return; } for(i=0;i<n;i++) fwrite(&fam[i],sizeof(FamType),1,fp); fclose(fp);}圖3-5信息存盤模塊函數流程圖3.6信息清盤圖3-6為信息清盤模塊函數的流程圖，將用戶輸入的信息全部清盤。代碼如下；voidDelAll(FamTypefam[],int&n)//去除家譜文件的全部記錄{ FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>不能翻開家譜文件"<<endl; return; } n=0; fclose(fp);}圖3-6信息讀盤模塊函數流程圖3.7信息查詢圖3-7為信息查詢模塊函數的流程圖，查詢用戶輸入數據的信息及家譜關系。具有的功能是1：找某人所有兒子2：找某人所有祖先3：找某人所有兄弟。用戶根據需要操作。找某人所有兒子的代碼：voidFindSon(BTree*bt)//輸出某人的所有兒子{ charxm[NAMEWIDTH]; BTree*p; cout<<">>父親姓名:"; cin>>xm; p=FindNode(bt,xm); if(p==NULL) cout<<">>不存在"<<xm<<"的父親!"<<endl; else { p=p->lchild; if(p==NULL) cout<<">>"<<xm<<"沒有妻子"<<endl; else { p=p->rchild; if(p==NULL) cout<<">>"<<xm<<"沒有兒子!"; else { cout<<">>"<<xm<<"的兒子:"; while(p!=NULL) { cout<<p->name; p=p->rchild; } cout<<endl; } } }}//找某人所有祖先的代碼：voidAncestor(BTree*bt)//輸出某人所有的祖先{ BTree*p; charxm[NAMEWIDTH]; cout<<">>輸入姓名:"; cin>>xm; p=FindNode(bt,xm); if(p!=NULL) Path(bt,p); else cout<<">>不存在"<<xm;}//找某人所有兄弟的代碼：voidFindBrother(BTree*bt){ charxm[NAMEWIDTH]; BTree*p,*father; cout<<">>某人的姓名:"; cin>>xm; p=FindNode(bt,xm); Path1(bt,p);//雙親存在數組St[MaxSize] father=St[0]; findson1(bt,father); //調用findson函數找兒子}圖3-7查詢模塊函數流程圖

4實驗結果4.1菜單函數功能測試系統運行后就會自動顯示如圖4-1的主菜單，選項包括：1、文件，2、家譜，0、退出，。當用戶選擇相應的代號就進入相應的功能模塊。圖4-1主菜單函數功能檢測4.2輸入功能函數測試系統運行后就會自動顯示如圖4-2的輸入功能模塊，界面出現1：輸入>>輸入父親、母親和兒子的姓名用戶輸入信息。圖4-2輸入功能函數測試4.3輸出功能函數測試系統運行后就會自動顯示如圖4-3的輸出功能模塊，界面出現2：輸出。用戶輸入數字2后系統自動輸出數據信息。圖4-3輸出功能函數測試4.4清盤功能函數測試系統運行后就會自動顯示如圖4-4的清盤功能模塊，界面出現9：全清。用戶輸入數9后自動系統去除所有的數據并返回。圖4-4清盤功能函數測試4.5存盤功能函數測試系統運行后就會自動顯示如圖4-5的存盤功能模塊，界面出現0：存盤返回。用戶輸入數0后系統自動保存所有的數據并返回。圖4-5存盤功能函數測試4.6查詢功能函數測試系統運行后就會自動顯示如圖4-6的查詢功能模塊，界面出現1：找某人的所有兒子圖4-6查詢功能函數測試

5體會程序的關鍵是掌握二叉樹的相關操作、二叉樹的創立和運用、結點的查找、祖宗結點的查找等。在編程的過程中，出現了很多問題，如二叉樹無法建立、程序內存讀取不了、忘了添加頭文件等錯誤。在單步調試和添加提示輸出的情況下修改程序運行正確。查找首先要判斷該結點是否為空，再與查找到的結點比擬，否那么會內存無法讀取，強行結束程序。祖宗結點的查找一直是個大問題，在參考書的幫助下想到了后續遍歷，是可以從孩子往上找到。兄弟結點的查找，往上找哥哥，還要往下找弟弟，首先要找到母親結點，再依次輸出。

致謝感謝學校機房給我們提供良好的寫代碼環境。感謝松哥和瑩姐孜孜不倦的教導我們。感謝在寫代碼期間同學們對我的幫助，讓我能順利的寫出代碼。

參考文獻[1]譚浩強.C語言課程設計〔第三版〕.北京：清華大學出版社,1996.5[2]方超昆.C++程序設計教程.北京：郵電大學出版社,2009[3]李春葆.數據結構教程〔第3版〕：清華大學出版社，2009[4]WalterSavitch.C++面向對象程序設計〔第7版〕：清華大學出版社，2010附錄：源代碼#include<iostream.h>#include<stdio.h>#include<malloc.h>#include<string.h>#include<stdlib.h>#defineMaxWidth40#defineMaxSize30#defineNAMEWIDTH10typedefstructfnode{ charfather[NAMEWIDTH]; charwife[NAMEWIDTH]; charson[NAMEWIDTH]; charbrother[NAMEWIDTH];}FamType;typedefstructtnode{ charname[NAMEWIDTH]; structtnode*lchild,*rchild;}BTree;//家譜樹類型BTree*CreatBTree(char*root,FamTypefam[],intn)//從fam中〔含n個記錄〕遞歸創立一棵二叉樹{ inti=0,j; BTree*bt,*p; bt=(BTree*)malloc(sizeof(BTree));//創立父親結點 strcpy(bt->name,root); bt->lchild=bt->rchild=NULL; while(i<n&&strcmp(fam[i].father,root)!=0) i++; if(i<n)//找到該姓名的記錄 { p=(BTree*)malloc(sizeof(BTree));//創立母親結點 p->lchild=p->rchild=NULL; strcpy(p->name,fam[i].wife); bt->lchild=p; for(j=0;j<n;j++)//找所有兒子 if(strcmp(fam[j].father,root)==0)//找到一個兒子 { p->rchild=CreatBTree(fam[j].son,fam,n); p=p->rchild; } } return(bt);}BTree*FindNode(BTree*bt,charxm[])//采用線序遞歸算法找name為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)); } }}voidfindson1(BTree*bt,BTree*p)//找p的孩子{ charxm[NAMEWIDTH]; if(p==NULL) cout<<"沒有孩子！"; else { p=p->lchild; if(p==NULL) cout<<"沒有孩子！"; else { p=p->rchild; if(p==NULL) cout<<"沒有兄弟!"; else { cout<<"兄弟:"; while(p!=NULL) { cout<<p->name<<""; p=p->rchild; } cout<<endl; } } }}voidFindSon(BTree*bt)//輸出某人的所有兒子{ charxm[NAMEWIDTH]; BTree*p; cout<<">>父親姓名:"; cin>>xm; p=FindNode(bt,xm); if(p==NULL) cout<<">>不存在"<<xm<<"的父親!"<<endl; else { p=p->lchild; if(p==NULL) cout<<">>"<<xm<<"沒有妻子"<<endl; else { p=p->rchild; if(p==NULL) cout<<">>"<<xm<<"沒有兒子!"; else { cout<<">>"<<xm<<"的兒子:"; while(p!=NULL) { cout<<p->name; p=p->rchild; } cout<<endl; } } }} BTree*St[MaxSize];intPath(BTree*bt,BTree*s)//采用后續非遞歸遍歷法輸出從根結點到*s結點的路徑{ BTree*p; inti,flag,top=-1;//棧指針置初值 do { while(bt)//將bt的所有左結點進棧 { top++; St[top]=bt; bt=bt->lchild; } p=NULL;//p指向當前結點的前一個已訪問的結點 flag=1;//設置bt的訪問標記為已訪問過 while(top!=-1&&flag) { bt=St[top];//取出當前的棧頂元素 if(bt->rchild==p)//右子樹不存在或已被訪問 { if(bt==s)//當前訪問的結點為要找的結點，輸出路徑 { cout<<">>所有祖先:"; for(i=0;i<top;i++) cout<<St[i]->name<<endl; return1; } else { top--; p=bt;//p指向剛被訪問的結點 } } else { bt=bt->rchild;//bt指向右子樹 flag=0;//設置未被訪問的標記 } } }while(top!=-1);//棧不為空時循環 return0;//其他情況時返回0}intPath1(BTree*bt,BTree*s)//采用后續非遞歸遍歷法輸出從根結點到*s結點的路徑{ BTree*p; inti,flag,top=-1;//棧指針置初值 do { while(bt)//將bt的所有左結點進棧 { top++; St[top]=bt; bt=bt->lchild; } p=NULL;//p指向當前結點的前一個已訪問的結點 flag=1;//設置bt的訪問標記為已訪問過 while(top!=-1&&flag) { bt=St[top];//取出當前的棧頂元素 if(bt->rchild==p)//右子樹不存在或已被訪問 { if(bt==s)//當前訪問的結點為要找的結點，輸出路徑 { for(i=0;i<top;i++) return1; } else { top--; p=bt;//p指向剛被訪問的結點 } } else { bt=bt->rchild;//bt指向右子樹 flag=0;//設置未被訪問的標記 } } }while(top!=-1);//棧不為空時循環 return0;//其他情況時返回0}voidAncestor(BTree*bt)//輸出某人所有的祖先{ BTree*p; charxm[NAMEWIDTH]; cout<<">>輸入姓名:"; cin>>xm; p=FindNode(bt,xm); if(p!=NULL) Path(bt,p); else cout<<">>不存在"<<xm;}voidFindBrother(BTree*bt){ charxm[NAMEWIDTH]; BTree*p,*father; cout<<">>某人的姓名:"; cin>>xm; p=FindNode(bt,xm); Path1(bt,p);//雙親存在數組St[MaxSize] father=St[0]; findson1(bt,father); //調用findson函數找兒子}voidDelAll(FamTypefam[],int&n)//去除家譜文件的全部記錄{ FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>不能翻開家譜文件"<<endl; return; } n=0; fclose(fp);}voidReadFile(FamTypefam[],int&n)//讀家譜文件并存入fam數組中{ FILE*fp; longlength; inti; if((fp=fopen("fam.dat","rb"))==NULL) { n=0; return; } fseek(fp,0,2);//家譜文件位置指針移到家譜文件尾 length=ftell(fp);//length求出家譜文件長度 rewind(fp);//家譜文件位置指針移到家譜文件首 n=length/sizeof(FamType);//n求出家譜文件中的記錄個數 for(i=0;i<n;i++) fread(&fam[i],sizeof(FamType),1,fp);//將家譜文件中的數據讀到fam中 fclose(fp);}voidSaveFile(FamTypefam[],intn)//將fam數組存入數據家譜文件{ inti; FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>數據家譜文件不能翻開"<<endl; return; } for(i=0;i<n;i++) fwrite(&fam[i],sizeof(FamType),1,fp); fclose(fp);}voidInputFam(FamTypefam[],int&n)//添加一個記錄{ cout<<">>輸入父親、母親和兒子姓名:"; cin