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

1、.课程设计报告课程名称数据结构课题名称排序综合专业班级学号姓名联系方式指导教师2011年12月21日. 1.3..362.2.472.2.582.2.6102.2.7112.2.8122.2.9122.2.10132.2.11142.3152.4193194.201问题陈述家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理软件，实.现对一个家族所有的资料进行收集整理。支持对家谱的存储、更新、查询、统计等操作。并用计算机永久储存家族数据，方便随时调用。2设计方法阐述2.1 总体规划在动手编制程序之前，先要做好程序的规划，包括程序储存

2、数据所用的结构，数据类型等等， 只有确定了数据类型和数据结构，才能在此基础上进行各种算法的设计和程序的编写。首先是考虑数据类型。在家谱中，家族成员是最基本的组成部分，对于家族管理中，已经不能再进行细分了，所以选定家族成员作为数据的基本类型，并在程序中定义COperationFamilytree类。其中COperationFamilytree类的各种属性可以根据需要进行添加或删除，从日常生活应用的角度出发，制定了COperationFamilytree类中包含了一下属性：char nameMAX_CHARNUM;/姓名Date birthday;/出生日期In tsex; /性别char add

3、rMAX_CHARNUM;/基本资料int live;/健在否Date deathday;/死亡日期int ChildNums(Person pNode) ;/返回 pNode孩子数intInSiblingPos(Person pNode);/返回 pNode在其兄弟中的排行为方便计算机进行比较，在familytree类的某些属性中用数字代替了某些不会改变的字符串， 譬如性别 （ 1 代表男， 0 代表女）、判断是否健在 （ 1 为是， 0 为否）。在设置日期上，为方便以后的计算与比较，也将日期用整型数字表示19990505 表示 1999 年 5 月 5 日，这种表示方法只需在输入和输出上作

4、少许的运算便可方便地与日期进行转换。在家族关系的表示上，并没有用相关家属的姓名作为储存数据，而仅仅是存储了各关系亲属的ID ，方便日后作为指针指示调用相对应的家族成员。其中在属性pNode 上，其表示的是下一个同父母的弟或妹 ID，也就是说，当某家族成员有若干个子女，其pNode 仅指向第一个孩子，其余的孩.子如何表示呢？可以通过第一个孩子的pNode 指示，如此类推，直到孩子的pNode =0 为止。这样就可以避免需在程序设计时预定父母可以拥有的孩子数，有多少孩子就表示多少， 实现了动态的储存数据。在选择数据结构方面，从直观来说，选择树型结构通过链表来连接数据无疑是最直观易懂的，我在一开始构

5、思的时候也是从树型结构去想的，但当构思到如何存储和提取数据是，便发现了问题。 毫无疑问，用指针来处理数据的确是方便直观，但当我要储存数据是，便发现把指针储存进去是没有作用的，因为当我们下一次读取数据的时候，数据内存地址已经不同了， 不在是我们上次存储数据时的地址，也就是说指针这时已经是没有作用了。要解决这样的问题， 我们必须要在存储数据之前，先家族树序列化，用数组 （或者其他可以用数字表示关系的方法） 来存储， 并且， 再下一次读取数据时，再把数据按照序列号重新组成一个家族树， 过程比较繁复，而且实现起来也不容易。所以我便考虑直接用数组来存储数据，即使是在内存中也用数组来处理数据间的联系。运用

6、顺序表这个结构虽然不是那么直观，但在查找数据时的算法设计比较简单容易实现，效率高，而且在内存中的数据可以直接读入到文件中，文件中的数据也可以直接读入内存，不需要进行转换。所以在衡量的各个方面之后，我决定用数组来处理数据间的联系。2.2 功能构想构想好总体规划之后，便开始设计程序中需要用到的各个功能函数，初步构想是要先实现最基本的几项功能，其中数据操作的有：增加成员，修改成员资料，删除成员；数据存取的有：打开家谱，新建家谱，保存家谱，另存家谱；数据查询的有：查看某代信息，按姓名查找，按生日查找，查看成员关系，按出生日期排序等等。2.2.1 增加成员这项功能做得不够理想，在规划时没有把成员以配偶的

7、形式增加，而只能以子女的形式增加。对应的函数代码如下：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)/ 若本

