课程设计报课程设计名称:数据结构系 ：三 系学生姓名：班级：10计本2学 号:成 绩：指导教师：开课时间：2011-2012学年1学期设计题目家谱的设计与实现（树，查找）二主要内容家谱的设计主要是实现对家庭成员信息的建立、查找、插入、修改、删除等功能。可。基本功能如下：（1）家谱祖先数据的录入（树的根结点）。（2）家庭成员的添加：即添加某一人的儿女，儿女的数目由控制台端给出，然后输入相应 的儿女姓名（此处儿女的姓名不能重名）。（3）家庭成员的修改：可以修改某一成员的姓名。（4）家庭成员的查询：查询某一成员在家族中的辈分（第几代），并能查询此成员的所有 子女及这一辈的所有成员。（5）家庭成员的删除：删除此成员时，若其有后代，将删除其所有后代成员。三.课题设计的基本思想，原理和算法描述1.基本思想此课题使用的数据结构为树形结构，为使结构整洁清晰在此使用二叉树结构，其中data 存储结构中包含以下信息：姓名、性别、代目。而二叉树结构中1为直系成员，m为旁系成 员（即配偶）。lchild指针指向其的兄弟，rchild指向孩子，实现功能的具体代码如下：ty pedef st rue t node /定义 data 存struct node l;/家谱中直系成储结构员charnameSTA; /姓名struct node m;/家谱中旁系成charsex;/性别员intgenera tio n;/代目struct ft *lchild;/用来指向兄弟node;struct ft *rchild;/用来指向孩子ft; typedef struet ft2.输出界面:实现其功能的代码见源程序及注释。回. 15書-.旳 a 1 2 3 4 5C:User3Di euDe-sktn.3. 输入信息 通过搜索结点直接赋值，包含以下几个函数：(1) 主要功能函数：void Add()在主函数中直接调用。下面四个函数为其子函数。(2) 搜索指针函数： ft *search(ft *p,char ch) 搜索需要改动的结点。( 3)获得代目函数： int generation(ft *p,char ch) 获得搜索到的成员的代目的返回值。( 4)存储孩子函数： void saves(ft *p,char b,char c,int d) 创建结点并对 l 赋值。 思路如下：如该结点没有右孩子则直接创建右孩子结点，如果存在右孩子则对右孩子创 建左孩子，作为兄弟结点，如此循环。( 5)存储配偶函数： void savep(ft *p,char b,char c,int d) 直接对 m 成员赋值 详细代码见源程序及注释。4. 输出结点信息 通过搜索结点获得数据后输出，包含以下几个函数：(1) 主要功能函数： void Search() 在主函数中直接调用。下面两个函数为其子函数。(2) 搜索指针函数： ft *search(ft *p,char ch) 搜索需要获得的结点。(3) 输出数据函数： void disp(ft *n) 对搜索到数据的输出 详细代码见源程序及注释。5. 修改成员姓名 通过搜索结点获得数据后修改，包含以下几个函数：(1) 主要功能函数： void Change() 在主函数中直接调用。下面两个函数为其子函数。(2) 搜索指针函数： ft *search(ft *p,char ch) 搜索需要修改的结点，然后直接赋值修改6. 删除成员及其孩子二代三代C三代：E此功能在二叉树结构中实现需要用到如下思想，包含以下几个函数：主要功能函数： void Del()搜索指针函数： ft *search(ft *p,char ch)搜索双亲函数： ft *parent(ft *p,ft *q,int *flag) 删除A则只需用free(root)函数初始化；删除 结点则需要知道结点在二叉树的位置，通过parent函数得到双亲结点。用flag标志，-1为左孩子，1为右孩子。如删除B,则通过parent函数得到A结点，flag标志为1,进行如下操作：B的rchild指针指向NULL, A的rchild指向C,即A-rchild=B-lchild ；如删除C或E,则可直接使B或D的lchild值等于C或E的lchild, rchild指向NULL即可。具体代码见源程序及注解。四源程序及注释#include #include #include #include #define STA 10 typedef struct node /定义 data 存储结构char nameSTA; /姓名char sex;/性别intgen era tion; 代目node;typedef struct ftstruct node l;/家谱中直系家属struct node m;/家谱中旁系家属struct ft *lchild;用来指向兄弟 struct ft *rchild;用来指向孩子ft;ft *root;ft *search(ft *p,char ch) 输入头指针，姓名 ft *q;if(p=NULL) return NULL;/没有家谱，头 指针下为空if(strcmpi(p-l.name,ch)=0|strcmpi(p- m.n ame,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)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,*&flag);int generation(ft *p,char ch)ft *q;if(p=NULL) return NULL;if(strcmpi(p-l.name,ch)=0)returnp-l.ge neratio n;家谱不为空，头指针下有这 个人if(p-lchild)q=search(p-lchild,ch);/ 在做孩子中找if(q) retur n q-l.ge nera tion; /找到if(p-rchild)q=search(p-rchild,ch);/ 在右孩子中 找if(q!=NULL) return q-l.generation;t=t-lchild;return NULL;I初始化家谱II建立家谱的第一代人II输入姓名（不超过10个字符）II及性别M/F （男/女）II如：XX M（姓名为XX性别男）|III家谱 bata1.0Iprintf(%s %ct,t-l.name,t-l.sex);printf( rvoid savep(ft *p,char b,char c,int d)/ 建立家 谱配偶节点for(int i=0;im.namei=bi;p-m.sex=c;p-m.generation=d;void saves(ft *p,char b,char c,int d)建立家 谱孩子结点for(int i=0;il.namei=bi;p-l.sex=c;p-l.generation=d; p-m.name0=0;void disp(ft *n)ft *t=NULL;printf(此人姓名:%s性别%c为第%d代 n,n-l.name,n-l.sex,n-l.generation);pri ntf(此人的配偶:)； printf(%sn,n-m.name);pri ntf(此人的孩子:)； if(n-rchild=NULL)； else if(n-rchild-lchild=NULL) printf(%s %ct,n-rchild-l.name,n-rchil d-l.sex)；elseprintf(%s %ct,n-rchild-l.name,n-rchil d-l.sex)；t=n-rchild-lchild； while(t!=NULL)printf(n)；void Reset()system(cls)；char bSTA,c；int a；printf(n)；printf(n)；printf(n)；printf(n)；printf(n)；printf(n)；printf(n)；printf(n)；printf(n)；pri ntf(请输入:)；free(root)；root=(ft *)malloc(sizeof(ft)；sca nf(%s %c,&b,&c);a=1; 输入姓名，性 别root-rchild=NULL； root-lchild=NULL； saves(root,b,c,a);/存 入结构 system(cls)； prin tf(初始化成功!n);void Manu()n);printf( |选择操作：In);printf( |1 0.退出 |n);printf( | 家谱| 1.输入 |n);printf( | 版本:batal.O | 2.查找 |n);printf(| (C)2011 SQ Co.| 3.修改 |n);printf( |三系计本团队| 4.删除|n);p r i n tf( |保留所有权利 | 5.初始化| n);pri ntf( 111n);void Add() ft *n,*m,*t=NULL;char bSTA,