數(shù)據(jù)結(jié)構(gòu)(二叉樹)家譜管理系統(tǒng)#內(nèi)容清晰

1、數(shù)學(xué)與計算機(jī)學(xué)院課程設(shè)計說明書課 程 名 稱: 數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計 課 程 代 碼: 題 目: 二叉樹生成家譜 年級/專業(yè)/班: 學(xué) 生 姓 名: 學(xué) 號: 開 始 時 間: 2015 年 12 月 09 日完 成 時 間: 2015 年 12 月 29 日課程設(shè)計成績：學(xué)習(xí)態(tài)度及平時成績（30）技術(shù)水平與實(shí)際能力（20）創(chuàng)新（5） 說明書（計算書、圖紙、分析報告）撰寫質(zhì)量（45）總 分（100）指導(dǎo)教師簽名： 年 月 日目 錄 （小三黑體，居中）1 需求分析61.1任務(wù)與分析61.2測試數(shù)據(jù)62 概要設(shè)計72.1 ADT描述72.2程序模塊結(jié)構(gòu)82.3各功能模塊93 詳細(xì)設(shè)計103.1結(jié)

2、構(gòu)體定義103.2 初始化113.3 插入操作133.4 查詢操作154 調(diào)試分析185 用戶使用說明186 測試結(jié)果18結(jié) 論23附 錄24參考文獻(xiàn)25摘 要隨著計算機(jī)科學(xué)技術(shù)、計算機(jī)產(chǎn)業(yè)的迅速發(fā)展，計算機(jī)的應(yīng)用普及也在以驚人的速度發(fā)展，計算機(jī)應(yīng)用已經(jīng)深入到人類社會的各個領(lǐng)域。計算機(jī)的應(yīng)用早已不限于科學(xué)計算，而更多地應(yīng)用在信息處理方面。計算機(jī)可以存儲的數(shù)據(jù)對象不再是純粹的數(shù)值，而擴(kuò)展到了字符、聲音、圖像、表格等各種各樣的信息。對于信息的處理也不再是單純的計算，而是一些如信息存儲、信息檢索等非數(shù)值的計算。那么，現(xiàn)實(shí)世界的各種數(shù)據(jù)信息怎樣才能夠存儲到計算機(jī)的內(nèi)存之中，對存入計算機(jī)的數(shù)據(jù)信息怎樣進(jìn)

3、行科學(xué)處理，這涉及計算機(jī)科學(xué)的信息表示和算法設(shè)計問題。為解決現(xiàn)實(shí)世界中某個復(fù)雜問題，總是希望設(shè)計一個高效適用的程序。這就需要解決怎樣合理地組織數(shù)據(jù)、建立合適的數(shù)據(jù)結(jié)構(gòu)，怎樣設(shè)計適用的算法，以提高程序執(zhí)行的時間效率和空間效率?！皵?shù)據(jù)結(jié)構(gòu)”就是在此背景下逐步形成、發(fā)展起來的。在各種高級語言程序設(shè)計的基本訓(xùn)練中，解決某一實(shí)際問題的步驟一般是：分析實(shí)際問題；確定數(shù)學(xué)模型；編寫程序；反復(fù)調(diào)試程序直至得到正確結(jié)果。所謂數(shù)學(xué)模型一般指具體的數(shù)學(xué)公式、方程式等，如牛頓迭代法解方程，各種級數(shù)的計算等。這屬于數(shù)值計算的一類問題。而現(xiàn)實(shí)生活中，更多的是非數(shù)值計算問題，如手機(jī)中的通訊錄，人們對它的操作主要是查找、增加

