家譜的實現(xiàn)與設計

1、 課 程 設 計 報 告課程設計名稱：數(shù)據(jù)結構課程設計 系 ： 三系 學 生 姓 名 ： 朱強 班 級： 13軟件 學 號： 20130311227 成 績： 指 導 教 師： 劉杰 開 課 時 間：2014-2015學年一學期設計題目一：家譜的實現(xiàn)與設計一、 實習目的 通過學習，了解并初步掌握設計、實現(xiàn)較大系統(tǒng)的完整過程，包括系統(tǒng)分析、編碼設計、編碼集成以及調試分析，熟練掌握數(shù)據(jù)結構的選擇、設計、實現(xiàn)、以及操作方法，為進一步的開發(fā)應用打好基礎。二、 問題描述家譜的設計主要是實現(xiàn)對家庭成員信息的建立、查找、插入、修改、刪除等功能?？?。基本功能如下：（1）家譜祖先數(shù)據(jù)的錄入（樹的根結點）。（2）

2、家庭成員的添加：即添加某一人的兒女，兒女的數(shù)目由控制臺端給出，然后輸入相應的兒女姓名（此處兒女的姓名不能重名）。（3）家庭成員的修改：可以修改某一成員的姓名。（4）員的查詢：查詢某一成員在家族中的輩分（第幾代），并能查詢此成員的所有子女及這一輩的所有成員。（5）家庭成員的刪除：刪除此成員時，若其有后代，將刪除其所有后代成員。三、 需求分析 該程序所做的工作是對家族成員的的管理，為家族成員對各代成員的姓名，性別及子女情況的記錄、查詢提供方便。此程序規(guī)定： 1.在姓名錄入時，姓名為10個字母以內的字符串；性別以M/F表示； 2.程序的輸出信息主要為：輸出家族成員在家族中的輩分（第幾代），并能查詢此

3、成員的所有子女及這一輩的所有成員。3.程序的功能主要包括：家譜祖先數(shù)據(jù)的錄入、家庭成員的添加、家庭成員的修改、員的查詢、家庭成員的刪除；四、 概要設計系統(tǒng)用到的數(shù)據(jù)有：char nameMAX; char sex; /int generation;1）typedef struct node /定義data存儲結構2）typedef struct ft /創(chuàng)建結構體3）ft *search(ft *p,char ch) / 搜索指針函數(shù)4）ft *parent(ft *p,ft *q,int *flag) /通過parent函數(shù)得到雙親結點。用flag標志，-1為左孩子，1為右孩子 5）int

4、generation(ft *p,char ch) / 獲得搜索到的成員的代目的返回值6）void saves(ft *p,char b,char c,int d) /建立家譜孩子結點 創(chuàng)建結點并對l賦值 保存7）void InitTree() /初始化8)void Add() /添加9)void Search() /查詢10)void Change() /修改11)void Delete() /刪除12)int main() /主函數(shù)各程序模塊之間的調用關系：主函數(shù)12）可以調用7）至11）。五、 詳細設計#include <stdio.h>#include <malloc

5、.h>#include <string>#include <stdlib.h>#define MAX 10 typedef struct node /定義data存儲結構char nameMAX; /姓名char sex; /性別int generation;/代目node;typedef struct ft /創(chuàng)建結構體struct node l; /家譜中直系家屬struct ft *lchild;/用來指向兄弟struct ft *rchild;/用來指向孩子ft;ft *root; /root是結構體ft的指針ft *search(ft *p,char c

6、h) / 搜索指針函數(shù)ft *q;if(p=NULL) return NULL;/沒有家譜，頭指針下為空if(strcmp(p->,ch)=0)return p;/家譜不為空，頭指針下有這個人if(p->lchild)q=search(p->lchild,ch);/在兄弟中找if(q) return q;/找到if(p->rchild)q=search(p->rchild,ch); /在孩子中找if(q!=NULL) return q; return NULL;/沒有找到ft *parent(ft *p,ft *q,int *flag) /通過pare

