数据结构课程设计论文及代码-家谱系统的设计与实现

工程名称：家谱系统的设计与实现学生姓名：学号：班级：指导教师：2011年12月23日目录TOC\o"1-2"\u1系统需求分析 11.1问题分析 11.2任务意义 12设数据结构设计及用法说明 23详细设计和编码 33.1初始化 33.2功能选择 43.3信息输入 73.4信息输出 73.5信息存盘 83.6信息清盘 93.7信息查询 104实验结果 134.1菜单函数功能测试 134.2输入功能函数测试 134.3输出功能函数测试 134.4清盘功能函数测试 134.5存盘功能函数测试 144.6查询功能函数测试 15致谢 17参考文献 18附录：源代码 191系统需求分析1.1问题分析从课程设计的题目要求可以知道，我需要设计一个对数据输入，输出，储存，查找的多功能软件，我选择用二叉树来保存家族的根本信息，包括姓名及它们的关系，但是由于家族信息很巨大而且关系很复杂所以采用二叉树来储存它们的信息及输出它们的关系。并且具有保存文件的功能，以便下次直接使用先前存入的信息。1.2任务意义家谱的功能是查询家族每个人的信息，并且输出它们的信息，还要具有查询输出功能。这样复习了一下查询。插入。删除函数的应用。并复习了上学期c语言的文件储存及调用功能，子函数和递归调用功能，熟练运用这些函数。

