家谱管理系统设计与实现.doc

课程设计报告
课程名称《数据结构》
课题名称排序综合
专业
班级
学号
姓名
联系方式
指导教师
20 11 年 12 月 21 日
目录
1。 问题陈述…………………………………………………………………………3
2．设计方法阐述………………………………………………………………………3
2。1总体规划……………………………………………………………………3
2.2功能构想……………………………………………………………………4
2.2。1增加成员………………………………………………………………4
2。2。2修改成员资料……………………………………………………………5
2。2。3删除成员………………………………………………………………6
2。2.4打开家谱…………………………………………………………………7
2。2。5新建家谱…………………………………………………………………8
2.2。6保存家谱…………………………………………………………………10
2。2.7查看某代信息……………………………………………………………11
2。2。8按姓名查找………………………………………………………………12
2.2。9按生日查找………………………………………………………………12
2。2.10查看成员关系…………………………………………………………13
2。2。11按出生日期排序………………………………………………………14
2。3板块整合………………………………………………………………………15
2。4调试分析………………………………………………………………………19
3．总结……………………………………………………………………………19
4。 测试结果…………………………………………………………………………20
1．问题陈述
家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理软件，实现对一个家族所有的资料进行收集整理.支持对家谱的存储、更新、查询、统计等操作.并用计算机永久储存家族数据,方便随时调用。
2．设计方法阐述
2.1总体规划
在动手编制程序之前，先要做好程序的规划，包括程序储存数据所用的结构,数据类型等等，只有确定了数据类型和数据结构,才能在此基础上进行各种算法的设计和程序的编写。
首先是考虑数据类型。在家谱中，家族成员是最基本的组成部分，对于家族管理中，已经不能再进行细分了，所以选定家族成员作为数据的基本类型，并在程序中定义COperationFamilytree类。其中COperationFamilytree类的各种属性可以根据需要进行添加或删除，从日常生活应用的角度出发，制定了COperationFamilytree类中包含了一下属性:
char name［MAX_CHARNUM]; //姓名
Date birthday； //出生日期
Intsex; //性别
char addr［MAX_CHARNUM]; //基本资料
int live； //健在否
Date deathday； //死亡日期
int ChildNums(Person pNode） ；//返回pNode孩子数
intInSiblingPos（Person pNode）; //返回pNode在其兄弟中的排行
为方便计算机进行比较，在familytree类的某些属性中用数字代替了某些不会改变的字符串，譬如性别(1代表男，0代表女)、判断是否健在（1为是,0为否）.在设置日期上，为方便以后的计算与比较，也将日期用整型数字表示19990505表示1999年5月5日，这种表示方法只需在输入和输出上作少许的运算便可方便地与日期进行转换.在家族关系的表示上,并没有用相关家属的姓名作为储存数据，而仅仅是存储了各关系亲属的ID,方便日后作为指针指示调用相对应的家族成员。其中在属性pNode上,其表示的是下一个同父母的弟或妹ID，也就是说，当某家族成员有若干个子女，其pNode仅指向第一个孩子，其余的孩子如何表示呢？可以通过第一个孩子的pNode指示，如此类推,直到孩子的pNode=0为止。这样就可以避免需在程序设计时预定父母可以拥有的孩子数，有多少孩子就表示多少，实现了动态的储存数据。
在选择数据结构方面，从直观来说，选择树型结构通过链表来连接数据无疑是最直观易懂的，我在一开始构思的时候也是从树型结构去想的，但当构思到如何存储和提取数据是，便发现了问题.毫无疑问，用指针来处理数据的确是方便直观,但当我要储存数据是，便发现把指针储存进去是没有作用的，因为当我们下一次读取数据的时候，数据内存地址已经不同了,不在是我们上次存储数据时的地址，也就是说指针这时已经是没有作用了。要解决这样的问题,我们必须要在存储数据之前,先家族树序列化,用数组（或者其他可以用数字表示关系的方法）来存储，并且,再下一次读取数据时，再把数据按照序列号重新组成一个家族树，过程比较繁复，而且实现起来也不容易。所以我便考虑直接用数组来存储数据，即使是在内存中也用数组来处理数据间的联系。运用顺序表这个结构虽然不是那么直观，但在查找数据时的算法设计比较简单容易实现，效率高，而且在内存中的数据可以直接读入到文件中,文件中的数据也可以直接读入内存，不需要进行转换.所以在衡量的各个方面之后，我决定用数组来处理数据间的联系.
2。2功能构想
构想好总体规划之后，便开始设计程序中需要用到的各个功能函数，初步构想是要先实现最基本的几项功能,其中数据操作的有:增加成员,修改成员资料，删除成员；数据存取的有：打开家谱,新建家谱，保存家谱，另存家谱;数据查询的有:查看某代信息,按姓名查找,按生日查找，查看成员关系，按出生日期排序等等。
2。2。1增加成员
这项功能做得不够理想，在规划时没有把成员以配偶的形式增加，而只能以子女的形式增加。
对应的函数代码如下：
void COperationFamilytree::Add（Person parent， Person addNode）
｛
//本函数把addNode结点加入到其父结点parent下
addNode—>child=addNode—>sibling=0； //把欲加入的结点所有指针域置空
addNode—>parent=parent； //因addNode欲加为parent的孩子，故addNode结点的父指针域应指向parent
if(parent==0）｛ //若parent为0,则表示欲加addNode为根结点
if(T==0）｛ //若本为空家谱
T=addNode; //把addNode当成根结点
return；
｝
addNode—〉child=T; //使原来的根结点成为新根结点的孩子
T—〉parent=addNode；
T=addNode;
return;
}
if（parent—〉child==0） //parent无孩子，把addNode加入其孩子
parent->child=addNode;
else
InsertSibling（parent-〉child,addNode）； //把addNode加到parent孩子的兄弟域中
｝
2.2.2修改成员资料
修改成员这项功能实现起来比较简单,找到要修改成员的名字，再输入新修改的值,整个函数没有什么需要运用算法的地方，但如果想真正写好这个函数，则需要考虑相当多的细节，譬如各个输入项目的错误处理等等,要非常全面地考虑各项细节.函数代码如下：
void CFamilytreeDlg:：OnModify(）
｛
// TODO： Add your command handler code here
if(operFamilytree。GetRoot（)==0）
return;
CModifyInfoDlg dlg;
HTREEITEM hItem；
hItem=m_peTree.GetSelectedItem（);
dlg.m_newname=m_peTree.GetItemText(hItem）;
Person oneself=0；
char oldname［MAX_CHARNUM］；
strcpy（oldname,dlg。m_newname);
operFamilytree.Find（operFamilytree。GetRoot（），oneself,oldname）；
if（dlg。DoModal(）==IDCANCEL）
return；
UpdateData(FALSE);
Person newValue=new PersonNode；
strcpy(newValue-〉info.name，dlg。m_newname)； //判断家谱中是否已有用户给定的新名字
if（strcmp(newValue—〉info.name，oldname)==0）; //用户不修改姓名
else{
Person p=0;
operFamilytree.Find(operFamilytree。GetRoot（),p,newValue—〉info.name）; //查找家谱中有没有此人
if（p！=0）｛
AfxMessageBox（”家谱中已有此人!");
delete newValue；
return;
｝
｝
strcpy（newValue—>info。addr，dlg.m_newaddr）；
newValue—〉info。marry=dlg.m_marry；
newValue->info。live=dlg.m_live；
newValue-〉info.birthday。day=dlg.m_birthday_day;
newValue-〉info.birthday。month=dlg.m_birthday_month;
newValue-〉info。birthday。year=dlg.m_birthday_year；
if（！newValue—〉info.live)｛ //如若过世，则应有死亡日期
newValue—〉info。deathday.day=dlg。m_deathday_day；
newValue—〉info。deathday。month=dlg.m_deathday_month;
newValue—〉info.deathday。year=dlg。m_deathday_year；
if(！operFamilytree.IsDateValid(newValue-〉info。deathday））{
AfxMessageBox（”此人信息中死亡日期不合实际！”)；
delete newValue；
return；
｝
if（operFamilytree。CompareDate（newValue->info。deathday，newValue-〉info。birthday）==—1)｛
AfxMessageBox(”此人死亡日期不可能比其出生日期早！”）；
return;
}
｝
operFamilytree。Modify（oneself,newValue）；
RefreshTree(）；
RefreshList(）;
IsFamilytreeModified=true; //置家谱修改标记为真
delete newValue；
｝
2.2。3删除成员
用数组来储存数据,，最麻烦的就是删除数组元素了,在这个程序中,删除数组不但意味着要重新排列各成员，还要重新更新各成员的关系，所以我个人认为在这个程序中，删除成员函数可以说是一个难点。通过分析,发现删除成员的情况就只有两种,只要针对这两种情况处理好删除，就可以完成成员删除这个功能。
１，删除的成员是出于家族中最底层的,也就是删除该成员不会牵连其他成员，但这也需要处理好其父母的孩子数。
２，删除的成员还有子孙,则需要连带所有子孙都要删除出家谱。遇到这种情况，不但要像上一种情况那样处理父母和兄弟姐妹的关系，还要记录牵连删除的总人数，因为删除不再是简单删除了一个人，而是若干个，通过递归调用，可以统计出需要删除的数目
删除函数的相关代码如下：
void COperationFamilytree::Delete(Person ＆rootNode）
｛
//本函数删除以rootNode为根结点的所有结点
if（rootNode-〉parent） //如果rootNode有父结点
if（rootNode->parent—〉child==rootNode） //如果rootNode为其父结点的第一个孩子
rootNode—〉parent—〉child=rootNode—〉sibling； //因要删掉rootNode,故把其父结点的孩子指针指向rootNode的第一个兄弟
else{ //如果rootNode不是父结点的第一个孩子
Person p=rootNode-〉parent->child； //找到rootNode应在兄弟中的位置
for（;p—〉sibling!=rootNode；p=p—〉sibling）
;
p-〉sibling=rootNode—〉sibling； //插入到兄弟中
｝
PostOrderTraverse(rootNode-〉child,DestroyNode)；//删除以rootNode—〉child为根结点的所有结点
if（rootNode==T） //删除rootNode结点。如果rootNode为根结点，则删除根结点T
DestroyNode（T）；
else
DestroyNode(rootNode)；
}
2.2。4打开家谱
打开家谱函数的相关代码如下：
int COperationFamilytree：:ReadNode（FILE ＊fp, Person ＆T，char＊ parentname）
{
//本函数从文件fp中读取信息到结点T中，并读取结点的父亲名字到字符数组parentname中
//分别读取结点值,为:姓名，出生日期(年，月，日)，婚否，地址,健在否，(如过世,还有死亡日期）
fscanf（fp，"%s%d%d%d％d％s％d”，T->info.name，&T-〉info.birthday。year,＆T—〉info.birthday。month，
＆T->info。birthday。day，＆T—〉info.marry,T—〉info.addr,＆T—〉info。live）；
if(T—〉info.live==0）
fscanf（fp，"％d%d%d”，＆T—>info.deathday.year，&T—〉info。deathday.month，
&T—>info。deathday。day）;
fscanf(fp,”％s"，parentname)；
if（！IsDateValid(T—〉info。birthday)） //出生日期合法性检查
return FILE_DATA_NOT_PRACTICAL;
if（T—>info。live==0） //若过世，死亡日期合法性检查
｛ if （CompareDate(T—>info.birthday，T—>info.deathday)！=—1)
return FILE_DATA_NOT_PRACTICAL；
if(！IsDateValid(T—>info.deathday））
return FILE_DATA_NOT_PRACTICAL;}
return OK;
｝
2.2。5新建家谱
新建家谱函数的相关代码如下：
void COperationFamilytree:：NewFamilytree（）
{
//本函数新建一空家谱
DestroyFamilytree（); //删除原有家谱
T=0；
｝
int COperationFamilytree:：CreateFamilytree（CString filename）
{
//本函数建立一新家谱
DestroyFamilytree（）; //建立一新家谱之前,清空原有家谱
FILE＊ fp;
if（（fp=fopen（filename，"r”））==0) //打开文件filename
return READ_FILE_ERROR；
T=new PersonNode; //定义根结点
if(！T）
return NOT_ENOUGH_MEMORY；
T—>child=0；
T—〉sibling=0;
T-〉parent=0；
Person parentT， temp； //定义两个临时结点
char parentname［MAX_CHARNUM］； //定义一个临时字符串数组
//读取根结点值,（姓名,出生日期(年，月，日),婚否,地址,健在否,（如过世,还有死亡日期）)
int result；
result=ReadNode（fp，T，parentname）;
if（result==FILE_DATA_NOT_PRACTICAL){
delete T； //若不合法，删除申请的堆空间
T=0；
return result;
｝
if(strcmp（T->info。name,parentname）==0）{ //根结点名字与其父亲名字相同,说明为空树
delete T；
T=0；
return PEDIGREE_EMPTY;
｝
temp=new PersonNode; //申请一结点
if(！temp）｛ //申请失败
DestroyFamilytree（）; //释放申请空间
return NOT_ENOUGH_MEMORY；
}
result=ReadNode（fp，temp，parentname）;
while（strcmp(temp->info.name,parentname）＆＆strcmp（temp—〉info。name，”end"）){ //读取信息结束的条件是两个人的名字同为end
if(result==FILE_DATA_NOT_PRACTICAL）{ //若数据不合法,释放已申请空间，然后返回
delete temp;
DestroyFamilytree(）；
return result；
｝
parentT=0；
Find(T，parentT，parentname）; //找到parentname所在结点parentT
if（parentT）｛ //如果parentT存在，说明parentname在家谱中
//并且parentname为temp的父亲
int cmp;
cmp=CompareDate（temp—〉info.birthday，parentT—>info。birthday);
if(cmp〈0）｛ //若孩子出生日期比父亲大,则不对
delete temp;
DestroyFamilytree（）;
return FILE_DATA_NOT_PRACTICAL;
}
temp—〉child=temp-〉sibling=0；
temp—〉parent=parentT； //temp的父指针指向parentT;
if（parentT->child）{ //parentname已经有孩子
InsertSibling(parentT—>child，temp）；
｝//if
else //parentname无孩子，则temp应为
parentT—〉child=temp； //parentname的第一个孩子
｝//if
else｛ //parentT不存在,说明家谱中不存在parentname此人
DestroyFamilytree（)； //返回出错信息
return FILE_DATA_ERROR;
｝
temp=new PersonNode; //申请一结点
if（！temp)｛ //申请失败
DestroyFamilytree（); //释放申请空间
return NOT_ENOUGH_MEMORY；
｝
result=ReadNode（fp,temp，parentname); //继续读取数据
｝//while
if（temp）
delete temp;
fclose（fp）；
return OK；
}
2.2。6保存家谱
保存家谱函数的相关代码如下:
int COperationFamilytree:：SaveFamilytree（CString filename）
{
//本函数保存家谱到文件filename中
FILE＊ fp；
if(（fp=fopen(filename，"w"))==0) //打开文件filename
return WRITE_FILE_ERROR；
PreOrderTraverse（fp,T,SaveNode）; //从根结点开始存储家谱数据
//置家谱数据结束标记(一结点的名字与其父结点的名字同为end）
fprintf(fp,”%s ％d ％d %d ％d ％s ％d %s”，”end”,1999，12,
2,1,"end"，1，”end”）;
fclose（fp)；
return OK；
｝
void COperationFamilytree::PreOrderTraverse(FILE＊ fp，Person ＆T， void (__cdecl ＊Visit）(FILE＊ fp，Person ＆））
{
//本函数把所有以T结点为根结点的结点值存到文件fp中
if（T）｛
（＊Visit）（fp，T)；
PreOrderTraverse(fp,T—>child，Visit）；
PreOrderTraverse（fp，T—〉sibling，Visit);
｝
}
void SaveNode（FILE ＊fp， Person ＆pNode)
{
//本函数向文件fp中存取一结点pNode
char ch='\n’;
if（pNode)｛
fprintf(fp，”％s ％d %d ％d ％d ％s ％d ”,pNode—〉info。name，pNode-〉info。birthday。year，
pNode—>info。birthday。month,pNode—>info。birthday。day，pNode—〉info。marry,
pNode—〉info。addr，pNode-〉info。live）；
if(pNode-〉info。live==0)
fprintf(fp,” ％d ％d ％d "，pNode—>info。deathday.year,pNode-〉info。deathday。month，
pNode-〉info。deathday.day)；
if（pNode—>parent)
fprintf（fp,” ％s ”，pNode—>parent->info。name)；
else
fprintf(fp，" ％s”，”-1”);
fprintf（fp," ％c”,ch）；
}
｝
2.2。7查看某代信息
查看某代信息函数的相关代码如下：
int COperationFamilytree：:InGenerationPos（Person pNode）
｛
//本函数返回pNode结点在第几代
int pos=1;
Person p；
p=pNode-〉parent；
for（；p!=0;p=p—〉parent）
pos++；
return pos;
｝
2.2。8按姓名查找
按姓名查找函数的相关代码如下:
void COperationFamilytree:：Find（Person＆ T，Person& Tname，char＊ name）
｛
//本函数以T为根结点开始，搜索结点信息中名字等于name的结点
if（T)｛ //如果T存在
if（strcmp（T-〉info。name,name）==0) //T结点姓名和name相同,把T结点指针传给Tname
Tname=T；
else｛
Find（T—〉sibling，Tname，name)； //对T的兄弟递归搜索
Find（T—〉child，Tname，name）; //对T的孩子递归搜索
｝
｝
}
2。2。9按生日查找
按生日查找函数的相关代码如下:
void COperationFamilytree：:Find(Person &T， Person＊& Tname，int month， int day）
｛
//本函数以T为根结点开始,搜索结点信息中生日等于month，day的结点，
//并把所有符合条件的结点指针值存入以Tname为起始地址的地址数组中
if（T）{ //如果T存在
if（T—>info。birthday。month==month&＆T-〉info。birthday.day==day){
//T结点生日与所给相同,把T结点指针传给Tname,同时Tname指针前进
Person temp；
temp=new PersonNode；
temp=T；
if（temp—〉info。birthday。month==month＆&temp-〉info。birthday。day==day）
{
＊Tname=temp；
Tname++；
｝
temp=NULL;
}
Find（T—>child,Tname，month,day）; //对T的孩子递归搜索
Find(T—>sibling,Tname,month，day）； //对T的兄弟递归搜索
｝
｝
2。2.10查看成员关系
查看成员关系函数的相关代码如下：
void CFamilytreeDlg：:OnFamilytreeRelations（）
｛
// TODO： Add your command handler code here
CRelationsDlg dlg；
if(dlg。DoModal()==IDCANCEL)
return;
UpdateData(FALSE）；
int pos1,pos2;
Person oneself=0;
char name1［MAX_CHARNUM]，name2[MAX_CHARNUM];
strcpy（name1，dlg。m_firstname）；
operFamilytree。Find（operFamilytree.GetRoot(）,oneself，name1)；
if（oneself）
pos1=operFamilytree。InGenerationPos(oneself)；
else｛
AfxMessageBox(”本家谱中找不到”+CString(name1）+”！"）；
return；
｝
Person p，q；
CString generation;
generation+=oneself-〉info。name;
generation+=”在家谱中的位置： ”；
for(q=oneself,p=q-〉parent;p！=0；p=p->parent）｛
generation+=q—〉info。name;
generation+= ”-〉"；
q=p；
｝
generation+=q->info.name;
generation+="\n”;
oneself=0;
strcpy(name2，dlg。m_secondname);
operFamilytree。Find(operFamilytree。GetRoot()，oneself,name2)；
if（oneself)
pos2=operFamilytree。InGenerationPos（oneself)；
else｛
AfxMessageBox（”本家谱中找不到"+CString（name2）+"！"）;
return;
}
generation+=oneself—>info。name；
generation+=”在家谱中的位置： ";
for（q=oneself，p=q-〉parent；p！=0；p=p->parent）{
generation+=q—>info。name;
generation+= ” -〉 ";
q=p;
｝
generation+=q-〉info.name；
generation+="\n\n"；
CString cmpResult;
if（pos1〉pos2）
cmpResult。Format(”％s在第％d代，％s在第％d代,％s是％s的晚辈.”，name1，pos1，name2
,pos2，name1，name2)；
else if（pos1<pos2）
cmpResult.Format(”%s在第％d代，％s在第％d代，％s是%s的长辈。"，name1，pos1，name2
，pos2,name1,name2）;
else
cmpResult.Format("％s与％s同在第%d代。”,name1,name2，pos2）;
generation+=cmpResult;
AfxMessageBox(generation）;
}
2。2。11按出生日期排序
按出生日期排序函数的相关代码如下：
void COperationFamilytree：：SortByBirthday（QuickSortNode *order）
{
//本函数对顺序表order以出生日期的大小排序
int totalNums=0；
QuickSortNode＊ startaddr=order;
startaddr++;
GetPersonNums(T,totalNums）；
CopyInfoFromBiTreeToArray(T，startaddr）；
QuickSort(order，1，totalNums）；
}
2。3板块整合
以上的功能设计生成的各种函数文件仅是独立的各个板块,要将这些函数有机地联系起来,才能形成可以应用的程序，首先我用了一个DefineStruct。h声明数据类型与各个应用函数，其代码如下：
根据家谱的特点，采用孩子—兄弟的二叉树链表表示法（链表的基本单位为以结构PersomNode表示的结点），各种操作以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(Dat