课程设计报告课程设计名称：数据结构系：三系学生姓名：***班级：10计本2学号：***********成绩：指导教师：**开课时间：2011-2012 学年1 学期一．设计题目家谱的设计与实现（树，查找）二．主要内容家谱的设计主要是实现对家庭成员信息的建立、查找、插入、修改、删除等功能。
可。
基本功能如下：（1）家谱祖先数据的录入（树的根结点）。
（2）家庭成员的添加：即添加某一人的儿女，儿女的数目由控制台端给出，然后输入相应的儿女姓名（此处儿女的姓名不能重名）。
（3）家庭成员的修改：可以修改某一成员的姓名。
（4）家庭成员的查询：查询某一成员在家族中的辈分（第几代），并能查询此成员的所有子女及这一辈的所有成员。
（5）家庭成员的删除：删除此成员时，若其有后代，将删除其所有后代成员。
三．课题设计的基本思想，原理和算法描述1.基本思想此课题使用的数据结构为树形结构，为使结构整洁清晰在此使用二叉树结构，其中data 存储结构中包含以下信息：姓名、性别、代目。
而二叉树结构中l为直系成员，m为旁系成员（即配偶）。
lchild指针指向其的兄弟，rchild指向孩子，实现功能的具体代码如下：typedef struct node{ //定义data存储结构char name[STA]; //姓名char sex; //性别int generation;//代目}node;typedef struct ft{struct node l; //家谱中直系成员struct node m; //家谱中旁系成员struct ft *lchild;//用来指向兄弟struct ft *rchild;//用来指向孩子}ft;2.输出界面：实现其功能的代码见源程序及注释。
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.删除成员及其孩子思想，包含以下几个函数：主要功能函数：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 <stdio.h>#include <malloc.h>#include <stdlib.h>#include <string>#define STA 10typedef struct node{ //定义data存储结构char name[STA]; //姓名char sex; //性别int generation;//代目}node;typedef struct ft{struct 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->,ch)==0||strcmpi(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){if(p==NULL) return NULL;//没有家谱，头指针下为空if(p->rchild==NULL) {flag=0;return NULL;}else{if(p->lchild==q){*flag=1;return p;}else if(p->rchild==q){*flag=-1;return p;}else{if(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->,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) return q->l.generation;}return NULL;}void savep(ft *p,char b[],char c,int d)//建立家谱配偶节点{for(int i=0;i<STA;i++)p->[i]=b[i];p->m.sex=c;p->m.generation=d;}void saves(ft *p,char b[],char c,int d)//建立家谱孩子结点{for(int i=0;i<STA;i++)p->[i]=b[i];p->l.sex=c;p->l.generation=d;p->[0]='\0';}void disp(ft *n){ft *t=NULL;printf("此人姓名:%s 性别%c 为第%d代\n",n->,n->l.sex,n->l.generation);printf("此人的配偶:");printf("%s\n",n->);printf("此人的孩子:");if(n->rchild==NULL);else if(n->rchild->lchild==NULL)printf("%s %c\t",n->rchild->,n->rchil d->l.sex);else{printf("%s %c\t",n->rchild->,n->rchil d->l.sex);t=n->rchild->lchild;while(t!=NULL){printf("%s %c\t",t->,t->l.sex);t=t->lchild;}}printf("\n");}void Reset(){system("cls");char b[STA],c;int a;printf("┏━━━━━━━━━━━━┓\n");printf("┃初始化家谱... ┃\n");printf("┃建立家谱的第一代人┃\n");printf("┃输入姓名(不超过10个字符)┃\n");printf("┃及性别[M/F（男/女)] ┃\n");printf("┃如：XX M(姓名为XX性别男)┃\n");printf("┃┃\n");printf("┃家谱bata1.0┃\n");printf("┗━━━━━━━━━━━━┛\n");printf("请输入:");free(root);root=(ft *)malloc(sizeof(ft));scanf("%s %c",&b,&c);a=1;//输入姓名，性别root->rchild=NULL;root->lchild=NULL;saves(root,b,c,a);//存入结构system("cls");printf("初始化成功!\n");}void Manu(){printf("┏━━━━━━━━━━━━┓\n");printf("┃选择操作: ┃\n");printf("┣━━━━━━━┓0.退出┃\n");printf("┃家谱┃1.输入┃\n");printf("┃版本:bata1.0 ┃2.查找┃\n");printf("┃(C)2011 SQ Co.┃3.修改┃\n");printf("┃三系计本团队┃4.删除┃\n");printf("┃保留所有权利┃5.初始化┃\n");printf("┗━━━━━━━┻━━━━┛\n");}void Add(){ft *n,*m,*t=NULL;char b[STA],c,d[STA];int i;getchar();printf("请输入相关人姓名:\n");//判断是否有重名scanf("%s",&d);n=search(root,d);int a=generation(root,d);while(n==NULL){printf("此人不存在,请输入姓名:\n");getchar();scanf("%s",&d);n=search(root,d);}printf("选择家庭成员类别:(1.配偶 2.孩子)\n");scanf("%d",&i);if(i==1){getchar();printf("配偶输入:\n");scanf("%s %c",&b,&c);m=search(root,b);if(m!=NULL) printf("出现重名，请在姓名后标记后再输入\n");else savep(n,b,c,a);printf("操作结束!\n");}else//i=2孩子{getchar();if(n->rchild==NULL){printf("孩子输入:\n");scanf("%s %c",&b,&c);a++;m=search(root,b);if(m!=NULL) printf("出现重名，请在姓名后标记后再输入\n");else{n->rchild=(ft*)malloc(sizeof(ft));n->rchild->lchild=NULL;n->rchild->rchild=NULL;saves(n->rchild,b,c,a);}printf("操作结束!\n");}else{n=n->rchild;while(n->lchild!=NULL)n=n->lchild;printf("孩子输入:\n");scanf("%s %c",&b,&c);a++;m=search(root,b);if(m!=NULL) printf("出现重名，请在姓名后标记后再输入\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 d[STA];getchar();printf("输入姓名，查找相关信息:\n");scanf("%s",&d);n=search(root,d);while(n==NULL){printf("此人不存在，请再次输入:\n");getchar();scanf("%s",&d);n=search(root,d);}disp(n);}void Change(){getchar();char a[STA],r[STA],c;ft *n;printf("*注：修改配偶可直接在输入中覆盖\n");printf("请输入要修改的相关人姓名:");scanf("%s",&a);n=search(root,a);while(n==NULL){printf("此人不存在,请输入姓名:\n");getchar();scanf("%s",&a);n=search(root,a);}printf("请更改:");scanf("%s %c",&r,&c);for(int i=0;i<STA;i++)n->[i]=r[i];n->l.sex=c;printf("修改成功!\n");}void Del(){getchar();ft *n,*m;int flag;char d[STA],a[STA];printf("请输入要删除的相关人姓名:");scanf("%s",&a);n=search(root,a);while(n==NULL){printf("此人不存在\n");goto sd;}disp(n);printf("确定删除此人及其后代？(确定请输入[OK]):");scanf("%s",&d);if(strcmpi(d,"OK")==0){m=parent(root,n,&flag);if(flag>0)m->lchild=n->lchild;else if(flag<0)m->rchild=n->lchild;elseprintf("家谱为空或此人为头结点，无法删除！");}else{printf("操作取消！\n");}sd: printf("结束操作！\n"); }int main(){Reset();for(;;){system("pause");system("cls");Manu();int choice;scanf("%d",&choice);switch(choice){case 0:exit(0); break;case 1:Add(); break;case 2:Search();break;case 3:Change();break;case 4:Del(); break;case 5:Reset(); break;}}return 0;}五、运行示例及结果分析1.建立二叉树模型：2.操作截图：A配偶:B二代：C二代：D 三代：F三代：G二代：E并依次添加成员E，F，G。