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

实用标准文案课程设计报告课程名称 数据结构 课题名称 排序综合 专业 班级 学号姓名 联系方式 指导教师20 11 年 12 月 21 日目 录1. 问题陈述32设计方法阐述32.1总体规划3 2.2功能构想42.2.1增加成员42.2.2修改成员资料52.2.3删除成员62.2.4打开家谱72.2.5新建家谱82.2.6保存家谱102.2.7查看某代信息112.2.8按姓名查找122.2.9按生日查找122.2.10查看成员关系132.2.11按出生日期排序142.3板块整合15 2.4调试分析193总结194. 测试结果201问题陈述家谱用于记录某家族历代家族成员的情况与关系。现编制一个家谱资料管理软件，实现对一个家族所有的资料进行收集整理。支持对家谱的存储、更新、查询、统计等操作。并用计算机永久储存家族数据，方便随时调用。2设计方法阐述2.1总体规划在动手编制程序之前，先要做好程序的规划，包括程序储存数据所用的结构，数据类型等等，只有确定了数据类型和数据结构，才能在此基础上进行各种算法的设计和程序的编写。首先是考虑数据类型。在家谱中，家族成员是最基本的组成部分，对于家族管理中，已经不能再进行细分了，所以选定家族成员作为数据的基本类型，并在程序中定义COperationFamilytree 类。其中COperationFamilytree 类的各种属性可以根据需要进行添加或删除，从日常生活应用的角度出发，制定了COperationFamilytree 类中包含了一下属性：char nameMAX_CHARNUM; /姓名Date birthday; /出生日期In tsex; /性别char addrMAX_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结点的父指针域应指向parentif(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;elseInsertSibling(parent-child,addNode);/把addNode加到parent孩子的兄弟域中2.2.2修改成员资料修改成员这项功能实现起来比较简单，找到要修改成员的名字，再输入新修改的值，整个函数没有什么需要运用算法的地方，但如果想真正写好这个函数，则需要考虑相当多的细节，譬如各个输入项目的错误处理等等，要非常全面地考虑各项细节。函数代码如下：void CFamilytreeDlg:OnModify() / TODO: Add your command handler code hereif(operFamilytree.GetRoot()=0)return;CModifyInfoDlg dlg;HTREEITEM hItem;hItem=m_peTree.GetSelectedItem();dlg.m_newname=m_peTree.GetItemText(hItem);Person oneself=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,oldname)=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=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为根结点，则删除根结点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,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_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)returnFILE_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)/打开文件filenamereturn 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 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)/根结点名字与其父亲名字相同，说明为空树delete 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)/若数据不合法，释放已申请空间，然后返回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;/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)/申请失败DestroyFamilytree();/释放申请空间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_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中存取一结点pNodechar 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-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 ,pN);elsefprintf(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-,name)=0)/T结点姓名和name相同，把T结点指针传给TnameTname=T;elseFind(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 hereCRelationsDlg dlg;if(dlg.DoModal()=IDCANCEL)return;UpdateData(FALSE);int pos1,pos2;Person oneself=0;char name1MAX_CHARNUM,name2MAX_CHARNUM;strcpy(name1,dlg.m_firstname);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)generation+=;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+=;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(pos1pos2)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)/本函数对顺序表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 指针为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 加为结点parent 的孩子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 在家谱中是第几代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);/对orderlow.high中的记录进行快速排序(供SortByBirthday 函数调用)int Partition(QuickSortNode* order,int low,int high);/对orderlow.high中的记录进行一次排序(供QuickSort 函数调用)bool IsLeapYear(int year);/判断是否闰年（供IsDateValid 调用，以检查日期是否合法）根据MFC 的特点，采用CfamilytreeDlg 类实现用户窗口界面指令对于家谱的各种操作。class CFamilytreeDlg : public CDialogpublic:void SaveTip();/保存提示void InitListCtrl();/初始化列表控件void RefreshTree();/刷新树，(即刷新显示)void RefreshList();/刷新列表void DisplayFamilytree(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 );/把addnode 加入到树的hParentItem 结点中去private:char savepathMAX_CHARNUM;/家谱第一次被保存时的路径bool IsFamilytreeModified;/家谱是否被修改标记COperationFamilytree operFamilytree;/对家谱操作的一个类实例，所有的家谱操作均由它调用成员函数来完成;为使程序结构趋于清晰，分别使用CAddInfoDlg