数据结构实训指导家谱树Word下载.docx

1、家谱树保存到文件；从文件中读取数据重建家谱树；按各种关键字进行查询；某一成员的所有祖先（直系祖先）的查询；某一成员的所有直系亲属的查询确定两个成员的关系；统计成员人数；家谱成员的年龄，身高；选做功能包括：在打开家谱的当天，提醒当天有哪些人过生日；对已经去世的成员以寿命为关键字进行排序（寿命精确到天，采用快速排序算法）；对简历的内容进行用KMP算法进行字符搜索；编写基于MFC的图形界面。（没有MFC基础的同学不做）；其它自由发挥的功能，如果有意义有难度可以提高最后成绩。3 成绩评定办法总成绩由最终答辩成绩，平时抽检成绩，实训报告成绩3部分组成，比例为：4:3:3。3.1最终版本程序的考核标准：1

2、、没有完成基本功能，编程风格较差，例如：如采用全局变量，采用goto语句，缺少必要的注释语句，程序结构混乱等。成绩评定为D（不及格）。2、完成基本功能，系统框架设计基本合理，人机接口友好，但存在不多于3个bug，编程风格较好，成绩评定为C（及格）。3、完成基本功能，系统框架设计合理，人机接口友好，并实现至少2项选做功能，编程风格良好，测试用例丰富，测试结果完整。成绩评定为B（良好）。4、完成基本功能，系统框架设计合理，人机接口友好，实现至少3项选做功能，并能在老师给出的选做功能的基础上，提出自己其它有意义的功能并实现。编程风格良好，测试用例丰富，测试结果完整。成绩评定为A（良好）。3.2实训报

3、告的考核标准：1、没有按规定的格式编写实训报告，内容敷衍了事，测试用例记载不详细，成绩评定为D（不及格）。2、按规定的格式编写实训报告，内容能充分描述作者所做系统，所用图表和算法几乎与教师所给指导材料雷同，测试用例记载详细，成绩评定为 C（及格）。3、按规定的格式编写实训报告，内容能充分描述作者所做系统，根据所提文档能方便的进行系统重现，文理较通顺，图表基本完备，所用图表和算法与教师所给指导材料不尽雷同，测试用例记载详细，并能基本覆盖所有程序的所有可能出错情况。4、按规定的格式编写实训报告，内容能充分描述作者所做系统，根据所提交文档能方便的进行系统重现，文理通顺，图表完备，所用图表和算法与教师

4、所给指导材料不尽雷同，测试用例记载详细，并能覆盖所有程序的所有可能出错情况。程序调试过程，作者实训体会编写真实深刻，对以后做这一实训题目的同学具有一定借鉴意义。3.3 平时抽检成绩的评价标准：1、总体上来说，不能按时完成各阶段任务基本功能，需要延迟提交的最高成绩降低一个档次，也就是说最高成绩只能为B。、能按时完成基本功能，没有BUG；或者能完成该任务阶段的所有选做功能，但存在不多于3个BUG，成绩评定为A。3、能按时完成基本功能，但存在不多于2个BUG；或者能完成该任务阶段的一半以上选做功能，但存在不多于3个BUG，成绩评定为B。3、能按时完成基本功能，但存在不多于3个BUG；或者能完成该任务

5、阶段的任一选做功能，但存在不多于4个BUG，成绩评定为C。4、分阶段任务基本功能没有实现，且延时4学时后仍不能完成，成绩评定为D。4 系统功能模块结构这里给出的功能模块结构示意图只供参考，个人可以根据自己的想法另行设计，只要能实现给定的功能即可。图1 系统总体结构示意图5 数据结构5.1 总体数据结构1、家谱树采用孩子兄弟二叉树表来实现，如图2 所示的家谱采用图3所示的孩子兄弟二叉树来存储。图2 树状形式的家谱示意图 图2中同一父亲的亲兄弟已经按年龄从大到小排序，即最左边的孩子是父节点的第一个孩子。将其转化为孩子兄弟二叉树的方法是：对某一个节点，令其左子树指针指向该节点的第一个孩子，右子树指针

6、指向该节点的下一个兄弟。按这种方法，图2所示的家谱树可用如图3所示的孩子兄弟二叉树来实现：图3 孩子兄弟二叉树表示的家谱树2、节点数据结构：建议将节点信息中个人信息作为一个结构体。日期信息作为一个包含年、月、日三个成员的结构体。节点包括三个成员域：节点个人信息（结构体）；第一个孩子指针；下一个兄弟指针；其中节点个人信息结构体可包括：姓名、出生日期、死亡日期、性别、出生地、家庭住址、职业、职位、辈分、简历、父亲姓名、其他等。 为方便操作，可在节点中加入指向父亲的指针。6 分阶段任务分解及其关键算法提示6.1阶段任务一（6学时）6.1.1基本功能1、确定整个程序的功能模块。实现程序的主界面，要对主

7、界面的功能选择输入进行容错处理。2、实现单个结点信息的录入。3、对录入日期信息进行合法性检验。6.1.2选做功能1、采用改变字体颜色的方式突出显示主界面的功能项。2、计算从出生日期到死亡日期的实际天数6.1.3关键算法提示日期信息进行合法性检验包括两方面，首先是年份，月份，日期必须在一定的数字范围内，特别注意闰年的问题。其次是出生日期必须在死亡日期之前。参考流程图：图4 日期信息的合法性检验流程图6.2阶段任务二（10学时）6.2.1基本功能1、若家谱树为空，则新建家谱树。实现成员节点的添加。基本功能中可以强制要求所有成员不同名，即不考虑同名情况（符合小家族的实际情况）。2、添加成员节点时，可

