数据结构课程设计报告（用二叉树实现家谱管理系统）.doc

1、数据结构课程设计题目：用二叉树实现家谱管理系统姓名：学号：完成日期：一、需求分析 建立输入文件以存放最初家谱中各成员的信息。 成员的信息中均应包含以下内容：姓名、出生日期、婚否、地址、健在否、死亡日期（若其已死亡）也可附加其它信息、但不是必需的。 能对修改后的家谱存盘以备以后使用。 能从文件中读出已有的家谱，形成树状关系。 家谱建立好之后，以图形方式显示出来。 显示第n 代所有人的信息。 按照姓名查询，输出成员信息（包括其本人、父亲、孩子的信息）。 按照出生日期查询成员名单。 输入两人姓名，确定其关系。 某人添加孩子。 删除某人（若其还有后代，则一并删除）。 修改某人信息。 按出生日期对家谱中

2、所有人排序。 打开一家谱时，若家谱中某人的生日在打开家谱的那一天，应给出提示。二、概要设计采用二叉树进行家谱的管理、树形控件及列表控件进行家谱的显示。程序涉及以下三种类型，但基本操作均在“家谱”类型中。1定义“个人信息”类型：ADT Person数据对象：D=Pj | Pj=姓名、出生日期、婚否、地址、健在否（如过世，还应有其死亡日期），j=0,1,2,n,其中n=0数据关系：R=基本操作：无。ADT Person2.定义“家谱类型文件”类型ADT FamilytreeFile数据对象：D=Aj | Aj 属于 Person,j=1,2,3,n 其中n=1数据关系：D 中每个对象用换行符隔开,

3、R= | Aj 属于D,j=1,3,n 其中n=1,String 属于字符串类型，为Aj 父亲姓名(若String=-1,Aj 无父亲，若String=Aj 的姓名,表示家谱文件结束)基本操作：1 打开家谱类型文件，并建立兄弟、孩子二叉树。2 从内存中读取兄弟、孩子二叉树，并建立家谱类型文件。ADT FamilytreeFlie3定义“家谱”类型ADT Familytree数据对象：D=Aj | Aj 属于Person,j=1,2,3,n 其中n=0数据关系：V= | Aj-1,Aj 属于D,j=2,3,n 其中n=2，且Aj-1 与Aj 为祖先与后代关系（parent）、后代与祖先关系(ch

4、ild)、兄弟之间关系（sibling）基本操作：1 显示某人信息。2 修改某人信息。3 增加某人孩子。4 删除某人。5 通过某人查找其双亲、孩子、兄弟。ADT Familytree三、详细设计1定义“个人信息”类型：struct Info /一个人的有关信息在内存中的存储结构char nameMAX_CHARNUM; /姓名Date birthday; /出生日期int marry; /婚否char addrMAX_CHARNUM; /住址int live; /健在否Date deathday; /死亡日期;2.定义“家谱类型文件”类型 /一个人的有关信息在磁盘文件中存储结构char nam

5、eMAX_CHARNUM; /姓名int birthday.year; /出生年份int birthday.month; /出生月份int birthday.day; /出生日期int marry; /婚否char addrMAX_CHARNUM; /住址int live; /健在否int deathday.year; /死亡年份int deathday.month; /死亡月份int deathday.day; /死亡日期char fathername; /父亲名字;3定义“家谱”类型struct PersonNode /一个人的信息和与其他人关系的存储结构Info info; /自己的信息

6、PersonNode* parent; /指向父亲的指针PersonNode* child; /指向孩子的指针PersonNode* sibling; /指向兄弟的指针*Person;4. 用结构Date 存储日期struct Date /年、月、日存储结构int year; /年int month; /月int day; /日;5用结构QuickSortNode 存储快速排序数组值（为快速排序而设）struct QuickSortNode /为以出生日期大小快速排序建立的存储结构Date birthday; /出生日期Person oneself; /指向自己的指针;6. 根据家谱的特点，采