7、nt函數(shù)得到雙親結點。用flag標志，-1為左孩子，1為右孩子 if(p=NULL)return NULL; /沒有家譜，頭指針下為空if(p->rchild=NULL)*flag=0;return NULL;elseif(p->lchild=q)*flag=1;return p;else if(p->rchild=q)*flag=-1;return p;elseif(p->lchild!=NULL)parent(p->lchild,q,*&flag);if(p->rchild!=NULL)parent(p->rchild,q,*&fl

8、ag);int generation(ft *p,char ch) / 獲得搜索到的成員的代目的返回值ft *q;if(p=NULL) return NULL;if(strcmpi(p->,ch)=0) return p->l.generation; /家譜不為空，頭指針下有這個人if(p->lchild)q=search(p->lchild,ch); /在兄弟中找if(q) return q->l.generation; /找到if(p->rchild)q=search(p->rchild,ch); /在孩子中找if(q!=NULL) r

9、eturn q->l.generation;return NULL;void saves(ft *p,char b,char c,int d) /建立家譜孩子結點 創(chuàng)建結點并對l賦值 保存 for(int i=0;i<MAX;i+)p->i=bi; p->l.sex=c;p->l.generation=d;void disp(ft *n) /搜索到數(shù)據(jù)的輸出ft *t=NULL;printf("此人姓名:%s 性別%c 為第%d代n",n->,n->l.sex,n->l.generation); pri

