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

《数据结构实训指导家谱树.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、个人收集整理勿做商业用途计Y１0４班数据结构实训指导广西工学院计算机工程系阳树洪２０11年1２月个人收集整理勿做商业用途１　实训目的本次实训的总体目的在于通过系统的编程训练，培养学生编写一个具有一定难度的小型系统的能力，培养学生从编写单个程序,实现单个程序功能到进行系统开发，整体调试的能力。从知识点的角度来说，目的在于通过本实训项目,让学生对二叉树这一重要数据结构的运用更加熟练。2实训题目：树状家谱管理系统。本次实训的题目是树状家谱管理系统。要求利用数据结构的知识,通过将树转换为二叉树的概念,采用孩子兄弟二叉树的方式

2、实现家谱管理系统。不容许采用数据库实现家谱管理。每个树结点表示一个家族成员，成员基本信息可包含,姓名、出生日期、死亡日期、性别、出生地、家庭住址、职业、职位、辈分、简历、父亲姓名、其他。具体属性自行确定。要求实现的总体基本功能包括:家谱信息的录入,修改,删除；家谱树的层次化显示;家谱树保存到文件；从文件中读取数据重建家谱树；按各种关键字进行查询；某一成员的所有祖先(直系祖先)的查询;某一成员的所有直系亲属的查询确定两个成员的关系;统计成员人数；家谱成员的年龄，身高；选做功能包括：在打开家谱的当天，提醒当天有哪些人过生

3、日;对已经去世的成员以寿命为关键字进行排序（寿命精确到天，采用快速排序算法)；对简历的内容进行用KMP算法进行字符搜索；编写基于MFC的图形界面。(没有MFC基础的同学不做）;其它自由发挥的功能,如果有意义有难度可以提高最后成绩。3成绩评定办法总成绩由最终答辩成绩，平时抽检成绩,实训报告成绩３部分组成，比例为：4：3:3。个人收集整理勿做商业用途3.１最终版本程序的考核标准：1、没有完成基本功能，编程风格较差,例如：如采用全局变量，采用goto语句,缺少必要的注释语句，程序结构混乱等。成绩评定为Ｄ(不及格)。２、完成

4、基本功能,系统框架设计基本合理，人机接口友好,但存在不多于３个ｂug,编程风格较好，成绩评定为Ｃ(及格)。3、完成基本功能，系统框架设计合理,人机接口友好，并实现至少２项选做功能,编程风格良好,测试用例丰富,测试结果完整。成绩评定为Ｂ（良好)。４、完成基本功能,系统框架设计合理,人机接口友好,实现至少3项选做功能，并能在老师给出的选做功能的基础上，提出自己其它有意义的功能并实现。编程风格良好，测试用例丰富,测试结果完整。成绩评定为A(良好）。3.2实训报告的考核标准:１、没有按规定的格式编写实训报告，内容敷衍了事，测

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

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

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

8、示的孩子兄弟二叉树来存储。图2树状形式的家谱示意图个人收集整理勿做商业用途图2中同一父亲的亲兄弟已经按年龄从大到小排序，即最左边的孩子是父节点的第一个孩子。将其转化为孩子兄弟二叉树的方法是:对某一个节点,令其左子树指针指向该节点的第一个孩子,右子树指针指向该节点的下一个兄弟。按这种方法,图2所示的家谱树可用如图３所示的孩子兄弟二叉树来实现:图３