江苏大学2024秋季《数据结构与算法设计》课程设计—王的传承--基于C++的族谱系统设计
本课程设计为江苏大学王新宇老师《数据结构与算法设计》结课课程设计，题目为“王的传承”，即对成吉思汗的家族亲缘关系进行整理。课题要求利用合适的数据结构，完成一个族谱程序的设计，以此实现对成吉思汗家族关系的结构化整理、显示与对家庭成员的编辑等。具体要求见下。
根据课程设计要求文件，列出课题要实现的基本功能如下：
(1) 初始化系统: 读取族谱数据文件（txt文件），建立初始族谱。
(2) 显示族谱: 输出族谱。
(3) 添加成员: 提示输入成员信息，在族谱中添加成员。
(4) 修改成员: 提示输入成员姓名，修改成员信息。
(5) 删除成员: 提示输入成员姓名，从族谱中删除成员。
(6) 查询: 根据指定条件查询数据并输出。
(7) 保存: 保存当前族谱数据到文件。
(8) 退出: 退出文件。
此外，还需要设计合适的图形界面来实现对功能的显式调用。
对于系统的每个功能，可以建立一个相应的模块来完成这一功能，因此族谱系统应包括如下功能模块。
(1) 打印功能模块：输出显示图形化的族谱，包括成员的姓名以及成员之间的父子关系。
(2) 查询功能模块：根据指定条件对成员的信息进行查询，通过按名字查询、按代查询、查询父亲、查询孩子、查询兄弟五种查询条件，查询成员的姓名、生、卒年以及父亲。
(3) 添加功能模块：添加新的成员信息，包括姓名、生年、卒年、父亲。
(4) 编辑功能模块：编辑指定成员的信息，包括姓名、生年、卒年、父亲。
(5) 删除功能模块：删除指定成员的信息。
(6) 文件I/O功能模块：在文件中存储和从文件中读取族谱中的成员信息。
由上述模块构成的系统功能模块图如图2-1所示。
图2-1 族谱系统功能模块图
(1) 主菜单界面设计
族谱系统的功能包括 打印族谱 、 查询成员信息 、 添加成员 、 编辑成员 、 删除成员 、 退出程序 。因为读取txt文件为必须操作，所以无需添加在功能界面，启动时自动完成即可。系统主菜单的设计如图2-2所示。
图2-2 系统主菜单UI设计
(2) 查询模块子菜单界面设计
由于本系统要求根据多种条件进行查询，因此可以为查询模块单独设计了一个子菜单界面，用以选择查询依据的条件。其功能包括 按姓名查询 、 按代查询 、 退出查询 ，共计两种查询方式。查询模块的设计如图2-3所示。
图2-3 查询模块子菜单UI设计
(3) 二级查询子菜单界面设计
除了按姓名和按代查询，系统还要求可以查询父亲、孩子以及兄弟，而这三者的实现均依赖于某一指定成员。因此，可以通过在具体成员信息下显示一个二级查询界面，来实现以上三种查询。功能包括查询父亲、查询孩子、查询兄弟、退出查询。二级查询子菜单界面设计如图2-4所示。
图2-4 二级查询子菜单UI设计
为了设计族谱系统使用的类和数据结构，需要明确应用设计的对象，以及为了实现族谱系统功能需要建立的对象，进而对这些对象进行分析和抽象建立相应的数据结构。
根据所学知识，我们知道，可以用树的结构来存储一对多的数据关系，族谱一父多子的分支结构恰好与之相符。进一步地，由于一个父亲有多个孩子，且孩子数量不固定，若使用传统的树形存储结构，节点会存在指针数量不确定的问题，因此考虑使用孩子兄弟树作为储结构。孩子兄弟树将每个节点的孩子用“左孩子指针”和“右兄弟指针”表示，能高效存储多叉树，避免普通多叉树中需要多个指针的问题，且孩子兄弟树的拓展性好，特别适合不规则、多分支的树状结构。因此可以确定一个孩子兄弟树的类用以底层调用。
针对此问题，对象的信息有姓名、生年、卒年、父亲、孩子五者，而后两者可以通过树的操作实现查找，因此需要在节点对象的设计种引入三个数据域，分别存放姓名、生年以及卒年，以及两个指针域，分别指向首孩子以及兄弟。至此确定了孩子兄弟树依赖的节点类设计。
在程序设计中，一个系统需要具有较好的可扩展性和可维护性。为达这个目的，可以利用分层设计的方法，把系统划分为多个层次进行设计。开发时，每个层次只需要完成自己的功能，维护也聚焦自身，很少或不会牵扯到其他层次。因此，在本系统中，可以将与用户交互部分独立成一个界面对象，相当于系统的前端，而族谱对象则负责调用孩子兄弟树的原始存储结构来实现相应的操作。
综上，族谱系统包括树节点、树、族谱、界面共四个对象，其中树节点、树与数据的存储、组织有关，族谱和界面与功能的实现与操作有关。将这四者进行分析和抽象，确定各类对象的属性和服务就可以得到对应的类，即树节点类，树类，族谱类以及界面类。这四个类的属性合计服务设计如图2-5所示。
图2-5 系统的类图