數(shù)據(jù)結構家譜課程設計報告

1、精選文檔 家譜管理系統(tǒng) 姓名：田鑫磊學號：1514020421(1)功能部分：本程序共實現(xiàn)了6個功能分別為：1. 讀出家譜并顯示 2. 確定指定成員在家族中的輩份3. 輸出指定輩的所有成員4. 在家譜中添加新成員，并追加到文件中5. 輸出指定家庭的所有成員6. 退出本系統(tǒng)(2)各功能的算法思想：1. 讀出家譜并顯示 存儲結構用棧，按照先顯示雙親，然后顯示其所有孩子的順序顯示所有的家庭成員。2. 確定指定成員在家族中的輩份用求成員所在的二叉樹中的層數(shù)（按層遍歷二叉樹）來確定，這里采用的是遞歸算法3. 輸出指定輩的所有成員此處定義了一個新的結構體類型（增加存儲節(jié)點所在的層數(shù)），定義如下： stru

2、ct BTNode *q; int loc; /存結點所在的層數(shù)qu10; 并用一個隊列來比較顯示同輩分的所有成員。4. 在家譜中添加新成員，并追加到文件中首先，輸入一個新成員的名字；然后，輸入其雙親；之后，再添加到整個存儲二叉鏈表中。然后，再將新的存儲結構寫回到文件中。二叉鏈表的結點類型為：typedef struct node ElemType data10; /存放成員的名字 struct node *child; /其孩子指針 struct node *brother; /其兄弟指針 BTNode;5. 輸出指定家庭的所有成員首先，設一個棧，并設一個標記位，先置1；然后，找到輸入的要待

3、顯示的成員，將標記位置0；再次，顯示其孩子和兄弟，依次下去直到顯示完其所有的親戚。6. 退出本系統(tǒng)通過一個輸入字符q來控制，每完成一個功能，系統(tǒng)提示是否要繼續(xù)操作：當q為“Y”或者“y”時，顯示菜單，程序繼續(xù)執(zhí)行；當q為其他字符時，程序執(zhí)行結束，退出本系統(tǒng)。三、詳細設計：通過一個do-while語句來控制各個模塊的選擇和實現(xiàn)。1. 讀出家譜并顯示void display(BTNode *b) BTNode *q10; /定義一個棧 int front,rear; int k; BTNode *p; p=b;k=0; front=-1;rear=0; qrear=p; /頭結點先入棧 while

4、(front<rear) front+; p=qfront; printf("%s",p->data ); /頭結點出棧，并顯示 printf("("); disbr(p->child); printf(")n"); if(p->child!=NULL) /顯示其孩子 rear+;qrear=p->child; if(p->brother!=NULL) /顯示其兄弟 rear+;qrear=p->brother; 2. 確定指定成員在家族中的輩分int generation(BTNode *b

5、,int h,ElemType x)/用遞歸的思想 int i; if(b=NULL) return(0); i=strcmp(b->data,x); /比較是否相等 if(i=0) return(h); int L=generation(b->child,h+1,x); if(L=0) L=generation(b->brother,h,x); return(L);3.輸出指定輩的所有成員void layer(BTNode *t,int m) struct /定義一個新的結點類型，在孩子兄弟存儲結構的基礎上添加一個數(shù)據(jù)域存其所在層數(shù) BTNode *q; int loc;q

6、u10; int front,rear; BTNode *p; p=t;k=0; front=-1;rear=0; qurear.q=p; qurear.loc=1; if( qurear.loc=m) /找到m輩的即輸出 printf("%c",p->data); while(front<rear) /通過站查找所有m輩的結點并輸出 front+; p=qufront.q; if(p->child!=NULL) rear+;qurear.q=p->child; qurear.loc=qufront.loc+1; if(m= qurear.loc)

7、printf("%s ",p->child->data); if(p->brother!=NULL) rear+;qurear.q=p->brother; qurear.loc=qufront.loc; if( qurear.loc=m) printf("%s ",p->brother->data); 4.在家譜中添加新成員，并追加到文件中void add(BTNode *&b,ElemType y,ElemType x)char filename20=" "FILE *fp;BTNode

8、*p,*q;int i;p=FindNode(b,y);q=(BTNode *)malloc(sizeof(BTNode);for(i=0;xi!='0'i+)q->datai=xi;q->datai='0'q->child=q->brother=NULL;if(p->child =NULL)p->child=q;else p=p->child;while(p->brother!=NULL)p=p->brother ; p->brother=q; display(b);printf("向文件中

9、讀入新家譜n"); printf("n input a filename:"); scanf("%s",&filename);if(fp=fopen(filename,"w")=NULL) puts("n can't open the file.");exit(0);else DispBTNode(b,fp);fclose (fp);void DispBTNode(BTNode *b,FILE *fp)char a10;int i=0;if(b!=NULL) while(b->dat

10、ai!='0') ai=b->datai; i+; ai='0' fputs(a,fp); /寫入文件if(b->child!=NULL | b->brother!=NULL)fputs(s,fp);DispBTNode(b->child,fp); /遞歸寫入其孩子if (b->brother!=NULL) fputs(p,fp); DispBTNode(b->brother,fp); /遞歸寫入其兄弟fputs(t,fp); 5.輸出指定家庭的所有成員void dispfamily(BTNode *b,ElemType x)

11、 BTNode *p;BTNode *qMaxSize;int top=-1,tap=1;if(b!=NULL) top+; qtop=b; while(top>-1) p=qtop; top-; if(strcmp(p->data,x)=0) /查找此人 top=-1; tap=0; if(p->child!=NULL) top+; qtop=p->child; if(tap=0) display(p->child); /顯示其孩子 return ; if(p->brother!=NULL) top+; qtop=p->brother; if(tap

12、=0) display(p->brother); /顯示其兄弟 return ; 6.退出本系統(tǒng)此處通過一個輸入字符q來控制，當q為“Y”或者“y”時，顯示菜單，程序繼續(xù)執(zhí)行，當q為其他字符時，程序執(zhí)行結束，退出本系統(tǒng)。此時q=N。四：調(diào)試分析1首先，將已有家譜存儲文件寫在一個txt文檔里，內(nèi)容為：輸出結果為：2調(diào)試時遇到的問題：（1）當選擇功能3（添加新成員），添加完成員后，寫回文件時出現(xiàn)了錯誤，原本添加的為其中一個結點的孩子，結果寫回文件時卻成了該結點的孫子，也就是本是要添加為此結點的孩子的兄弟，結果卻成了其孩子的孩子。最后經(jīng)過單步跟蹤發(fā)現(xiàn)寫入文件的函數(shù)編寫錯誤，缺少判斷條件，經(jīng)過修改后，此問題得到了解決。（2）當選擇功能0（顯示此家譜），沒有按照事先存儲在txt中的文件顯示，通過認真檢查程序中顯示成員的函數(shù)（按層遍歷）、不斷調(diào)試，發(fā)現(xiàn)并不是該顯示函數(shù)的錯誤，因為在功能4（輸出指定家庭的所有成員）中，也是通過調(diào)用該函數(shù)實現(xiàn)輸出功能，于是，檢查txt文件中事先存儲的家譜成員，發(fā)現(xiàn)是由于“（”與“）”沒有匹配好，導致沒有按照預期想法創(chuàng)建二叉樹造成的錯誤，通過修改txt文件，使得錯誤得以解決。五、課程設計總結 通過本次課程設計，我覺得自己最大的收獲就是：由于對二叉鏈表的存儲比較感興趣，我選做的是家譜，開始覺得無從下手，但是經(jīng)過仔細分析后