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

1课程设计介绍 1、1课程设计项目简介 家谱就是一种以表谱形式,记载一个以血缘关系为主体得家族世系繁衍与重要人物事迹得特殊图书载体.家谱就是中国特有得文化遗产，就是中华民族得三大文献之一，属珍贵得人文资料，对于历史学,民俗学，人口学，社会学与经济学得深入研究，均有不可替代得重要功能。本项目对家谱管理进行简单得模拟，以实现查瞧祖先与子孙个人信息 、插入家族成员等功能。 1、2课设题目分析本程序得实质就是完成对家谱成员信息得建立、查找、插入等功能。可以首先定义家族成员得数据结构，然后将每个功能写成一个函数来完成对数据得操作,最后完成主函数以验证各个函数功能并得出运行结果。本程序包含以下几个模块（1 建立家族关系树。此模块将构建一个家族关系，对数据初始化，构造关系树并录入数据一遍后续程序使用。（2） 添加新成员。此模块将添加一个新成员，实现对家族关系得修改。（3） 家族关系得查询。此模块将实现对家族不同关系得查询（4） 主程序模块。此模块实现整个程序得进入与进出,以及各种初始化处理。1、课程题目原理与数据结构 因为家族得成员之间存在一个对多个得层次结构关系，所以不能用线性表来表示与实现。家谱从形状上瞧像一颗倒长得树，所以用树结构来表示比较合适。树形结构就是一类非常重要得非线性数据结构,直观瞧来树就是以分支关系定义得层次结构. 因此本课程设计可以采用得数据结构有树状结构与队列。树状结构采用三叉链表来实现，队列采用链式队列实现。1、4功能分析说明图家族关系查询系统退出系统打开一个家族关系按关系查找各个家庭成员建立一个家族关系添加一个家庭成员查找一个成员得兄弟查找一个成员得祖先查找成员得子孙后代查找一个成员得孩子查找成员得堂兄弟查找成员祖先路径查找成员就是第几代查找一个成员双亲2 分析与实现 2、1 基本数据结构与栈队得操作2.1。 结点基本数据结构与链队得定义/家族关系树实现*#incldestrin、#incl mllo、incldeiits、hnclstdi、ludestlib、hincludeo、#includemath、h#inluefronplqu-rea=NUL; elepinf（”内存不足！”)；retrn NL； rturnpqu;int Queemt(LinQueue pl）/* 判断链接表示队列就是否为空队列*/ eur（lqunt=NULL）;voi LueEQuu（LinQuu plq,TriTe *）* 进队列 Noe *p（de )maloc(sizeo（Node）)； i（p=ULL） printf(”内存分配失败！n)； es inf=x; -ne=NUL; if（pqufrnt=ULL） 原来为空队*/ plqufn=p； els lqu-rear-x=p; pluer=p; int QuueDQuee(inkQueue*lqu，TriTre *x）/* 出队列 Node *p； (lufron=NULL)pritf（队列空！n”）；eturn EROR; else p=plqu-fot;x=p-io； plqurnt=plufronext; fee(）；retrnOK； TiTree LueFrnt(LinkQueue *plqu)/在非空队列中求队头元素*/return（lqufront-info)；2、2建立家族关系221 建立家族关系并存入文件 基本思想:首先输入家族关系得名称，以此名称为文件名,建立文本文件接下来按层次输入结点信息，输入一个在文件中写入一行同时将输入得信息保存 到二位字符数组fmiy中。字符数组famil就是全局变量,存储临时信息 、 注意，输入时每个结点信息占一行,一个结点有多个兄弟，以“”作为兄弟结束标志,结点若无孩子，直接以“代替。依次输入各节点信息,以“#” 作为结束标志。最后使用函数CretrTee建立家族关系树、lixianliguoyu liguojun liguoqiangliyongzhi liyongrui liyongmingliwende liwenjia TrTee *Create（DaaTypefamilynMAXNUM) 建立家族关系并存入文件/in i； /* i控制faly数组下标/taTye ch，srMAN； /*ch存储输入得y或n，str存储输入得字符串TriT *t;FI fp；stcy（name，famlname）； / 以家族名为文本文件名存储*/srct（name，、tx”)；fp=fpen（fname，”）; *以读取方式打开文件/ （fp） / 文件已存在*/fcos(fp）；pinf（%s 得家族关系已存在!重新建立请按“Y”,直接打开请按“”,familyname）；ch=ch(）；getcha()； /接收回车/i(h=N|ch=n)tOpe（amlyna）；/ 直接打开*/etur t;if（!f|h=Y|c） 重新建立,执行以下操作*=foe(fnam，”w”); 以写入方式打开文件,不存在则新建*/printf(请按层次输入结点,每个结点信息占一行n”)；pintf(”兄弟输入结束以“”为标志,结束标志为“#”n、 )；gs（st)；fpts(t，fp）；putc(n，f)；stcp（familyi，tr)； /* 将成员信息存储到字符数组中*/i+; *faily数组下标后移/while(str0!=#） pritf(、 ”）； /以点提示符提示继续输入/ges(str）；fputs（sr,fp）; / 写到文件中，每个信息占一行/fptc(n，f）;srcpy（famil，str）;/将成员信息存储到字符数组中/+； /faily数组下标后移*/fose（f）； /* 关闭文件/=TrTreereate()； 根据fmily数组信息创建三叉树*pintf(家族关系已成功建立！”)；rurn ; 返回树2。建立家族关系树基本思想:采用指针数组作为指针，保存输入得结点地址。队列得尾指针指向当前结点。头指针指向当前结点得双亲结点。输入得结点信息已存储在字符数组al中。将信息复制到字符串数组“ch中 ，如果”ch不就是“”,则建立一个新结点。若新结点就是第一个结点，则它就是根结点,将其入队，指针tree指向这个根节点;如果不就是根结点,则将当前结点链接到双亲结点上,即当前结点得双亲指针就就是队头元素,然后将当前结点入队列.接着判断fag得值,如果flag=，表示当前结点没有左孩子,那么当前结点就就是双亲得左孩子。否则，当前结点就就是双亲得右孩子.用指针rot指向刚刚入队得结点.继续复制数组famil得下个元素。如果“c” 就是。则fag=0(因为“”后面得第一个孩子为左孩子),同时判断“”就是否就是第一次出现，如果就是第一次,则令标志ta;如果不就是第一次出现.则出队列，ot指向队头元素（实际上ot总就是指向双亲结点)。继续复制ily得下一个元素。知道遇到“”结束。函数返回指针ree。 /建立家族关系树*/Tree TireeCrete(）TriTee *t,x=ULL,*tree,*ot=ULL；LnkQuue QueueCreaeEmpty（）；/建立一个空得队列，存储指向树得指针*/int i=,fag0,stt=0；DatapesrMANUM; /存放faml数组中信息*/strpy(str，famlyi）； 复制*/i+； /* amily数组下标后移while（tr0！=) / 没遇到结束标志继续循环while(str0!=） /* 没遇到兄弟输入结束标志继续/if（o=ULL) / 空树/rot=（TriTre *)alloc(zeof（TriTre)；/ 申请空间*/strcpy（roodata，st）;root-paent=U;rot-lhidULL；ootrcld=NUL;LQueeEnQuee（q,rot); /将ro存入队列*/tree=root;else /* 不为空树*t=（TiTre *）mallo(sizo(TrTree);/ 申请空间*/strcpy(tdata,str）；-lchdNULL；-rhildNUL;tpret=LQeueGront(）; /当前结点得双亲为队头元素LueuEnQueue（q，t）； /入队*/if(!fag） /* lg为，当前结点没有左孩子*rolcid=t；els la为，当前结点已有左孩子*/rtrchd=t;ot； *root指向新得结点t */la=1； /* 标记当前结点已有左孩子*strcpy（str,family)； i+；if(start！) /* 标记不就是第一次出现“/LQeueuue(q，）； /* 出队*/if（q-frnt!=NUL）root=QeuGeFront()；/ root为队头元素/start=1; /* 标记已出现过“*fag0； /* “”后面得结点一定为左孩子*strcy(str,alyi);+；return ee； * 返回树*/2、打开一个家族关系 首先输入家族关系名,以家族名为文件名打开文件，如果家族关系不存在,返回空;如果存在,文件打开,读取文件。将文件得每行信息依次存储在数组faiy【】中。* 打开一个家族关系/TriTeeOpn（aaTpfamilyameMXUM)n =，0；DataType ch;LE fp;rre ；scpy(nae,fmilyname)； /以家族名为文本文件名存储*/src(fname，”、tt”);fp=pe（name，”r); / 以读取方式打开文件/ if(fp=NUL) /*文件不存在*rin（%得家族关系不存在!n”，familame）;return U；elsec=fgetc（p）； / 按字符读取文件*/hl（ch！=EOF） /* 读到文件尾结束/if（ch！=n) /* ch不为一个结点信息得结尾*/mlj=ch； /*将文件信息存储到family数组中/j+； elseamilyij=0； /*字符串结束标志/i+； /* fmly数组行下标后移/j=0; /* fail数组列下标归零hg(fp); * 继续读取文件信息*/cose(fp); / 关闭文件/t=TrTreeeate（family)； / 调用函数建立三叉链表*/printf(家族关系已成功打开！n）；turnt；2、4在家族关系中查找一个成员就是否存在用递归算法实现.如果树空，返回ULL。如果根节点就就是要查找得成员，返回根节点；否则，递归查找它得左右子树。/ 查找一个成员就是否存在*/TriTee Serh(riTee*t，atTpet）TTree*temp；i（t=LL） / 如果树空则返回NULL /etn NUL;lsif（trmp（t-data,str）=) *如果找到返回该成员指针/ t； e / 如果没找到遍历左右子树进行查找*/tep=Searh（t-lhi,st）；/* 递归查找/i(tem） 结点不空则查找*/rtun(erh（thild，st)）;elserur(Serch(t-rcil，tr）；、5 向家族中添加一个新成员基本思想:添加得新成员要根据其双亲确定其在家族中得位置。首先判断该双亲就是否在此家族关系中,若存在则查找其双亲,将新结点插入其双亲得最后一个孩子之后；若没有孩子，则直接作为左孩子插入。以写入得方式打开文件，如果成功打开,则更新famly数组中得信息,并查找新成员得双亲所在位置与其对应得“个数,如果“”个数小于双亲位置，则添加“实质相等，新成员不插入到最后“”之前。最后将ami数组中信息写入文件保存，关闭文件./* 添加一个新成员*/voidApend(TrTre *t)inti=0，parpos=1，crps，nu,end0,ount=;DataTyp chiMAXUM,prMXNUM； 存储输入得孩子与其双亲结点*/TriTree tpar,tm;FIL fp;intf(”请输入要添加得成员与其父亲，以回车分隔！n、 )；ges（chi)；pif(”、 ）; / 以点提示符提示继续输入/es(pa）；tpar=Sarch（t,p）； * 查找双亲结点就是否存在*/if(！tp）pri（%s该成员不存在！n）;els /* 存在则添加其孩子/emp(TiTee *)malloc（izo（TriTee）)；* 申请空间/temp-arntpar； strcpy（tepdat,chi）；tep-lhild=NULL； /* 新结点左右孩子置空/temrchild=ULL；f（tp-lcild) /* 成员存在左孩子*/tar=parlchild； * 遍历当前成员左孩子得右子树*/whie（tparrhild） /* 当前结点右孩子存在/par=tprchil； *继续遍历右孩子*/prrcild=temp； 将新结点添加到所有孩子之后/ ele / 没有孩子则直接添加/palhil=tep；fp=fpe（fame，”)； / 以写入方式打开文件/if(p)while（strc(par,filyi）！=0&famyi0!）i(famii0!=） * 查找双亲在数组中位置ao+； / parp计数/i+; * family数组行下标后移/i=0； /* family数组行下标归*/while(famiyi0！=#）if(familyi0=） / 查找“得个数，第一个不计*/count+； /cou累加个数i(cunt=parps） 说明此“”与其前一个“”之前为par得孩子/curpos=i； /cupos计当前位置/i+； / famly数组行下标后移if(cuntparos) “”数小于prpo数/nm=apoco; /* 添加“”个数为um */fo(j=；j=i+num；j+） /* 从数组末尾添加“”*trcpy（familyj,0”）; stcpy（fii+num+1,”#0)；/ “#”移到数组末尾*/ srcpy(family+nm1，hi); /* 在最后一个“”前添加新成员*d=； /* nd为时标记已添加 elsefor（j=i；jrpos;j-) /* 当前位置到数组最后得全部信息后移一行*/sc(family+1，familyj）；try(amilycurpos,chi）; 将新结点存储到“”得前一行*/f(=1） /* 若ed为，则数组末尾下标后移nu位*=im；for（=0;daa）;2.6。2 查找一个成员得所有祖先路径查找一个成员得所有祖先路径，需要从它得双亲一直向上查找到根结点。基本思想：对与结点t,先判断它就是否就是根结点(根节点得双亲就是NUL),如果就是根结点,直接输出它本身;如果不就是，查找它得双亲指针指向得结点,将双亲信息输出。继续查找，直到找到根结点./查找一个成员得所有祖先/void AnestorPath（TrTret）i(t-parnt=NUL） /*若该成员为祖先，则直接输出/ptf（”% 无祖先！n，t-data)；el / 否则继续查找祖先*/pintf（”s 所有祖先路径:s,tdata，-da）；while(tprn！=NL）/ 若当前成员得双亲不就是祖先,则继续查找if（” - s，-parta）；* 访问当前成员得双亲/=taent； 继续循环查找/rinf(”)；26.3 查找一个成员得双亲基本思想：先判断结点t就是否就是根结点，过不就是根结点，直接输出该结点双亲指针得结点信息;若就是根结点,输出提示信息，结点无双亲。* 查找一个成员得双亲/vid Parn（TrTree*t)if（t-parent！=NU) /* 若该成员为祖先，则无双亲prinf（s 得双亲为sn,tdta,tpet-ata)；eleprinf(s 无双亲！n”,tdata）；2.4 确定一个成员就是第几代确定一个成员就是第几代,只要知道从它本身到根结点包括得祖先个数就可。因而对于跟结点t，从它本身开始一直向上查找到根结点,查找得过程中用变量ot(初值为1)计数,最后输出ount。*确定一个成员就是第几代*/vid Gnraton（riTree *t)t ount=； 计数*DtaType strMAXNUM；strcp（sr,dt）； * 存储当前信息*hile（tarnt!=NULL）/* 查找其双亲*cn+; 累加计数*t=t-parent;rintf(s 就是第%代！n”，st，cont）；2。6。5 查找一个成员得兄弟 一个成员得为其双亲除了该成员以外得所有孩子。 基本思想：对于结点t,先判断它就是否就是跟结点，若就是根结点，则无兄弟；若不就是根结点,则找到结点t得双亲。接着判断双亲得左孩子与左孩子得兄弟就是否都存在（若只有左孩子,左孩子就就是要查找得这个成员），如果都不存在，则无兄弟;如果都存在，对双亲得左孩子操作。若左孩子不就是要查找得这个成员，则将结点信息输出.接下来查找左孩子得右兄弟，判断当前结点就是否就是要查找得这个成员，若不就是，则将结点信息输出,继续查找当前结点得右兄弟，直到NLL为止./ 查找一个成员得兄弟oidrohrs(TrTr *t,DataTypest） /*查找兄弟/ if（tprent!=NULL） /若该结点就是祖先，则无兄弟/ttparent; /* 该结点得兄弟即为其双亲除该成员以外得所有孩子*/if(tlhild&t-lcild-rchid） 当前结点得左孩子及其右孩子都存在*printf（%s得所有兄弟有:”，sr）；=-ild； hile（t) /* 遍历当前成员左孩子得右子树 if(srcmp（t-data，tr)!0） 遍历右子树，选择输出*/pritf( ”,t-data）； *访问当前结点/t=tchid;pint（”)；elsepf(”s 无兄弟!”，st）；elseprit（s 无兄弟！n，str）;2。6 查找一个成员得堂兄弟 一个成员得堂兄弟为其双亲得双亲结点得所有孩子得孩子（该成员除外）、 基本思想：如果结点得双亲与双亲得双亲(爷爷)都存在,首先考虑爷爷得左孩子。如果爷爷得左孩子不就是结点t得双亲，那么爷爷还有其她孩子。现对爷爷得左孩子得左孩子访问，如果不就是结点t就输出。同样，对爷爷左孩子得左孩子得右孩子、右孩子得右孩子一直访问下去，直到无右孩子为止。如果爷爷还有其她孩子，那么就对爷爷得左孩子得右孩子、爷爷得左孩子得右孩子得右孩子-即对爷爷得其她孩子做相同得处理。/查找一个成员得堂兄弟v Coni(Triree t)int fag=0;TTee*ct;TrTe emp；f(rent&t-parentpart）/ 当前结点得双亲及其双亲都存在/=tpantparentlci;/* 当前结点等于其祖先得第一个孩子*/wi（t） 存在则继续查找* i(tcmp（data，ch-parendaa）！=0)* 不就是同一结点/f(t-lchd) / 当前结点存在左孩子temp=tlcil;whil（emp） /* 遍历当前结点左孩子得右子树*if（stcmp（epda,chdata)！=0)if(!fl） *第一次输入时先输出下句*/printf（% 得所有堂兄弟有:，ch-dat）；pint（s ，temp-data);/ 访问当前成员*/fa=;temp=emprchid； * 继续遍历右孩子/=trchl; / 继续遍历右孩子/prnf（”n);i(！fla） 标志没有输出结点/prit(”s 无堂兄弟！n”,chdat）；.。7 查找一个成员得所有孩子 一个成员得所有孩子包括左孩子与左孩子得右孩子、左孩子得右孩子得右孩子-直到右孩子为空为止。 基本思想：首先判断结点t就是否有左孩子,如果没有，输出没有孩子；如果有左孩子，输出左孩子得信息，然后判断左孩子得右孩子就是否为空，若不为空(存在右孩子)，输出左孩子得右孩子得信息,接着循环判断结点就是否有右孩子,有就输出,直到右孩子为空。/* 查找一个成员得所有孩子/vodChildre（TiTre ） * 遍历左孩子*/ f(t-lhil） /* 当前结点存在左孩子/printf（% 得所有孩子有:,tdata）；t-child； /*遍历当前成员左孩子得右子树/wile(t） 不空*/ pint(% ”，tata）;/ 访问当前成员/t=rchi； rintf(”n)；seprint(s 无孩子！n”,-dt）;*中序遍历一棵树*/id re（ire *） i(t） / 二叉树存在/IOrdr（tlchild); /* 中序遍历左子树*print(%s ”，tda);/* 访问成员/Irder（trchd); / 中序遍历右子树/2.68 查找一个成员得子孙后代 一个成员得子孙后代就就是其左子树上得所有结点，所以对其左子树进行中序遍历即可。/ 查找一个成员得子孙后代/ vid Desndans（TiTre t) * 遍历左孩子*/