数据结构实训指导-家谱树.docx

《数据结构实训指导-家谱树.docx》由会员分享，可在线阅读，更多相关《数据结构实训指导-家谱树.docx（11页珍藏版）》请在优知文库上搜索。

1、1实训目的计Y104班数据结构实训指导广西3院计算机工想寐阳树洪2011年12月本次实训的总体目的在于通过系统的编程训练，培养学生编写一个具有一定难度的小型系统的能力，培养学生从编写单个程序，实现单个程序功能到进行系统开发，整体调试的能力。从知识点的角度来说，目的在于通过本实训工程，让学生对二叉树这一重要数据结构的运用更加熟练。2实训题目：树状家谱管理系统。本次实训的题目是树状家谱管理系统。要求利用数据结构的知识，通过将树转换为二叉树的概念，采用孩子兄弟二叉树的方式实现家谱管理系统。不容许采用数据库实现家谱管理。每个树结点表示一个家族成员，成员根本信息可包含，姓名、出生日期、死亡日期、性别、出

2、生地、家庭住址、职业、职位、辈分、简历、父亲姓名、其他。具体属性自行确定。要求实现的总体根本功能包括：家谱信息的录入，修改，删除；家谱树的层次化显示；家谱树保存到文件；从文件中读取数据重建家谱树；按各种关键字进行查询；某一成员的所有祖先（直系祖先）的查询；某一成员的所有直系亲属的查询确定两个成员的关系；统计成员人数；家谱成员的年龄，身高；选做功能包括：在翻开家谱的当天，提醒当天有哪些人过生日；对已经去世的成员以寿命为关键字进行排序（寿命精确到天，采用快速排序算法）；对简历的内容进行用KMP算法进行字符搜索；编写基于MFC的图形界面。（没有MFC根底的同学不做）；其它自由发挥的功能，如果有意义有

3、难度可以提高最后成绩。3成绩评定方法总成绩由最终辩论成绩，平时抽检成绩，实训报告成绩3局部组成，比例为：4:3:3。3.1 最终版本程序的考核标准：1、没有完成根本功能，编程风格较差，例如：如采用全局变量，采用goto语句，缺少必要的注释语句，程序结构混乱等。成绩评定为D（不及格）。2、完成根本功能，系统框架设计根本合理，人机接口友好，但存在不多于3个bug,编程风格较好，成绩评定为C（及格）。3、完成根本功能，系统框架设计合理，人机接口友好，并实现至少2项选做功能，编程风格良好，测试用例丰富，测试结果完整。成绩评定为B（良好）。4、完成根本功能，系统框架设计合理，人机接口友好，实现至少3项选

4、做功能，并能在老师给出的选做功能的根底上，提出自己其它有意义的功能并实现。编程风格良好，测试用例丰富，测试结果完整。成绩评定为A（良好）。3.2 实训报告的考核标准：1、没有按规定的格式编写实训报告，内容敷衍了事，测试用例记载不详细，成绩评定为D（不及格）。2、按规定的格式编写实训报告，内容能充分描述作者所做系统，所用图表和算法几乎与教师所给指导材料雷同，测试用例记载详细，成绩评定为C（及格）。3、按规定的格式编写实训报告，内容能充分描述作者所做系统，根据所提文档能方便的进行系统重现，文理较通顺，图表根本完备，所用图表和算法与教师所给指导材料不尽雷同，测试用例记载详细，并能根本覆盖所有程序的所

5、有可能出错情况。成绩评定为B（良好）。4、按规定的格式编写实训报告，内容能充分描述作者所做系统，根据所提交文档能方便的进行系统重现，文理通顺，图表完备，所用图表和算法与教师所给指导材料不尽雷同，测试用例记载详细，并能覆盖所有程序的所有可能出错情况。程序调试过程，作者实训体会编写真实深刻，对以后做这一实训题目的同学具有一定借鉴意义。成绩评定为Al良好）。33平时抽检成绩的评价标准：1、总体上来说，不能按时完成各阶段任务根本功能，需要延迟提交的最高成绩降低一个档次，也就是说最高成绩只能为B。2、能按时完成根本功能，没有BUG；或者能完成该任务阶段的所有选做功能，但存在不多于3个BUG,成绩评定为A

