數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)論文及代碼-家譜系統(tǒng)的設(shè)計(jì)與實(shí)現(xiàn)

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

2系統(tǒng)數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)及用法說明采用文件保存信息，并且從文件中輸出原先保存的信息，用結(jié)構(gòu)體fnode來儲(chǔ)存家族的信息，采用遞歸的方法從fam中創(chuàng)立一個(gè)空二叉樹，然后初始化二叉樹。采用InputFam函數(shù)添加信息，OutputFam函數(shù)輸出信息，DelAll函數(shù)刪除家族的全部記錄，SaveFile函數(shù)保存添加的信息，F(xiàn)indNode函數(shù)查找節(jié)點(diǎn)。文件1：輸入輸入父親、母親和兒子的姓名0：存盤返回文件1：輸入輸入父親、母親和兒子的姓名0：存盤返回圖2數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)圖相應(yīng)的存儲(chǔ)結(jié)構(gòu)代碼為：typedefstructfnode{ charfather[NAMEWIDTH]; charwife[NAMEWIDTH]; charson[NAMEWIDTH]; charbrother[NAMEWIDTH];}FamType;typedefstructtnode{ charname[NAMEWIDTH]; structtnode*lchild,*rchild;}BTree;3詳細(xì)設(shè)計(jì)和編碼3.1初始化圖3-1為初始化函數(shù)的流程圖，主要是對二叉樹中數(shù)據(jù)域置空，對二叉樹中的數(shù)據(jù)進(jìn)行初始化。代碼如下：BTree*CreatBTree(char*root,FamTypefam[],intn)//從fam中〔含n個(gè)記錄〕遞歸創(chuàng)立一棵二叉樹{ inti=0,j; BTree*bt,*p; bt=(BTree*)malloc(sizeof(BTree));//創(chuàng)立父親結(jié)點(diǎn) 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));//創(chuàng)立母親結(jié)點(diǎn) 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)//找到一個(gè)兒子 { p->rchild=CreatBTree(fam[j].son,fam,n); p=p->rchild; } } return(bt);}圖3-1初始化函數(shù)流程圖3.2功能選擇圖3-2為功能選擇模塊函數(shù)的流程圖，主要提供1：文件2：家譜兩個(gè)功能模塊讓用戶選擇。輸入數(shù)字1的時(shí)候，出現(xiàn)界面1：輸入2：輸出9：清盤0：存盤返回。返回后輸入數(shù)字2，出現(xiàn)界面1：找某人的所有兒子2：找某人所有祖先3：找某人所有兄弟。用戶根據(jù)提示操作。代碼如下：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功能選擇模塊函數(shù)流程圖3.3信息輸入圖3-3為信息輸入模塊函數(shù)的流程圖，出現(xiàn)界面請輸入父親、母親和兒子的姓名讓用戶輸入信息。代碼如下：voidInputFam(FamTypefam[],int&n)//添加一個(gè)記錄{ cout<<">>輸入父親、母親和兒子姓名:"; cin>>fam[n].father>>fam[n].wife>>fam[n].son; n++;}圖3-3信息輸入模塊函數(shù)流程圖3.4信息輸出圖3-4為信息輸出模塊函數(shù)的流程圖，自動(dòng)輸出數(shù)據(jù)的信息及它們之間的家譜關(guān)系。按順序輸出父親，母親，兒子。代碼如下：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信息輸出模塊函數(shù)流程圖3.5信息存盤圖3-5為信息存盤模塊函數(shù)的流程圖，將用戶輸入的信息存盤，下次要用時(shí)自動(dòng)調(diào)用。代碼如下：voidSaveFile(FamTypefam[],intn)//將fam數(shù)組存入數(shù)據(jù)家譜文件{ inti; FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>數(shù)據(jù)家譜文件不能翻開"<<endl; return; } for(i=0;i<n;i++) fwrite(&fam[i],sizeof(FamType),1,fp); fclose(fp);}圖3-5信息存盤模塊函數(shù)流程圖3.6信息清盤圖3-6為信息清盤模塊函數(shù)的流程圖，將用戶輸入的信息全部清盤。代碼如下；voidDelAll(FamTypefam[],int&n)//去除家譜文件的全部記錄{ FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>不能翻開家譜文件"<<endl; return; } n=0; fclose(fp);}圖3-6信息讀盤模塊函數(shù)流程圖3.7信息查詢圖3-7為信息查詢模塊函數(shù)的流程圖，查詢用戶輸入數(shù)據(jù)的信息及家譜關(guān)系。具有的功能是1：找某人所有兒子2：找某人所有祖先3：找某人所有兄弟。用戶根據(jù)需要操作。找某人所有兒子的代碼：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);//雙親存在數(shù)組St[MaxSize] father=St[0]; findson1(bt,father); //調(diào)用findson函數(shù)找兒子}圖3-7查詢模塊函數(shù)流程圖

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

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