4、、刪除或者修改電話記錄。再如，人們經(jīng)常在互聯(lián)網(wǎng)上查閱各種新聞，或查閱電子地圖，人們可以在某城區(qū)地圖上查找自己所需的街道或店鋪，其操作主要是搜索和查詢。下面再來分析幾個典型實(shí)例，它們的主要特點(diǎn)是：不同實(shí)例的數(shù)據(jù)元素之間存在不同的關(guān)系；對數(shù)據(jù)信息的處理主要有插入、刪除、排序、檢索等。關(guān)鍵詞：網(wǎng)絡(luò)化；計算機(jī)；對策；二叉樹引 言 課程設(shè)計的目的：通過本項(xiàng)課程設(shè)計，培養(yǎng)學(xué)生獨(dú)立思考、綜合運(yùn)用所學(xué)有關(guān)相應(yīng)知識的能力，使學(xué)生鞏固數(shù)據(jù)結(jié)構(gòu)課程學(xué)習(xí)的內(nèi)容，掌握工程軟件設(shè)計的基本方法，強(qiáng)化上機(jī)動手編程能力，闖過理論與實(shí)踐相結(jié)合的難關(guān)；為了培養(yǎng)學(xué)生綜合運(yùn)用所學(xué)知識、獨(dú)立分析和解決實(shí)際問題的能力，培養(yǎng)創(chuàng)意識和創(chuàng)新能力

5、，使學(xué)生獲得科學(xué)研究的基礎(chǔ)訓(xùn)練。為后續(xù)各門計算機(jī)課程的學(xué)習(xí)和畢業(yè)設(shè)計打下堅實(shí)基礎(chǔ)。同時，可以利用這次機(jī)會來檢驗(yàn)自己的c/c+/數(shù)據(jù)結(jié)構(gòu)水平，提高自己的寫作水平，鍛煉自己的動手能力。而此次課程設(shè)計的意義在于：增強(qiáng)自己的動手能力，熟悉和掌握二叉樹各種遍歷的算法，以及遞歸在遍歷二叉樹中的應(yīng)用，增強(qiáng)自己的調(diào)試程序和測試程序的能力。1 需求分析1.1任務(wù)與分析1.建立輸入文件以存放最刜家譜中各成員的信息。 2.成員的信息中均應(yīng)包含以下內(nèi)容： 姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡） 也可附加其它信息、但不是必需的。 3.能對修改后的家譜存盤以備以后使用。 4.能從文件中讀出已有的家譜，

6、形成樹狀關(guān)系。 5.家譜建立好之后，以圖形方式顯示出來。 6.顯示第n 代所有人的信息。 7.按照姓名查詢，輸出成員信息（包括其本人、父親、孩子的信息）。 8.按照出生日期查詢成員名單。 9.輸入兩人姓名，確定其關(guān)系。 10.給某人添加孩子。 11.刪除某人（若其還有后代，則一并刪除）。 12.修改某人信息。 13.用括號法輸出家譜成員信息1.2測試數(shù)據(jù)1 徐朝嬴 m 1938-1-20 1 彭代芳 0 此人相當(dāng)?shù)臒嵝?0 2 3 4 5 100002 徐廷文 m 1964-8-3 2 李太群 1 此人相當(dāng)有責(zé)任心 0 6 7 100003 徐素華 w 1966-4-6 2 李奉光 1 此人很

7、好 0 100004 徐軍華 m 1969-7-8 2 曲舞 1 此人很有正義感 0 100005 徐廷國 m 1972-9-2 2 木瑪 1 此人心的很善良 0 10000 6 徐光勇 m 1989-1-27 3 Nomarry 2 此人很牛逼 0 100007 徐光超 m 1992-9-5 3 Nomarry 2 此人亦很牛逼 0 100002 概要設(shè)計2.1 ADT描述 1.ADT Person 數(shù)據(jù)對象：D=Pj | Pj=姓名、出生日期、婚否、地址、健在否（如過世，還應(yīng)有其死亡日 期），j=0,1,2, n,其中n=0 數(shù)據(jù)關(guān)系：R= 基本操作： 無。 ADT Person2.ADT

