数学与计算机学院课程设计说明书课程名称: 数据结构与算法课程设计课程代码:题目: 二叉树生成家谱年级/专业/班:学生姓名:学号:开始时间:2015 年12 月09 日完成时间:2015 年12 月29 日课程设计成绩：指导教师签名：年月日目录（小三黑体，居中）1 需求分析 (8)1.1任务与分析 (8)1.2测试数据 (9)2 概要设计 (9)2.1 ADT描述 (9)2.2程序模块结构 (10)2.3各功能模块 (12)3 详细设计 (14)3.1结构体定义 (14)3.2 初始化 (15)3.3 插入操作 (18)3.4 查询操作 (22)4 调试分析 (25)5 用户使用说明 (26)6 测试结果 (26)结论 (30)附录 (32)参考文献 (33)摘要随着计算机科学技术、计算机产业的迅速发展，计算机的应用普及也在以惊人的速度发展，计算机应用已经深入到人类社会的各个领域。
计算机的应用早已不限于科学计算，而更多地应用在信息处理方面。
计算机可以存储的数据对象不再是纯粹的数值，而扩展到了字符、声音、图像、表格等各种各样的信息。
对于信息的处理也不再是单纯的计算，而是一些如信息存储、信息检索等非数值的计算。
那么，现实世界的各种数据信息怎样才能够存储到计算机的存之中，对存入计算机的数据信息怎样进行科学处理，这涉及计算机科学的信息表示和算法设计问题。
为解决现实世界中某个复杂问题，总是希望设计一个高效适用的程序。
这就需要解决怎样合理地组织数据、建立合适的数据结构，怎样设计适用的算法，以提高程序执行的时间效率和空间效率。
“数据结构”就是在此背景下逐步形成、发展起来的。
在各种高级语言程序设计的基本训练中，解决某一实际问题的步骤一般是：分析实际问题；确定数学模型；编写程序；反复调试程序直至得到正确结果。
所谓数学模型一般指具体的数学公式、方程式等，如牛顿迭代法解方程，各种级数的计算等。
这属于数值计算的一类问题。
而现实生活中，更多的是非数值计算问题，如手机中的通讯录，人们对它的操作主要是查找、增加、删除或者修改记录。
再如，人们经常在互联网上查阅各种新闻，或查阅电子地图，人们可以在某城区地图上查找自己所需的街道或店铺，其操作主要是搜索和查询。
下面再来分析几个典型实例，它们的主要特点是：不同实例的数据元素之间存在不同的关系；对数据信息的处理主要有插入、删除、排序、检索等。
关键词：网络化；计算机；对策；二叉树引言课程设计的目的：通过本项课程设计，培养学生独立思考、综合运用所学有关相应知识的能力，使学生巩固《数据结构》课程学习的容，掌握工程软件设计的基本方法，强化上机动手编程能力，闯过理论与实践相结合的难关；为了培养学生综合运用所学知识、独立分析和解决实际问题的能力，培养创意识和创新能力，使学生获得科学研究的基础训练。
为后续各门计算机课程的学习和毕业设计打下坚实基础。
同时，可以利用这次机会来检验自己的c/c++/数据结构水平，提高自己的写作水平，锻炼自己的动手能力。
而此次课程设计的意义在于：增强自己的动手能力，熟悉和掌握二叉树各种遍历的算法，以及递归在遍历二叉树中的应用，增强自己的调试程序和测试程序的能力。
1 需求分析1.1任务与分析1.建立输入文件以存放最刜家谱中各成员的信息。
2.成员的信息中均应包含以下容：、出生日期、婚否、地址、健在否、死亡日期（若其已死亡）也可附加其它信息、但不是必需的。
3.能对修改后的家谱存盘以备以后使用。
4.能从文件中读出已有的家谱，形成树状关系。
5.家谱建立好之后，以图形方式显示出来。
6.显示第n 代所有人的信息。
7.按照查询，输出成员信息（包括其本人、父亲、孩子的信息）。
8.按照出生日期查询成员。
9.输入两人，确定其关系。
10.给某人添加孩子。
11.删除某人（若其还有后代，则一并删除）。
12.修改某人信息。
13.用括号法输出家谱成员信息1.2测试数据1 徐朝嬴 m 1938-1-20 1 代芳 0 此人相当的热心 02345 100002 徐廷文 m 1964-8-3 2 太群 1 此人相当有责任心 0 6 7 100003 徐素华 w 1966-4-6 2 奉光 1 此人很好0 100004 徐军华 m 1969-7-8 2 曲舞 1 此人很有正义感 0 100005 徐廷国 m 1972-9-2 2 木玛 1 此人心的很善良 0 100006 徐光勇 m 1989-1-27 3 Nomarry 2 此人很牛逼0 100007 徐光超 m 1992-9-5 3 Nomarry 2 此人亦很牛逼 0 100002 概要设计2.1 ADT描述1.ADT Person{数据对象：D={Pj | Pj={、出生日期、婚否、地址、健在否（如过世，还应有其死亡日期）}，j=0,1,2,…… n,其中n>=0}数据关系：R={} 基本操作：无。
}ADT Person2.ADT FamilytreeFile{数据对象：D={Aj | Aj 属于 Person,j=1,2,3，……,n 其中n>=1}数据关系：D 中每个对象用换行符隔开, R={ | Aj 属于D,j=1,2，3,……,n 其中n>=1,String 属于字符串类型，为 Aj 父亲(若String=-1,Aj 无父亲，若String=Aj 的,表示家谱文件结束)}基本操作： 1．打开家谱类型文件，并建立兄弟、孩子二叉树。
2．从存中读取兄弟、孩子二叉树，并建立家谱类型文件。
}ADT FamilytreeFlie3.ADT Familytree{数据对象：D={Aj | Aj 属于Person,j=1,2,3,……,n 其中n>=0}数据关系：V={ | Aj-1,Aj 属于D,j=2,3,……，n 其中n>=2，且Aj-1 与Aj 为祖先与后代关系（parent）、后代与祖先关系(child)、兄弟之间关系（sibling）}基本操作： 1．显示某人信息。
2．修改某人信息。
3．增加某人孩子。
4．删除某人。
5．通过某人查找其双亲、孩子、兄弟。
}ADT Familytree2.2程序模块结构2.2.1 结构体定义struct People //定义结构体People{int num;char name[20];char sex;char borndate[15];int generation;char matename[20];int parent;char infor[100];LinkList child;}；struct Node //定义结构体Node {int a;struct Node * next;}；struct LinkList //定义链表{NodePoint La;}；struct Tree //定义树PeoplePoint Tr; int Length;int TREE_INIT_SIZE; }；2.3 各功能模块void InitTree(Tree &TR);//在树已定义的情况下，初始化树TRLinkList InitLinkList(void);//在什么都没有的情况下，初始化一个带头结点的链表并返回链表Lvoid AddLinkList(LinkList p);//对带头结点的链表pl，添加一个节点为m的节点在表头void CreatFamilyTree(Tree &TR);//在什么都没有的情况下，创建一个家谱TR。
并返回TRvoid PrintPeople(PeoplePoint p);// 已知某节点的指针p，输出people p 的相关信息void PrintLinkList(LinkList p);//已知链表p，输出链表p中的信息int CompareNum(PeoplePoint p,int num);//已知某节点的指针p和一个编号num，比较p的num和num，如果相等返回1，否则返回0int CompareName(PeoplePoint p,char a[]);//已知某节点的指针p和一个a，比较p的name，如果两者相等返回1，否则返回0void TraveTreePrint(Tree TR);//已知树TR，按规定输出节点信息，根据编号、、孩子输出void AddPeople(Tree &TR);//已知树TR，当有人出生时，添加一个节点void MarryChange(Tree TR,char name[20]);//已知树TR和一个人的name，因为结婚需要改变节点中的配偶一栏void Open(Tree &TR);//打开保存家谱信息的文件void Save(Tree TR);//保存家谱信息到指定文件void PrintTree(Tree TR);//输出家谱中所有成员的信息3 详细设计3.1结构体定义struct People //定义结构体People{int num;char name[20];char sex;char borndate[15];int generation;char matename[20];int parent;char infor[100];LinkList child;}；struct Node //定义结构体Node{int a;struct Node * next;}；struct LinkList //定义链表{NodePoint La;}；struct Tree //定义树{PeoplePoint Tr;int Length;int TREE_INIT_SIZE;}；3.2 初始化void InitTree(Tree &TR) //在树已定义的情况下，初始化树TR {People peop[INIT_SIZE];TR.Tr=peop;TR.Length=0;TR.TREE_INIT_SIZE=INIT_SIZE;}LinkList InitLinkList(void)//在什么都没有的情况下，初始化一个带头结点的链表并返回链表L{LinkList L;NodePoint Head;Head=(NodePoint)malloc(sizeof(Node));Head->a=0;Head->next=NULL;=Head;return (L);}void CreatFamilyTree(Tree &TR) //在什么都没有的情况下，创建一个家谱TR。
并返回TR{LinkList lp;TR.Tr=peop;TR.Length=0;TR.TREE_INIT_SIZE=INIT_SIZE;int i=0,n,j,k,c;cout<<"请输入家谱中一共有多少人\n";cin>>n;TR.Length=n;for(i=0;i<n;i++){(peop[i].num)=i+1;cout<<"请输入该人的:\n";cin>>peop[i].name;cout<<"请输入该人的性别:\n";cin>>peop[i].sex;cout<<"请输入该人的出生日期:\n";cin>>peop[i].borndate;cout<<"请输入该人是第几代人:\n";cin>>peop[i].generation;cout<<"请输入其配偶的，如无则输入Nomarry\n"; cin>>peop[i].matename;cout<<"请输入其双亲的编号:\n";cin>>peop[i].parent;cout<<"请输入该人相关的备注信息:\n";cin>>peop[i].infor;LinkList L;NodePoint Head;Head=(NodePoint)malloc(sizeof(Node));Head->a=0;Head->next=NULL;=Head;peop[i].child=L;lp=peop[i].child;cout<<"请输入其孩子的个数:\n"; cin>>k;for(j=0;j<k;j++){cout<<"请输入孩子的编号:\n"; cin>>c;AddLinkList(lp,c);}}}3.3 插入操作void AddPeople(Tree &TR)//已知树TR ，当有人出生时，添加一个节点 {int k,c,j,m; LinkList L,L1,L2; NodePoint Head; PeoplePoint p1,p2,p3;if(TR.Length>=TR.TREE_INIT_SIZE){TR.Tr=(PeoplePoint)realloc(TR.Tr,(TR.TREE_INIT_SIZE+TREEINCREMENT)*L EN);if(!TR.Tr) exit(OVERFLOW);}p1=peop;p2=p1+(TR.Length);p2->num=TR.Length+1;cout<<"请输入该人的:\n";gets(p2->name);cout<<"请输入该人的性别:\n";cin>>p2->sex;cout<<"请输入该人的出生日期:\n";cin>>p2->borndate;cout<<"请输入该人是第几代人:\n";cin>>p2->generation;cout<<"请输入其配偶的，如无则输入Nomarry\n"; gets(p2->matename);cout<<"请输入其双亲的编号:\n";cin>>p2->parent;cout<<"请输入该人相关的备注信息:\n";gets(p2->infor);gets(p2->infor);Head=(NodePoint)malloc(sizeof(Node));Head->a=0;Head->next=NULL;=Head;p2->child=L;L1=p2->child;cout<<"请输入其孩子的个数:\n"; cin>>k;for(j=0;j<k;j++){cout<<"请输入孩子的编号:\n"; cin>>c;AddLinkList(L1,c);}m=p2->parent-1;p3=p1+m;L2=p3->child;AddLinkList(L2,p2->num);TR.Length=TR.Length+1;cout<<"添加成功\n";}3.4 查询操作void TraveTreePrint(Tree TR)//已知树TR，按规定输出节点信息，根据编号、、孩子输出{PeoplePoint p;int i,j,k,Flag;char name1[15],name2[15];p=TR.Tr;printf("根据编号查找请输入1，根据查找请输入2，根据孩子查找请输入3:\n");scanf("%d",&i);if(i==1){printf("请输入该节点的编号:\n");scanf("%d",&k);for(j=0;j<TR.Length;j++){Flag=CompareNum((p+j),k);if(Flag)PrintPeople((p+j));}}if(i==2){printf("请输入该人的:\n"); gets(name1);gets(name1);for(j=0;j<TR.Length;j++){Flag=CompareName((p+j),name1); if(Flag)PrintPeople((p+j));}}if(i==3){printf("请输入其孩子的:\n"); gets(name2);gets(name2);for(j=0;j<TR.Length;j++){if(strcmp(peop[j].name,name2)==0)PrintPeople((p+(peop[j].parent-1)));}}}4 调试分析在调试时，遇到的几个问题如下：1）建立树时，由于新申请结点的孩子指针、兄弟指针、及双亲指针均未赋空值。