8、为空家谱T=addNode;/ 把 addNode 当成根结点return;addNode-child=T;/ 使原来的根结点成为新根结点的孩子T-parent=addNode;T=addNode;return;if(parent-child=0)/parent无孩子，把addNode 加入其孩子parent-child=addNode;elseInsertSibling(parent-child,addNode);/ 把 addNode 加到 parent孩子的兄弟域中2.2.2 修改成员资料修改成员这项功能实现起来比较简单，找到要修改成员的名字，再输入新修改的值，整个函数没有什么需要运用算

9、法的地方，但如果想真正写好这个函数，则需要考虑相当多的细节，譬如各个输入项目的错误处理等等，要非常全面地考虑各项细节。函数代码如下：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 one

10、self=0;char oldnameMAX_CHARNUM;strcpy(oldname,dlg.m_newname); operFamilytree.Find(operFamilytree.GetRoot(),oneself,oldname); if(dlg.DoModal()=IDCANCEL)return;UpdateData(FALSE);Person newValue=new PersonNode;strcpy(newV,dlg.m_newname);/ 判断家谱中是否已有用户给定的新名字.if(strcmp(newV,old

11、name)=0) ;/ 用户不修改姓名elsePerson p=0;operFamilytree.Find(operFamilytree.GetRoot(),p,newV);/ 查找家谱中有没有此人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=d

12、lg.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;i

13、f(!operFamilytree.IsDateValid(newValue-info.deathday)AfxMessageBox( 此人信息中死亡日期不合实际!);delete newValue;return;if(operFamilytree.CompareDate(newValue-info.deathday,newValue-info.bi rthday)=-1)AfxMessageBox( 此人死亡日期不可能比其出生日期早!);return;operFamilytree.Modify(oneself,newValue);RefreshTree();RefreshList();IsF

14、amilytreeModified=true; / 置家谱修改标记为真 delete newValue;2.2.3 删除成员用数组来储存数据， ，最麻烦的就是删除数组元素了，在这个程序中，删除数组不但意味着要重新排列各成员，还要重新更新各成员的关系，所以我个人认为在这个程序中，删除.成员函数可以说是一个难点。通过分析， 发现删除成员的情况就只有两种，只要针对这两种情况处理好删除，就可以完成成员删除这个功能。，删除的成员是出于家族中最底层的，也就是删除该成员不会牵连其他成员，但这也需要处理好其父母的孩子数。，删除的成员还有子孙，则需要连带所有子孙都要删除出家谱。遇到这种情况， 不但要像上一种情况

15、那样处理父母和兄弟姐妹的关系，还要记录牵连删除的总人数，因为删除不再是简单删除了一个人，而是若干个，通过递归调用，可以统计出需要删除的数目删除函数的相关代码如下：void COperationFamilytree:Delete(Person &rootNode)/ 本函数删除以 rootNode 为根结点的所有结点if(rootNode-parent)/ 如果 rootNode 有父结点if(rootNode-parent-child=rootNode)/ 如果 rootNode 为其父结点的第一个孩子rootNode-parent-child=rootNode-sibling; /因要删掉r

16、ootNode,故把其父结点的孩子指针指向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 结点。如果 ro

17、otNode 为根结点，则删除根结点TDestroyNode(T);elseDestroyNode(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,

18、T-,&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)/ 出生日期合法性检查returnFILE_DA

19、TA_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)returnFILE_DATA_NOT_PRACTICAL;return OK;2.2.5 新建家谱新建家谱函数的相关代码如下：void COperationFamilytree:NewFamilytree()/ 本函数新建一空家谱DestroyFamilytree

20、();/ 删除原有家谱T=0;int COperationFamilytree:CreateFamilytree(CString filename)./ 本函数建立一新家谱DestroyFamilytree();/ 建立一新家谱之前， 清空原有家谱FILE* fp;if(fp=fopen(filename,r)=0)/ 打开文件filenamereturn READ_FILE_ERROR;T=new PersonNode;/ 定义根结点if(!T)return NOT_ENOUGH_MEMORY;T-child=0;T-sibling=0;T-parent=0;Person parentT,