7、用孩子-兄弟的二叉树链表表示法（链表的基本单位为以结构ersonNode 表示的结点），各种操作以COperationFamilytree 类来实现。以下是CoperationFamilytree 类包含的数据成员及基本操作class COperationFamilytreepublic:COperationFamilytree();/构造函数virtual COperationFamilytree();/析构函数void NewFamilytree();/新建一空家谱int CreateFamilytree(CString filename);/从输入文件filename 中读取数据建立家谱

8、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 所在结点,

9、如找到，存于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& rootNod

10、e);/删除以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);/返回

11、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 R

12、eadNode(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);/把家

13、谱中以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);/判断是否闰年（供IsDateVal

14、id 调用，以检查日期是否合法）;7. 根据MFC 的特点，采用CfamilytreeDlg 类实现用户窗口界面指令对于家谱的各种操作。class CFamilytreeDlg : public CDialogpublic:void SaveTip();/保存提示void InitListCtrl();/初始化列表控件void RefreshTree();/刷新树，(即刷新显示)void RefreshList();/刷新列表void DisplayFamilytree(Person& pNode);/显示树void DisplayInListCtrl(Person pNode);/把pNod

15、e 结点的信息在列表控件中显示出来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 cou

16、nt,int generation);/显示所有第generation 代人的信息void AddToTree(HTREEITEM hParentItem,Person addnode );/把addnode 加入到树的hParentItem 结点中去private:char savepathMAX_CHARNUM;/家谱第一次被保存时的路径bool IsFamilytreeModified;/家谱是否被修改标记COperationFamilytree operFamilytree;/对家谱操作的一个类实例，所有的家谱操作均由它调用成员函数来完成;8为使程序结构趋于清晰，分别使用CAddInf

17、oDlg、CBirthdayDlg、CDelInfoDlg、CFileOpenAndSaveDlg、CModifyInfoDlg、CPersonalInfoDlg、CRelationsDlg、CSearchGenerationDlg 类实现用户窗口对于家谱的增加成员、按生日查找、删除成员、文件输入输出、修改成员信息、按名字查找、成员关系显示、按代数显示等各种操作。纵上所示，本程序的两主要类为CoperationFamilytree 类：所有对家谱的操作均由此类完成。CFamilytreeDlg 类：所有对用户菜单命令的解释均由此类完成，然后调用CoperationFamilytree 类的成员

18、函数执行命令并显示结果。四、重要函数分析1.读取家谱文件，建立二叉树int COperationFamilytree:ReadNode(FILE *fp, Person &T,char* parentname)/本函数从文件fp 中读取信息到结点T 中,并读取结点的父亲名字到字符数组parentname 中/分别读取结点值,为:姓名,出生日期(年,月,日),婚否,地址,健在否,(如过世，还有死亡日期)fscanf(fp,%s%d%d%d%d%s%d,T-info.name,&T-info.birthday.year,&T-info.birthday.month,&T-info.birthday

19、.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(!IsDateValid(T-info.

20、deathday)return FILE_DATA_NOT_PRACTICAL;return OK;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-sibli

21、ng=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-info.name,parentname)=0) /根结点名字与其父亲

22、名字相同，说明为空树delete T;T=0;return PEDIGREE_EMPTY;temp=new PersonNode; /申请一结点if(!temp) /申请失败DestroyFamilytree(); /释放申请空间return NOT_ENOUGH_MEMORY;result=ReadNode(fp,temp,parentname);while(strcmp(temp-info.name,parentname)&strcmp(temp-info.name,end) /读取信息结束的条件是两个人的名字同为endif(result=FILE_DATA_NOT_PRACTICAL)

23、/若数据不合法，释放已申请空间，然后返回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-paren

24、t=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)

25、/申请失败DestroyFamilytree(); /释放申请空间return NOT_ENOUGH_MEMORY;result=ReadNode(fp,temp,parentname); /继续读取数据/whileif(temp)delete temp;fclose(fp);return OK;2由兄弟、孩子二叉树生成家谱文件void SaveNode(FILE *fp, Person &pNode)/本函数向文件fp 中存取一结点pNodechar ch=n;if(pNode)fprintf(fp,%s %d %d %d %d %s %d,pNode-info.name,pNode-inf

26、o.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-info.name);e