2系统数据结构设计及用法说明采用文件保存信息，并且从文件中输出原先保存的信息，用结构体fnode来储存家族的信息，采用递归的方法从fam中创立一个空二叉树，然后初始化二叉树。采用InputFam函数添加信息，OutputFam函数输出信息，DelAll函数删除家族的全部记录，SaveFile函数保存添加的信息，FindNode函数查找节点。文件1：输入输入父亲、母亲和儿子的姓名0：存盘返回文件1：输入输入父亲、母亲和儿子的姓名0：存盘返回图2数据存储结构图相应的存储结构代码为：typedefstructfnode{ charfather[NAMEWIDTH]; charwife[NAMEWIDTH]; charson[NAMEWIDTH]; charbrother[NAMEWIDTH];}FamType;typedefstructtnode{ charname[NAMEWIDTH]; structtnode*lchild,*rchild;}BTree;3详细设计和编码3.1初始化图3-1为初始化函数的流程图，主要是对二叉树中数据域置空，对二叉树中的数据进行初始化。代码如下：BTree*CreatBTree(char*root,FamTypefam[],intn)//从fam中〔含n个记录〕递归创立一棵二叉树{ inti=0,j; BTree*bt,*p; bt=(BTree*)malloc(sizeof(BTree));//创立父亲结点 strcpy(bt->name,root); bt->lchild=bt->rchild=NULL; while(i<n&&strcmp(fam[i].father,root)!=0) i++; if(i<n)//找到该姓名的记录 { p=(BTree*)malloc(sizeof(BTree));//创立母亲结点 p->lchild=p->rchild=NULL; strcpy(p->name,fam[i].wife); bt->lchild=p; for(j=0;j<n;j++)//找所有儿子 if(strcmp(fam[j].father,root)==0)//找到一个儿子 { p->rchild=CreatBTree(fam[j].son,fam,n); p=p->rchild; } } return(bt);}图3-1初始化函数流程图3.2功能选择图3-2为功能选择模块函数的流程图，主要提供1：文件2：家谱两个功能模块让用户选择。输入数字1的时候，出现界面1：输入2：输出9：清盘0：存盘返回。返回后输入数字2，出现界面1：找某人的所有儿子2：找某人所有祖先3：找某人所有兄弟。用户根据提示操作。代码如下：voidmain(){ BTree*bt; BTree*p,*father; FamTypefam[MaxSize]; intn,sel,sell; charxm[NAMEWIDTH]; ReadFile(fam,n); do { cout<<"1.文件2:家谱0:退出请选择:"; cin>>sel; switch(sel) { case1: do { cout<<"1:输入2:输出9:全清0:存盘返回请选择:"; cin>>sell; switch(sell) { case9: DelAll(fam,n); break; case1: InputFam(fam,n); break; case2: OutputFile(fam,n); break; case0: SaveFile(fam,n); break; } }while(sell!=0); break; case2: bt=CreatBTree("f1",fam,n); do { cout<<"1:找某人所有儿子2:找某人所有祖先3:查找某人所有兄弟0:返回请选择:"; cin>>sell; switch(sell) { case1: FindSon(bt); break; case2: cout<<">>"; Ancestor(bt); cout<<endl; break; case3: cout<<">>"; FindBrother(bt); cout<<endl; break; } }while(sell!=0); break; } }while(sel!=0);}图3-2功能选择模块函数流程图3.3信息输入图3-3为信息输入模块函数的流程图，出现界面请输入父亲、母亲和儿子的姓名让用户输入信息。代码如下：voidInputFam(FamTypefam[],int&n)//添加一个记录{ cout<<">>输入父亲、母亲和儿子姓名:"; cin>>fam[n].father>>fam[n].wife>>fam[n].son; n++;}图3-3信息输入模块函数流程图3.4信息输出图3-4为信息输出模块函数的流程图，自动输出数据的信息及它们之间的家谱关系。按顺序输出父亲，母亲，儿子。代码如下：voidOutputFile(FamTypefam[],intn)//输出简朴文件的所有记录{ inti; if(n<0) { cout<<">>没有任何记录!"<<endl; return; } for(i=0;i<n;i++) cout<<fam[i].father<<fam[i].wife<<fam[i].son;}图3-4信息输出模块函数流程图3.5信息存盘图3-5为信息存盘模块函数的流程图，将用户输入的信息存盘，下次要用时自动调用。代码如下：voidSaveFile(FamTypefam[],intn)//将fam数组存入数据家谱文件{ inti; FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>数据家谱文件不能翻开"<<endl; return; } for(i=0;i<n;i++) fwrite(&fam[i],sizeof(FamType),1,fp); fclose(fp);}图3-5信息存盘模块函数流程图3.6信息清盘图3-6为信息清盘模块函数的流程图，将用户输入的信息全部清盘。代码如下；voidDelAll(FamTypefam[],int&n)//去除家谱文件的全部记录{ FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>不能翻开家谱文件"<<endl; return; } n=0; fclose(fp);}图3-6信息读盘模块函数流程图3.7信息查询图3-7为信息查询模块函数的流程图，查询用户输入数据的信息及家谱关系。具有的功能是1：找某人所有儿子2：找某人所有祖先3：找某人所有兄弟。用户根据需要操作。找某人所有儿子的代码：voidFindSon(BTree*bt)//输出某人的所有儿子{ charxm[NAMEWIDTH]; BTree*p; cout<<">>父亲姓名:"; cin>>xm; p=FindNode(bt,xm); if(p==NULL) cout<<">>不存在"<<xm<<"的父亲!"<<endl; else { p=p->lchild; if(p==NULL) cout<<">>"<<xm<<"没有妻子"<<endl; else { p=p->rchild; if(p==NULL) cout<<">>"<<xm<<"没有儿子!"; else { cout<<">>"<<xm<<"的儿子:"; while(p!=NULL) { cout<<p->name; p=p->rchild; } cout<<endl; } } }}//找某人所有祖先的代码：voidAncestor(BTree*bt)//输出某人所有的祖先{ BTree*p; charxm[NAMEWIDTH]; cout<<">>输入姓名:"; cin>>xm; p=FindNode(bt,xm); if(p!=NULL) Path(bt,p); else cout<<">>不存在"<<xm;}//找某人所有兄弟的代码：voidFindBrother(BTree*bt){ charxm[NAMEWIDTH]; BTree*p,*father; cout<<">>某人的姓名:"; cin>>xm; p=FindNode(bt,xm); Path1(bt,p);//双亲存在数组St[MaxSize] father=St[0]; findson1(bt,father); //调用findson函数找儿子}图3-7查询模块函数流程图

