数据结构课程设计之简易家谱-报告.doc

课程设计（论文）

编号：学号：201140410119

课程设计

教学院计算机学院课程名称数据结构课程设计题目简易家谱系统专业计算机科学与技术班级（1）班姓名陈建辉同组人员周海涛，石义沣，明廷柱指导教师程细才

2013年1月8日

目录

TOC\*MERGEFORMAT一概述 PAGEREF_Toc323532
1.课程设计的目的 PAGEREF_Toc131742
2.课程设计的要求 PAGEREF_Toc153212
二总体方案设计 PAGEREF_Toc25553
1.简单家谱系统整体设计思路 PAGEREF_Toc38763
2．简单家谱系统的主要特点及功能 PAGEREF_Toc1695
三详细设计 PAGEREF_Toc312447
1.查询全部的家谱成员信息 PAGEREF_Toc289907
2.确定指定成员在家族中的辈份 PAGEREF_Toc148537
3.在家谱中添加新成员，并追加到文件中 PAGEREF_Toc28869
四程序的调试与运行结果说明 PAGEREF_Toc1246512
1.实验结果截图: PAGEREF_Toc2485812
2．调试时遇到的问题 PAGEREF_Toc2696712
五课程设计总结 PAGEREF_Toc2096813
附录一:程序源代码 PAGEREF_Toc2746616
附录二:参考文献 PAGEREF_Toc2485125


一概述
1.课程设计的目的
1．理解和掌握该课程中的有关基本概念，程序设计思想和方法。
2．培养综合运用所学知识独立完成课题的能力。
3．培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。
4．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。
2.课程设计的要求
设计要求：输入家族成员情况，建立树结构，统计家族成员人数，能查询家族成员辈份情况。
系统功能：1.输入、修改与删除家谱信息功能2.查询功能：1）某家谱成员的所有子孙的集合2）某家谱成员的所有祖先的集合3）某家谱成员的所有同辈成员的集合4）求某家谱成员的所有上一辈成员的集合5）给出两个家谱成员，确定他们的关系
二总体方案设计
1.简单家谱系统整体设计思路
此次课程设计的整体思路是采用遍历算法，整个树的定义使用两个结构体来表示，一个结构体专门用于存放每一个节点的信息，另一个节点中定义了三个指针域，分别为父指针域（兄长指针域），兄弟指针域，子指针域，整个树的输入采用文件导入的方式，首先将文件导入到树中，文件包含每一个家族成员的信息，以及一个标志位flag，标志位的值为0，1，2,0表示此节点没有兄弟节点，1表示此节点至少有一个子节点，2表示此节点至少有一个兄弟节点，使用的算法是先定义一个链式队列，将文件中第一个节点的内容读取放入开辟的树的节点的空间里，然后将树节点放入队列中，此时队列不为空，以队列不为空为判断条件，进行while循环，判断flag的值，循环体中再进行文件读取，循环中进行判断，若flag为0，则继续判断队列是否为空，为空就结束循环，若不为空，则继续出队列，取标志位进行判断，若标志位为1，则生成新节点，用刚刚出列的节点的子指针域进行指向新节点，新节点的父指针域指向出列的节点，剩余的域为空，然后将新生成的节点插入到队列中，若flag为1，则进行兄弟节点的插入，继续循环，若flag不为0，则在进行判断，若为2，则继续进行兄弟节点的插入，以此类推，根据文件的读取，将树生成，本程序中所有的算法都基于以上所介绍的算法。

关于IO的设计：
考虑到题目要求家谱信息以树形的形式一次读入内存，而个人的各种资料现在虽然条目不多，但随着程序的升级，以后可能变得越来越大。我把树形结构和个人信息记录的文档分为两个文件保存在外存中，一个文件串行化地记录家谱树的结构信息，保存少量个人信息作为识别标志；另一个文件保存完整的个人信息，所有的个人信息以线性记录的方式记录在其中。当程序运行要读入家谱结构时，只读入保存少量记录的文件并建立起树形结构。索引时，以树形中的少量信息为依据在另一个文件中找到全部的各人信息资料。
这样的好处主要有两点：
1.由于树形结构是串行化记录于外存，一个节点记录多次，信息大量冗余，如果树形节点中保留全部信息，必将造成大量的空间浪费；只保存作为索引的少量信息在树形结构中，节约了空间。
2.由于结构的精简，在家谱初始化时读入内存需要的时间相应减少，节约了装载时间。
这样做存在的