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

1、數(shù)據(jù)結(jié)構(gòu)與算法實(shí)驗(yàn)報(bào)告專業(yè)班級(jí)姓名學(xué)號(hào)實(shí)驗(yàn)項(xiàng)目實(shí)驗(yàn)一二叉樹(shù)的應(yīng)用實(shí)驗(yàn)?zāi)康?、 進(jìn)一步掌握指針變量的含義及應(yīng)用2、掌握二叉樹(shù)的結(jié)構(gòu)特征，以及各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及使用范圍3、掌握用指針類型描述、訪問(wèn)和處理二叉樹(shù)的運(yùn)算實(shí)驗(yàn)內(nèi)容題目1:編寫(xiě)一個(gè)程序，采用一棵二叉樹(shù)表示一個(gè)家譜關(guān)系。要求程序具有如下功能：(1 )用括號(hào)表示法輸出家譜二叉樹(shù)，(2) 查找某人的所有兒子，(3) 查找某人的所有祖先。算法設(shè)計(jì)分析(一 )數(shù)據(jù)結(jié)構(gòu)的定義為了能夠用二叉樹(shù)表示配偶、子女、兄弟三種關(guān)系，特采用以下存儲(chǔ)關(guān)系，則能在二叉樹(shù)上 實(shí)現(xiàn)家譜的各項(xiàng)運(yùn)算。二叉樹(shù)型存儲(chǔ)結(jié)構(gòu)定義為：typedef struct SNODEchar n

2、ame MAX ;/人名struct SNODE *left;/ 指向配偶結(jié)點(diǎn)struct SNODE * right; /指向兄弟或子女結(jié)點(diǎn) FNODE ;(二)總體設(shè)計(jì)實(shí)驗(yàn)由主函數(shù)、家譜建立函數(shù)、家譜輸出函數(shù)、兒子查找函數(shù)、祖先查找函數(shù)、結(jié)點(diǎn)定位函 數(shù)、選擇界面函數(shù)七個(gè)函數(shù)共同組成其功能描述如下：(1) 主函數(shù)：統(tǒng)籌調(diào)用各個(gè)函數(shù)以實(shí)現(xiàn)相應(yīng)功能void main ()(2) 家譜建立函數(shù)：與用戶交互建立家族成員對(duì)應(yīng)關(guān)系void InitialFamily(FNODE* &head) /家譜建立函數(shù)(3) 家譜輸出函數(shù)：用括號(hào)表示法輸出家譜輸出形式為：父和母(子1和子妻1 (孫1),子2和子妻

3、2 (孫2)void PrintFamily ( FNODE * head) /家譜輸出函數(shù)（4）兒子查找函數(shù) : 在家譜中查找到某人所有的子女并輸出，同時(shí)也能辨別出其是否為家族成員與是否有子女void FindSon（FNODE *b,char p ） /兒子查找函數(shù)（5）祖先查找函數(shù)： 在家譜中查找到某人所有的祖先并輸出，同時(shí)也能辨別出其是否為家族中成員。int FindAncestor（FNODE *head ， char son ） /祖先查找函數(shù)（6 ）結(jié)點(diǎn)定位函數(shù) :在家譜中找到用戶輸入人名所對(duì)應(yīng)的結(jié)點(diǎn)。FNODE findnode（FNODE *b,char p ） /結(jié)點(diǎn)定位函

4、數(shù)（7） 選擇界面函數(shù)：為便于編寫(xiě)程序，將用戶選擇部分獨(dú)立為此函數(shù).void PRINT （int &n）（三）各函數(shù)的詳細(xì)設(shè)計(jì) :void InitialFamily（FNODE * head） /家譜建立函數(shù) 1:首先建立當(dāng)前人的信息，將其左右結(jié)點(diǎn)置為空， 2：然后讓用戶確定其是否有配偶 ,如果沒(méi)有配偶 ,則當(dāng)前程序結(jié)束， 3：如果有則建立其配偶信息，并將配偶結(jié)點(diǎn)賦給當(dāng)前人的左結(jié)點(diǎn)； 4：再讓用戶確定其是否有子女 ,如果有則遞歸調(diào)用家譜建立函數(shù)建立子女結(jié)點(diǎn)，并將其賦 給配偶結(jié)點(diǎn)的下一個(gè)右結(jié)點(diǎn) .5：如無(wú)，則程序結(jié)束void PrintFamily （FNODE head） /家譜輸出函數(shù)

5、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)用輸出其子女信息，最后輸出a、 ”“）”；5:當(dāng)配偶結(jié)點(diǎn)為空時(shí)，則判斷其右結(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：如不然 ,則先后遞歸訪問(wèn)其左結(jié)點(diǎn) ,再不是則遞歸訪問(wèn)右

6、結(jié)點(diǎn)void FindSon （FNODE *b ，char p） /兒子查找函數(shù) 1：在家譜中定位到要查找的結(jié)點(diǎn)，如無(wú)則輸出“查找不到此人” 2：判斷其配偶結(jié)點(diǎn)與子女結(jié)點(diǎn)是否為空，為空則輸出“無(wú)子女” 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)棧為空時(shí)程序結(jié)束， 3：棧不為空時(shí)，判斷棧頂元素是否已訪問(wèn)過(guò),4:訪問(wèn)過(guò)，再判斷是否為查找結(jié)點(diǎn)，如是則輸出棧中保存的其祖先結(jié)點(diǎn)，并濾過(guò)其兄弟結(jié)