6、。3、能按时完成根本功能，但存在不多于2个BUG；或者能完成该任务阶段的一半以上选做功能，但存在不多于3个BUG,成绩评定为B。3、能按时完成根本功能，但存在不多于3个BUG；或者能完成该任务阶段的任一选做功能，但存在不多于4个BUG,成绩评定为C。4、分阶段任务根本功能没有实现，且延时4学时后仍不能完成，成绩评定为D。4系统功能模块结构这里给出的功能模块结构示意图只供参考，个人可以根据自己的想法另行设计，只要能实现给定的功能即可。图1系统总体结构示意图5数据结构5.1总体数据结构1、家谱树采用孩子兄弟二叉树表来实现，如图2所示的家谱采用图3所示的孩子兄弟二叉树来存储。图2树状形式的家谱示意图

7、图2中同一父亲的亲兄弟已经按年龄从大到小排序，即最左边的孩子是父节点的第一个孩子。将其转化为孩子兄弟二叉树的方法是：对某一个节点，令其左子树指针指向该节点的第一个孩子，右子树指针指向该节点的下一个兄弟。按这种方法，图2所示的家谱树可用如图3所示的孩子兄弟二叉树来实现：图3孩子兄弟二叉树表示的家谱树2、节点数据结构：建议将节点信息中个人信息作为一个结构体。日期信息作为一个包含年、月、日三个成员的结构体。节点包括三个成员域：节点个人信息（结构体）；第一个孩子指针；下一个兄弟指针；其中节点个人信息结构体可包括：姓名、出生日期、死亡日期、性别、出生地、家庭住址、职业、职位、辈分、简历、父亲姓名、其他等

8、。为方便操作，可在节点中参加指向父亲的指针。6分阶段任务分解及其关键算法提示6.1 阶段任务一（6学时）6.1.1 根本功能1、确定整个程序的功能模块。实现程序的主界面，要对主界面的功能选择输入进行容错处理。2、实现单个结点信息的录入。3、对录入日期信息进行合法性检验。1.1.2 选做功能1、采用改变字体颜色的方式突出显示主界面的功能项。2、计算从出生日期到死亡日期的实际天数1.1.3 关键算法提不日期信息进行合法性检验包括两方面，首先是年份，月份，日期必须在一定的数字范围内，特别注意闰年的问题。其次是出生日期必须在死亡日期之前。参考流程图：图4日期信息的合法性检验流程图6.2 阶段任务二（1

9、0学时）6.2.1 根本功能1、假设家谱树为空，那么新建家谱树。实现成员节点的添加。根本功能中可以强制要求所有成员不同名，即不考虑同名情况（符合小家族的实际情况2、添加成员节点时，可以选择将新添加的节点作为整个家谱的上一代祖先，或者将新添加的节点作为某个现有成员的孩子。3、作为某个现有成员的孩子，根据给出的父节点的姓名将该结点添加到相应位置，注意，针对某一父节点，添加第一个孩子和其它孩子的区别。4、要求在孩子兄弟二叉树中按各个孩子的年龄进行排序。6.2.2 选做功能1、如果容许存在同名，如何实现。2、父子之间的出生年月应该符合常理，比方儿子应该至少比父亲小多少岁（自行设定）。同时，父亲如果已经

10、死亡，那么其死亡日期最多只能在儿子出生之前的多少个月（自行设定，不考虑过继或领养的情况）。同时，同一父节点的孩子之间，亲兄弟的出生日期应该至少有多少个月的差距（只考虑一夫一妻制）。6.2.3 关键算法提示成员节点添加时，先判断新节点是作为整个家族的上一代祖先还是某个成员的孩子，假设作为整个家族的祖先，那么调用添加祖先模块，假设作为某个成员的孩子，那么调用添加孩子模块；在添加孩子模块中，先判断父节点是否有第一个孩子，假设无，那么将新节点作为父亲的第一个孩子，否那么调用添加兄弟模块；添加兄弟时应按年龄寻找插入位置。参考流程图：图5添加成员孩子模块流程图图6添加兄弟模块流程图6.3 阶段任务三（8学