致謝感謝學(xué)校機(jī)房給我們提供良好的寫代碼環(huán)境。感謝松哥和瑩姐孜孜不倦的教導(dǎo)我們。感謝在寫代碼期間同學(xué)們對我的幫助，讓我能順利的寫出代碼。

參考文獻(xiàn)[1]譚浩強(qiáng).C語言課程設(shè)計(jì)〔第三版〕.北京：清華大學(xué)出版社,1996.5[2]方超昆.C++程序設(shè)計(jì)教程.北京：郵電大學(xué)出版社,2009[3]李春葆.數(shù)據(jù)結(jié)構(gòu)教程〔第3版〕：清華大學(xué)出版社，2009[4]WalterSavitch.C++面向?qū)ο蟪绦蛟O(shè)計(jì)〔第7版〕：清華大學(xué)出版社，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個(gè)記錄〕遞歸創(chuàng)立一棵二叉樹{ inti=0,j; BTree*bt,*p; bt=(BTree*)malloc(sizeof(BTree));//創(chuàng)立父親結(jié)點(diǎn) 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));//創(chuàng)立母親結(jié)點(diǎn) 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)//找到一個(gè)兒子 { p->rchild=CreatBTree(fam[j].son,fam,n); p=p->rchild; } } return(bt);}BTree*FindNode(BTree*bt,charxm[])//采用線序遞歸算法找name為xm的結(jié)點(diǎn){ 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)//采用后續(xù)非遞歸遍歷法輸出從根結(jié)點(diǎn)到*s結(jié)點(diǎn)的路徑{ BTree*p; inti,flag,top=-1;//棧指針置初值 do { while(bt)//將bt的所有左結(jié)點(diǎn)進(jìn)棧 { top++; St[top]=bt; bt=bt->lchild; } p=NULL;//p指向當(dāng)前結(jié)點(diǎn)的前一個(gè)已訪問的結(jié)點(diǎn) flag=1;//設(shè)置bt的訪問標(biāo)記為已訪問過 while(top!=-1&&flag) { bt=St[top];//取出當(dāng)前的棧頂元素 if(bt->rchild==p)//右子樹不存在或已被訪問 { if(bt==s)//當(dāng)前訪問的結(jié)點(diǎn)為要找的結(jié)點(diǎn)，輸出路徑 { cout<<">>所有祖先:"; for(i=0;i<top;i++) cout<<St[i]->name<<endl; return1; } else { top--; p=bt;//p指向剛被訪問的結(jié)點(diǎn) } } else { bt=bt->rchild;//bt指向右子樹 flag=0;//設(shè)置未被訪問的標(biāo)記 } } }while(top!=-1);//棧不為空時(shí)循環(huán) return0;//其他情況時(shí)返回0}intPath1(BTree*bt,BTree*s)//采用后續(xù)非遞歸遍歷法輸出從根結(jié)點(diǎn)到*s結(jié)點(diǎn)的路徑{ BTree*p; inti,flag,top=-1;//棧指針置初值 do { while(bt)//將bt的所有左結(jié)點(diǎn)進(jìn)棧 { top++; St[top]=bt; bt=bt->lchild; } p=NULL;//p指向當(dāng)前結(jié)點(diǎn)的前一個(gè)已訪問的結(jié)點(diǎn) flag=1;//設(shè)置bt的訪問標(biāo)記為已訪問過 while(top!=-1&&flag) { bt=St[top];//取出當(dāng)前的棧頂元素 if(bt->rchild==p)//右子樹不存在或已被訪問 { if(bt==s)//當(dāng)前訪問的結(jié)點(diǎn)為要找的結(jié)點(diǎn)，輸出路徑 { for(i=0;i<top;i++) return1; } else { top--; p=bt;//p指向剛被訪問的結(jié)點(diǎn) } } else { bt=bt->rchild;//bt指向右子樹 flag=0;//設(shè)置未被訪問的標(biāo)記 } } }while(top!=-1);//棧不為空時(shí)循環(huán) return0;//其他情況時(shí)返回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);//雙親存在數(shù)組St[MaxSize] father=St[0]; findson1(bt,father); //調(diào)用findson函數(shù)找兒子}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數(shù)組中{ 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求出家譜文件中的記錄個(gè)數(shù) for(i=0;i<n;i++) fread(&fam[i],sizeof(FamType),1,fp);//將家譜文件中的數(shù)據(jù)讀到fam中 fclose(fp);}voidSaveFile(FamTypefam[],intn)//將fam數(shù)組存入數(shù)據(jù)家譜文件{ inti; FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>數(shù)據(jù)家譜文件不能翻開"<<endl; return; } for(i=0;i<n;i++) fwrite(&fam[i],sizeof(FamType),1,fp); fclose(fp);}voidInputFam(FamTypefam[],int&n)//添加一個(gè)記錄{ cout<<">>輸入父親、母親和兒子姓名:"; cin