27、lsefprintf(fp, %s,-1);fprintf(fp, %c,ch);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

28、 %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);3按照姓名、出生日期查找家谱成员void COpera

29、tionFamilytree:Find(Person& T,Person& Tname,char* name)/本函数以T 为根结点开始,搜索结点信息中名字等于name 的结点if(T) /如果T 存在if(strcmp(T-info.name,name)=0) /T 结点姓名和name 相同，把T 结点指针传给TnameTname=T;elseFind(T-sibling,Tname,name); /对T 的兄弟递归搜索Find(T-child,Tname,name); /对T 的孩子递归搜索void COperationFamilytree:Find(Person &T, Person*&

30、 Tname,int month, intday)/本函数以T 为根结点开始,搜索结点信息中生日等于month,day 的结点,/并把所有符合条件的结点指针值存入以Tname 为起始地址的地址数组中if(T) /如果T 存在if(T-info.birthday.month=month&T-info.birthday.day=day) /T 结点生日与所给相同，把T 结点指针传给Tname,同时Tname 指针前进*Tname=T;Tname+;elseFind(T-sibling,Tname,month,day); /对T 的兄弟递归搜索Find(T-child,Tname,month,day

31、); /对T 的孩子递归搜索4按照出生日期对家谱排序void CFamilytreeDlg:OnFamilytreeSort()/ TODO: Add your command handler code hereRefreshList();QuickSortNode* order;int totalNums=0;operFamilytree.GetPersonNums(operFamilytree.GetRoot(),totalNums);order=new QuickSortNodetotalNums+1;if(!order)AfxMessageBox(内存不足!);return;AfxMe

32、ssageBox(排序后结果请见下部列表。);operFamilytree.SortByBirthday(order);for(int i=1;itotalNums+1;i+)DisplayInListCtrl(orderi.oneself);delete order;void COperationFamilytree:SortByBirthday(QuickSortNode *order)/本函数对顺序表order以出生日期的大小排序int totalNums=0;QuickSortNode* startaddr=order;startaddr+;GetPersonNums(T,totalN

33、ums);CopyInfoFromBiTreeToArray(T,startaddr);QuickSort(order,1,totalNums);int COperationFamilytree:Partition(QuickSortNode *order, int low, int high)/本函数供QuickSort 函数调用/交换顺序表order中从low 到high 的记录，便枢轴记录到位，并返回其所在位置，此时/在它之前（后）的记录均不大（小）于它order0=orderlow; /用子表的第一个记录做枢轴记录Date pivotkey=orderlow.birthday; /枢轴

