数据结构(二叉树)家谱管理系统.pdf

数学与计算机学院 课程设计说明书 课 程 名 称:数据结构与算法课程设计 课 程 代 码:题 目:二叉树生成家谱 年级/专业/班:学 生 姓 名:学 号:开 始 时 间:2015 年 12 月 09 日 完 成 时 间:2015 年 12 月 29 日 课程设计成绩：学习态度及平时成绩（30）技术水平与实际能力（20）创新（5）说明书（计算书、图纸、分析报告）撰写质量（45）总 分（100）指导教师签名：年 月 日 目 录（小三黑体，居中）欢迎下载 3 1 需求分析.6 1.1 任务与分析.6 1.2 测试数据.6 2 概要设计.7 2.1 ADT描述.7 2.2 程序模块结构.8 2.3 各功能模块.9 3 详细设计.10 3.1 结构体定义.10 3.2 初始化.11 3.3 插入操作.13 3.4 查询操作.15 4 调试分析.18 5 用户使用说明.18 6 测试结果.18 结 论.23 附 录.24 参考文献.25 欢迎下载 4 摘 要 随着计算机科学技术、计算机产业的迅速发展，计算机的应用普及也在以惊人的速度发展，计算机应用已经深入到人类社会的各个领域。计算机的应用早已不限于科学计算，而更多地应用在信息处理方面。计算机可以存储的数据对象不再是纯粹的数值，而扩展到了字符、声音、图像、表格等各种各样的信息。对于信息的处理也不再是单纯的计算，而是一些如信息存储、信息检索等非数值的计算。那么，现实世界的各种数据信息怎样才能够存储到计算机的内存之中，对存入计算机的数据信息怎样进行科学处理，这涉及计算机科学的信息表示和算法设计问题。为解决现实世界中某个复杂问题，总是希望设计一个高效适用的程序。这就需要解决怎样合理地组织数据、建立合适的数据结构，怎样设计适用的算法，以提高程序执行的时间效率和空间效率。“数据结构”就是在此背景下逐步形成、发展起来的。在各种高级语言程序设计的基本训练中，解决某一实际问题的步骤一般是：分析实际问题；确定数学模型；编写程序；反复调试程序直至得到正确结果。所谓数学模型一般指具体的数学公式、方程式等，如牛顿迭代法解方程，各种级数的计算等。这属于数值计算的一类问题。而现实生活中，更多的是非数值计算问题，如手机中的通讯录，人们对它的操作主要是查找、增加、删除或者修改电话记录。再如，人们经常在互联网上查阅各种新闻，或查阅电子地图，人们可以在某城区地图上查找自己所需的街道或店铺，其操作主要是搜索和查询。下面再来分析几个典型实例，它们的主要特点是：不同实例的数据元素之间存在不同的关系；对数据信息的处理主要有插入、删除、排序、检索等。关键词：网络化；计算机；对策；二叉树 欢迎下载 5 引 言 课程设计的目的：通过本项课程设计，培养学生独立思考、综合运用所学有关相应知识的能力，使学生巩固数据结构课程学习的内容，掌握工程软件设计的基本方法，强化上机动手编程能力，闯过理论与实践相结合的难关；为了培养学生综合运用所学知识、独立分析和解决实际问题的能力，培养创意识和创新能力，使学生获得科学研究的基础训练。为后续各门计算机课程的学习和毕业设计打下坚实基础。同时，可以利用这次机会来检验自己的 c/c+/数据结构水平，提高自己的写作水平，锻炼自己的动手能力。而此次课程设计的意义在于：增强自己的动手能力，熟悉和掌握二叉树各种遍历的算法，以及递归在遍历二叉树中的应用，增强自己的调试程序和测试程序的能力。欢迎下载 6 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 此人相当的热心 0 2 3 4 5 10000 2 徐廷文 m 1964-8-3 2 李太群 1 此人相当有责任心 0 6 7 10000 3 徐素华 w 1966-4-6 2 李奉光 1 此人很好 0 10000 4 徐军华 m 1969-7-8 2 曲舞 1 此人很有正义感 0 10000 欢迎下载 7 5 徐廷国 m 1972-9-2 2 木玛 1 此人心的很善良 0 10000 6 徐光勇 m 1989-1-27 3 Nomarry 2 此人很牛逼 0 10000 7 徐光超 m 1992-9-5 3 Nomarry 2 此人亦很牛逼 0 10000 2 概要设计 2.1 ADT 描述 1.ADT Person 数据对象：D=Pj|Pj=姓名、出生日期、婚否、地址、健在否（如过世，还应有其死亡日 期），j=0,1,2,n,其中 n=0 数据关系：R=基本操作：无。ADT Person 2.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 FamilytreeFlie 3.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 通过某人查找其双亲、孩子、兄弟。欢迎下载 8 ADT Familytree 2.2 程序模块结构 2.2.1 结构体定义 struct People /定义结构体 People int num;char name20;char sex;char borndate15;int generation;char matename20;int parent;char infor100;LinkList child;；struct Node /定义结构体 Node int a;struct Node*next;；struct LinkList /定义链表 NodePoint La;；struct Tree /定义树 PeoplePoint Tr;int Length;int TREE_INIT_SIZE;；欢迎下载 9 2.3 各功能模块 void InitTree(Tree&TR);/在树已定义的情况下，初始化树 TR LinkList InitLinkList(void);/在什么都没有的情况下，初始化一个带头结点的链表并返回链表L void AddLinkList(LinkList p);/对带头结点的链表pl，添加一个节点为m 的节点在表头 void CreatFamilyTree(Tree&TR);/在什么都没有的情况下，创建一个家谱 TR。并返回 TR void PrintPeople(PeoplePoint p);/已知某节点的指针 p，输出 people p 的相关信息 void PrintLinkList(LinkList p);/已知链表 p，输出链表 p 中的信息 int CompareNum(PeoplePoint p,int num);/已知某节点的指针 p 和一个编号num，比较 p 的 num 和 num，如果相等返回 1，否则返回 0 int CompareName(PeoplePoint p,char a);/已知某节点的指针 p 和一个姓名a，比较 p 的 name，如果两者相等返回 1，否则返回 0 void TraveTreePrint(Tree TR);/已知树 TR，按规定输出节点信息，根据编号、姓名、孩子输出 void AddPeople(Tree&TR);/已知树 TR，当有人出生时，添加一个节点 新建家谱模块 查找功能模块 添加成员模块 修改婚姻信息 退出程序模块 件读取文件读全部功能模块 读取家谱模块 保存家谱模块 void PrintPeople(PeoplePovoid AddPeople(Tree&TR)void MarryChange(Tree TR,cExit(1)void InitTree(Tree&TR)void PrintTree(Tree TR);void Open(Tree&TR);void Save(Tree TR);输出成员模块 欢迎下载 10 void MarryChange(Tree TR,char name20);/已知树 TR 和一个人的姓名 name，因为结婚需要改变节点中的配偶一栏 void Open(Tree&TR);/打开保存家谱信息的文件 void Save(Tree TR);/保存家谱信息到指定文件 void PrintTree(Tree TR);/输出家谱中所有成员的信息 3 详细设计 3.1 结构体定义 struct People /定义结构体 People int num;char name20;char sex;char borndate15;int generation;char matename20;int parent;char infor100;LinkList child;；struct Node /定义结构体 Node int a;struct Node*next;；struct LinkList /定义链表 NodePoint La;；struct Tree /定义树 PeoplePoint Tr;int Length;int TREE_INIT_SIZE;；欢迎下载 11 3.2 初始化 void InitTree(Tree&TR)/在树已定义的情况下，初始化树TR People peopINIT_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;L.La=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;coutn;TR.Length=n;for(i=0;in;i+)(peopi.num)=i+1;coutpeopi.name;coutpeopi.sex;coutpeopi.borndate;coutpeopi.generation;coutpeopi.matename;coutpeopi.parent;coutpeopi.infor;LinkList L;NodePoint Head;Head=(NodePoint)malloc(sizeof(Node);Head-a=0;Head-next=NULL;L.La=Head;peopi.child=L;lp=peopi.child;coutk;欢迎下载 13 for(j=0;jk;j+)coutc;AddLinkList(lp,c);3.3 插入操作 void AddPeople(Tree&TR)/已知树 TR，当有人出生时，添加一个节点 输入成员信息 开始 AddLinkList(L1,c);结束 判断格式是否正确 是 否 欢迎下载 14 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)*LEN);if(!TR.Tr)exit(OVERFLOW);p1=peop;p2=p1+(TR.Length);p2-num=TR.Length+1;coutname);coutp2-sex;coutp2-borndate;coutp2-generation;coutmatename);coutp2-parent;coutinfor);gets(p2-infor);欢迎下载 15 Head=(NodePoint)malloc(sizeof(Node);Head-a=0;Head-next=NULL;L.La=Head;p2-child=L;L1=p2-child;coutk;for(j=0;jk;j+)coutc;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 查询操作 欢迎下载 16 void TraveTreePrint(Tree TR)/已知树 TR，按规定输出节点信息，根据编号、姓名、孩子输出 PeoplePoint p;int i,j,k,Flag;char name115,name215;p=TR.Tr;printf(根据编号查找请输入 1，根据姓名查找请输入 2，根据孩子查找请输入3:n);scanf(%d,&i);if(i=1)printf(请输入该节点的编号:n);scanf(%d,&k);进入函数 结束 PrintPeople(p+j);PrintPeople(p+j);PrintPeople(p+(peopj.p选择功能 A=1 A=2 A=3 输出信息 输出信息 输出信息 欢迎下载 17 for(j=0;jTR.Length;j+)Flag=CompareNum(p+j),k);if(Flag)PrintPeople(p+j);if(i=2)printf(请输入该人的姓名:n);gets(name1);gets(name1);for(j=0;jTR.Length;j+)Flag=CompareName(p+j),name1);if(Flag)PrintPeople(p+j);if(i=3)printf(请输入其孩子的姓名:n);gets(name2);gets(name2);for(j=0;jTR.Length;j+)if(strcmp(peopj.name,name2)=0)欢迎下载 18 PrintPeople(p+(peopj.parent-1);4 调试分析 在调试时，遇到的几个问题如下：1）建立树时，由于新申请结点的孩子指针、兄弟指针、及双亲指针均未赋空值。而在以后的函数中对树迚行递归操作时均以这些指针值中的一个或几个是否为空 作为递归结束条件。从而导致调用这些函数时出现系统保护异常（使用了不安全 的指针）。2）刚开始初除结点时，只考虑到初除其本身结点的情况，而初除其孩子结点的 情况未考虑到，故在初除某些结点时使树出现了“断链”现象。故在程序代码中 对初除某一结点迚行操作时，首先要刞断此结点是否有孩子及兄弟，然后迚行相 应操作。本程序的编译环境为 Microsoft Visual C+6.0,在 Windows 8 下编译通过。5 用户使用说明 用户在打开软件后即可使用本软件，傻瓜式操作，界面简单易懂，用户在使用本软件过程中若出现隐私泄露或受到任何损失，与作者无关。6 测试结果 部分测试结果：欢迎下载 19 图 1：初始状态 欢迎下载 20 图 2：创建家谱 图 3：添加成员 欢迎下载 21 图 4：添加一个孩子 图 5：修改成员的婚姻状态 欢迎下载 22 图 6：输出所有家谱中的成员 图 7：从文件读取并输出 欢迎下载 23 结 论 通过一个学期以来的数据结构的学习，加深了我对 C+程序设计语言的认识，使得我对程序的开发过程有了更深的认识，这一次的数据结构课程设计是对我学习的检验，在这次实验中，我利用了各种开发工具以及建模工具，还在图书馆查过不少资料，最终解决了一个个难题。通过这次的实验，我得出了一个结论，任何一门语言的学习都是空洞的，只有在自己实验验证后才能让自己学到真正的知识。以上便是我对数据结构课程设计这门课的总结，我会抓紧时间将没有吃透的知识点补齐。今后我仍然会继续学习，克服学习中遇到的难关，在打牢基础的前提下向更深入的层面迈进！欢迎下载 24 附 录 源码文件如下：二叉树实现家谱运算.cpp 欢迎下载 25 参考文献 1杨宝刚.开展企业管理信息化工作的步骤J.企业管理.2002.（11）.1215 2Islamabad.Software tools for forgery detectionJ.Business line.2001.(5）.2932 3数据结构（C 语言版）清华大学出版社严蔚敏、吴伟民编著 4C 至 Visual C+程序设计语言科学出版社蔡常丰、林小苹编著 5Microsoft Visual C+6.0 高手速成兵器工业出版社步行者工作室编著 6C+程序设计清华大学出版社谭浩强编著