7、點(diǎn)不輸出；不是查找結(jié)點(diǎn) ,則退棧一個(gè)元素5：未訪問(wèn)過(guò) ,則取當(dāng)前棧頂元素，置訪問(wèn)標(biāo)志- 1，同時(shí)取其右結(jié)點(diǎn)6：棧不為空或當(dāng)前所取結(jié)點(diǎn)不為空時(shí)，轉(zhuǎn)到2；實(shí)驗(yàn)測(cè)試結(jié)果及結(jié)果分析曰JREC(略)電fDebugE;sLf（二）結(jié)果分析（一）測(cè)試結(jié)果error(sK編譯/調(diào)試査找;I家詣he辭宙文件jfi輯章若ffiA工程(Globals)卡團(tuán)家classesj ClassVJBB區(qū)FiltW巳w實(shí)驗(yàn)總結(jié)（略）附錄 實(shí)驗(yàn)程序代碼（該部分請(qǐng)加注釋 ）/* 程序定義部分： / include include #include string.h define MAX 20 typedef struct SNO

8、DE char name MAX;/人名struct SNODE *left ；/ 指向配偶結(jié)點(diǎn)struct SNODE right;/指向兄弟或子女結(jié)點(diǎn)FNODE ；/* 家譜建立函數(shù) /void InitialFamily （ FNODE * head） FNODE *s ，*r, q;int tag ； q=（FNODE ） malloc（sizeof（FNODE） ）； q=NULL;s=（FNODE *）malloc（sizeof （FNODE ）； printf（ 輸”入姓名 n” ）;scanf（ %s ， s name） ;s-left=s-right=NULL;head=r=

9、s;printf （%s 是否有配偶 ?有 1,無(wú) n” ,hea-d name）；/建立配偶結(jié)點(diǎn)scanf（ %d”， tag）；if（tag ）s=（FNODE ） malloc （sizeof（FNODE ）; printf（ 輸入其配偶姓名： n”；） scanf（ ” s， s name） ;sleft=s- right=NULL; r left=s;r=s;do/遞歸調(diào)用建立孩子結(jié)點(diǎn)printf（%s 是否還有子女？有 1,無(wú) 0n ，head-name）； scanf（ ” %d” ,&tag）;if（tag）InitialFamily （ q）；r-right=q; r=q;w

10、hile(tag) ；/ 家譜輸出部分 */void PrintFamily(FNODE head)FNODE s； if(head!=NULL )printf ( ” %s，”head name) ; if(head left ！=NULL) s=head left;printf (”和 %s(,s name)； PrintFamily ( s right ); printf( ”)；) ”if ( head right!=NULL )printf ( ， ”) ;PrintFamily ( head right )；/ 結(jié)點(diǎn)定位函數(shù) /FNODE *findnode(FNODE *b,ch

11、ar p )FNODE *q ；if(b=NULL )return NULL ；else if ( !strcmp ( b name， p) return b ；elseq=findnode ( b- left ，p)；if(q ！=NULL ) return q ； else return( findnode ( b-right ，/不為空時(shí)輸出當(dāng)前結(jié)點(diǎn)/輸出配偶結(jié)點(diǎn)/遞歸調(diào)用輸出孩子結(jié)點(diǎn)/遞歸調(diào)用輸出兄弟結(jié)點(diǎn)/在家譜中定位所要查找結(jié)點(diǎn))/ 如果與查找人名相同則返回該結(jié)點(diǎn)/否則遞歸調(diào)用其左結(jié)點(diǎn)p) ; /遞歸調(diào)用右結(jié)點(diǎn)/* 兒子查找函數(shù) */void FindSon(FNODE b,char

12、 p)FNODE *q; q=findnode(b,p); if(q!=NULL )/存在孩子結(jié)點(diǎn)時(shí)輸出q=q- left;if (q=NULL | q right=NULL )/判斷有無(wú)子女printf( %s 沒(méi)有子女！ n,p ) ;else/輸出則配偶結(jié)點(diǎn)的所有子女結(jié)點(diǎn)q=q-right ；printf (” %子女為：”；while(q ！ =NULL )printf( ”s ” -,q name) ； q=qright；printf (”n)；elseprintf( 不存在你要查找的人 !n)；/祖先查找函數(shù) /int FindAncestor ( FNODE head， char

13、 son)FNODE p,s；FNODE *stack MAX ；int tag MAX ；int top= 1,i；p=findnode(head,son)；/定位結(jié)點(diǎn)if( p=NULL ) printf (不存在你要查找的人！n);return 0 ； s=head； dowhile(s ！=NULL)/將其所有左結(jié)點(diǎn)進(jìn)棧top+;stacktop=s;tagtop=0;s=s left ；if（ top 1）if（tagtop =1）/被訪問(wèn)過(guò)時(shí)if （ stack top=p）/如果為所查找結(jié)點(diǎn)時(shí)輸出祖先printf （ %s 祖先為： n ， son）； for（i=0 ；i to

14、p;i+ ）if（stacki right=stacki+1 ） /將其兄弟結(jié)點(diǎn)刪除，只保留父母 結(jié)點(diǎn)i+;if（i top）/依次輸出夫妻結(jié)點(diǎn)printf（ ”s， stack i name） ;i+;if （ iname）;break；top- ；else/未訪問(wèn)過(guò)則訪問(wèn)其右結(jié)點(diǎn)并置訪問(wèn)標(biāo)志s=stack top;if（top0 ）s=s-right ； tagtop =1;while（s ! =NULL | top! =-1）;if（top=-1 ）printf（查找不到 s的祖先！ n” ,p）;else printf （ n）;return 1 ；/* 選擇界面函數(shù)部分 ： /voi

15、d PRINT （int &n ）do printf (請(qǐng)選擇：n”)；printf (1 :建立家譜 n ”)printf(:” 輸出家譜 n);printf(: ”查找某人所有兒子n ”)；printf (”查找某人所有的祖先n);scanf( % d ”，&n); while (n0| | n4);/ *主函數(shù)部分：調(diào)用選擇界面函數(shù)，再依據(jù)用戶的選擇，調(diào)用相應(yīng)函數(shù)，實(shí)現(xiàn)相關(guān)功能*/void main()FNODE * head;int n=0 ;char nameMAX;head=NULL ;doPRINT(n );switch (n)case 1: InitialFamily (head); break;case 2： PrintFamily (head); printf (n) ;break;case 3: printf(請(qǐng)輸入要查找的姓名:n);scanf( ” s”ame);FindSon(head,name);break ;case 4： printf(請(qǐng)輸入要查找的姓名n ”；)scanf (% s”，name);n=FindAncestor (head,name);printf (”n)