21、temp;/ 定义两个临时结点char parentnameMAX_CHARNUM;/ 定义一个临时字符串数组/ 读取根结点值,( 姓名 , 出生日期 ( 年 , 月 , 日 ), 婚否 , 地址 , 健在否 ,( 如过世，还有死亡日期 )int result;result=ReadNode(fp,T,parentname);if(result=FILE_DATA_NOT_PRACTICAL)delete T;/ 若不合法，删除申请的堆空间T=0;return result;if(strcmp(T-,parentname)=0)/ 根结点名字与其父亲名字相同，说明为空树del

22、ete T;T=0;return PEDIGREE_EMPTY;temp=new PersonNode;/ 申请一结点if(!temp)/ 申请失败DestroyFamilytree();/ 释放申请空间return NOT_ENOUGH_MEMORY;result=ReadNode(fp,temp,parentname);while(strcmp(,parentname)&strcmp(,end)/ 读取信息结束的条件是两个人的名字同为endif(result=FILE_DATA_NOT_PRACTICAL)/ 若数据不合法， 释放已申

23、请空间，然后返回delete temp;.DestroyFamilytree();return result;parentT=0;Find(T,parentT,parentname);/ 找到parentname所在结点parentTif(parentT)/ 如果 parentT 存在，说明parentname 在家谱中/ 并且 parentname 为 temp 的父亲int cmp;cmp=CompareDate(temp-info.birthday,parentT-info.birthday);if(cmpchild=temp-sibling=0;temp-parent=parentT;

24、/temp的父指针指向parentT;if(parentT-child)/parentname已经有孩子InsertSibling(parentT-child,temp);/ifelse/parentname无孩子 , 则 temp应为parentT-child=temp;/parentname的第一个孩子/ifelse/parentT不存在 , 说明家谱中不存在parentname 此人DestroyFamilytree();/ 返回出错信息return FILE_DATA_ERROR;temp=new PersonNode;/ 申请一结点if(!temp)/ 申请失败DestroyFami

25、lytree();/ 释放申请空间return NOT_ENOUGH_MEMORY;result=ReadNode(fp,temp,parentname);/ 继续读取数据/whileif(temp)delete temp;fclose(fp);return OK;2.2.6 保存家谱.保存家谱函数的相关代码如下：int COperationFamilytree:SaveFamilytree(CString filename)/ 本函数保存家谱到文件 filename 中FILE* fp;if(fp=fopen(filename,w)=0)/ 打开文件filenamereturn WRITE_

26、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;voidCOperationFamilytree:PreOrderTraverse(FILE*fp,Person&T, void(_cdecl*Visit)(FILE* fp,Person &)/ 本函数把所有以T 结点为根结点的结点值存到文件fp 中

27、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,pN,pNode-info.birthday.year,pNode-info.birthday.month,pNode-info.birthday.day,pNode-inf

28、o.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 ,pN);elsefprintf(fp, %s,-1);.fprintf(fp, %c,ch);2.2.7 查看某代信息查看某代信息函数的相关代码如下：int COperationFa

29、milytree: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-,name)=0)/T结

30、点姓名和name相同，把T 结点指针传给TnameTname=T;elseFind(T-sibling,Tname,name);/ 对 T 的兄弟递归搜索Find(T-child,Tname,name);/ 对 T 的孩子递归搜索2.2.9 按生日查找按生日查找函数的相关代码如下：voidCOperationFamilytree:Find(Person&T, Person*& Tname,intmonth, intday)/ 本函数以T 为根结点开始, 搜索结点信息中生日等于month,day 的结点 ,/ 并把所有符合条件的结点指针值存入以Tname为起始地址的地址数组中if(T)/ 如果

31、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,d

32、ay);/ 对 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 name1MAX_CHARNUM,name2MAX_CHARNUM; strcpy(name1,dlg.m_firstn

33、ame); operFamilytree.Find(operFamilytree.GetRoot(),oneself,name1); if(oneself)pos1=operFamilytree.InGenerationPos(oneself);elseAfxMessageBox( 本家谱中找不到+CString(name1)+!);return;Person p,q;CString generation;generation+=;generation+=在家谱中的位置: ;for(q=oneself,p=q-parent;p!=0;p=p-parent)ge

34、neration+=;generation+= -;q=p;.generation+=;generation+=n;oneself=0;strcpy(name2,dlg.m_secondname);operFamilytree.Find(operFamilytree.GetRoot(),oneself,name2);if(oneself)pos2=operFamilytree.InGenerationPos(oneself);elseAfxMessageBox( 本家谱中找不到+CString(name2)+!);return;generation+

