数据结构课程设计
题目：家谱管理系统
姓名：徐昕
学号：08000129
完成日期：2002.6.20
一、需求分析
² 建立输入文件以存放最初家谱中各成员的信息。
² 成员的信息中均应包含以下内容：
姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡）
也可附加其它信息、但不是必需的。
² 能对修改后的家谱存盘以备以后使用。
² 能从文件中读出已有的家谱，形成树状关系。
² 家谱建立好之后，以图形方式显示出来。
² 显示第 n 代所有人的信息。
² 按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。
² 按照出生日期查询成员名单。
² 输入两人姓名，确定其关系。
² 某人添加孩子。
² 删除某人（若其还有后代，则一并删除）。
² 修改某人信息。
² 按出生日期对家谱中所有人排序。
² 打开一家谱时，若家谱中某人的生日在打开家谱的那一天，应给出提示。
二、概要设计
采用二叉树进行家谱的管理、树形控件及列表控件进行家谱的显示。程序涉及以下三种类
型，但基本操作均在“家谱”类型中。
1．定义“个人信息”类型：
ADT Person{
数据对象：D={Pj | Pj={姓名、出生日期、婚否、地址、健在否（如过世，还应有其死亡日
期）}，j=0,1,2,……n,其中 n>=0}
数据关系：R={}
基本操作：
无。
}ADT Person
2.定义“家谱类型文件”类型
ADT FamilytreeFile{
数据对象：D={Aj | Aj 属于 Person,j=1,2,3……,n 其中 n>=1}
数据关系：D 中每个对象用换行符隔开,
R={ <Aj,String> | Aj 属于 D,j=1,3,……,n 其中 n>=1,String 属于字符串类型，为
Aj 父亲姓名(若 String=-1,Aj无父亲，若 String=Aj 的姓名,表示家谱文件结束)}
基本操作：
1． 打开家谱类型文件，并建立兄弟、孩子二叉树。
2． 从内存中读取兄弟、孩子二叉树，并建立家谱类型文件。
}ADT FamilytreeFlie
3．定义“家谱”类型
ADT Familytree{
数据对象：D={Aj | Aj属于 Person,j=1,2,3,……,n 其中 n>=0}
数据关系：V={<Aj-1,Aj> | Aj-1,Aj属于 D,j=2,3,……n 其中 n>=2，且 Aj-1 与 Aj为祖先与
后
代关系（parent）、后代与祖先关系(child)、兄弟之间关系（sibling）}
基本操作：
1． 显示某人信息。
2． 修改某人信息。
3． 增加某人孩子。
4． 删除某人。
5． 通过某人查找其双亲、孩子、兄弟。
}ADT Familytree
三、详细设计
1．定义“个人信息”类型：
struct Info{ //一个人的有关信息在内存中的存储结构
char name[MAX_CHARNUM]; //姓名
Date birthday; //出生日期
int marry; //婚否
char addr[MAX_CHARNUM]; //住址
int live; //健在否
Date deathday; //死亡日期
};
2.定义“家谱类型文件”类型
{ //一个人的有关信息在磁盘文件中存储结构
char name[MAX_CHARNUM]; //姓名
int birthday.year; //出生年份
int birthday.month; //出生月份
int birthday.day; //出生日期
int marry; //婚否
char addr[MAX_CHARNUM]; //住址
int live; //健在否
int deathday.year; //死亡年份
int deathday.month; //死亡月份
int deathday.day; //死亡日期
char fathername; //父亲名字
};
3．定义“家谱”类型
struct PersonNode{ //一个人的信息和与其他人关系的存储
结构
Info info; //自己的信息
PersonNode* parent; //指向父亲的指针
PersonNode* child; //指向孩子的指针
PersonNode* sibling; //指向兄弟的指针
}*Person;
4. 用结构 Date 存储日期
struct Date{ //年、月、日存储结构
int year; //年
int month; //月
int day; //日
};
5．用结构 QuickSortNode 存储快速排序数组值（为快速排序而设）
struct QuickSortNode{ //为以出生日期大小快速排序建立的存储结构
Date birthday; //出生日期
Person oneself; //指向自己的指针
};
6. 根据家谱的特点，采用孩子-兄弟的二叉树链表表示法（链表的基本单位为以结构Ｐ
ersonNode 表示的结点），各种操作以 COperationFamilytree 类来实现。
以下是 CoperationFamilytree 类包含的数据成员及基本操作
class COperationFamilytree
{
public:
COperationFamilytree();
//构造函数
virtual ~COperationFamilytree();
//析构函数
void NewFamilytree();
//新建一空家谱
int CreateFamilytree(CString filename);
//从输入文件 filename 中读取数据建立家谱
void DestroyFamilytree();
//删除家谱
int SaveFamilytree(CString filename);
//保存家谱
void PreOrderTraverse(FILE* fp,Person& T ,void (*Visit)(FILE* fp,Person& T));
//先序遍历(为保存家谱而做)
void PostOrderTraverse(Person& T,void (*Visit)(Person& T));
//后序遍历(为删除家谱而做)
void Find(Person& T,Person& Tname,char* name);
//从根结点出发，搜索 name 所在结点,如找到，存于 Tname 中，找不到，Tname 为 0
//使用前确保 Tname 指针为 0
void Find(Person&T,Person*& Tname,int month,int day);
//从根结点出发，搜索家谱中 birthday.month 等于 month,birthday.day 等于 day 的所有
结//点,如找到，存于以 Tname 为首地址的指针数组中，找不到，Tname 为 0 使用前确
保//Tname 指针为 0
void Add(Person parent,Person addNode);
//把 addnode 加为结点 parent 的孩子
void Delete(Person& rootNode);
//删除以 rootNode 为根结点的所有结点
void Modify(Person& pNode,Person newValue);
//修改 pNode 结点为新值 newValue
void SortByBirthday(QuickSortNode* order);
//对家谱以出生日期排序，并把排序结果放在数组 order中
void GetPersonNums(Person&T,int& personNums);
//得到家谱中总人数
int InGenerationPos(Person pNode);
//返回 pNode 在家谱中是第几代
int InSiblingPos(Person pNode);
//返回 pNode 在其兄弟中的排行
int ChildNums(Person pNode);
//返回 pNode 孩子数
int CompareDate(Date date1,Date date2);
//比较两日期的大小
bool IsDateValid(Date date);
//检验日期是否合法
Person& GetRoot();
//得到根结点
friend void SaveNode(FILE* fp,Person& pNode);
//保存结点 pNode 到文件 fp 中
friend void DestroyNode(Person& pNode);
//删除结点
private:
Person T;
//二叉树的根结点
int ReadNode(FILE* fp,Person&T,char* parentname);
//从文件 fp 中读取信息到结点 T 中，读取此结点的父亲姓名到 parentnaem 中(供
CreateFamilytree 函数调用)
void InsertSibling(Person& firstSibling,Person insertSibling);
//把 insertSibling 插入到以 firstSibling 为首的兄弟中(供 CreateFamilytree 函数调用)
void CopyInfoFromBiTreeToArray(Person&T,QuickSortNode*&order);
//把家谱中以 pNode 结点为根结点的出生日期拷贝到快速排序结构数组 order 中(供
SortByBirthday 函数调用)
void QuickSort(QuickSortNode* order,int low,int high);
//对 order[low...high]中的记录进行快速排序(供 SortByBirthday 函数调用)
