数据结构课设报告

《数据结构》课程设计报告题目：简易电子家谱系统的设计与实现姓名:涂雯学号：U200814434班级：0806专业：计算机科学与技术报告日期：2010年9月18日一．问题描述问题背景家谱是记载同一姓氏血缘关系的世系、重要人物、个人事迹、家族历史为主要内容的谱籍，又称“族谱”、“家谱”、“家乘”，还有称作“谱碟”。家谱上可以追本溯源，缅怀先人，下可以辨明关系，联络宗亲，从而启孝梯心，唤德善之本，激励后人，奋发有为，其作用不可尽述。在社会方面，家谱对于海内外华人寻根认祖，增强民族凝聚力起着重要作用。在文史工作者，家谱是研究人口学、社会学、经济学、历史学、氏族学、人物传记，以及研究地方史乃是重要资料。在个人方面家谱又是每个公民身份证明之一。问题内容：用树形的形式表示某家族的家谱，每个树结点表示一个家族成员，成员基本信息如下，具体属性自行确定。1、姓名2、性别3、出生地4、配偶5、电话6、家庭住址7、职业8、简历9、其他系统实现功能：1、家谱信息1.1、输入1.2、修改1.3、删除2、查询2.1、某家谱成员的所有子孙的集合2.2、某家谱成员的所有祖先的集合2.3、某家谱成员的所有同辈成员的集合2.4、求某家谱成员的所有上一辈成员的集合2.5、给出两个家谱成员，确定他们的关系2.6、其他查询3、统计功能3.1、统计家谱成员的总人数3.2、统计从事某种职业的人数3.3、综合统计其他功能要求：1、用文件保存家谱信息2、图形方式显示家谱二．系统总体设计（模块结构图）三．算法和数据结构的设计由于家族关系本身具有树的特点，所以家族关系在内存的数据结构首选为树。家庭成员之间的关系，用树形结构（家族树）表示，通过左孩子右兄弟的方式变为二叉树，创建的过程实际上就是二叉树的添加结点的过程，根据父亲的名字添加在父亲结点的左边。家谱的创建FamilyTree::FamilyTree(){T=NULL;//开始为空家谱}家谱结点的添加voidFamilyTree::Add(personparent,personaddNode){//将addnode添加到parent作为parent的孩子结点intn=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值加1addNode-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值加1if(parent-firstchild==NULL)//如果parent无孩子，把addNode加入其firstchildparent-firstchild=addNode;elseInsertSibling(parent-firstchild,addNode);//否则插入到相应的兄弟结点中去}家谱结点的修改就是将结点的指针传入，更新数据就可完成，代码如下：voidFamilyTree::Modify(person&curnode,personnewnode){//修改某个人的信息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;}家谱结点的删除是删除该结点及这个结点对应的所有孩子结点的信息，释放内存空间就可完成，代码如下：voidFamilyTree::Delete(person&rootNode){//删除rootnode结点以及他的所有孩子结点if(rootNode-parent)//rootnode不是根结点if(rootNode-parent-firstchild==rootNode)//如果rootnode为其父结点的第一个孩子rootNode-parent-firstchild=rootNode-nextsibling;//将rootnode的nextsibling结点变为rootnodeparent结点的firstchild结点else{personp=rootNode-parent-firstchild;//否则，找到rootnode在兄弟中的位置for(;p-nextsibling!=rootNode;p=p-nextsibling);p-nextsibling=rootNode-nextsibling;//插入到兄弟中}PostOrderTraverse(rootNode-firstchild,DestroyNode);//调用后序遍历删除rootnode的所有孩子结点if(rootNode==T)//删除rootnode结点DestroyNode(T);elseDestroyNode(rootNode);}家谱信息的存储是按先序遍历的方式依次存入硬盘的，读取的时候，将第一个结点的信息对应根结点，后面依次根据父亲的姓名使用插入函数完成家谱的重建，代码如下：voidFamilyTree::SaveFamilyTree(){//保存二叉树到文件fstreamf(1.dat,ios::binary|ios::out);//以二进制写方式打开文件if(!f){cerr文件打开失败！endl;//如果不能打开，显示出错信息return;}PreOrderTraverse(f,T,SaveNode);//调用先序遍历写二叉树信息到文件f.close();//关闭文件//person&t=FamilyTree::GetRoot();//返回家谱的根结点//returnt;}家谱信息的遍历主要使用递归的方式遍历家谱树，代码入下：先序遍历：voidFamilyTree::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);}}后序遍历：voidFamilyTree::PostOrderTraverse(person&T,void(__cdecl*Visit)(person&T)){//后序遍历二叉树，并执行visit函数if(T){PostOrderTraverse(T-firstchild,Visit);PostOrderTraverse(T-nextsibling,Visit);(*Visit)(T);}}成员的查找查找部分涉及的查找方法多样，这里用按姓名查找来代表，其他查找使用的算法思想是类似的，使用递归的方法，代码如下：voidFamilyTree::FindByName(person&T,person&Tname,char*name)//searchthenameininfofromrootT{//查找姓名＝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递归搜索}}}四．程序测试及结果分析程序在VC里编译连接运行以后，显示主界面如下：选择相应的操作数，以回车键结束。例如新建家谱时，出现如下界面，按提示输入各种信息。添加成员，类似界面，按照操作提示输入家谱成员信息。载入家谱：显示家谱所有信息：删除彭了及其子孙后的结果如下：删除成功。重新保存家谱并退出：退出后再进入，显示家谱所有成员信息，可以看出文件已经被保存。经过测试，功能都已实现。五．复杂度分析1)NewFamilyTree()O(1)2)FamilyTree()O(1)3)CreateFamilyTree()O(n)4)DestroyNode(person&pnode)O(1)5)DestroyFamilyTree()O(n)6)PostOrderTraverse(person&T,void(__cdecl*Visit)(person&T))O(n)7)PreOrderTraverse(fstream&f,person&T,void(__cdecl*Visit)(fstream&f,person&T))O(n)8)SaveNode(fstream&f,person&pnode)O(1)9)SaveFamilyTree()O(n)10)ReadNode(fstream&f,person&pnode)O(1)11)FindByName(person&T,person&Tname,char*name)O(n)12)FindByBirthplace(person&T,person&Tname,char*birthplace)O(n)13)FindByBirthday(person&T,person&Tname,Dateday1)O(n)14)FindByDeathday(person&T,person&Tname,Dateday1)O(n)15)FindBySex(person&T,person&Tname,char*sex)O(n)16)FindByHeight(person&T,person&Tname,inth)O(n)17)FindByAddress(person&T,person&Tname,char*address)O(n)18)FindByEducation(person&T,person&Tname,char*edu)O(n)19)FindByOccupation(person&T,person&Tname,char*job)O(n)20)FindByTopHeadship(person&T,person&Tname,char*top)O(n)21