35、=;generation+=在家谱中的位置: ;for(q=oneself,p=q-parent;p!=0;p=p-parent)generation+=;generation+= - ;q=p;generation+=;generation+=nn;CString cmpResult;if(pos1pos2)cmpResult.Format(%s在 第 %d 代 ， %s 在 第 %d 代 ， %s 是 %s 的 晚辈.,name1,pos1,name2 ,pos2,name1,name2);else if(pos

36、1pos2)cmpResult.Format(%s在 第 %d 代 ， %s 在 第 %d 代 ， %s 是 %s 的 长辈.,name1,pos1,name2 ,pos2,name1,name2);elsecmpResult.Format(%s与%s同在第 %d代 .,name1,name2,pos2);generation+=cmpResult;AfxMessageBox(generation);2.2.11 按出生日期排序按出生日期排序函数的相关代码如下：void COperationFamilytree:SortByBirthday(QuickSortNode *order)/ 本函数

37、对顺序表order以出生日期的大小排序.int totalNums=0;QuickSortNode* startaddr=order;startaddr+;GetPersonNums(T,totalNums);CopyInfoFromBiTreeToArray(T,startaddr);QuickSort(order,1,totalNums);2.3 板块整合以上的功能设计生成的各种函数文件仅是独立的各个板块，要将这些函数有机地联系起来，才能形成可以应用的程序，首先我用了一个DefineStruct.h声明数据类型与各个应用函数，其代码如下：根据家谱的特点，采用孩子- 兄弟的二叉树链表表示法（

38、链表的基本单位为以结构PersomNode表示的结点），各种操作以COperationFamilytree类来实现。以下是 CoperationFamilytree类包含的数据成员及基本操作class COperationFamilytree /定义家族成员结构public:COperationFamilytree();/ 构造函数virtual COperationFamilytree();/ 析构函数void NewFamilytree();/ 新建一空家谱int CreateFamilytree(CString filename);/ 从输入文件 filename 中读取数据建立家谱vo

39、id 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);/ 从根结点出发，搜索

40、 name 所在结点 , 如找到，存于 Tname 中，找不到， Tname 为 0/ 使用前确保 Tname 指针为 0void Find(Person&T,Person*& Tname,int month,int day);/ 从根结点出发， 搜索家谱中 birthday.month等于 month,birthday.day等于 day 的所有结/ 点 , 如找到， 存于以 Tname 为首地址的指针数组中，找不到， Tname 为 0 使用前确保 Tname/ 指针为 0void Add(Person parent,Person addNode);/ 把 addnode 加为结点 par

41、ent的孩子void Delete(Person& rootNode);/ 删除以 rootNode为根结点的所有结点void Modify(Person& pNode,Person newValue);/ 修改 pNode 结点为新值 newValuevoid SortByBirthday(QuickSortNode* order);/ 对家谱以出生日期排序，并把排序结果放在数组order中void GetPersonNums(Person&T,int& personNums);/ 得到家谱中总人数int InGenerationPos(Person pNode);/ 返回 pNode 在家

42、谱中是第几代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

43、(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 Co

44、pyInfoFromBiTreeToArray(Person&T,QuickSortNode*&order);/ 把家谱中以 pNode 结点为根结点的出生日期拷贝到快速排序结构数组order中 ( 供SortByBirthday函数调用 )void QuickSort(QuickSortNode* order,int low,int high);/ 对 orderlow.high中的记录进行快速排序( 供 SortByBirthday函数调用 )int Partition(QuickSortNode* order,int low,int high);/ 对 orderlow.high中的记录

45、进行一次排序( 供 QuickSort函数调用 )bool IsLeapYear(int year);/ 判断是否闰年（供IsDateValid调用，以检查日期是否合法）根据 MFC 的特点，采用 CfamilytreeDlg类实现用户窗口界面指令对于家谱的各种操作。class CFamilytreeDlg : public CDialogpublic:void SaveTip();./ 保存提示void InitListCtrl();/ 初始化列表控件void RefreshTree();/ 刷新树， ( 即刷新显示 )void RefreshList();/ 刷新列表void Displa

46、yFamilytree(Person& pNode);/ 显示树void DisplayInListCtrl(Person pNode);/ 把 pNode 结点的信息在列表控件中显示出来void Display(CString temp);/ 在列表控件中显示其他信息void FindInTree(HTREEITEM& hRootItem,HTREEITEM& hItem,char* name);/ 在树 hRootItem中查找 name 所在结点，如找到，把其结点句柄存入hItem中 , 找不到，/hItem为0. 注意，使用该函数时，确保hItem初值为 0void BirthdayTip();/ 每次打开一新家谱文件时的生日提示void DisplayGenerationInfo(Person& pNode,bool& flag,int count,int generation);/ 显示所有第 generation 代人的信息void AddToTree(HTREEITEM hParentItem,Person addnode );/