8、 FamilytreeFile 數(shù)據(jù)對象：D=Aj | Aj 屬于 Person,j=1,2,3，,n 其中n=1 數(shù)據(jù)關(guān)系：D 中每個對象用換行符隔開, R=| Aj 屬于D,j=1,2，3,n 其中n=1,String 屬于字符串類型，為 Aj 父親姓名(若String=-1,Aj 無父親，若String=Aj 的姓名,表示家譜文件結(jié)束) 基本操作： 1 打開家譜類型文件，并建立兄弟、孩子二叉樹。 2 從內(nèi)存中讀取兄弟、孩子二叉樹，并建立家譜類型文件。 ADT FamilytreeFlie3.ADT Familytree 數(shù)據(jù)對象：D=Aj | Aj 屬于Person,j=1,2,3,n

9、其中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 通過某人查找其雙親、孩子、兄弟。 ADT Familytree2.2程序模塊結(jié)構(gòu)2.2.1結(jié)構(gòu)體定義struct People /定義結(jié)構(gòu)體Peopleint num;char name20;char sex;char borndate15;int generation;char matename20;

10、int parent;char infor100;LinkList child;；struct Node /定義結(jié)構(gòu)體Nodeint a;struct Node * next;；struct LinkList /定義鏈表NodePoint La;；struct Tree /定義樹PeoplePoint Tr;int Length;int TREE_INIT_SIZE;；全部功能模塊2.3各功能模塊輸出成員模塊保存家譜模塊件讀取文件讀取模塊新建家譜模塊讀取家譜模塊退出程序模塊修改婚姻信息添加成員模塊查找功能模塊void PrintTree(Tree TR);void Save(Tree TR);

11、void Open(Tree &TR);void InitTree(Tree &TR);Exit(1)void MarryChange(Tree TR,char name20);void AddPeople(Tree &TR);void PrintPeople(PeoplePoint p);void InitTree(Tree &TR); /在樹已定義的情況下，初始化樹TR LinkList InitLinkList(void); /在什么都沒有的情況下，初始化一個帶頭結(jié)點(diǎn)的鏈表并返回鏈表L void AddLinkList(LinkList p); /對帶頭結(jié)點(diǎn)的鏈表pl，添加一個節(jié)點(diǎn)為m的

12、節(jié)點(diǎn)在表頭void CreatFamilyTree(Tree &TR); /在什么都沒有的情況下，創(chuàng)建一個家譜TR。并返回TRvoid PrintPeople(PeoplePoint p); / 已知某節(jié)點(diǎn)的指針p，輸出people p 的相關(guān)信息void PrintLinkList(LinkList p); /已知鏈表p，輸出鏈表p中的信息int CompareNum(PeoplePoint p,int num); /已知某節(jié)點(diǎn)的指針p和一個編號num，比較p的num和num，如果相等返回1，否則返回0int CompareName(PeoplePoint p,char a);/已知某節(jié)點(diǎn)的

13、指針p和一個姓名a，比較p的name，如果兩者相等返回1，否則返回0void TraveTreePrint(Tree TR); /已知樹TR，按規(guī)定輸出節(jié)點(diǎn)信息，根據(jù)編號、姓名、孩子輸出void AddPeople(Tree &TR); /已知樹TR，當(dāng)有人出生時，添加一個節(jié)點(diǎn)void MarryChange(Tree TR,char name20); /已知樹TR和一個人的姓名name，因?yàn)榻Y(jié)婚需要改變節(jié)點(diǎn)中的配偶一欄void Open(Tree &TR);/打開保存家譜信息的文件void Save(Tree TR);/保存家譜信息到指定文件void PrintTree(Tree TR);

14、/輸出家譜中所有成員的信息3 詳細(xì)設(shè)計3.1結(jié)構(gòu)體定義struct People /定義結(jié)構(gòu)體Peopleint num;char name20;char sex;char borndate15;int generation;char matename20;int parent;char infor100;LinkList child;；struct Node /定義結(jié)構(gòu)體Nodeint a;struct Node * next;；struct LinkList /定義鏈表NodePoint La;；struct Tree /定義樹PeoplePoint Tr;int Length;int T

