数据结构课程设计报告(用二叉树实现家谱管理系统).doc
《数据结构课程设计报告(用二叉树实现家谱管理系统).doc》由会员分享,可在线阅读,更多相关《数据结构课程设计报告(用二叉树实现家谱管理系统).doc(13页珍藏版)》请在沃文网上搜索。
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
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
20 积分
下载 | 加入VIP,下载更划算! |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 课程设计 报告 二叉 实现 家谱 管理 系统
