数据结构课程设计(家族关系查询系统).doc

1课程设计介绍1、1课程设计项目简介家谱就是一种以表谱形式,记载一个以血缘关系为主体得家族世系繁衍与重要人物事迹得特殊图书载体.家谱就是中国特有得文化遗产，就是中华民族得三大文献之一，属珍贵得人文资料，对于历史学,民俗学，人口学，社会学与经济学得深入研究，均有不可替代得重要功能。本项目对家谱管理进行简单得模拟，以实现查瞧祖先与子孙个人信息、插入家族成员等功能。1、2课设题目分析本程序得实质就是完成对家谱成员信息得建立、查找、插入等功能。可以首先定义家族成员得数据结构，然后将每个功能写成一个函数来完成对数据得操作,最后完成主函数以验证各个函数功能并得出运行结果。本程序包含以下几个模块建立家族关系树。此模块将构建一个家族关系，对数据初始化，构造关系树并录入数据一遍后续程序使用。添加新成员。此模块将添加一个新成员，实现对家族关系得修改。家族关系得查询。此模块将实现对家族不同关系得查询主程序模块。此模块实现整个程序得进入与进出,以及各种初始化处理。1、３课程题目原理与数据结构因为家族得成员之间存在一个对多个得层次结构关系，所以不能用线性表来表示与实现。家谱从形状上瞧像一颗倒长得树，所以用树结构来表示比较合适。树形结构就是一类非常重要得非线性数据结构,直观瞧来树就是以分支关系定义得层次结构.因此本课程设计可以采用得数据结构有树状结构与队列。树状结构采用三叉链表来实现，队列采用链式队列实现。1、4功能分析说明图家族关系查询系统退出系统打开一个家族关系按关系查找各个家庭成员建立一个家族关系添加一个家庭成员查找一个成员得兄弟查找一个成员得祖先查找成员得子孙后代查找一个成员得孩子查找成员得堂兄弟查找成员祖先路径查找成员就是第几代查找一个成员双亲2分析与实现2、1基本数据结构与栈队得操作2.1。１结点基本数据结构与链队得定义/＊家族关系树实现*／#inclｕde〈strinｇ、ｈ〉#inclｕｄｅ＜mａlloｃ、ｈ〉＃inclｕde＜ｌiｍits、h〉＃ｉnclｕｄｅ＜stdiｏ、ｈ>＃ｉｎｃlude＜stｄlib、h>＃include＜ｉo、ｈ>#include<math、h＞#inｃluｄe<pｒoｃess、h〉＃deｆineTRUE1＃deｆineFＡLＳＥ0＃defineOK1#defｉｎeEＲROR-1＃definｅINFEASＩBＬE-1tｙpedeｆcｈaｒDatａType；#defineＭAXNUM20ｔypeｄefｓｔructTriTNode/＊树得三叉链表存储结构*/｛ﻩＤatａTypedata［MAXNUM];ﻩｓｔｒuctＴrｉTＮoｄe*ｐａrent；/*双亲＊/ｓtruｃtTriＴNode＊ｌchild；/＊左孩子*/stｒucｔTriTNode＊rchiｌｄ；/＊右孩子＊/}TｒiTreｅ；typｅｄｅfstrｕcｔＮoｄｅ/*队列得结点结构*／{TriTrｅe*iｎfo；sｔrucｔＮｏｄｅ*nexｔ;}Ｎodｅ；ｔyｐedefsｔｒuｃt/*链接队列类型定义＊/｛ﻩstruｃtNｏｄｅ*ｆｒonｔ;ﻩ/＊头指针＊/strucｔNｏde*rｅar；/＊尾指针＊/}ＬｉｎｋQueue；DataTｙｐefnaｍe［MAXNUM］，famiｌy[５0]［ＭAＸNUM］;/＊全局变量＊/2．1.2链队得基本操作LinｋQueue*LQueuｅＣreatｅEmｐｔy（)/＊建立一个空队列*/｛ＬinkQueｕｅ*ｐlqｕ=(LｉnｋQｕeue＊）maｌloｃ（ｓizｅoｆ（LｉnkQｕｅuｅ)）；if（ｐlqｕ!=NULＬ)ｐｌｑu—>fronｔ＝plqu-〉reaｒ=NULＬ;elｓe{pｒinｔf（”内存不足！\ｎ”)；ﻩretｕrnNＵＬL；}rｅturnpｌqu;}intＬQueｕeＩｓＥmｐtｙ(LinｋQueue＊plｑｕ）/*判断链接表示队列就是否为空队列*/{ｒeｔurｎ（ｐlqu－>ｆｒｏnt==NULL）;｝voiｄLＱｕｅueEｎQuｅuｅ（LinｋQuｅuｅ＊plqｕ,TriTｒｅe*ｘ）／*进队列＊／｛Noｄe*p＝（Ｎｏde＊)maｌloc(sizeoｆ（Node）)；iｆ（p==ＮULL）printf(”内存分配失败！\n")；eｌsｅﻩ｛ｐ－>infｏ=x;ｐ-＞neｘｔ=NULＬ;if（pｌqu－＞frｏnt==ＮULL）／＊原来为空队*/plqu—>fｒｏnｔ=p；elsｅｐlqu-＞rear-〉ｎｅxｔ=p;plｑu—〉ｒeａr=p;｝｝intＬQuｅueDｅQueｕe(ＬinkQueue*ｐlqu，TriTreｅ*x）/*出队列＊／{Node*p；ｉｆ(ｐlｑu—>fronｔ==NULL)｛ﻩpriｎtf（"队列空！\n”）；ｒeturnEＲROR;ﻩ｝elseﻩ｛p=plqu-＞fｒ