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

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

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

家谱树保存到文件；

从文件中读取数据重建家谱树；

按各种关键字进行查询；

某一成员的所有祖先（直系祖先）的查询；

某一成员的所有直系亲属的查询

确定两个成员的关系；

统计成员人数；

家谱成员的年龄，身高；

选做功能包括：

在打开家谱的当天，提醒当天有哪些人过生日；

对已经去世的成员以寿命为关键字进行排序（寿命精确到天，采用快速排序算法）；

对简历的内容进行用KMP算法进行字符搜索；

编写基于MFC的图形界面。

（没有MFC基础的同学不做）；

其它自由发挥的功能，如果有意义有难度可以提高最后成绩。

3成绩评定办法

总成绩由最终答辩成绩，平时抽检成绩，实训报告成绩3部分组成，比例为：

4:

3:

3。

3.1最终版本程序的考核标准：

1、没有完成基本功能，编程风格较差，例如：

如采用全局变量，采用goto语句，缺少必要的注释语句，程序结构混乱等。

成绩评定为D（不及格）。

2、完成基本功能，系统框架设计基本合理，人机接口友好，但存在不多于3个bug，编程风格较好，成绩评定为C（及格）。

3、完成基本功能，系统框架设计合理，人机接口友好，并实现至少2项选做功能，编程风格良好，测试用例丰富，测试结果完整。

成绩评定为B（良好）。

4、完成基本功能，系统框架设计合理，人机接口友好，实现至少3项选做功能，并能在老师给出的选做功能的基础上，提出自己其它有意义的功能并实现。

编程风格良好，测试用例丰富，测试结果完整。

成绩评定为A（良好）。

3.2实训报告的考核标准：

1、没有按规定的格式编写实训报告，内容敷衍了事，测试用例记载不详细，成绩评定为D（不及格）。

2、按规定的格式编写实训报告，内容能充分描述作者所做系统，所用图表和算法几乎与教师所给指导材料雷同，测试用例记载详细，成绩评定为C（及格）。

3、按规定的格式编写实训报告，内容能充分描述作者所做系统，根据所提文档能方便的进行系统重现，文理较通顺，图表基本完备，所用图表和算法与教师所给指导材料不尽雷同，测试用例记载详细，并能基本覆盖所有程序的所有可能出错情况。

4、按规定的格式编写实训报告，内容能充分描述作者所做系统，根据所提交文档能方便的进行系统重现，文理通顺，图表完备，所用图表和算法与教师所给指导材料不尽雷同，测试用例记载详细，并能覆盖所有程序的所有可能出错情况。

程序调试过程，作者实训体会编写真实深刻，对以后做这一实训题目的同学具有一定借鉴意义。

3.3平时抽检成绩的评价标准：

1、总体上来说，不能按时完成各阶段任务基本功能，需要延迟提交的最高成绩降低一个档次，也就是说最高成绩只能为B。

２、能按时完成基本功能，没有BUG；

或者能完成该任务阶段的所有选做功能，但存在不多于3个BUG，成绩评定为A。

3、能按时完成基本功能，但存在不多于2个BUG；

或者能完成该任务阶段的一半以上选做功能，但存在不多于3个BUG，成绩评定为B。

3、能按时完成基本功能，但存在不多于3个BUG；

或者能完成该任务阶段的任一选做功能，但存在不多于4个BUG，成绩评定为C。

4、分阶段任务基本功能没有实现，且延时4学时后仍不能完成，成绩评定为D。

4系统功能模块结构

这里给出的功能模块结构示意图只供参考，个人可以根据自己的想法另行设计，只要能实现给定的功能即可。

图1系统总体结构示意图

5数据结构

5.1总体数据结构

1、家谱树采用孩子兄弟二叉树表来实现，如图2所示的家谱采用图3所示的孩子兄弟二叉树来存储。

图2树状形式的家谱示意图

图2中同一父亲的亲兄弟已经按年龄从大到小排序，即最左边的孩子是父节点的第一个孩子。

将其转化为孩子兄弟二叉树的方法是：

对某一个节点，令其左子树指针指向该节点的第一个孩子，右子树指针指向该节点的下一个兄弟。

按这种方法，图2所示的家谱树可用如图3所示的孩子兄弟二叉树来实现：

图3孩子兄弟二叉树表示的家谱树

2、节点数据结构：

建议将节点信息中个人信息作为一个结构体。

日期信息作为一个包含年、月、日三个成员的结构体。

节点包括三个成员域：

节点个人信息（结构体）；

第一个孩子指针；

下一个兄弟指针；

其中节点个人信息结构体可包括：

姓名、出生日期、死亡日期、性别、出生地、家庭住址、职业、职位、辈分、简历、父亲姓名、其他等。

为方便操作，可在节点中加入指向父亲的指针。

6分阶段任务分解及其关键算法提示

6.1阶段任务一（6学时）

6.1.1基本功能

1、确定整个程序的功能模块。

实现程序的主界面，要对主界面的功能选择输入进行容错处理。

2、实现单个结点信息的录入。

3、对录入日期信息进行合法性检验。

6.1.2选做功能

1、采用改变字体颜色的方式突出显示主界面的功能项。

2、计算从出生日期到死亡日期的实际天数

6.1.3关键算法提示

日期信息进行合法性检验包括两方面，首先是年份，月份，日期必须在一定的数字范围内，特别注意闰年的问题。

其次是出生日期必须在死亡日期之前。

参考流程图：

图4日期信息的合法性检验流程图

6.2阶段任务二（10学时）

6.2.1基本功能