11、时）6.3.1 根本功能1、将家谱树保存到二进制文件。注意，不能保存空白节点。2、从文件读入家谱信息，重建孩子兄弟二叉树形式的家谱。6.3.2 选作功能从文件中读出所有节点信息到一个数组中，然后按一年中生日的先后进行快速排序。6.3.3 关键算法提不采用先序遍历二叉树的方式将节点信息保存到文件。保存信息时，可以只保存节点个人信息（结构体）；而无需保存指针域。从文件读取信息重建二叉时，先将节点信息读入到缓冲区，通过读入结构体中父亲姓名找到父节点，然后用与节点添加类似的方式将读入的节点添加到二叉树上。6.4 阶段任务四（8学时）6.4.1 根本功能1、按姓名查询家谱成员并显示该成员的各项信息。2、

12、给出某一成员的姓名，删除该成员和该成员的所有子孙。3、成员信息的修改。信息修改时要给出选择界面让用户选择需要修改的信息项。根本功能中可以限定不容许修改父亲姓名和本人姓名。对日期信息进行修改时要进行检验。4、实现层次递进的方式显示整个家谱，显示结果应该表达家谱树的结构。6.4.2 选作功能1、容许重新指定父亲。2、容许修改本人姓名。如果节点中都保存有父亲姓名，那么本人的所有孩子应同步修改。6.4.3 关键算法提不1、采用先序遍历二叉树的方式查询节点信息。2、采用后序遍历的方式删除节点。3、成员信息的层次化显示应该充分利用辈分信息。如图2所示的家谱显示结果可以如图7所示（容许其它显示方式，能表达家

13、谱树的结构即可）李甲天李一河李二金李二银李一福李一山李二铁李三国李三家李三建图7家谱信息层次化显示示意图6.5 阶段任务五（8学时）6.5.1 根本功能1、按各种关键字进行查询，要求给出关键字选择界面，并显示符合查询条件的节点信息。2、信息统计根本要求包括：平均身高，平均寿命，男女成员各多少，平均家庭人口数目（假定每个成员构成一个家庭，该家庭的家庭成员是指成员本人和他的孩子，即家庭人口数=孩子数+1）。要给出统计项的选择界面，如图8所示仅供参考，可以有其它形式）统计操作图7统计项选择界面3、查询某一成员的所有直系亲属。4、给出某一成员的所有嫡系祖先。5、确定两人关系。假设两人辈分不等，那么应指

14、出甲是乙的多少代长辈（晚辈），甲是否是乙的直系长辈（晚辈），假设辈分相同，那么应指出是亲兄弟还是多少代的堂兄弟。6.5.2 选做功能1、在控制台界面输出查询结果的同时，将查询统计结果输出到文本文件，注意，不容许使用全局变量。2、对简历中的内容进行KMP算法匹配，即，搜索简历中包含某一内容的成员。6.5.3 关键算法提示确定两人关系时，应充分利用辈分信息和指向父节点的指针。假设辈分相同，那么由父指针往上追溯，可知两人是亲兄弟还是堂兄弟；假设辈分不等，那么从辈分较小的一方往上追溯到较大的辈分数，如果追溯过程中出现辈分较大的一方，那么说明辈分较大者是辈分较小者的直系长辈，反之那么不是。6.6 阶段任

15、务六（8学时）系统总体调试与测试。应该对出现的错误进行详细记载，VC编译器有出错提示的可以才用出错信息屏幕拷贝的方式；对逻辑错误要进行深入分析；详细记载错误的解决方法。测试情况要求给出测试目的，输入，输出，截屏结果，结果分析。例如：测试目的：检测在出生日期和死亡日期输入时，程序是否对闰年进行检测。测试用例1：输入：出生日期1921年2月29日输出：给出提示“你输入的日期有误，请重新输入”。截屏：WDE!三CJPCJPYSH_5DebugCJPYSH.exeMXX.X.XMWM新个谙撵作i三三r=asd年:1921角：2日：29国生日期输入错误，请重新输入出生日期年：结果分析：1921年不是闰年，程序能正确检测。测试用例2：输入：出生日期1920年2月29日输出：没有出错提示信息，直接进入下一步输入。截屏:W3D:ttJBj#sfeiJII