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

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

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

3、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é)點定位函數(shù) :在家譜中找到用戶輸入人名所對應(yīng)的結(jié)點。FNODE findnode（FNODE *b,char p ） /結(jié)點定位函

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

5、1：首先判斷當(dāng)前結(jié)點是否為空，如果為空則結(jié)束程序;2：如果不為空，則輸出當(dāng)前結(jié)點信息， 3：然后判斷其左結(jié)點（配偶結(jié)點）是否為空，如不為空則輸出“和配偶信息。 4：再判斷配偶結(jié)點的右結(jié)點是否為空，如不為空則遞歸調(diào)用輸出其子女信息，最后輸出a、 ”“）”；5:當(dāng)配偶結(jié)點為空時，則判斷其右結(jié)點（兄弟結(jié)點 ）是否為空6：如果不為空 ,則輸出“，” ,并遞歸調(diào)用輸出兄弟信息7 程序結(jié)束FNODE *findnode（FNODE *b ，char p） /結(jié)點定位函數(shù) 1：當(dāng)前結(jié)點是否為空 ,為空則返回空；2:如果和查找信息相同，則返回當(dāng)前結(jié)點；3：如不然 ,則先后遞歸訪問其左結(jié)點 ,再不是則遞歸訪問右

6、結(jié)點void FindSon （FNODE *b ，char p） /兒子查找函數(shù) 1：在家譜中定位到要查找的結(jié)點，如無則輸出“查找不到此人” 2：判斷其配偶結(jié)點與子女結(jié)點是否為空，為空則輸出“無子女” 3：不為空則輸出其配偶結(jié)點的所有右結(jié)點（子女結(jié)點）。int FindAncestor （ FNODE *head,char son ） /祖先查找函數(shù) 1：先在家譜中定位到要查找的結(jié)點 ,如為空輸出“不存在此人” ，程序結(jié)束 2:先將父母結(jié)點入棧 ,當(dāng)棧為空時程序結(jié)束， 3：棧不為空時，判斷棧頂元素是否已訪問過,4:訪問過，再判斷是否為查找結(jié)點，如是則輸出棧中保存的其祖先結(jié)點，并濾過其兄弟結(jié)

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

8、DE char name MAX;/人名struct SNODE *left ；/ 指向配偶結(jié)點struct SNODE right;/指向兄弟或子女結(jié)點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,無 n” ,hea-d name）；/建立配偶結(jié)點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é)點printf（%s 是否還有子女？有 1,無 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é)點定位函數(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 ，/不為空時輸出當(dāng)前結(jié)點/輸出配偶結(jié)點/遞歸調(diào)用輸出孩子結(jié)點/遞歸調(diào)用輸出兄弟結(jié)點/在家譜中定位所要查找結(jié)點)/ 如果與查找人名相同則返回該結(jié)點/否則遞歸調(diào)用其左結(jié)點p) ; /遞歸調(diào)用右結(jié)點/* 兒子查找函數(shù) */void FindSon(FNODE b,char

12、 p)FNODE *q; q=findnode(b,p); if(q!=NULL )/存在孩子結(jié)點時輸出q=q- left;if (q=NULL | q right=NULL )/判斷有無子女printf( %s 沒有子女！ n,p ) ;else/輸出則配偶結(jié)點的所有子女結(jié)點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é)點if( p=NULL ) printf (不存在你要查找的人！n);return 0 ； s=head； dowhile(s ！=NULL)/將其所有左結(jié)點進棧top+;stacktop=s;tagtop=0;s=s left ；if（ top 1）if（tagtop =1）/被訪問過時if （ stack top=p）/如果為所查找結(jié)點時輸出祖先printf （ %s 祖先為： n ， son）； for（i=0 ；i to

14、p;i+ ）if（stacki right=stacki+1 ） /將其兄弟結(jié)點刪除，只保留父母 結(jié)點i+;if（i top）/依次輸出夫妻結(jié)點printf（ ”s， stack i name） ;i+;if （ iname）;break；top- ；else/未訪問過則訪問其右結(jié)點并置訪問標(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 (請選擇：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ù)，實現(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(請輸入要查找的姓名:n);scanf( ” s”ame);FindSon(head,name);break ;case 4： printf(請輸入要查找的姓名n ”；)scanf (% s”，name);n=FindAncestor (head,name);printf (”n)