1、若家谱树为空，则新建家谱树。

实现成员节点的添加。

基本功能中可以强制要求所有成员不同名，即不考虑同名情况（符合小家族的实际情况）。

2、添加成员节点时，可以选择将新添加的节点作为整个家谱的上一代祖先，或者将新添加的节点作为某个现有成员的孩子。

3、作为某个现有成员的孩子，根据给出的父节点的姓名将该结点添加到相应位置，注意，针对某一父节点，添加第一个孩子和其它孩子的区别。

4、要求在孩子兄弟二叉树中按各个孩子的年龄进行排序。

6.2.2选做功能

1、如果容许存在同名，如何实现。

2、父子之间的出生年月应该符合常理，比如儿子应该至少比父亲小多少岁（自行设定）。

同时，父亲如果已经死亡，则其死亡日期最多只能在儿子出生之前的多少个月（自行设定，不考虑过继或领养的情况）。

同时，同一父节点的孩子之间，亲兄弟的出生日期应该至少有多少个月的差距（只考虑一夫一妻制）。

6.2.3关键算法提示

成员节点添加时，先判断新节点是作为整个家族的上一代祖先还是某个成员的孩子，若作为整个家族的祖先，则调用添加祖先模块，若作为某个成员的孩子，则调用添加孩子模块；

在添加孩子模块中，先判断父节点是否有第一个孩子，若无，则将新节点作为父亲的第一个孩子，否则调用添加兄弟模块；

添加兄弟时应按年龄寻找插入位置。

图5添加成员孩子模块流程图

图6添加兄弟模块流程图

6.3阶段任务三（8学时）

6.3.1基本功能

1、将家谱树保存到二进制文件。

注意，不能保存空白节点。

2、从文件读入家谱信息，重建孩子兄弟二叉树形式的家谱。

6.3.2选作功能

从文件中读出所有节点信息到一个数组中，然后按一年中生日的先后进行快速排序。

6.3.3关键算法提示

采用先序遍历二叉树的方式将节点信息保存到文件。

保存信息时，可以只保存节点个人信息（结构体）；

而无需保存指针域。

从文件读取信息重建二叉时，先将节点信息读入到缓冲区，通过读入结构体中父亲姓名找到父节点，然后用与节点添加类似的方式将读入的节点添加到二叉树上。

6.4阶段任务四（8学时）

6.4.1基本功能

1、按姓名查询家谱成员并显示该成员的各项信息。

2、给出某一成员的姓名，删除该成员和该成员的所有子孙。

3、成员信息的修改。

信息修改时要给出选择界面让用户选择需要修改的信息项。

基本功能中可以限定不容许修改父亲姓名和本人姓名。

对日期信息进行修改时要进行检验。

4、实现层次递进的方式显示整个家谱，显示结果应该体现家谱树的结构。

6.4.2选作功能

1、容许重新指定父亲。

2、容许修改本人姓名。

如果节点中都保存有父亲姓名，则本人的所有孩子应同步修改。

6.4.3关键算法提示

1、采用先序遍历二叉树的方式查询节点信息。

2、采用后序遍历的方式删除节点。

3、成员信息的层次化显示应该充分利用辈分信息。

如图2所示的家谱显示结果可以如图7所示（容许其它显示方式，能体现家谱树的结构即可）

图7家谱信息层次化显示示意图

6.5阶段任务五（8学时）

6.5.1基本功能

1、按各种关键字进行查询，要求给出关键字选择界面，并显示符合查询条件的节点信息。

2、信息统计基本要求包括：

平均身高，平均寿命，男女成员各多少，平均家庭人口数目（假定每个成员构成一个家庭，该家庭的家庭成员是指成员本人和他的孩子，即家庭人口数=孩子数+1）。

要给出统计项的选择界面，如图8所示（仅供参考，可以有其它形式）

图7统计项选择界面

3、查询某一成员的所有直系亲属。

4、给出某一成员的所有嫡系祖先。

5、确定两人关系。

若两人辈分不等，则应指出甲是乙的多少代长辈（晚辈），甲是否是乙的直系长辈（晚辈），若辈分相同，则应指出是亲兄弟还是多少代的堂兄弟。

6.5.2选做功能

1、在控制台界面输出查询结果的同时，将查询统计结果输出到文本文件，注意，不容许使用全局变量。

2、对简历中的内容进行KMP算法匹配，即，搜索简历中包含某一内容的成员。

6.5.3关键算法提示

确定两人关系时，应充分利用辈分信息和指向父节点的指针。

若辈分相同，则由父指针往上追溯，可知两人是亲兄弟还是堂兄弟；

若辈分不等，则从辈分较小的一方往上追溯到较大的辈分数，如果追溯过程中出现辈分较大的一方，则说明辈分较大者是辈分较小者的直系长辈，反之则不是。

6.6阶段任务六（8学时）

系统总体调试与测试。

应该对出现的错误进行详细记载，VC编译器有出错提示的可以才用出错信息屏幕拷贝的方式；

对逻辑错误要进行深入分析；

详细记载错误的解决方法。

测试情况要求给出测试目的，输入，输出，截屏结果，结果分析。

例如：

测试目的：

检测在出生日期和死亡日期输入时，程序是否对闰年进行检测。

测试用例1：

输入：

出生日期1921年2月29日

输出：

给出提示“你输入的日期有误，请重新输入”。

截屏：

结果分析：

1921年不是闰年，程序能正确检测。

测试用例2：

出生日期1920年2月29日

没有出错提示信息，直接进入下一步输入。

1920年是闰年，程序能正确检测。