4实验结果4.1菜单函数功能测试系统运行后就会自动显示如图4-1的主菜单，选项包括：1、文件，2、家谱，0、退出，。当用户选择相应的代号就进入相应的功能模块。图4-1主菜单函数功能检测4.2输入功能函数测试系统运行后就会自动显示如图4-2的输入功能模块，界面出现1：输入>>输入父亲、母亲和儿子的姓名用户输入信息。图4-2输入功能函数测试4.3输出功能函数测试系统运行后就会自动显示如图4-3的输出功能模块，界面出现2：输出。用户输入数字2后系统自动输出数据信息。图4-3输出功能函数测试4.4清盘功能函数测试系统运行后就会自动显示如图4-4的清盘功能模块，界面出现9：全清。用户输入数9后自动系统去除所有的数据并返回。图4-4清盘功能函数测试4.5存盘功能函数测试系统运行后就会自动显示如图4-5的存盘功能模块，界面出现0：存盘返回。用户输入数0后系统自动保存所有的数据并返回。图4-5存盘功能函数测试4.6查询功能函数测试系统运行后就会自动显示如图4-6的查询功能模块，界面出现1：找某人的所有儿子图4-6查询功能函数测试

5体会程序的关键是掌握二叉树的相关操作、二叉树的创立和运用、结点的查找、祖宗结点的查找等。在编程的过程中，出现了很多问题，如二叉树无法建立、程序内存读取不了、忘了添加头文件等错误。在单步调试和添加提示输出的情况下修改程序运行正确。查找首先要判断该结点是否为空，再与查找到的结点比拟，否那么会内存无法读取，强行结束程序。祖宗结点的查找一直是个大问题，在参考书的帮助下想到了后续遍历，是可以从孩子往上找到。兄弟结点的查找，往上找哥哥，还要往下找弟弟，首先要找到母亲结点，再依次输出。

致谢感谢学校机房给我们提供良好的写代码环境。感谢松哥和莹姐孜孜不倦的教导我们。感谢在写代码期间同学们对我的帮助，让我能顺利的写出代码。

