數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì)-二叉樹生成家譜

二叉樹生成家譜32/31數(shù)學(xué)與計(jì)算機(jī)學(xué)院課程設(shè)計(jì)說明書課程名稱:數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)課程代碼:題目:二叉樹生成家譜年級/專業(yè)/班:/軟件工程/2班學(xué)生姓名:學(xué)號:開始時(shí)間:年12月09日完成時(shí)間:年12月29日課程設(shè)計(jì)成績：學(xué)習(xí)態(tài)度及平時(shí)成績（30）技術(shù)水平與實(shí)際能力（20）創(chuàng)新（5）說明書（計(jì)算書、圖紙、分析報(bào)告）撰寫質(zhì)量（45）總分（100）指導(dǎo)教師簽名：年月日目錄（小三黑體，居中）TOC\o"1-2"\h\z\u1需求分析 61.1任務(wù)與分析 61.2測試數(shù)據(jù) 62概要設(shè)計(jì) 72.1ADT描述 72.2程序模塊結(jié)構(gòu) 82.3各功能模塊 93詳細(xì)設(shè)計(jì) 103.1結(jié)構(gòu)體定義 103.2初始化 113.3插入操作 133.4查詢操作 154調(diào)試分析 185用戶使用說明 186測試結(jié)果 18結(jié)論 23附錄 24參考文獻(xiàn) 25

摘要隨著計(jì)算機(jī)科學(xué)技術(shù)、計(jì)算機(jī)產(chǎn)業(yè)的迅速發(fā)展，計(jì)算機(jī)的應(yīng)用普及也在以驚人的速度發(fā)展，計(jì)算機(jī)應(yīng)用已經(jīng)深入到人類社會(huì)的各個(gè)領(lǐng)域。計(jì)算機(jī)的應(yīng)用早已不限于科學(xué)計(jì)算，而更多地應(yīng)用在信息處理方面。計(jì)算機(jī)可以存儲(chǔ)的數(shù)據(jù)對象不再是純粹的數(shù)值，而擴(kuò)展到了字符、聲音、圖像、表格等各種各樣的信息。對于信息的處理也不再是單純的計(jì)算，而是一些如信息存儲(chǔ)、信息檢索等非數(shù)值的計(jì)算。那么，現(xiàn)實(shí)世界的各種數(shù)據(jù)信息怎樣才能夠存儲(chǔ)到計(jì)算機(jī)的內(nèi)存之中，對存入計(jì)算機(jī)的數(shù)據(jù)信息怎樣進(jìn)行科學(xué)處理，這涉及計(jì)算機(jī)科學(xué)的信息表示和算法設(shè)計(jì)問題。為解決現(xiàn)實(shí)世界中某個(gè)復(fù)雜問題，總是希望設(shè)計(jì)一個(gè)高效適用的程序。這就需要解決怎樣合理地組織數(shù)據(jù)、建立合適的數(shù)據(jù)結(jié)構(gòu)，怎樣設(shè)計(jì)適用的算法，以提高程序執(zhí)行的時(shí)間效率和空間效率?！皵?shù)據(jù)結(jié)構(gòu)”就是在此背景下逐步形成、發(fā)展起來的。 在各種高級語言程序設(shè)計(jì)的基本訓(xùn)練中，解決某一實(shí)際問題的步驟一般是：分析實(shí)際問題；確定數(shù)學(xué)模型；編寫程序；反復(fù)調(diào)試程序直至得到正確結(jié)果。所謂數(shù)學(xué)模型一般指具體的數(shù)學(xué)公式、方程式等，如牛頓迭代法解方程，各種級數(shù)的計(jì)算等。這屬于數(shù)值計(jì)算的一類問題。而現(xiàn)實(shí)生活中，更多的是非數(shù)值計(jì)算問題，如手機(jī)中的通訊錄，人們對它的操作主要是查找、增加、刪除或者修改電話記錄。再如，人們經(jīng)常在互聯(lián)網(wǎng)上查閱各種新聞，或查閱電子地圖，人們可以在某城區(qū)地圖上查找自己所需的街道或店鋪，其操作主要是搜索和查詢。下面再來分析幾個(gè)典型實(shí)例，它們的主要特點(diǎn)是：不同實(shí)例的數(shù)據(jù)元素之間存在不同的關(guān)系；對數(shù)據(jù)信息的處理主要有插入、刪除、排序、檢索等。關(guān)鍵詞：網(wǎng)絡(luò)化；計(jì)算機(jī)；對策；二叉樹

