家譜的實(shí)現(xiàn)與設(shè)計(jì)

1、 課 程 設(shè) 計(jì) 報(bào) 告課程設(shè)計(jì)名稱：數(shù)據(jù)結(jié)構(gòu)課程設(shè)計(jì) 系 ： 三系 學(xué) 生 姓 名 ： 朱強(qiáng) 班 級(jí)： 13軟件 學(xué) 號(hào)： 20130311227 成 績(jī)： 指 導(dǎo) 教 師： 劉杰 開(kāi) 課 時(shí) 間：2014-2015學(xué)年一學(xué)期設(shè)計(jì)題目一：家譜的實(shí)現(xiàn)與設(shè)計(jì)一、 實(shí)習(xí)目的 通過(guò)學(xué)習(xí)，了解并初步掌握設(shè)計(jì)、實(shí)現(xiàn)較大系統(tǒng)的完整過(guò)程，包括系統(tǒng)分析、編碼設(shè)計(jì)、編碼集成以及調(diào)試分析，熟練掌握數(shù)據(jù)結(jié)構(gòu)的選擇、設(shè)計(jì)、實(shí)現(xiàn)、以及操作方法，為進(jìn)一步的開(kāi)發(fā)應(yīng)用打好基礎(chǔ)。二、 問(wèn)題描述家譜的設(shè)計(jì)主要是實(shí)現(xiàn)對(duì)家庭成員信息的建立、查找、插入、修改、刪除等功能。可?；竟δ苋缦拢海?）家譜祖先數(shù)據(jù)的錄入（樹(shù)的根結(jié)點(diǎn)）。（2）

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

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

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

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

6、h) / 搜索指針函數(shù)ft *q;if(p=NULL) return NULL;/沒(méi)有家譜，頭指針下為空if(strcmp(p->,ch)=0)return p;/家譜不為空，頭指針下有這個(gè)人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;/沒(méi)有找到ft *parent(ft *p,ft *q,int *flag) /通過(guò)pare

7、nt函數(shù)得到雙親結(jié)點(diǎn)。用flag標(biāo)志，-1為左孩子，1為右孩子 if(p=NULL)return NULL; /沒(méi)有家譜，頭指針下為空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; /家譜不為空，頭指針下有這個(gè)人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) /建立家譜孩子結(jié)點(diǎn) 創(chuàng)建結(jié)點(diǎn)并對(duì)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("此人無(wú)子女!");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("此人無(wú)同輩成員!");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(" 請(qǐng)輸入始祖的姓名 性別:n"); printf("輸入姓名(不超過(guò)10個(gè)字符)n");printf("性別：M/F（男/女) n");printf("格式：XX M(姓名為XX性別男)n");free(root); /釋放root （ft） 空間root=(ft *)malloc(sizeof(ft); / 創(chuàng)建一個(gè)ft結(jié)構(gòu)體大小的空間 然后強(qiáng)制轉(zhuǎn)換為ft *類型的指針 然后賦值給root ,這時(shí) root指向一個(gè)struct di

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

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

16、;int a=generation(root,d);while(n=NULL)printf("此人不在家譜內(nèi),請(qǐng)重新輸入姓名: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("輸入姓名，查找相關(guān)信息:n");scanf("%s",&d);n=search(root,d);while(n=NULL)printf("

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

20、ot;此人存在，請(qǐng)輸入新信息:");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("請(qǐng)輸入要?jiǎng)h除人的姓名:");scanf("%s",a);n=search(root,a);while(n=NULL)printf("此人不存在,請(qǐng)

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;六、 測(cè)試分析建立一個(gè)家譜，輸入第一代人的姓名與性別以上為，在第一代aa下添加子女：bb、cc、dd，在第二代bb下添加子女ee、ff，在cc下添加子女gg修改bb為hh，修改gg為ii，查找一下，發(fā)現(xiàn)已修改成功刪除ee、hh，查找一下，aa子女hh、

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

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