数据结构家谱管理系统报告书

《数据结构家谱管理系统报告书》由会员分享，可在线阅读，更多相关《数据结构家谱管理系统报告书（7页珍藏版）》请在金锄头文库上搜索。

1、 数据结构大作业说明文档数据结构大作业说明文档一、一、题目的选择题目的选择这次数据结构的大作业，我的选题是家谱管理系统的设计与实现。由于平 时疏于编程针对我得个人实际我把主要的目标定位在完成家谱管理系 统得基本要求。 （基本要求大纲中有，就不浪费版面了）二、二、设计的思路设计的思路接到这个题目，我的总体设计思路是先为程序搭建好一个结构框架，再跟 据时间的宽裕程度和其它的要求逐步增强程序的性能。关于关于 IO 的设计：的设计： 考虑到题目要求家谱信息以树形的形式一次读入内存，而个人的各种资料 现在虽然条目不多，但随着程序的升级，以后可能变得越来越大。我把树形结 构和个人信息记录的文档分为两个文件

2、保存在外存中，一个文件串行化地记录 家谱树的结构信息，保存少量个人信息作为识别标志；另一个文件保存完整的 个人信息，所有的个人信息以线性记录的方式记录在其中。当程序运行要读入 家谱结构时，只读入保存少量记录的文件并建立起树形结构。索引时，以树形 中的少量信息为依据在另一个文件中找到全部的各人信息资料。 这样的好处主要有两点： 1. 由于树形结构是串行化记录于外存，一个节点记录多次，信息大量冗余， 如果树形节点中保留全部信息，必将造成大量的空间浪费；只保存作为索引的 少量信息在树形结构中，节约了空间。 2. 由于结构的精简，在家谱初始化时读入内存需要的时间相应减少，节约 了装载时间。 这样做存在

3、的问题： 每次执行修改，添加，删除，查询时都要直接访问外存来取得或写入数据。 内外存访问上的巨大时间差的存在，使得进行这些操作相对来说并不显得很高 效。关于树形的结构：关于树形的结构： 在树形结构的选择上，根据实际中多子女的现象选择一般树，考虑到家谱 中成员可能存在的不定成员数问题，抛弃了以数组为基础的一般树方案，决定 用链表来实现。 树形结构的外存保存。为了提高效率，树形结构在程序初始化时由外存文 件一次读入内存，此后不管插入还是修改，删除都不再对外存的树结构保存文 件进行操作，只在内存中处理，程序退出时对外存树结构文件进行一次更新。 也就是说，不管在程序运行中中对家谱结构进行多少种，多少次

4、的操作，外存 的树结构文件始终只会被程序访问两次。关于功能的设计（以基本要求为准）：关于功能的设计（以基本要求为准）： 1.插入：用户按提示输入资料，在树形中插入节点，在个人完整记录 文件中添加插入人的所有信息并保存。 2.删除：用户输入被删除人的识别关键字（即名字） ，在树形结构中删 除此人，在个人记录文件中不处理。 3.修改：用户输入被删除任的识别关键字（即名字） ，从个人完整记录 文件中读出该人所有信息供用户进行修改，然后写回。 4.查询：完成了关键字查找部分和关系查找部分，读出个人全部信息 并显示。关于个人资料单元：关于个人资料单元： 由于树形节点要涉及到大量的逻辑操作，要用到一些运算

5、符的重载，个人 资料在树形单元定义为 class 类，而写入文件的单元存萃是数据，定义为简单的 struct 类。 定义为 struct 和 class 类，使得不管是树形结构插入删除还是 IO 都是对整个 结构体进行的操作，这样，如果要往结构体中添加若干个新信息条目或取消一 些不必要的信息条目，需要修改的代码非常之少，方便了以后的升级。三、三、程序源程序源/头文件及主要类的说明头文件及主要类的说明程序包含六个文件。一个源文件：test.cpp ；五个头文件：GTNode.h 、GTree.h 、IOMan.h 、 LList.h Link.h 。GTNode.h 头文件的说明：头文件的说明：