引言課程設(shè)計(jì)的目的：通過本項(xiàng)課程設(shè)計(jì)，培養(yǎng)學(xué)生獨(dú)立思考、綜合運(yùn)用所學(xué)有關(guān)相應(yīng)知識的能力，使學(xué)生鞏固《數(shù)據(jù)結(jié)構(gòu)》課程學(xué)習(xí)的內(nèi)容，掌握工程軟件設(shè)計(jì)的基本方法，強(qiáng)化上機(jī)動(dòng)手編程能力，闖過理論與實(shí)踐相結(jié)合的難關(guān)；為了培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識、獨(dú)立分析和解決實(shí)際問題的能力，培養(yǎng)創(chuàng)意識和創(chuàng)新能力，使學(xué)生獲得科學(xué)研究的基礎(chǔ)訓(xùn)練。為后續(xù)各門計(jì)算機(jī)課程的學(xué)習(xí)和畢業(yè)設(shè)計(jì)打下堅(jiān)實(shí)基礎(chǔ)。同時(shí)，可以利用這次機(jī)會(huì)來檢驗(yàn)自己的c/c++/數(shù)據(jù)結(jié)構(gòu)水平，提高自己的寫作水平，鍛煉自己的動(dòng)手能力。而此次課程設(shè)計(jì)的意義在于：增強(qiáng)自己的動(dòng)手能力，熟悉和掌握二叉樹各種遍歷的算法，以及遞歸在遍歷二叉樹中的應(yīng)用，增強(qiáng)自己的調(diào)試程序和測試程序的能力。1需求分析1.1任務(wù)與分析1.建立輸入文件以存放最刜家譜中各成員的信息。2.成員的信息中均應(yīng)包含以下內(nèi)容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡）也可附加其它信息、但不是必需的。3.能對修改后的家譜存盤以備以后使用。4.能從文件中讀出已有的家譜，形成樹狀關(guān)系。5.家譜建立好之后，以圖形方式顯示出來。6.顯示第n代所有人的信息。7.按照姓名查詢，輸出成員信息（包括其本人、父親、孩子的信息）。8.按照出生日期查詢成員名單。9.輸入兩人姓名，確定其關(guān)系。10.給某人添加孩子。11.刪除某人（若其還有后代，則一并刪除）。12.修改某人信息。13.用括號法輸出家譜成員信息1.2測試數(shù)據(jù)1徐朝嬴m1938-1-201彭代芳0此人相當(dāng)?shù)臒嵝?2345100002徐廷文m1964-8-32李太群1此人相當(dāng)有責(zé)任心067100003徐素華w1966-4-62李奉光1此人很好0100004徐軍華m1969-7-82曲舞1此人很有正義感0100005徐廷國m1972-9-22木瑪1此人心的很善良0100006徐光勇m1989-1-273Nomarry2此人很牛逼0100007徐光超m1992-9-53Nomarry2此人亦很牛逼0100002概要設(shè)計(jì)2.1ADT描述1.ADTPerson{數(shù)據(jù)對象：D={Pj|Pj={姓名、出生日期、婚否、地址、健在否（如過世，還應(yīng)有其死亡日期）}，j=0,1,2,……n,其中n>=0}數(shù)據(jù)關(guān)系：R={}基本操作：無。}ADTPerson2.ADTFamilytreeFile{數(shù)據(jù)對象：D={Aj|Aj屬于Person,j=1,2,3，……,n其中n>=1}數(shù)據(jù)關(guān)系：D中每個(gè)對象用換行符隔開,R={

|Aj屬于D,j=1,2，3,……,n其中n>=1,String屬于字符串類型，為Aj父親姓名(若String=-1,Aj無父親，若String=Aj的姓名,表示家譜文件結(jié)束)}基本操作：1．打開家譜類型文件，并建立兄弟、孩子二叉樹。2．從內(nèi)存中讀取兄弟、孩子二叉樹，并建立家譜類型文件。}ADTFamilytreeFlie3.ADTFamilytree{數(shù)據(jù)對象：D={Aj|Aj屬于Person,j=1,2,3,……,n其中n>=0}數(shù)據(jù)關(guān)系：V={

|Aj-1,Aj屬于D,j=2,3,……，n其中n>=2，且Aj-1與Aj為祖先與后代關(guān)系（parent）、后代與祖先關(guān)系(child)、兄弟之間關(guān)系（sibling）}基本操作：1．顯示某人信息。2．修改某人信息。3．增加某人孩子。4．刪除某人。5．通過某人查找其雙親、孩子、兄弟。}ADTFamilytree2.2程序模塊結(jié)構(gòu)2.2.1結(jié)構(gòu)體定義structPeople//定義結(jié)構(gòu)體People{intnum;charname[20];charsex;charborndate[15];intgeneration;charmatename[20];intparent;charinfor[100];LinkListchild;}；structNode//定義結(jié)構(gòu)體Node{inta;structNode*next;}；structLinkList//定義鏈表{NodePointLa;}；structTree//定義樹{PeoplePointTr;intLength;intTREE_INIT_SIZE;}；全部功能模塊2.3各功能模塊全部功能模塊輸出成員模塊保存家譜模塊件讀取文件讀取模塊新建家譜模塊讀取家譜模塊退出程序模塊修改婚姻信息添加成員模塊輸出成員模塊保存家譜模塊件讀取文件讀取模塊新建家譜模塊讀取家譜模塊退出程序模塊修改婚姻信息添加成員模塊查找功能模塊voidPrintTree(TreeTR);voidSave(TreeTR);voidOpen(Tree&TR);voidInitTree(Tree&TR);Exit(1)voidMarryChange(TreeTR,charname[20]);voidAddPeople(Tree&TR);voidPrintTree(TreeTR);voidSave(TreeTR);voidOpen(Tree&TR);voidInitTree(Tree&TR);Exit(1)voidMarryChange(TreeTR,charname[20]);voidAddPeople(Tree&TR);voidPrintPeople(PeoplePointp);voidInitTree(Tree&TR);//在樹已定義的情況下，初始化樹TRLinkListInitLinkList(void);//在什么都沒有的情況下，初始化一個(gè)帶頭結(jié)點(diǎn)的鏈表并返回鏈表LvoidAddLinkList(LinkListp);//對帶頭結(jié)點(diǎn)的鏈表pl，添加一個(gè)節(jié)點(diǎn)為m的節(jié)點(diǎn)在表頭voidCreatFamilyTree(Tree&TR);//在什么都沒有的情況下，創(chuàng)建一個(gè)家譜TR。并返回TRvoidPrintPeople(PeoplePointp);//已知某節(jié)點(diǎn)的指針p，輸出peoplep的相關(guān)信息voidPrintLinkList(LinkListp);//已知鏈表p，輸出鏈表p中的信息intCompareNum(PeoplePointp,intnum);//已知某節(jié)點(diǎn)的指針p和一個(gè)編號num，比較p的num和num，如果相等返回1，否則返回0intCompareName(PeoplePointp,chara[]);//已知某節(jié)點(diǎn)的指針p和一個(gè)姓名a，比較p的name，如果兩者相等返回1，否則返回0voidTraveTreePrint(TreeTR);//已知樹TR，按規(guī)定輸出節(jié)點(diǎn)信息，根據(jù)編號、姓名、孩子輸出voidAddPeople(Tree&TR);//已知樹TR，當(dāng)有人出生時(shí)，添加一個(gè)節(jié)點(diǎn)voidMarryChange(TreeTR,charname[20]);//已知樹TR和一個(gè)人的姓名name，因?yàn)榻Y(jié)婚需要改變節(jié)點(diǎn)中的配偶一欄voidOpen(Tree&TR);//打開保存家譜信息的文件voidSave(TreeTR);//保存家譜信息到指定文件voidPrintTree(TreeTR);//輸出家譜中所有成員的信息3詳細(xì)設(shè)計(jì)3.1結(jié)構(gòu)體定義structPeople//定義結(jié)構(gòu)體People{intnum;charname[20];charsex;charborndate[15];intgeneration;charmatename[20];intparent;charinfor[100];LinkListchild;}；structNode//定義結(jié)構(gòu)體Node{inta;structNode*next;}；structLinkList//定義鏈表{NodePointLa;}；structTree//定義樹{PeoplePointTr;intLength;intTREE_INIT_SIZE;}；3.2初始化voidInitTree(Tree&TR)//在樹已定義的情況下，初始化樹TR{Peoplepeop[INIT_SIZE];TR.Tr=peop;TR.Length=0;TR.TREE_INIT_SIZE=INIT_SIZE;}LinkListInitLinkList(void)//在什么都沒有的情況下，初始化一個(gè)帶頭結(jié)點(diǎn)的鏈表并返回鏈表L{LinkListL;NodePointHead;Head=(NodePoint)malloc(sizeof(Node));Head->a=0;Head->next=NULL;L.La=Head;return(L);}voidCreatFamilyTree(Tree&TR)//在什么都沒有的情況下，創(chuàng)建一個(gè)家譜TR。并返回TR{LinkListlp; TR.Tr=peop;TR.Length=0;TR.TREE_INIT_SIZE=INIT_SIZE;inti=0,n,j,k,c;cout<<"請輸入家譜中一共有多少人\n";cin>>n;TR.Length=n;for(i=0;i<n;i++){(peop[i].num)=i+1;cout<<"請輸入該人的姓名:\n";cin>>peop[i].name;cout<<"請輸入該人的性別:\n";cin>>peop[i].sex;cout<<"請輸入該人的出生日期:\n";cin>>peop[i].borndate;cout<<"請輸入該人是第幾代人:\n";cin>>peop[i].generation;cout<<"請輸入其配偶的姓名，如無則輸入Nomarry\n";cin>>peop[i].matename;cout<<"請輸入其雙親的編號:\n";cin>>peop[i].parent;cout<<"請輸入該人相關(guān)的備注信息:\n";cin>>peop[i].infor;LinkListL;NodePointHead;Head=(NodePoint)malloc(sizeof(Node));Head->a=0;Head->next=NULL;L.La=Head;peop[i].child=L;lp=peop[i].child;cout<<"請輸入其孩子的個(gè)數(shù):\n";cin>>k;for(j=0;j<k;j++){cout<<"請輸入孩子的編號:\n";cin>>c;AddLinkList(lp,c);}}}開始3.3插入操作開始輸入成員信息輸入成員信息判斷格式是否正確判斷格式是否正確是是AddLinkList(L1,c);AddLinkList(L1,c);否否結(jié)束結(jié)束voidAddPeople(Tree&TR)//已知樹TR，當(dāng)有人出生時(shí)，添加一個(gè)節(jié)點(diǎn){intk,c,j,m;LinkListL,L1,L2;NodePointHead;PeoplePointp1,p2,p3;if(TR.Length>=TR.TREE_INIT_SIZE){TR.Tr=(PeoplePoint)realloc(TR.Tr,(TR.TREE_INIT_SIZE+TREEINCREMENT)*LEN);if(!TR.Tr)exit(OVERFLOW);}p1=peop;p2=p1+(TR.Length);p2->num=TR.Length+1;cout<<"請輸入該人的姓名:\n";gets(p2->name);cout<<"請輸入該人的性別:\n";cin>>p2->sex;cout<<"請輸入該人的出生日期:\n";cin>>p2->borndate;cout<<"請輸入該人是第幾代人:\n";cin>>p2->generation;cout<<"請輸入其配偶的姓名，如無則輸入Nomarry\n";gets(p2->matename);cout<<"請輸入其雙親的編號:\n";cin>>p2->parent;cout<<"請輸入該人相關(guān)的備注信息:\n";gets(p2->infor);gets(p2->infor);Head=(NodePoint)malloc(sizeof(Node));Head->a=0;Head->next=NULL;L.La=Head;p2->child=L;L1=p2->child;cout<<"請輸入其孩子的個(gè)數(shù):\n";cin>>k;for(j=0;j<k;j++){cout<<"請輸入孩子的編號:\n";cin>>c;AddLinkList(L1,c);}m=p2->parent-1;p3=p1+m;L2=p3->child;AddLinkList(L2,p2->num);TR.Length=TR.Length+1;cout<<"添加成功\n";}3.4查詢操作進(jìn)入進(jìn)入函數(shù)選擇功能選擇功能A=1A=3A=1A=3AA=2PrintPeople((p+(peop[j].parent-1)))PrintPeople((p+j));PrintPeople((p+j));PrintPeople((p+(peop[j].parent-1)))PrintPeople((p+j));PrintPeople((p+j));輸出信息輸出信息輸出信息輸出信息輸出信息輸出信息結(jié)束結(jié)束voidTraveTreePrint(TreeTR)//已知樹TR，按規(guī)定輸出節(jié)點(diǎn)信息，根據(jù)編號、姓名、孩子輸出{PeoplePointp;inti,j,k,Flag;charname1[15],name2[15];p=TR.Tr;printf("根據(jù)編號查找請輸入1，根據(jù)姓名查找請輸入2，根據(jù)孩子查找請輸入3:\n");scanf("%d",&i);if(i==1){printf("請輸入該節(jié)點(diǎn)的編號:\n");scanf("%d",&k);for(j=0;j<TR.Length;j++){Flag=CompareNum((p+j),k);if(Flag)PrintPeople((p+j));}}if(i==2){printf("請輸入該人的姓名:\n");gets(name1);gets(name1);for(j=0;j<TR.Length;j++){Flag=CompareName((p+j),name1);if(Flag)PrintPeople((p+j));}}if(i==3){printf("請輸入其孩子的姓名:\n");gets(name2);gets(name2);for(j=0;j<TR.Length;j++){if(strcmp(peop[j].name,name2)==0)PrintPeople((p+(peop[j].parent-1)));}}}4調(diào)試分析在調(diào)試時(shí)，遇到的幾個(gè)問題如下：1）建立樹時(shí)，由于新申請結(jié)點(diǎn)的孩子指針、兄弟指針、及雙親指針均未賦空值。而在以后的函數(shù)中對樹迚行遞歸操作時(shí)均以這些指針值中的一個(gè)或幾個(gè)是否為空作為遞歸結(jié)束條件。從而導(dǎo)致調(diào)用這些函數(shù)時(shí)出現(xiàn)系統(tǒng)保護(hù)異常（使用了不安全的指針）。2）剛開始初除結(jié)點(diǎn)時(shí)，只考慮到初除其本身結(jié)點(diǎn)的情況，而初除其孩子結(jié)點(diǎn)的情況未考慮到