8、以选择将新添加的节点作为整个家谱的上一代祖先，或者将新添加的节点作为某个现有成员的孩子。3、作为某个现有成员的孩子，根据给出的父节点的姓名将该结点添加到相应位置，注意，针对某一父节点，添加第一个孩子和其它孩子的区别。4、要求在孩子兄弟二叉树中按各个孩子的年龄进行排序。6.2.2选做功能1、如果容许存在同名，如何实现。2、父子之间的出生年月应该符合常理，比如儿子应该至少比父亲小多少岁（自行设定）。同时，父亲如果已经死亡，则其死亡日期最多只能在儿子出生之前的多少个月（自行设定，不考虑过继或领养的情况）。同时，同一父节点的孩子之间，亲兄弟的出生日期应该至少有多少个月的差距（只考虑一夫一妻制）。6.2

9、.3关键算法提示成员节点添加时，先判断新节点是作为整个家族的上一代祖先还是某个成员的孩子，若作为整个家族的祖先，则调用添加祖先模块，若作为某个成员的孩子，则调用添加孩子模块；在添加孩子模块中，先判断父节点是否有第一个孩子，若无，则将新节点作为父亲的第一个孩子，否则调用添加兄弟模块；添加兄弟时应按年龄寻找插入位置。图5 添加成员孩子模块流程图图6 添加兄弟模块流程图6.3阶段任务三（8学时）6.3.1基本功能1、将家谱树保存到二进制文件。注意，不能保存空白节点。2、从文件读入家谱信息，重建孩子兄弟二叉树形式的家谱。6.3.2选作功能 从文件中读出所有节点信息到一个数组中，然后按一年中生日的先后进

10、行快速排序。6.3.3关键算法提示采用先序遍历二叉树的方式将节点信息保存到文件。保存信息时，可以只保存节点个人信息（结构体）；而无需保存指针域。从文件读取信息重建二叉时，先将节点信息读入到缓冲区，通过读入结构体中父亲姓名找到父节点，然后用与节点添加类似的方式将读入的节点添加到二叉树上。6.4阶段任务四（8学时）6.4.1基本功能1、按姓名查询家谱成员并显示该成员的各项信息。2、给出某一成员的姓名，删除该成员和该成员的所有子孙。3、成员信息的修改。信息修改时要给出选择界面让用户选择需要修改的信息项。基本功能中可以限定不容许修改父亲姓名和本人姓名。对日期信息进行修改时要进行检验。4、实现层次递进的

11、方式显示整个家谱，显示结果应该体现家谱树的结构。6.4.2选作功能1、容许重新指定父亲。2、容许修改本人姓名。如果节点中都保存有父亲姓名，则本人的所有孩子应同步修改。6.4.3关键算法提示1、采用先序遍历二叉树的方式查询节点信息。2、采用后序遍历的方式删除节点。3、成员信息的层次化显示应该充分利用辈分信息。如图2所示的家谱显示结果可以如图7所示（容许其它显示方式，能体现家谱树的结构即可）图7 家谱信息层次化显示示意图6.5阶段任务五（8学时）6.5.1基本功能1、按各种关键字进行查询，要求给出关键字选择界面，并显示符合查询条件的节点信息。2、信息统计基本要求包括：平均身高，平均寿命，男女成员各

12、多少，平均家庭人口数目（假定每个成员构成一个家庭，该家庭的家庭成员是指成员本人和他的孩子，即家庭人口数=孩子数+1）。要给出统计项的选择界面，如图8所示（仅供参考，可以有其它形式）图7 统计项选择界面3、查询某一成员的所有直系亲属。4、给出某一成员的所有嫡系祖先。5、确定两人关系。若两人辈分不等，则应指出甲是乙的多少代长辈（晚辈），甲是否是乙的直系长辈（晚辈），若辈分相同，则应指出是亲兄弟还是多少代的堂兄弟。6.5.2选做功能1、在控制台界面输出查询结果的同时，将查询统计结果输出到文本文件，注意，不容许使用全局变量。2、对简历中的内容进行KMP算法匹配，即，搜索简历中包含某一内容的成员。6.5

13、.3关键算法提示确定两人关系时，应充分利用辈分信息和指向父节点的指针。若辈分相同，则由父指针往上追溯，可知两人是亲兄弟还是堂兄弟；若辈分不等，则从辈分较小的一方往上追溯到较大的辈分数，如果追溯过程中出现辈分较大的一方，则说明辈分较大者是辈分较小者的直系长辈，反之则不是。6.6阶段任务六（8学时）系统总体调试与测试。应该对出现的错误进行详细记载，VC编译器有出错提示的可以才用出错信息屏幕拷贝的方式；对逻辑错误要进行深入分析；详细记载错误的解决方法。 测试情况要求给出测试目的，输入，输出，截屏结果，结果分析。例如：测试目的：检测在出生日期和死亡日期输入时，程序是否对闰年进行检测。测试用例1：输入：出生日期 1921年2月29日输出：给出提示“你输入的日期有误，请重新输入”。截屏：结果分析：1921年不是闰年，程序能正确检测。测试用例2：出生日期 1920年2月29日没有出错提示信息，直接进入下一步输入。1920年是闰年，程序能正确检测。