6、 文件中有 GTNode 模板类的定义和说明，GTNode 类是一般树的节点类，类 中的私有变量包含一个待定义的数据变量，一个最左孩子指针，一个右兄弟指 针，一个父指针。类中公有成员函数的作用主要是对四个私有成员进行返值和 置值，此外还包括一个叶子节点的判断函数。GTree.h 头文件的说明：头文件的说明： 文件中有 GTree 模板类的定义和说明，GTree 类是一般树类，以 GTNode 类为基础进行操作。 一般树类的私有部分包括两个私有变量：树的根指针和整型的当前树的节 点个数记录。另外还有三个私有辅助函数：析构辅助函数，打印辅助函数和查 找辅助函数。这三个函数都是用递归的方式访问整棵树

7、来完成打印，查找和树 的析构。 一般树的公有部分重定义了构造和析构函数，定义了以私有的辅助查找函 数为基础的对外的查找函数，定义了节点插入函数，节点删除函数和返回值节 点个数记录的求树节点个数的函数。List.h 头文件的说明：头文件的说明： 文件中定义并说明了模板类 List 类，这是程序中最简单的一个类，类中只 有公有部分，包含一个待定义的数据变量，一个指向下一个节点的指针，和两 个构造函数。LList.h 头文件的说明：头文件的说明： 文件中定义并说明了模板类 LList 类，这是一个但链表类，这个类主要是 我以数据结构教材中了 LList 类为范本，进行一些细部的修改，并添加了一些 成

8、员函数后形成。 LList 类的私有部分包含了一个待定义的数据，头、尾和“栅栏”三个指， 两个分别辅助构造与析构的函数。 LList 类的公有部分我根据需要添加了一个删除最后一个节点的函数，其它 部分与教材中基本一致。IOMan.h 头文件的说明：头文件的说明： IOMan.h 头文件是本程序中最大的一个头文件，其它四个头文件都是这个 文件的支持。其中包含了两个类，一个结构：一个一般树节点类，一个 IOMan 类，一个个人记录文件模块化写入读出的结构。 这里重点介绍一下处理文件，树，输入输出的 IOMan 类，这个类也是本程 序的核心所在。 IOMan 类的私有部分包含一个树，一个链表和一个写

9、入辅助函数。树是用 来存放家谱中关系的结构；链表主要用来辅助输入，输出；写入辅助函数在链 表的帮助下完成串型化地把树的结构写入外存保存树结构的文档中。 IOMan 类的公有部分包含六个函数：构造函数，析构函数，家谱添加函数， 删除函数，修改函数和查找函数。构造函数处理完成家族树的建树任务，析构 函数同时完成家族树的写入外存保存，其它四个函数处理用户输入输出的同时 也对外部文件进行更新。test.cpp 源文件的说明：源文件的说明： 该文件中包含了 main 函数。在 main 函数中，如果没有记录文件，则完成 记录文件的创建，否则，完成记录文件的打开。同时，main 函数还提供初始化 的用户面

10、板供用户进行操作。四、四、主要函数的说明：主要函数的说明：这次的大作业，我在程序中总共新写了（原创）五个类和二十多个较复杂 的函数。其中的大部在源文件中都有较好的注释或用了比较常规的手法，在这 里就不多加说明了，现在介绍的主要是比较特别的几个函数。 IOMan:IOMan ( ) 构造函数。这个构造函数的逻辑流程是：先打开线型化 保存树形结构的文件，如果打开成功则继续后续操作，否则退出程序。在打开 结构文件成功的情况下，模块化以树节点大小为单位逐个读入保存在结构文件 中的内容，并用两个指针变量记录当前和上次读入的节点，如果当前读入节点 在树中存在，则更新上次记录指针为当前记录指针值，如果读入节

11、点不存在， 则把当前读入的节点值作为上次记录节点的孩子插入结构树中，最后读完整个 结构记录文件后，关闭该文件。 IOMan:IOMan ( ) 析构函数。该函数主要完成树结构的写入保存工作。函 数流程是：先打开保存树结构的文件，如打开失败则提示用户无法保存信息， 否则调用辅助函数 writeHelp ( ) 把树的结构写入结构保存文件。writeHelp ( ) 函数的写入规则是：遇到中间节点，往链表中添加该节点，先递归访问它的最左 孩子，从链表中剔除该节点，再访问它的右兄弟；遇到叶子节点，顺序写出链 表中所有节点数据和该节点，再递归访问它的右兄弟。 IOMan:appendIt ( ) 家谱