34、记录关键字while(lowhigh) /从表的两端交替地向中间扫描while(lowhigh&(CompareDate(orderhigh.birthday,pivotkey)=1|CompareDate(orderhigh.birthday,pivotkey)=0)-high;orderlow=orderhigh; /将比枢轴记录小的记录移到低端orderlow.birthday=orderhigh.birthday; /枢轴记录到位orderlow.oneself=orderhigh.oneself;while(lowhigh&(CompareDate(orderlow.birthday

35、,pivotkey)=-1|CompareDate(orderlow.birthday,pivotkey)=0)+low;orderhigh=orderlow; /将比枢轴记录大的记录移到高端orderlow=order0; /枢轴记录到位return low; /返回枢轴位置void COperationFamilytree:QuickSort(QuickSortNode *order, int low, int high)/本函数对顺序表orderlow.high作快速排序int pivotloc;if(lowchild,personNums); /递归调用GetPersonNums(T-

36、sibling,personNums);void COperationFamilytree:CopyInfoFromBiTreeToArray(Person &T,QuickSortNode *&order)/本函数先序遍历以T为根结点的所有结点，并把每一个结点的出生日期信息及其指针值/依次存入顺序表order中if(T)(*order).birthday=T-info.birthday;(*order).oneself=T;order+;CopyInfoFromBiTreeToArray(T-child,order);CopyInfoFromBiTreeToArray(T-sibling,o

37、rder);五、调试分析1该课程设计只有一个主要类，即对孩子兄弟二叉树的操作类。该类主要包括文件读取函数、创建孩子兄弟二叉树函数、在树中查找函数、遍历函数以及对树中结点进行加入、删除、修改的函数。由于树存储结构的特殊性，故编制这些算法时大量使用了递归，虽然这样做可能会降低程序的执行效率，但程序的易读性较强。2在调试时，遇到的几个问题如下：（1）建立树时，由于新申请结点的孩子指针、兄弟指针、及双亲指针均未赋空值。而在以后的函数中对树进行递归操作时均以这些指针值中的一个或几个是否为空作为递归结束条件。从而导致调用这些函数时出现系统保护异常（使用了不安全的指针）。（2）刚开始删除结点时，只考虑到删除

38、其本身结点的情况，而删除其孩子结点的情况未考虑到，故在删除某些结点时使树出现了“断链”现象。故在程序代码中对删除某一结点进行操作时，首先要判断此结点是否有孩子及兄弟，然后进行相应操作。（3）刚开始进行程序概要设计时，曾考虑到用控制台下的文本方式作为程序界面，实际操作后发现并不理想。一方面字符形式的界面友好性较差，另一方面显示整个家谱树的信息时不方便。故考虑用VC+中MFC 类自带的树型控件显示家谱层次，而用列表控件显示家谱中的信息。用后效果不错。六、用户手册1.本程序的运行环境为Windows95/98/ME 以及Windows 2000/NT/XP 操作系统，执行文件为FamilyTree.

39、exe。2.本程序的编译环境为Microsoft Visual C+ 6.0。在Windows 2000 下编译通过。3.进入演示程序后即显示窗口方式的用户界面：4.接受命令后既执行相应运算和显示相应结果。七、测试结果按下按钮“打开家谱”，打开一个家谱文件（*.ftf）按下按钮“新建家谱”，新建一个家谱文件（*.ftf）按下按钮“保存家谱”，将修改过的家谱保存按下按钮“另存家谱”，将修改过的家谱另存为一个家谱文件（*.ftf）按下按钮“删除该人”，将树型控件中选中的成员及其后代删除按下按钮“增加孩子”，给树型控件中选中的成员增加一个孩子按下按钮“更改资料”，更改树型控件中选中的成员的资料按下按

40、钮“按照姓名查找”，将家谱中特定名字的成员的信息显示在列表控件中按下按钮“确定两人关系”，将家谱中某两人的关系显示出来按下按钮“出生日期排序”，将家谱中的所有成员按出生日期排序并显示在列表控件中按下按钮“按照生日查找”，将家谱中特定日期出生的成员的信息显示在列表控件中选择菜单项目“关于”，显示该程序的版权信息选择菜单项目“退出”，结束该程序的运行八、附录源程序文件名清单：Familytree.cpp& Familytree.h主程序实现单元FileOpenAndSaveDlg.cpp& FileOpenAndSaveDlg.h文件输入输出实现单元OperationFamilytree.cpp&

41、 OperationFamilytree.h家谱操作实现单元StdAfx.cpp& StdAfx.h &Resourse.hMFC 类实现及资源头文件Familytree.rc& Familytree.rc2& Familytree.ico资源文件AddInfoDlg.cpp& AddInfoDlg.h增加成员的实现单元DelInfoDlg.cpp& DelInfoDlg.h删除成员的实现单元ModifyInfoDlg.cpp& ModifyInfoDlg.h修改成员资料的实现单元BirthdayDlg.cpp& BirthdayDlg.h按出生日期查找成员的实现单元PersonalInfoDlg.cpp& PersonalInfoDlg.h按姓名查找成员的实现单元RelationsDlg.cpp& RelationsDlg.h显示成员关系的实现单元SearchGenerationDlg.cpp& SearchGenerationDlgh显示代数的实现单元参考书目：数据结构（C 语言版）清华大学出版社严蔚敏、吴伟民编著C 至Visual C+程序设计语言科学出版社蔡常丰、林小苹编著Microsoft Visual C+ 6.0 高手速成兵器工业出版社步行者工作室编著C+程序设计清华大学出版社谭浩强编著姓名：郭志超 学号：031010151554042完_