家谱管理系统设计与实现

/课程设计报告 课程名称 《数据结构》 课题名称排序综合 专 业 班 级 学 号 姓 名 联系方式 指导老师 2011年12月21日目录1.问题陈述…………32．设计方法阐述………………………32.1总体规划……………………32.2功能构想……………………4增加成员………………4修改成员资料……………5删除成员………………6打开家谱…………………7新建家谱…………………8保存家谱…………………10查看某代信息……………11按姓名查找………………12按生日查找………………12查看成员关系…………13按诞生日期排序………142.3板块整合………………………152.4调试分析………………………193．总结……………194.测试结果…………201．问题陈述家谱用于记录某家族历代家族成员的状况和关系。现编制一个家谱资料管理软件，实现对一个家族全部的资料进行收集整理。支持对家谱的存储、更新、查询、统计等操作。并用计算机永久储存家族数据，便利随时调用。2．设计方法阐述2.1总体规划在动手编制程序之前，先要做好程序的规划，包括程序储存数据所用的结构，数据类型等等，只有确定了数据类型和数据结构，才能在此基础上进行各种算法的设计和程序的编写。首先是考虑数据类型。在家谱中，家族成员是最基本的组成部分，对于家族管理中，已经不能再进行细分了，所以选定家族成员作为数据的基本类型，并在程序中定义COperationFamilytree类。其中COperationFamilytree类的各种属性可以依据须要进行添加或删除，从日常生活应用的角度动身，制定了COperationFamilytree类中包含了一下属性：charname[MAX_CHARNUM];//姓名Datebirthday;//诞生日期Intsex;//性别charaddr[MAX_CHARNUM];//基本资料intlive;//健在否Datedeathday;//死亡日期intChildNums(PersonpNode);//返回pNode孩子数intInSiblingPos(PersonpNode); //返回pNode在其兄弟中的排行为便利计算机进行比较，在familytree类的某些属性中用数字代替了某些不会变更的字符串，譬如性别（1代表男，0代表女）、推断是否健在（1为是，0为否）。在设置日期上，为便利以后的计算和比较，也将日期用整型数字表示19990505表示1999年5月5日，这种表示方法只需在输入和输出上作少许的运算便可便利地和日期进行转换。在家族关系的表示上，并没有用相关家属的姓名作为储存数据，而仅仅是存储了各关系亲属的ID，便利日后作为指针指示调用相对应的家族成员。其中在属性pNode上，其表示的是下一个同父母的弟或妹ID，也就是说，当某家族成员有若干个子女，其pNode仅指向第一个孩子，其余的孩子如何表示呢？可以通过第一个孩子的pNode指示，如此类推，直到孩子的pNode=0为止。这样就可以避开需在程序设计时预定父母可以拥有的孩子数，有多少孩子就表示多少，实现了动态的储存数据。在选择数据结构方面，从直观来说，选择树型结构通过链表来连接数据无疑是最直观易懂的，我在一起先构思的时候也是从树型结构去想的，但当构思到如何存储和提取数据是，便发觉了问题。毫无疑问，用指针来处理数据的确是便利直观，但当我要储存数据是，便发觉把指针储存进去是没有作用的，因为当我们下一次读取数据的时候，数据内存地址已经不同了，不在是我们上次存储数据时的地址，也就是说指针这时已经是没有作用了。要解决这样的问题，我们必需要在存储数据之前，先家族树序列化，用数组（或者其他可以用数字表示关系的方法）来存储，并且，再下一次读取数据时，再把数据依据序列号重新组成一个家族树，过程比较繁复，而且实现起来也不简洁。所以我便考虑干脆用数组来存储数据，即使是在内存中也用数组来处理数据间的联系。运用依次表这个结构虽然不是那么直观，但在查找数据时的算法设计比较简洁简洁实现，效率高，而且在内存中的数据可以干脆读入到文件中，文件中的数据也可以干脆读入内存，不须要进行转换。所以在衡量的各个方面之后，我确定用数组来处理数据间的联系。2.2功能构想构想好总体规划之后，便起先设计程序中须要用到的各个功能函数，初步构想是要先实现最基本的几项功能，其中数据操作的有：增加成员，修改成员资料，删除成员；数据存取的有：打开家谱，新建家谱，保存家谱，另存家谱；数据查询的有：查看某代信息，按姓名查找，按生日查找，查看成员关系，按诞生日期排序等等。增加成员这项功能做得不够志向，在规划时没有把成员以配偶的形式增加，而只能以子女的形式增加。对应的函数代码如下： voidCOperationFamilytree::Add(Personparent,PersonaddNode){ //本函数把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孩子的兄弟域中}修改成员资料修改成员这项功能实现起来比较简洁，找到要修改成员的名字，再输入新修改的值，整个函数没有什么须要运用算法的地方，但假如想真正写好这个函数，则须要考虑相当多的微小环节，譬如各个输入项目的错误处理等等，要特殊全面地考虑各项微小环节。函数代码如下：voidCFamilytreeDlg::OnModify(){ //TODO:Addyourcommandhandlercodehere if(operFamilytree.GetRoot()==0) return; CModifyInfoDlgdlg; HTREEITEMhItem; hItem=m_peTree.GetSelectedItem(); dlg.m_newname=m_peTree.GetItemText(hItem); Persononeself=0; charoldname[MAX_CHARNUM]; strcpy(oldname,dlg.m_newname); operFamilytree.Find(operFamilytree.GetRoot(),oneself,oldname); if(dlg.DoModal()==IDCANCEL) return; UpdateData(FALSE); PersonnewValue=newPersonNode;strcpy(newValue->,dlg.m_newname); //推断家谱中是否已有用户给定的新名字 if(strcmp(newValue->,oldname)==0); //用户不修改姓名 else{ Personp=0; operFamilytree.Find(operFamilytree.GetRoot(),p,newValue->); //查找家谱中有没有此人 if(p!=0){ AfxMessageBox("家谱中已有此人!"); deletenewValue; 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("此人信息中死亡日期不合实际!"); deletenewValue; return; } if(operFamilytree.CompareDate(newValue->info.deathday,newValue->info.birthday)==-1){ AfxMessageBox("此人死亡日期不行能比其诞生日期早!"); return; } } operFamilytree.Modify(oneself,newValue); RefreshTree(); RefreshList(); IsFamilytreeModified=true; //置家谱修改标记为真 deletenewValue;}删除成员用数组来储存数据，，最麻烦的就是删除数组元素了，在这个程序中，删除数组不但意味着要重新排列各成员，还要重新更新各成员的关系，所以我个人认为在这个程序中，删除成员函数可以说是一个难点。通过分析，发觉删除成员的状况就只有两种，只要针对这两种状况处理好删除，就可以完成成员删除这个功能。１，删除的成员是出于家族中最底层的，也就是删除该成员不会牵连其他成员，但这也须要处理好其父母的孩子数。２，删除的成员还有子孙，则须要连带全部子孙都要删除出家谱。遇到这种状况，不但要像上一种状况那样处理父母和兄弟姐妹的关系，还要记录牵连删除的总人数，因为删除不再是简洁删除了一个人，而是若干个，通过递归调用，可以统计出须要删除的数目 删除函数的相关代码如下：voidCOperationFamilytree::Delete(Person&rootNode){ //本函数删除以rootNode为根结点的全部结点 if(rootNode->parent) //假如rootNode有父结点 if(rootNode->parent->child==rootNode) //假如rootNode为其父结点的第一个孩子 rootNode->parent->child=rootNode->sibling; //因要删掉rootNode,故把其父结点的孩子指针指向rootNode的第一个兄弟 else{ //假如rootNode不是父结点的第一个孩子 Personp=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);}打开家谱打开家谱函数的相关代码如下：intCOperationFamilytree::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)) //诞生日期合法性检查 return FILE_DATA_NOT_PRACTICAL; if(T->info.live==0) //若过世,死亡日期合法性检查 { if(CompareDate(T->info.birthday,T->info.deathday)!=-1) returnFILE_DATA_NOT_PRACTICAL; if(!IsDateValid(T->info.deathday)) return FILE_DATA_NOT_PRACTICAL;} returnOK;}新建家谱新建家谱函数的相关代码如下：voidCOperationFamilytree::NewFamilytree(){ //本函数新建一空家谱 DestroyFamilytree(); //删除原有家谱 T=0;}intCOperationFamilytree::CreateFamilytree(CStringfilename){ //本函数建立一新家谱 DestroyFamilytree(); //建立一新家谱之前，清空原有家谱 FILE*fp; if((fp=fopen(filename,"r"))==0) //打开文件filename returnREAD_FILE_ERROR; T=newPersonNode; //定义根结点 if(!T) returnNOT_ENOUGH_MEMORY; T->child=0; T->sibling=0; T->parent=0; PersonparentT,temp; //定义两个临时结点 charparentname[MAX_CHARNUM]; //定义一个临时字符串数组 //读取根结点值,(姓名,诞生日期(年,月,日),婚否,地址,健在否,(如过世，还有死亡日期)) intresult; result=ReadNode(fp,T,parentname); if(result==FILE_DATA_NOT_PRACTICAL){ deleteT; //若不合法，删除申请的堆空间 T=0; returnresult; } if(strcmp(T->,parentname)==0){ //根结点名字和其父亲名字相同，说明为空树 deleteT; T=0; returnPEDIGREE_EMPTY; } temp=newPersonNode; //申请一结点 if(!temp){ //申请失败 DestroyFamilytree(); //释放申请空间 returnNOT_ENOUGH_MEMORY; } result=ReadNode(fp,temp,parentname); while(strcmp(temp->,parentname)&&strcmp(temp->,"end")){ //读取信息结束的条件是两个人的名字同为end if(result==FILE_DATA_NOT_PRACTICAL){ //若数据不合法，释放已申请空间，然后返回 deletetemp; DestroyFamilytree(); returnresult; } parentT=0; Find(T,parentT,parentname); //找到parentname所在结点parentT if(parentT){ //假如parentT存在，说明parentname在家谱中 //并且parentname为temp的父亲 intcmp; cmp=CompareDate(temp->info.birthday,parentT->info.birthday); if(cmp<0){ //若孩子诞生日期比父亲大，则不对 deletetemp; 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(); //返回出错信息 returnFILE_DATA_ERROR; } temp=newPersonNode; //申请一结点 if(!temp){ //申请失败 DestroyFamilytree(); //释放申请空间 returnNOT_ENOUGH_MEMORY; } result=ReadNode(fp,temp,parentname); //接着读取数据 }//while if(temp) deletetemp; fclose(fp); returnOK;}保存家谱保存家谱函数的相关代码如下：intCOperationFamilytree::SaveFamilytree(CStringfilename){ //本函数保存家谱到文件filename中 FILE*fp; if((fp=fopen(filename,"w"))==0) //打开文件filename returnWRITE_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); returnOK;}voidCOperationFamilytree::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); }}voidSaveNode(FILE*fp,Person&pNode){ //本函数向文件fp中存取一结点pNode charch='\n'; if(pNode){ fprintf(fp,"%s%d%d%d%d%s%d",pNode->,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->); else fprintf(fp,"%s","-1"); fprintf(fp,"%c",ch); }}查看某代信息查看某代信息函数的相关代码如下：intCOperationFamilytree::InGenerationPos(PersonpNode){ //本函数返回pNode结点在第几代 intpos=1; Personp; p=pNode->parent; for(;p!=0;p=p->parent) pos++; returnpos;}按姓名查找按姓名查找函数的相关代码如下：voidCOperationFamilytree::Find(Person&T,Person&Tname,char*name){ //本函数以T为根结点起先,搜寻结点信息中名字等于name的结点 if(T){ //假如T存在 if(strcmp(T->,name)==0) //T结点姓名和name相同，把T结点指针传给Tname Tname=T; else{ Find(T->sibling,Tname,name); //对T的兄弟递归搜寻 Find(T->child,Tname,name); //对T的孩子递归搜寻 } }}按生日查找按生日查找函数的相关代码如下：voidCOperationFamilytree::Find(Person&T,Person*&Tname,intmonth,intday){ //本函数以T为根结点起先,搜寻结点信息中生日等于month,day的结点, //并把全部符合条件的结点指针值存入以Tname为起始地址的地址数组中if(T){ //假如T存在 if(T->info.birthday.month==month&&T->info.birthday.day==day){ //T结点生日和所给相同，把T结点指针传给Tname,同时Tname指针前进 Persontemp; temp=newPersonNode; 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的兄弟递归搜寻 }}查看成员关系查看成员关系函数的相关代码如下：voidCFamilytreeDlg::OnFamilytreeRelations(){ //TODO:Addyourcommandhandlercodehere CRelationsDlgdlg; if(dlg.DoModal()==IDCANCEL) return; UpdateData(FALSE); intpos1,pos2; Persononeself=0; charname1[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; } Personp,q; CStringgeneration; generation+=oneself->; generation+="在家谱中的位置:"; for(q=oneself,p=q->parent;p!=0;p=p->parent){ generation+=q->; generation+="->"; q=p; } generation+=q->; 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->; generation+="在家谱中的位置:"; for(q=oneself,p=q->parent;p!=0;p=p->parent){ generation+=q->; generation+="->"; q=p; } generation+=q->; generation+="\n\n"; CStringcmpResult; if(pos1>pos2) cmpResult.Format("%s在第%d代，%s在第%d代，%s是%s的晚辈.",name1,pos1,name2 ,pos2,name1,name2); elseif(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);}按诞生日期排序按诞生日期排序函数的相关代码如下：voidCOperationFamilytree::SortByBirthday(QuickSortNode*order){ //本函数对依次表order以诞生日期的大小排序 inttotalNums=0; QuickSortNode*startaddr=order; startaddr++; GetPersonNums(T,totalNums); CopyInfoFromBiTreeToArray(T,startaddr); QuickSort(order,1,totalNums);}2.3板块整合以上的功能设计生成的各种函数文件仅是独立的各个板块，要将这些函数有机地联系起来，才能形成可以应用的程序，首先我用了一个DefineStruct.h声明数据类型和各个应用函数，其代码如下：依据家谱的特点，接受孩子-兄弟的二叉树链表表示法（链表的基本单位为以结构PersomNode表示的结点），各种操作以COperationFamilytree类来实现。以下是CoperationFamilytree类包含的数据成员及基本操作classCOperationFamilytree//定义家族成员结构{public:COperationFamilytree();//构造函数virtual~COperationFamilytree();//析构函数voidNewFamilytree();//新建一空家谱intCreateFamilytree(CStringfilename);//从输入文件filename中读取数据建立家谱voidDestroyFamilytree();//删除家谱intSaveFamilytree(CStringfilename);//保存家谱voidPreOrderTraverse(FILE*fp,Person&T,void(*Visit)(FILE*fp,Person&T));//先序遍历(为保存家谱而做)voidPostOrderTraverse(Person&T,void(*Visit)(Person&T));//后序遍历(为删除家谱而做)voidFind(Person&T,Person&Tname,char*name);//从根结点动身，搜寻name所在结点,如找到，存于Tname中，找不到，Tname为0//运用前确保Tname指针为0voidFind(Person&T,Person*&Tname,intmonth,intday);//从根结点动身，搜寻家谱中birthday.month等于month,birthday.day等于day的全部结//点,如找到，存于以Tname为首地址的指针数组中，找不到，Tname为0运用前确保Tname//指针为0voidAdd(Personparent,PersonaddNode);//把addnode加为结点parent的孩子voidDelete(Person&rootNode);//删除以rootNode为根结点的全部结点voidModify(Person&pNode,PersonnewValue);//修改pNode结点为新值newValuevoidSortByBirthday(QuickSortNode*order);//对家谱以诞生日期排序，并把排序结果放在数组order中voidGetPersonNums(Person&T,int&personNums);//得到家谱中总人数intInGenerationPos(PersonpNode);//返回pNode在家谱中是第几代intInSiblingPos(PersonpNode);//返回pNode在其兄弟中的排行intChildNums(PersonpNode);//返回pNode孩子数intCompareDate(Datedate1,Datedate2);//比较两日期的大小boolIsDateValid(Datedate);//检验日期是否合法Person&GetRoot();//得到根结点friendvoidSaveNode(FILE*fp,Person&pNode);//保存结点pNode到文件fp中friendvoidDestroyNode(Person&pNode);//删除结点private:PersonT;//二叉树的根结点intReadNode(FILE*fp,Person&T,char*parentname);//从文件fp中读取信息到结点T中，读取此结点的父亲姓名到parentnaem中(供CreateFamilytree函数调用)voidInsertSibling(Person&firstSibling,PersoninsertSibling);//把insertSibling插入到以firstSibling为首的兄弟中(供CreateFamilytree函数调用)voidCopyInfoFromBiTreeToArray(Person&T,QuickSortNode*&order);//把家谱中以pNode结点为根结点的诞生日期拷贝到快速排序结构数组order中(供SortByBirthday函数调用)voidQuickSort(QuickSortNode*order,intlow,inthigh);//对order[low...high]中的记录进行快速排序(供SortByBirthday函数调用)intPartition(QuickSortNode*order,intlow,inthigh);//对order[low..high]中的记录进行一次排序(供QuickSort函数调用)boolIsLeapYear(intyear);//推断是否闰年（供IsDateValid调用，以检查日期是否合法）}依据MFC的特点，接受CfamilytreeDlg类实现用户窗口界面指令对于家谱的各种操作。classCFamilytreeDlg:publicCDialog{public:voidSaveTip();//保存提示voidInitListCtrl();//初始化列表控件voidRefreshTree();//刷新树，(即刷新显示)voidRefreshList();//刷新列表voidDisplayFamilytree(Person&pNode);//显示树voidDisplayInListCtrl(PersonpNode);//把pNode结点的信息在列表控件中显示出来voidDisplay(CStringtemp);//在列表控件中显示其他信息voidFindInTree(HTREEITEM&hRootItem,HTREEITEM&hItem,char*name);//在树hRootItem中查找name所在结点，如找到，把其结点句柄存入hItem中,找不到，//hItem为0.留意，运用该函数时，确保hItem初值为0voidBirthdayTip();//每次打开一新家谱文件时的生日提示voidDisplayGenerationInfo(Person&pNode,bool&flag,intcount,intgeneration);//显示全部第generation代人的信息voidAddToTree(HTREEITEMhParentItem,Personaddnode);//把addnode加入到树的hParentItem结点中去priva