数据结构课程设计、二叉树生成家谱

数学与计算机学院课程设计说明书课 程 名 称: 数据结构与算法课程设计 课 程 代 码: 6014389 题 目: 二叉树生成家谱 年级/专业/班: 2011 级/软件工程/2 班 学 生 姓 名: 陈凯雄 学 号: 312011080611223 开 始 时 间: 2012 年 12 月 09 日完 成 时 间: 2012 年 12 月 29 日课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书（计算书、图纸、分析报告）撰写质量（45）总 分（100）指导教师签名： 年 月 日二叉树生成家谱3 / 25目 录 （小三黑体，居中）1 需求分析 .61.1 任务与分析 .61.2 测试数据 .62 概要设计 .72.1 ADT 描述 .72.2 程序模块结构 .82.3 各功能模块 .93 详细设计 .103.1 结构体定义 .103.2 初始化 .113.3 插入操作 .133.4 查询操作 .154 调试分析 .185 用户使用说明 .186 测试结果 .18结 论 .23附 录 .24参考文献 .25二叉树生成家谱4 / 25摘 要随着计算机科学技术、计算机产业的迅速发展，计算机的应用普及也在以惊人的速度发展，计算机应用已经深入到人类社会的各个领域。计算机的应用早已不限于科学计算，而更多地应用在信息处理方面。计算机可以存储的数据对象不再是纯粹的数值，而扩展到了字符、声音、图像、表格等各种各样的信息。对于信息的处理也不再是单纯的计算，而是一些如信息存储、信息检索等非数值的计算。那么，现实世界的各种数据信息怎样才能够存储到计算机的内存之中，对存入计算机的数据信息怎样进行科学处理，这涉及计算机科学的信息表示和算法设计问题。为解决现实世界中某个复杂问题，总是希望设计一个高效适用的程序。这就需要解决怎样合理地组织数据、建立合适的数据结构，怎样设计适用的算法，以提高程序执行的时间效率和空间效率。 “数据结构”就是在此背景下逐步形成、发展起来的。在各种高级语言程序设计的基本训练中，解决某一实际问题的步骤一般是：分析实际问题；确定数学模型；编写程序；反复调试程序直至得到正确结果。所谓数学模型一般指具体的数学公式、方程式等，如牛顿迭代法解方程，各种级数的计算等。这属于数值计算的一类问题。而现实生活中，更多的是非数值计算问题，如手机中的通讯录，人们对它的操作主要是查找、增加、删除或者修改电话记录。再如，人们经常在互联网上查阅各种新闻，或查阅电子地图，人们可以在某城区地图上查找自己所需的街道或店铺，其操作主要是搜索和查询。下面再来分析几个典型实例，它们的主要特点是：不同实例的数据元素之间存在不同的关系；对数据信息的处理主要有插入、删除、排序、检索等。关键词：网络化；计算机；对策；二叉树二叉树生成家谱5 / 25引 言 课程设计的目的：通过本项课程设计，培养学生独立思考、综合运用所学有关相应知识的能力，使学生巩固数据结构课程学习的内容，掌握工程软件设计的基本方法，强化上机动手编程能力，闯过理论与实践相结合的难关；为了培养学生综合运用所学知识、独立分析和解决实际问题的能力，培养创意识和创新能力，使学生获得科学研究的基础训练。为后续各门计算机课程的学习和毕业设计打下坚实基础。同时，可以利用这次机会来检验自己的 c/c+/数据结构水平，提高自己的写作水平，锻炼自己的动手能力。而此次课程设计的意义在于：增强自己的动手能力，熟悉和掌握二叉树各种遍历的算法，以及递归在遍历二叉树中的应用，增强自己的调试程序和测试程序的能力。二叉树生成家谱6 / 251 需求分析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 此人相当的热心 0 2 3 4 5 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 此人很有正二叉树生成家谱7 / 25义感 0 100005 徐廷国 m 1972-9-2 2 木玛 1 此人心的很善良 0 10000 6 徐光勇 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 增加某人孩子。二叉树生成家谱8 / 254 删除某人。 5 通过某人查找其双亲、孩子、兄弟。 ADT Familytree2.2 程序模块结构2.2.1 结构体定义struct People /定义结构体 Peopleint num;char name20;char sex;char borndate15;int generation;char matename20;int parent;char infor100;LinkList child;；struct Node /定义结构体 Nodeint a;struct Node * next;；struct LinkList /定义链表NodePoint La;；struct Tree /定义树PeoplePoint Tr;int Length;int TREE_INIT_SIZE;；二叉树生成家谱9 / 252.3 各功能模块void InitTree(Tree /在树已定义的情况下，初始化树 TR LinkList InitLinkList(void); /在什么都没有的情况下，初始化一个带头结点的链表并返回链表 L void AddLinkList(LinkList p); /对带头结点的链表 pl，添加一个节点为 m的节点在表头void CreatFamilyTree(Tree /在什么都没有的情况下，创建一个家谱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 PrintPeople(PeoplePoint p);void AddPeople(Tree void MarryChange(Tree TR,char name20);Exit(1)void InitTree(Tree void PrintTree(Tree TR);void Open(Tree void Save(Tree TR);输出成员模块二叉树生成家谱10 / 25void AddPeople(Tree /已知树 TR，当有人出生时，添加一个节点void MarryChange(Tree TR,char name20); /已知树 TR 和一个人的姓名name，因为结婚需要改变节点中的配偶一栏void Open(Tree /打开保存家谱信息的文件void Save(Tree TR);/保存家谱信息到指定文件void PrintTree(Tree TR); /输出家谱中所有成员的信息3 详细设计3.1 结构体定义struct People /定义结构体 Peopleint num;char name20;char sex;char borndate15;int generation;char matename20;int parent;char infor100;LinkList child;；struct Node /定义结构体 Nodeint a;struct Node * next;；struct LinkList /定义链表NodePoint La;；struct Tree /定义树PeoplePoint Tr;int Length;int TREE_INIT_SIZE;；二叉树生成家谱11 / 253.2 初始化void InitTree(Tree TR.Tr=peop;TR.Length=0;TR.TREE_INIT_SIZE=INIT_SIZE;LinkList InitLinkList(void)/在什么都没有的情况下，初