数据结构课程设计—家谱系统.doc

一.前言1 项目简介 家谱（或称族谱）是一种以表谱形式，记载一个以血缘关系为主体的家族世系繁衍和重要人物事迹的特殊图书体裁。家谱是中国特有的文化遗产，是中华民族的三大文献（国史，地志，族谱）之一，属珍贵的人文资料，对于历史学、民俗学、人口学、社会学和经济学的深入研究，均有其不可替代的独特功能。2系统功能 本项目对家谱管理进行简单的模拟，以实现查看祖先和子孙个人信息、插入家族成员、删除家族成员等功能。本项目的实质是完成对家谱成员信息的建立、查找、插入、修改、删除等功能，可以首先定义家族成员的数据结构，然后将每个功能写成一个函数来完成对数据的操作，最后完成主函数以验证各个函数功能并得出运行结果。一 需求分析1. 系统需求本系统是家谱管理系统，顾名思义，是用来管理家族资料的，要实现建立新家谱，查找家谱文件，增加家族成员，修改家族成员，删除家族成员和查找家族成员等基本功能。家谱管理系统是给家族长辈管理家族资料用的，对电脑的操作不一定熟悉，所以操作界面一定要友好，一定要方便，dos界面的操作一般比较枯燥，综合各种原因，要用MFC实现可视化的界面。2. 环境需求硬件：acer ASPIRE 4740G I5处理器 2G内存 320G硬盘软件：vs 2008二 总体设计3.1 总体设计框架删除结点修改结点添加结点保存家谱读取文件建立家谱程序入口配偶信息关系查询基本查询输出家谱 图1 系统总体设计模块结构图3.2 数据结构设计 关于树形的结构：在树形结构的选择上，根据实际中多子女的现象选择一般树，考虑到家谱中成员可能存在的不定成员数问题，抛弃了以数组为基础的一般树方案，决定用链表来实现。树形结构的外存保存。为了提高效率，树形结构在程序初始化时由外存文件一次读入内存，此后不管插入还是修改，删除都不再对外存的树结构保存文件进行操作，只在内存中处理，程序退出时对外存树结构文件进行一次更新。也就是说，不管在程序运行中中对家谱结构进行多少种，多少次的操作，外存的树结构文件始终只会被程序访问两次。以二叉链表作为树的存储结构，链表中的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，它通过描述每个结点的一个孩子和兄弟信息来反映结点之间的层次关系，其具体的结点结构为：firstChilddatanextSibling其中，firstchild为指向该结点第一个孩子的指针，nextsibling为指向该结点下一个兄弟，elem是数据元素内容，举例如下：3.3 算法设计1、家谱的创建和结点的添加 家谱采用的树的结构，通过左孩子，右兄弟的方式变为二叉树，创建的过程实际上就是二叉树的添加结点的过程，根据父亲的名字添加在父亲结点的左边。代码如下：家谱的创建FamilyTree:FamilyTree() T=NULL;/开始为空家谱 家谱结点的添加void FamilyTree:Add(person parent, person addNode) /将addnode添加到parent作为parent的孩子结点 int n=0; addNode->firstchild=addNode->nextsibling=NULL; /初始时firstchild同nextsibling都为空 addNode->parent=parent; if(parent=NULL) /如果父结点空 if(T=NULL) /如果根结点空 addNode->data.Depth=n; T=addNode; /将addnode赋给根结点 return; n=T->data.Depth+1;/否则将原来的根结点成为新根结点的孩子 T->data.Depth=n; /并使原来根结点的depth值加1 addNode->firstchild=T; T->parent=addNode; T=addNode; return; strcpy(addNode->data.parentname,parent->data.name); n=parent->data.Depth+1; addNode->data.Depth=n;/将depth值加1 if(parent->firstchild=NULL) /如果parent无孩子，把addNode加入其firstchild parent->firstchild=addNode; else InsertSibling(parent->firstchild,addNode); /否则插入到相应的兄弟结点中去 2、 家谱结点的修改家谱结点的修改就是将结点的指针传入，更新数据就可完成，代码如下：void FamilyTree:Modify(person &curnode,person newnode) /修改某个人的信息 strcpy(curnode->data.name,newnode->data.name); strcpy(curnode->data.birthplace,newnode->data.birthplace); strcpy(curnode->data.sex,newnode->data.sex); strcpy(curnode->data.occupation,newnode->data.occupation); strcpy(curnode->data.education,newnode->data.education); strcpy(curnode->data.top_headship,newnode->data.top_headship); curnode->data.height=newnode->data.height; curnode->data.birthdate=newnode->data.birthdate; curnode->data.deathdate=newnode->data.deathdate; 3、 家谱结点的删除结点的删除，如果该结点没有子节点，则直接删除该结点所有信息，如果结点有子节点，则不能删除。void CCMy_Dlg:OnDelete()HTREEITEM pNode=m_pTreePage->m_ShowTree.GetSelectedItem();if(!pNode)MessageBox("请选择结点再删除!");return;if(DataTree.HaveChild(m_CurNode)MessageBox("该结点有孩子结点，不能直接删除!");return;if(MessageBox("确认删除?","警告",MB_ICONWARNING|MB_OKCANCEL)!=1)return;DataTree.DeleteNode(m_CurNode);/删除DataTree中相应的数据QUESTIONm_pTreePage->m_ShowTree.DeleteItem(pNode);if(m_pTreePage->m_ShowTree.GetCount()=0)/删除后若树为空GetDlgItem(IDC_GENERATION)->SetWindowText("未选结点");GetDlgItem(IDC_LINEALNAME)->SetWindowText("");GetDlgItem(IDC_MATENAME)->SetWindowText("");GetDlgItem(IDC_WHOSBRIEF)->SetWindowText("简介");GetDlgItem(IDC_INFORMATION)->SetWindowText("");bIsMemory=true;4、 家谱的存储和读取家谱信息的存储是按先序遍历的方式依次存入硬盘的，读取的时候，将第一个结点的信息对应根结点，后面依次根据父亲的姓名使用插入函数完成家谱的重建，代码如下：家谱的存储void FamilyTree:SaveFamilyTree() /保存二叉树到文件 fstream f("1.dat",ios:binary|ios:out);/以二进制写方式打开文件 if(!f) cerr<<"文件打开失败！"<<endl;/如果不能打开，显示出错信息 return;PreOrderTraverse(f,T,SaveNode);/调用先序遍历写二叉树信息到文件f.close();/关闭文件/person& t=FamilyTree:GetRoot();/ 返回家谱的根结点 /return t;家谱的重建（从文件读取）void FamilyTree:CreateFamilyTree() DestroyFamilyTree();/删除原来家谱树结构 int n=0;/初始化数组下标，用来看有几多个数据 fstream f("1.dat",ios:binary|ios:in);/以二进制读方式打开 if(!f) cerr<<"文件打开失败！"<<endl;/不能打开，显示出错信息 return;f.seekg(0,ios:end);/指针移到文件尾 long posEnd=f.tellg();f.seekg(0,ios:beg);/指针移到文件头 person parentT=new CSNode;person tempmax_char_num;/ 定义读取数据的数组 for(int i=0;i<max_char_num;i+)tempi=new CSNode; / 初始化一个地址值，且不能为空否则出错="" if(posEnd=f.tellg() /记录文件尾位置" f.tellg(="" )/ cout<<"这是一个空家谱！"<<endl; /文件头与文件尾相同，说明文件无数据，为空树 return; while(posEnd!=f.tellg()/从头到尾读取二进制数据 f.read(char*)&(tempn->data),sizeof(Info); n+; NewFamilyTree(); T=temp0;T->firstchild=T->nextsibling=NULL;/将第一个赋给根结点 T->parent = NULL;for(int j=1;j<n;j+) /其余继续用类似add（）函数来添加进树里FindByName(T,parentT,tempj->data.parentname); if(parentT) tempj->firstchild=tempj->nextsibling=NULL; tempj->parent=parentT; if(parentT->firstchild) InsertSibling(parentT->firstchild,tempj); else parentT->firstchild=tempj; f.close();/关闭文件流 5、 家谱信息的遍历主要使用递归的方式遍历家谱树，代码入下：先序遍历：void FamilyTree:PreOrderTraverse(fstream &f,person &T, void (_cdecl *Visit)(fstream &f,person &T) /先序遍历二叉树，并执行visit函数 if(T) (*Visit)(f,T); PreOrderTraverse(f,T->firstchild,Visit); PreOrderTraverse(f,T->nextsibling,Visit); 6、 家族成员的查找查找部分涉及的查找方法多样，这里用按姓名查找来代表，其他查找使用的算法思想是类似的，使用递归的方法，代码如下：void FamilyTree:FindByName(person& T,person& Tname,char* name)/search the name in info from root T /查找姓名name的人，若在家谱中，用Tname返回，否则Tname为空，Tname初始为空 if(T) if(strcmp(T->data.name,name)=0) /用string库的strcmp（）比较两个字符串，若相等，则找到符合条件的 Tname=T; else FindByName(T->firstchild,Tname,name); /对T的firstchild递归搜索 FindByName(T->nextsibling,Tname,name); /对T的nextsibling递归搜索 三 程序实现程序实现部分是算法设计的补充与完善，代码会与算法设计有不同，而且实现了MFC界面显示部分，最终工程的实现以程序的为主。注：代码太长不附在文档上四 测试报告1. 初始化界面： 图2 系统初始化界面效果图2文件读取保存模块 2.1 新建家谱 新建家谱实际操作为创建该家谱第一代成员，即该树的根结点。默认创建男性，默认创建当前结点的孩子结点，第一代不能创建兄弟结点，按取消操作，退出创建此家谱 图3 新建家谱界面设计效果图2.2 打开文件（1） 按打开按键，弹出文件窗口，默认打开txt格式文件图4 打开载入文件界面设计效果图（2） 打开文件后，操作窗口标题栏会显示该文件的文件名，并显示本家谱的信息 图5 打开文件信息效果图2.3 保存文件按保存按键，直接保存信息到文件，按另存为按键，弹出另存为窗口，可以选择保存路径保存家谱文件。 图6 保存文件信息页面效果图3. 操作模块3.1创建新结点 点击已经存在的一个结点，点击创建新结点按钮，表示在当前结点下创建子节点或者兄弟结点，左边显示编辑框，输入名字信息和配偶名字信息，可以选择性别，可以选择所创建新结点是当前结点的子节点或是兄弟结点。 图7 创建结点页面效果图3.2 修改结点点击要修改的结点，按修改结点按钮，左边显示编辑框，可以修改名字信息和配偶信息 图8 修改结点页面设计效果图3.3 删除结点（1） 删除子节点。选择要删除的子节点，按删除结点按钮，弹出警告窗口，询问是否确认删除结点，按确定删除结点 图9 删除子节点页面效果图（2） 删除有子节点的父节点，会弹出警告窗口，说明有子节点，不能删除该结点 图10 删除父节点页面效果图4. 查找4.1按照姓名信息关键字查找（1） 不区分大小写 图11 按照名字信息不分大小写查找页面效果图（2） 区分大小写 图12 按照姓名信息区分大小写查找页面效果图4.2 按照配偶名字信息关键字查找图13 按照配偶姓名信息查找页面效果图五 目标完成总结1. 完成了新家谱的创建，由根结点开始创建新的家谱树2. 完成了家谱文件的读取，可以打开指定路径的文件并在系统中显示该家谱信息3. 完成了家谱文件的保存，可以把新建或者修改的家谱文件保存到指定的路径4. 完成了家谱树中新结点的创建，可以创建原有结点的兄弟结点或者子结点，根节点只能创建其子结点5. 完成了家谱树中任意结点的修改功能，可以修改结点的信息和其配偶信息6. 完成了家谱树中任意子结点的删除功能，有子结点的父节点无法直接删除7. 完成了家谱树中结点的查找功能，可以按照姓名信息区分大小写或者不分大小写查找，也可以按照配偶信息查找六 遇到的问题和解决方案1. 需要设计一个简单易用的系统，方便没有计算机技术的管理人员使用，普通的dos界面就无法满足此要求了，所以就要采取编写可视化的解决方案。2. 没有学过可视化编程的相关技能，要从零开始学习此门课程，通过购买相关书籍和上网查找资料解决编程过程中遇到的问题。3. 测试阶段总会出现这样那样的问题，这时候就需要很多的耐心，并且要细心的处理每个错误。七 尚未解决的问题和应对策略1. 在删除结点功能上，只能删除子结点，不能删除拥有子结点的父结点，要解决这个尚未解决的问题，需要在程序上做修改，在树形结构上做修改。但是由于完成系统之后，还没写报告，由于时间紧迫，没有添加此项功能。2. 在删除结点功能上，每次只能删除一个结点，在效率上未能体现。这个问题是比较难解决的问题，以我现在的编程能力暂时未能想到解决方案，在日后的学习中会慢慢发掘和探索解决方法。3. 数据没有加密，容易篡改。由于数据存放于txt文件里面，修改里面的数据较为简单，严重影响系统的安全性。可以定义一种二进制文件，只有本系统才能打开，这样就对数据进行了加密。八 收获和心得这次大作业的完成时间是整整一个暑假，但回想起来，时间都用在实习上，没有好好利用暑假的两个月来做课程设计。由于我本身编程能力不强，构思，写代码，修改，调试的时间加起来绝对是要花上不少时间的，而且对于可视化MFC之前从来没用过，都要自学，所花的时间就更多了。就是因为付出很多，所以在前期的设计组织中，中期的代码编写和后期的修改调试中都学到了不少。起初我的家谱中数据并不是以结构的形式打包，读入，写出操作的时候代码异常繁琐，这是恰好看到一本编程书上有用结构输入输出的范例，深深感到结构化确实是方便多了，而且读写不容易出错。当时我的代码本已经写了有一大半，思虑再三，还是决定进行大换血，家谱数据的改变让程序来了个大换血，提高了效率的同时，代码几乎变了一多半。我想，当时唯一不变的就只有对整个程序越来越清醒地认识和对将要完成的代码的更准确地把握。代码完成之后，一编译，至少有五六十个错误提示，而且最末debug一行栏的最后一行提示因为先前的错误而中断编译，有的是指针指向错误，有的是忘了分号，括号，更多的是一些赋值错误，前面的错误都好改，赋值错误就比较麻烦了，因为要使用赋值的地方太多，逐行改代码虽然也可以，但实在是一个巨大工程。所谓巧招必是险招至少对我是这样说来惭愧，我只有尝试着写以前从未是过的运算符重载函数，为此专门翻找出了大一的C+教材，温习了一番运算符重载才战战兢兢地搞定了赋值问题。试运行时出现了更多的问题，而且更具有隐蔽性，几次为了一个逻辑错误而来回反复地翻看代码，嘿嘿，再加上网上有代码的传说，让人有想直接放弃的冲动，但一想到写代码的辛苦，觉得放弃了实在可惜。那几天吃饭，睡觉，走路，看电视，随时随地，都记挂着那几处错误，脑子都会浮现出代码的影子，不自觉地开始找错误。哎那种感觉！不知道是充实还是急迫地烦恼，最后终于找到了，根本来不急高兴，只有松了一口气和一阵的疲惫。不管怎样，我相信，有付出才会有收获，虽然完成的系统不是最好的，但我觉得已经很满足，很对得起我这个酱油程序员了。只有不断地学习，不断得提升自己，才能真正的取得成功，获得别人的肯定。这是我最大的收获了！