10、ntf("n");printf("此人的子女:"); /子女輸出if(n->rchild=NULL)printf("此人無子女!");else if(n->rchild->lchild=NULL)printf("姓名:%s 性別:%ct",n->rchild->,n->rchild->l.sex); else printf("姓名:%s 性別:%ct",n->rchild->,n->rchild->l.se

11、x); t=n->rchild->lchild; while(t!=NULL) printf("姓名:%s 性別:%ct",t->,t->l.sex); t=t->lchild; printf("n"); printf("n"); printf("此人的同輩成員:"); /同輩輸出if(n->lchild=NULL)printf("此人無同輩成員!");else if(n->lchild->lchild=NULL)printf(&quo

12、t;姓名:%s 性別:%ct",n->lchild->,n->lchild->l.sex); else printf("姓名:%s 性別:%ct",n->lchild->,n->lchild->l.sex); t=n->lchild->lchild; while(t!=NULL) printf("姓名:%s 性別:%ct",t->,t->l.sex); t=t->lchild; printf("n");void

13、InitTree() /初始化char bMAX,c;int a;printf(" 請輸入始祖的姓名 性別:n"); printf("輸入姓名(不超過10個字符)n");printf("性別：M/F（男/女) n");printf("格式：XX M(姓名為XX性別男)n");free(root); /釋放root （ft） 空間root=(ft *)malloc(sizeof(ft); / 創(chuàng)建一個ft結構體大小的空間 然后強制轉換為ft *類型的指針 然后賦值給root ,這時 root指向一個struct di

14、ctree結構體大小的新空間 scanf("%s %c",&b,&c);a=1; /輸入姓名，性別root->rchild=NULL; /清空左右孩子root->lchild=NULL; saves(root,b,c,a); /存入結構printf("家譜重構成功!n");void Manu()printf(" *n");printf(" * 請選擇對家譜的操作: *n");printf(" * 0.退出 *n");printf(" * 1.添加 *n&qu

15、ot;);printf(" * 2.查找 *n");printf(" * 3.修改 *n");printf(" * 4.刪除 *n");printf(" * 5.重構 *n");printf(" *n");void Add() /添加ft *n,*m,*t=NULL; char bMAX,c,dMAX;int i;printf("請輸入要添加子女的上一輩的姓名:n"); /判斷是否有重名scanf("%s",&d);n=search(root,d)

16、;int a=generation(root,d);while(n=NULL)printf("此人不在家譜內,請重新輸入姓名:n");scanf("%s",&d);n=search(root,d); /孩子信息添加if(n->rchild=NULL) printf("孩子姓名與性別輸入:n");scanf("%s %c",&b,&c);a+;m=search(root,b);if(m!=NULL)printf("出現(xiàn)重名，添加失敗!n");else n->rc

17、hild=(ft *)malloc(sizeof(ft); n->rchild->lchild=NULL;n->rchild->rchild=NULL;saves(n->rchild,b,c,a); printf("添加成功!n");elsen=n->rchild;while(n->lchild!=NULL)n=n->lchild;printf("孩子姓名與性別輸入:n");scanf("%s %c",&b,&c);a+;m=search(root,b);if(m!=NU

18、LL) printf("出現(xiàn)重名，添加失敗!n");else t=(ft *)malloc(sizeof(ft);saves(t,b,c,a);t->lchild=NULL;t->rchild=NULL;n->lchild=t; printf("添加成功!n"); void Search() /查詢ft *n;char dMAX;printf("輸入姓名，查找相關信息:n");scanf("%s",&d);n=search(root,d);while(n=NULL)printf("

19、;此人不存在，請再次輸入:n");scanf("%s",&d);n=search(root,d);disp(n);void Change() /修改char aMAX,rMAX,c;ft *n;printf("請輸入要修改人的姓名:");scanf("%s",&a);n=search(root,a);while(n=NULL)printf("此人不存在,請重新輸入姓名:n"); scanf("%s",&a);n=search(root,a);printf(&qu

20、ot;此人存在，請輸入新信息:");scanf("%s %c",&r,&c);for(int i=0;i<MAX;i+)n->i=ri;n->l.sex=c;printf("修改成功!n");void Delete() /刪除ft *n,*m;int flag;char dMAX,aMAX;printf("請輸入要刪除人的姓名:");scanf("%s",a);n=search(root,a);while(n=NULL)printf("此人不存在,請

21、重新輸入姓名:n");scanf("%s",&a);n=search(root,a); printf("n"); printf("此人已找到!n"); printf("n");m=parent(root,n,&flag);if(flag>0)m->lchild=n->lchild; printf("刪除成功!n");else if(flag<0)m->rchild=n->lchild; printf("刪除成功!n"

22、;);else if (flag = 0)root->l.generation = NULL;root->l.sex = NULL;strcpy(root->, "");printf("刪除成功!n");int main()system("color 5a");InitTree();for(;)system("pause");system("cls");Manu();int choice; scanf("%d",&choice);swit

23、ch(choice)case 0:exit(0); break;/退出case 1:Add(); break;/添加case 2:Search(); break;/查找case 3:Change(); break;/修改case 4:Delete(); break;/刪除case 5:InitTree(); break;/初始化return 0;六、 測試分析建立一個家譜，輸入第一代人的姓名與性別以上為，在第一代aa下添加子女：bb、cc、dd，在第二代bb下添加子女ee、ff，在cc下添加子女gg修改bb為hh，修改gg為ii，查找一下，發(fā)現(xiàn)已修改成功刪除ee、hh，查找一下，aa子女hh、

24、bb子女ee本身及其子代已被刪除重構家譜，子女信息消除七、 使用說明 首先運行程序，包括六個選項：0.退出家譜系統(tǒng). 1.家族成員的添加 2. 家族成員的查找3.家族人員姓名及性別修改4.刪除家族成員信息. 5.重新建立新的家譜圖 然后可以根據(jù)不同的需要選擇不同的選項進行操作最后退出程序。八、 運行程序過程中產生的問題及采取的措施在調試時，遇到的幾個問題如下：（1）建立樹時，由于新申請結點的孩子指針、兄弟指針、及雙親指針均未賦空值。而在以后的函數(shù)中對樹進行遞歸操作時均以這些指針值中的一個或幾個是否為空作為遞歸結束條件。從而導致調用這些函數(shù)時出現(xiàn)系統(tǒng)保護異常（使用了不安全的指針）。（2）剛開始刪

25、除結點時，只考慮到刪除其本身結點的情況，而刪除其孩子結點的情況未考慮到，故在刪除某些結點時使樹出現(xiàn)了“斷鏈”現(xiàn)象。故在程序代碼中對刪除某一結點進行操作時，首先要判斷此結點是否有孩子及兄弟，然后進行相應操作。（3）剛開始進行程序概要設計時，曾考慮到用控制臺下的文本方式作為程序界面，實際操作后發(fā)現(xiàn)并不理想。一方面字符形式的界面友好性較差，另一方面顯示整個家譜樹的信息時不方便。故考慮用VC+中MFC 類自帶的樹型控件顯示家譜層次，而用列表控件顯示家譜中的信息。用后效果不錯。九、 總結和展望轉眼課程設計已經結束，從選擇任務到上網查找資料，到源代碼的完成，再到真正的代碼運行出來，我對數(shù)據(jù)結構課程設計有了更深的了解、對以前學過的知識進行了鞏固和提高。數(shù)據(jù)結構是計算機程序設計的重要理論技術基礎。這次課程設計運用C語言作為描述語言，對二叉樹和查找進行描述，這次任務提高了我們對實際問題的解決能力，即運用所學知識對問題進行分析：了解問題的基本要求，怎樣將實際問題轉化成學科問題的