數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告范例

　　篇一：數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)報告范例

　　《數(shù)據(jù)結(jié)構(gòu)與算法》實(shí)驗(yàn)報告

　　專業(yè) 班級 姓名 學(xué)號

　　實(shí)驗(yàn)項(xiàng)目

　　實(shí)驗(yàn)一 二叉樹的應(yīng)用

　　實(shí)驗(yàn)?zāi)康?/strong>

　　1、進(jìn)一步掌握指針變量的含義及應(yīng)用。

　　2、掌握二叉樹的結(jié)構(gòu)特征，以及各種存儲結(jié)構(gòu)的特點(diǎn)及使用范圍。

　　3、掌握用指針類型描述、訪問和處理二叉樹的運(yùn)算。

　　實(shí)驗(yàn)內(nèi)容

　　題目1:編寫一個程序，采用一棵二叉樹表示一個家譜關(guān)系。要求程序具有如下功能：

　�。�1）用括號表示法輸出家譜二叉樹，

　�。�2）查找某人的'所有兒子，

　�。�3）查找某人的所有祖先。

　　算法設(shè)計分析

　�。ㄒ唬�數(shù)據(jù)結(jié)構(gòu)的定義

　　為了能夠用二叉樹表示配偶、子女、兄弟三種關(guān)系，特采用以下存儲關(guān)系，則能在二叉樹上實(shí)現(xiàn)家譜的各項(xiàng)運(yùn)算。

　　二叉樹型存儲結(jié)構(gòu)定義為：

　　typedef struct SNODE

　　{char name[MAX]; //人名

　　struct SNODE *left;//指向配偶結(jié)點(diǎn)

　　struct SNODE *right; //指向兄弟或子女結(jié)點(diǎn)

　　}FNODE;

　�。ǘ�）總體設(shè)計

　　實(shí)驗(yàn)由主函數(shù)、家譜建立函數(shù)、家譜輸出函數(shù)、兒子查找函數(shù)、祖先查找函數(shù)、結(jié)點(diǎn)定位函數(shù)、選擇界面函數(shù)七個函數(shù)共同組成。其功能描述如下：

　�。�1）主函數(shù)：統(tǒng)籌調(diào)用各個函數(shù)以實(shí)現(xiàn)相應(yīng)功能

　　void main()

　�。�2）家譜建立函數(shù)：與用戶交互建立家族成員對應(yīng)關(guān)系

　　void InitialFamily(FNODE *&head) //家譜建立函數(shù)

　　（3）家譜輸出函數(shù)：用括號表示法輸出家譜

　　輸出形式為：父和母（子1和子妻1（孫1），子2和子妻2（孫2））

　　void PrintFamily(FNODE *head) //家譜輸出函數(shù)

　�。�4）兒子查找函數(shù)：在家譜中查找到某人所有的子女并輸出，同時也能辨別出其是否為家族成員與是否有子女

　　void FindSon(FNODE *b,char p[]) //兒子查找函數(shù)

　�。�5）祖先查找函數(shù)：在家譜中查找到某人所有的祖先并輸出，同時也能辨別出其是否為家族中成員。

　　int FindAncestor(FNODE *head,char son[ ]) //祖先查找函數(shù)

　�。�6）結(jié)點(diǎn)定位函數(shù)：在家譜中找到用戶輸入人名所對應(yīng)的結(jié)點(diǎn)。

　　FNODE *findnode(FNODE *b,char p[]) //結(jié)點(diǎn)定位函數(shù)

　�。�7）選擇界面函數(shù)：為便于編寫程序，將用戶選擇部分獨(dú)立為此函數(shù)。

　　void PRINT(int &n)

　�。ㄈ�）各函數(shù)的詳細(xì)設(shè)計：

　　void InitialFamily(FNODE *&head) //家譜建立函數(shù)

　　1：首先建立當(dāng)前人的信息，將其左右結(jié)點(diǎn)置為空，

　　2：然后讓用戶確定其是否有配偶，如果沒有配偶，則當(dāng)前程序結(jié)束，

　　3：如果有則建立其配偶信息，并將配偶結(jié)點(diǎn)賦給當(dāng)前人的左結(jié)點(diǎn)；

　　4：再讓用戶確定其是否有子女，如果有則遞歸調(diào)用家譜建立函數(shù)建立子女結(jié)點(diǎn)，并將其賦給配偶結(jié)點(diǎn)的下一個右結(jié)點(diǎn)。

　　5：如無，則程序結(jié)束

　　void PrintFamily(FNODE *head) //家譜輸出函數(shù)

　　1：首先判斷當(dāng)前結(jié)點(diǎn)是否為空，如果為空則結(jié)束程序；

　　2：如果不為空，則輸出當(dāng)前結(jié)點(diǎn)信息，

　　3：然后判斷其左結(jié)點(diǎn)（配偶結(jié)點(diǎn)）是否為空，如不為空則輸出“和配偶信息。

　　4：再判斷配偶結(jié)點(diǎn)的右結(jié)點(diǎn)是否為空，如不為空則遞歸調(diào)用輸出其子女信息，最后輸出“）”；

　　5：當(dāng)配偶結(jié)點(diǎn)為空時，則判斷其右結(jié)點(diǎn)（兄弟結(jié)點(diǎn)）是否為空

　　6：如果不為空，則輸出“，”，并遞歸調(diào)用輸出兄弟信息

　　7程序結(jié)束

　　FNODE *findnode(FNODE *b,char p[]) //結(jié)點(diǎn)定位函數(shù)

　　1：當(dāng)前結(jié)點(diǎn)是否為空，為空則返回空；

　　2：如果和查找信息相同，則返回當(dāng)前結(jié)點(diǎn)；

　　3：如不然，則先后遞歸訪問其左結(jié)點(diǎn)，再不是則遞歸訪問右結(jié)點(diǎn)

　　void FindSon(FNODE *b,char p[]) //兒子查找函數(shù)

　　1：在家譜中定位到要查找的結(jié)點(diǎn)，如無則輸出“查找不到此人”

　　2：判斷其配偶結(jié)點(diǎn)與子女結(jié)點(diǎn)是否為空，為空則輸出“無子女”

　　3：不為空則輸出其配偶結(jié)點(diǎn)的所有右結(jié)點(diǎn)（子女結(jié)點(diǎn)）。

　　int FindAncestor(FNODE *head,char son[ ]) //祖先查找函數(shù)

　　1：先在家譜中定位到要查找的結(jié)點(diǎn)，如為空輸出“不存在此人”，程序結(jié)束

　　2：先將父母結(jié)點(diǎn)入棧，當(dāng)棧為空時程序結(jié)束，

　　3：棧不為空時，判斷棧頂元素是否已訪問過，

　　4：訪問過，再判斷是否為查找結(jié)點(diǎn)，如是則輸出棧中保存的其祖先結(jié)點(diǎn)，并濾過其兄弟結(jié)點(diǎn)不輸出；不是查找結(jié)點(diǎn)，則退棧一個元素

　　5：未訪問過，則取當(dāng)前棧頂元素，置訪問標(biāo)志——1，同時取其右結(jié)點(diǎn)

　　6：棧不為空或當(dāng)前所取結(jié)點(diǎn)不為空時，轉(zhuǎn)到2；

　　實(shí)驗(yàn)測試結(jié)果及結(jié)果分析

　�。ㄒ唬�測試結(jié)果

　　（二）結(jié)果分析

　　（略）

　　實(shí)驗(yàn)總結(jié)

　�。�略）