12、成员添加函数。该函数首先打印出家谱树的结构供 用户查看，然后由用户添加成员，为了确认添加位置，除了主根节点外，所有 添加的成员都要求用户输入父节点的关键码（即父亲姓名） ，否则无法添加。然 后用户按提示输入添加成员的信息，由系统保存在个人信息记录文件中，同时 更新树结构。当个人记录保存文件无法打开时提示用户无法添加。 IOMan:removeIt ( ) 家谱成员删除函数，不对个人记录文件进行操作，只在 树形机构中进行删除。 IOMan:changeIt ( ) 家谱成员修改函数，由用户输入新的信息，更新个人记 录文件。 IOMan:inquire ( ) 家族成员查看函数，该函数有两个选择提

13、供给用户：按 成员名字查找或者按父亲名字查找，查找到的结构包含树中的关系。五、五、心得体会心得体会这次大作业的推荐学时是 20 个学时，但回想起来，光这篇报告就写了有三 四个学时，由于我本身编程能力不强，构思，写代码，修改，调试的时间加起 来绝对是有余了。虽然付出不少，但在前期的设计组织中，中期的代码编写和 后期的修改调试中都学到了不少。 起初我的家谱中数据并不是以结构的形式打包，读入，写出操作的时候代 码异常繁琐，这是恰好看到一本编程书上有用结构输入输出的范例，深深感到 结构化确实是方便多了，而且读写不容易出错。当时我的代码本已经写了有一 大半，思虑再三，还是决定进行大换血，家谱数据的改变让

14、程序来了个大换血， 提高了效率的同时，代码几乎变了一多半。我想，当时唯一不变的就只有对整 个程序越来越清醒地认识和对将要完成的代码的更准确地把握。 代码完成之后，一编译，至少有五六十个错误提示，而且最末 debug 一行 栏的最后一行提示因为先前的错误而中断编译，有的是指针指向错误，有的是 忘了分号，括号，更多的是一些赋值错误，前面的错误都好改，赋值错误就比 较麻烦了，因为要使用赋值的地方太多，逐行改代码虽然也可以，但实在是一 个巨大工程。所谓巧招必是险招至少对我是这样说来惭愧，我只有尝 试着写以前从未是过的运算符重载函数，为此专门翻找出了大一的 C+教材， 温习了一番运算符重载才战战兢兢地搞

15、定了赋值问题。 试运行时出现了更多的问题，而且更具有隐蔽性，几次为了一个逻辑错误 而来回反复地翻看代码，嘿嘿，再加上网上有代码的传说，让人有想直接放弃 的冲动，但一想到写代码的辛苦，觉得放弃了实在可惜。那几天吃饭，睡觉， 走路，看电视，随时随地，都记挂着那几处错误，脑子都会浮现出代码的影子， 不自觉地开始找错误。哎那种感觉！不知道是充实还是急迫地烦恼，最后终 于找到了，根本来不急高兴，只有松了一口气和一阵的疲惫。 现在程序终于完成了，心里的石头也下了地。至于成绩，不想了六、六、程序运行剪影程序运行剪影剪影中只以两个节点的树为例，其实程序本身可以支持任意多节点，欢迎老师剪影中只以两个节点的树为例

16、，其实程序本身可以支持任意多节点，欢迎老师 测试。测试。主面板主面板个人信息显示（其中的数字个人信息显示（其中的数字 2 代表实际信息）代表实际信息）查询页面查询页面附：附： 程序得到了比较好的调试和极限输入测试，很多问题的到了解决，但有一程序得到了比较好的调试和极限输入测试，很多问题的到了解决，但有一 个漏洞，现有的设计很难完美解决：当用到亲戚查询，选择子女序号时，必须个漏洞，现有的设计很难完美解决：当用到亲戚查询，选择子女序号时，必须 按提示输入数字，否则系统会出现未知错误。其它界面即使随便输入系统也会按提示输入数字，否则系统会出现未知错误。其它界面即使随便输入系统也会 给予纠正。给予纠正。