15、REE_INIT_SIZE;；3.2 初始化void InitTree(Tree &TR) /在樹已定義的情況下，初始化樹TR People peopINIT_SIZE;TR.Tr=peop;TR.Length=0;TR.TREE_INIT_SIZE=INIT_SIZE;LinkList InitLinkList(void)/在什么都沒有的情況下，初始化一個帶頭結(jié)點(diǎn)的鏈表并返回鏈表L LinkList L;NodePoint Head;Head=(NodePoint)malloc(sizeof(Node);Head-a=0;Head-next=NULL;L.La=Head;return (L)

16、;void CreatFamilyTree(Tree &TR) /在什么都沒有的情況下，創(chuàng)建一個家譜TR。并返回TR LinkList lp;TR.Tr=peop;TR.Length=0;TR.TREE_INIT_SIZE=INIT_SIZE;int i=0,n,j,k,c;coutn;TR.Length=n;for(i=0;in;i+)(peopi.num)=i+1;;coutpeopi.sex;coutpeopi.borndate;coutpeopi.generation;coutpeopi.matename;coutpeopi.parent;coutpeopi

17、.infor;LinkList L;NodePoint Head;Head=(NodePoint)malloc(sizeof(Node);Head-a=0;Head-next=NULL;L.La=Head;peopi.child=L; lp=peopi.child;coutk;for(j=0;jk;j+)coutc;AddLinkList(lp,c);開始3.3 插入操作輸入成員信息判斷格式是否正確是AddLinkList(L1,c);否結(jié)束void AddPeople(Tree &TR)/已知樹TR，當(dāng)有人出生時，添加一個節(jié)點(diǎn)int k,c,j,m;LinkList L,L1,L2;Node

18、Point Head;PeoplePoint p1,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;coutname);coutp2-sex;coutp2-borndate;coutp2-generation;coutmatename);coutp2-parent;coutinfor);

19、gets(p2-infor);Head=(NodePoint)malloc(sizeof(Node);Head-a=0;Head-next=NULL;L.La=Head;p2-child=L;L1=p2-child;coutk;for(j=0;jk;j+)coutc;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)入函數(shù)選擇功能A=1A=3A=2PrintPeople(p+(peopj.parent-1)Prin

20、tPeople(p+j);PrintPeople(p+j);輸出信息輸出信息輸出信息結(jié)束void TraveTreePrint(Tree TR)/已知樹TR，按規(guī)定輸出節(jié)點(diǎn)信息，根據(jù)編號、姓名、孩子輸出PeoplePoint p;int i,j,k,Flag;char name115,name215;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;jTR.Length;j+)Flag=CompareNum(p+j),k)

21、;if(Flag)PrintPeople(p+j);if(i=2)printf(請輸入該人的姓名:n);gets(name1);gets(name1);for(j=0;jTR.Length;j+)Flag=CompareName(p+j),name1);if(Flag)PrintPeople(p+j);if(i=3)printf(請輸入其孩子的姓名:n);gets(name2);gets(name2);for(j=0;jTR.Length;j+)if(strcmp(,name2)=0)PrintPeople(p+(peopj.parent-1);4 調(diào)試分析在調(diào)試時，遇到的幾個問題如下： 1）建立樹時，由于新申請結(jié)點(diǎn)的孩子指針、兄弟指針、及雙親指針均未賦空值。 而在以后的函數(shù)中對樹迚行遞歸操作時均以這些指針值中的一個或幾個是否為空 作為遞歸結(jié)束條件。從而導(dǎo)致調(diào)用這些函數(shù)時出現(xiàn)系統(tǒng)保護(hù)異常（使用了不安全 的指針）。 2）剛開始初除結(jié)點(diǎn)時，只考慮到初除其本身結(jié)點(diǎn)的情況，而初除其孩子結(jié)點(diǎn)的 情況未考慮到，故在初除某些結(jié)點(diǎn)時使樹出現(xiàn)了“斷鏈”現(xiàn)象。故在程序代碼中 對初除某一結(jié)點(diǎn)迚行操作時，首先要刞斷此結(jié)點(diǎn)是否有孩子及兄弟，然后迚行相 應(yīng)操作。本程序