参考文献[1]谭浩强.C语言课程设计〔第三版〕.北京：清华大学出版社,1996.5[2]方超昆.C++程序设计教程.北京：邮电大学出版社,2009[3]李春葆.数据结构教程〔第3版〕：清华大学出版社，2009[4]WalterSavitch.C++面向对象程序设计〔第7版〕：清华大学出版社，2010附录：源代码#include<iostream.h>#include<stdio.h>#include<malloc.h>#include<string.h>#include<stdlib.h>#defineMaxWidth40#defineMaxSize30#defineNAMEWIDTH10typedefstructfnode{ charfather[NAMEWIDTH]; charwife[NAMEWIDTH]; charson[NAMEWIDTH]; charbrother[NAMEWIDTH];}FamType;typedefstructtnode{ charname[NAMEWIDTH]; structtnode*lchild,*rchild;}BTree;//家谱树类型BTree*CreatBTree(char*root,FamTypefam[],intn)//从fam中〔含n个记录〕递归创立一棵二叉树{ inti=0,j; BTree*bt,*p; bt=(BTree*)malloc(sizeof(BTree));//创立父亲结点 strcpy(bt->name,root); bt->lchild=bt->rchild=NULL; while(i<n&&strcmp(fam[i].father,root)!=0) i++; if(i<n)//找到该姓名的记录 { p=(BTree*)malloc(sizeof(BTree));//创立母亲结点 p->lchild=p->rchild=NULL; strcpy(p->name,fam[i].wife); bt->lchild=p; for(j=0;j<n;j++)//找所有儿子 if(strcmp(fam[j].father,root)==0)//找到一个儿子 { p->rchild=CreatBTree(fam[j].son,fam,n); p=p->rchild; } } return(bt);}BTree*FindNode(BTree*bt,charxm[])//采用线序递归算法找name为xm的结点{ BTree*p=bt; if(p==NULL) return(NULL); else { if(strcmp(p->name,xm)==0) return(p); else { bt=FindNode(p->lchild,xm); if(bt!=NULL) return(bt); else return(FindNode(p->rchild,xm)); } }}voidfindson1(BTree*bt,BTree*p)//找p的孩子{ charxm[NAMEWIDTH]; if(p==NULL) cout<<"没有孩子！"; else { p=p->lchild; if(p==NULL) cout<<"没有孩子！"; else { p=p->rchild; if(p==NULL) cout<<"没有兄弟!"; else { cout<<"兄弟:"; while(p!=NULL) { cout<<p->name<<""; p=p->rchild; } cout<<endl; } } }}voidFindSon(BTree*bt)//输出某人的所有儿子{ charxm[NAMEWIDTH]; BTree*p; cout<<">>父亲姓名:"; cin>>xm; p=FindNode(bt,xm); if(p==NULL) cout<<">>不存在"<<xm<<"的父亲!"<<endl; else { p=p->lchild; if(p==NULL) cout<<">>"<<xm<<"没有妻子"<<endl; else { p=p->rchild; if(p==NULL) cout<<">>"<<xm<<"没有儿子!"; else { cout<<">>"<<xm<<"的儿子:"; while(p!=NULL) { cout<<p->name; p=p->rchild; } cout<<endl; } } }} BTree*St[MaxSize];intPath(BTree*bt,BTree*s)//采用后续非递归遍历法输出从根结点到*s结点的路径{ BTree*p; inti,flag,top=-1;//栈指针置初值 do { while(bt)//将bt的所有左结点进栈 { top++; St[top]=bt; bt=bt->lchild; } p=NULL;//p指向当前结点的前一个已访问的结点 flag=1;//设置bt的访问标记为已访问过 while(top!=-1&&flag) { bt=St[top];//取出当前的栈顶元素 if(bt->rchild==p)//右子树不存在或已被访问 { if(bt==s)//当前访问的结点为要找的结点，输出路径 { cout<<">>所有祖先:"; for(i=0;i<top;i++) cout<<St[i]->name<<endl; return1; } else { top--; p=bt;//p指向刚被访问的结点 } } else { bt=bt->rchild;//bt指向右子树 flag=0;//设置未被访问的标记 } } }while(top!=-1);//栈不为空时循环 return0;//其他情况时返回0}intPath1(BTree*bt,BTree*s)//采用后续非递归遍历法输出从根结点到*s结点的路径{ BTree*p; inti,flag,top=-1;//栈指针置初值 do { while(bt)//将bt的所有左结点进栈 { top++; St[top]=bt; bt=bt->lchild; } p=NULL;//p指向当前结点的前一个已访问的结点 flag=1;//设置bt的访问标记为已访问过 while(top!=-1&&flag) { bt=St[top];//取出当前的栈顶元素 if(bt->rchild==p)//右子树不存在或已被访问 { if(bt==s)//当前访问的结点为要找的结点，输出路径 { for(i=0;i<top;i++) return1; } else { top--; p=bt;//p指向刚被访问的结点 } } else { bt=bt->rchild;//bt指向右子树 flag=0;//设置未被访问的标记 } } }while(top!=-1);//栈不为空时循环 return0;//其他情况时返回0}voidAncestor(BTree*bt)//输出某人所有的祖先{ BTree*p; charxm[NAMEWIDTH]; cout<<">>输入姓名:"; cin>>xm; p=FindNode(bt,xm); if(p!=NULL) Path(bt,p); else cout<<">>不存在"<<xm;}voidFindBrother(BTree*bt){ charxm[NAMEWIDTH]; BTree*p,*father; cout<<">>某人的姓名:"; cin>>xm; p=FindNode(bt,xm); Path1(bt,p);//双亲存在数组St[MaxSize] father=St[0]; findson1(bt,father); //调用findson函数找儿子}voidDelAll(FamTypefam[],int&n)//去除家谱文件的全部记录{ FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>不能翻开家谱文件"<<endl; return; } n=0; fclose(fp);}voidReadFile(FamTypefam[],int&n)//读家谱文件并存入fam数组中{ FILE*fp; longlength; inti; if((fp=fopen("fam.dat","rb"))==NULL) { n=0; return; } fseek(fp,0,2);//家谱文件位置指针移到家谱文件尾 length=ftell(fp);//length求出家谱文件长度 rewind(fp);//家谱文件位置指针移到家谱文件首 n=length/sizeof(FamType);//n求出家谱文件中的记录个数 for(i=0;i<n;i++) fread(&fam[i],sizeof(FamType),1,fp);//将家谱文件中的数据读到fam中 fclose(fp);}voidSaveFile(FamTypefam[],intn)//将fam数组存入数据家谱文件{ inti; FILE*fp; if((fp=fopen("fam.dat","wb"))==NULL) { cout<<">>数据家谱文件不能翻开"<<endl; return; } for(i=0;i<n;i++) fwrite(&fam[i],sizeof(FamType),1,fp); fclose(fp);}voidInputFam(FamTypefam[],int&n)//添加一个记录{ cout<<">>输入父亲、母亲和儿子姓名:"; cin