(完整word版)数据结构课程设计之简易家谱报告

1、编 号：学 号：201140410119HUBEI POLYTECHNIC UNIVERSITY课程设计教学院计算机学院课程名称数据结构课程设计题目简易家谱系统专业计算机科学与技术班级（1）班姓名陈建辉同组人员周海涛，石义津，明廷柱指导教师程细才2013 年 1 月 8 日课程设计（论文）一概述 21 .课程设计的目的 22 .课程设计的要求 2二总体方案设计 31 .简单家谱系统整体设计思路 32 .简单家谱系统的主要特点及功能 5三详细设计 71 .查询全部的家谱成员信息 72 .确定指定成员在家族中的辈份 73 .在家谱中添加新成员，并追加到文件中 9四程序的调试与运行结果说明 121

2、.实验结果截图： 122 .调试时遇到的问题 12五课程设计总结 13附录一：程序源代码 16附录二：参考文献 251源朗汽M冬伤课程设计（论文）概述1 .课程设计的目的1 .理解和掌握该课程中的有关基本概念，程序设计思想和方法。2 .培养综合运用所学知识独立完成课题的能力。3 .培养勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论， 全方位考虑问题等科学技术人员应具有的素质。4 .掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中 找到解决问题的新途径的悟性，初步培养工程意识和创新能力。2 .课程设计的要求设计要求：输入家族成员情况，建立树结构，统计家族成员人数，能查询

3、家族成员辈份情况。系统功能：1 .输入、修改与删除家谱信息功能2 .查询功能：1）某家谱成员的所有子孙的集合2）某家谱成员的所有祖先的集合3）某家谱成员的所有同辈成员的集合4）求某家谱成员的所有上一辈成员的集合5）给出两个家谱成员，确定他们的关系5二总体方案设计1 .简单家谱系统整体设计思路此次课程设计的整体思路是采用遍历算法，整个树的定义使用两个结 构体来表示，一个结构体专门用于存放每一个节点的信息，另一个节点中 定义了三个指针域，分别为父指针域（兄长指针域），兄弟指针域，子指针 域，整个树的输入采用文件导入的方式，首先将文件导入到树中，文件包 含每一个家族成员的信息，以及一个标志位flag

4、 ,标志位的值为0, 1, 2,0 表示此节点没有兄弟节点，1表示此节点至少有一个子节点，2表示此节点 至少有一个兄弟节点，使用的算法是先定义一个链式队列，将文件中第一 个节点的内容读取放入开辟的树的节点的空间里，然后将树节点放入队列 中，此时队列不为空，以队列不为空为判断条件，进行 while循环，判断 flag的值，循环体中再进行文件读取，循环中进行判断，若 flag为0,则 继续判断队列是否为空，为空就结束循环，若不为空，则继续出队列，取 标志位进行判断，若标志位为1,则生成新节点，用刚刚出列的节点的子指 针域进行指向新节点，新节点的父指针域指向出列的节点，剩余的域为空， 然后将新生成的

5、节点插入到队列中，若flag为1,则进行兄弟节点的插入， 继续循环，若flag不为0,则在进行判断，若为2,则继续进行兄弟节点 的插入，以此类推，根据文件的读取，将树生成，本程序中所有的算法都 基于以上所介绍的算法。关于IO的设计：考虑到题目要求家谱信息以树形的形式一次读入内存， 而个人的各种资 料现在虽然条目不多，但随着程序的升级，以后可能变得越来越大。我把树形结构和个人信息记录的文档分为两个文件保存在外存中，一个文 件串行化地记录家谱树的结构信息，保存少量个人信息作为识别标志；另 一个文件保存完整的个人信息，所有的个人信息以线性记录的方式记录在 其中。当程序运行要读入家谱结构时，只读入保存

6、少量记录的文件并建立 起树形结构。索引时，以树形中的少量信息为依据在另一个文件中找到全 部的各人信息资料。这样的好处主要有两点：1 .由于树形结构是用行化记录于外存，一个节点记录多次，信息大量冗余,如果树形节点中保留全部信息，必将造成大量的空间浪费；只保存作为索 引的少量信息在树形结构中，节约了空间。2 .由于结构的精简，在家谱初始化时读入内存需要的时间相应减少，节约 了装载时间。这样做存在的问题：每次执行修改，添加，删除，查询时都要直接访问外存来取得或写入数据。 内外存访问上的巨大时间差的存在，使得进行这些操作相对来说并不显得 很高效。关于树形的结构：在树形结构的选择上，根据实际中多子女的现

7、象选择一般树， 考虑到家谱中 成员可能存在的不定成员数问题，抛弃了以数组为基础的一般树方案，决 定用链表来实现。树形结构的外存保存。为了提高效率，树形结构在程序初始化时由外存文 件一次读入内存，此后不管插入还是修改，删除都不再对外存的树结构保 存文件进行操作，只在内存中处理，程序退出时对外存树结构文件进行一 次更新。也就是说，不管在程序运行中中对家谱结构进行多少种，多少次 的操作，外存的树结构文件始终只会被程序访问两次。关于功能的设计（以基本要求为准）：1. 插入：用户按提示输入资料，在树形中插入节点，在个人完整记录 文件中添加插入人的所有信息并保存。2. 删除：用户输入被删除人的识别关键字（

8、即名字），在树形结构中删 除此人，在个人记录文件中不处理。3. 修改：用户输入被删除任的识别关键字（即名字），从个人完整记录 文件中读出该人所有信息供用户进行修改，然后写回。4. 查询：完成了关键字查找部分和关系查找部分，读出个人全部信息 并显小0关于个人资料单元：由于树形节点要涉及到大量的逻辑操作，要用到一些运算符的重载，个人 资料在树形单元定义为class类，而写入文件的单元存萃是数据，定义为简 单的struct类。定义为struct和class类，使得不管是树形结构插入删除还是IO都是对 整个结构体进行的操作，这样，如果要往结构体中添加若干个新信息条目或取消一些不必要的信息条目，需要修改

9、的代码非常之少，方便了以后的 升级。2.简单家谱系统的主要特点及功能本系统的主要特点是算法简洁，易于阅读，用户交互界面良好。主要实现功能：1 .确定指定成员在家族中的辈份2 .输出指定辈的所有成员3 .在家谱中添加新成员，并追加到文件中4 .输出指定家庭的所有成员5 .退出本系统各功能的算法思想：1 .读出家谱并显示存储结构用栈，按照先显示双亲，然后显示其所有孩子的顺序显示所有家庭成员。2 .确定指定成员在家族中的辈份用求成员所在的二叉树中的层数 （按层遍历二叉树）来确定，这里采用的是 递归算法3 .输出指定辈的所有成员此处定义了一个新的结构体类型（增加存储节点所在的层数），定义如下: typ

10、edef struct ccstruct cc *child, *next;/next指向同辈份的人物char Name口；JPNode;并用一个队列来比较显示同辈分的所有成员。4 .在家谱中添加新成员，并追加到文件中首先，输入一个新成员的名字；然后，输入其双亲；之后，再添加到整个存储二叉链表中。然后，再将新的存储结构写回到文件中。二叉链表的结点类型为：typedef struct node存放成员的名字其孩子指针其兄弟指针ElemType data10;/struct node *child; / struct node *brother; / BTNode;5 .输出指定家庭的所有成员首先

11、，设一个栈，并设一个标记位，先置 1;然后，找到输入的要待显示的成员，将标记位置 0;再次，显示其孩子和兄弟，依次下去直到显示完其所有的亲戚6 .退出本系统。源朗汽M冬伤课程设计(论文)三详细设计1 .查询全部的家谱成员信息该部分程序所完成的具体功能是把贾府中所有的成员信息按照辈份依次显 示出来，首先从贾无名开始，然后下一辈份的贾演、贾源等最后是贾蓉的 信息。每个辈份之间都有间隔。设计思想：利用队列遍历所有的结点，在遍历的同时依次输出每个结点的 值(即为家庭成员的信息)。代码如下：void Dis_Family(JPNode *p)char nameNAME_length;JPNode *he

12、re = NULL;printf(请输入该家庭的首个成员：)； scanf(%s,name);here = Find_Name(p,name);if(here = NULL) printf(无该家庭!n); return;printf(n);DispJP(here);2 .确定指定成员在家族中的辈份该部分代码所完成的具体功能是查询某一个家庭成员的信息。首先手动输 入你要查询的那个成员的名字，然后利用队列依次查找该成员的信息，如果该 家谱中存在这个成员则输出该成员的有关信息；如果家谱中不存在该成员，则 输出提示信息：家谱中无此人！设计思想：有两个函数，一个函数(queryElemt)利用队列遍历

13、所有的节 点，在遍历的同时即可查找所输入的成员是否存在该家谱中；另外一个函数(queryElemtoFamily )用于输入你要查找的成员的辈分和输出查找的结果。代码如下: int beifen(JPNode *p, char name口)static int n = 1;static int level = 0;if(p = NULL )return level;if(Equal(p-Name,name) = 1)return (level=n);n+; beifen(p-child,name);n-; beifen(p-next,name); / 向右查询n不必加(先加后减)！ retur

14、n level;void Bei_Fen(JPNode *p)char nameNAME_length;int n=0;printf(请输入要查明辈分的人的姓名:); scanf(%s,name);n = beifen(p,name);if(n = 0)printf(该家族中无此人！n);else printf(n %s 是 %s 家族中的第 %cH n,name,p-Name,n);/*输出指定辈的所有成员*/void chabei(JPNode *p, int bei)static int n = 1;static int tag = 0;if(p = NULL )return;if(be

15、i = n)tag = 1;printf(%s ”,p-Name);n+; chabei(p-child,bei);n-; chabei(p-next,bei); / 向右查询n不必加(先加后减)! if(tag = 0)printf(该家族中还没有这一辈呢 .n);void Disp_Pei(JPNode *p)int bei;printf(n你想要查看那一辈的成员：)；scanf(%d”,&bei);printf(n.该家族中辈分为的成员有.nn,bei);chabei(p,bei);printf(n);3 .在家谱中添加新成员，并追加到文件中该部分程序所完成的具体功能是：输入你要添加人的

16、名字，比如吴长，他 会被添加到文件中。设计思想：首先确定他的父母，然后把他添加到他的父母的根节点之下。 代码如下：int Equal(char const *p,char const q)/判断两个字符串是否相等while(*p+ = *q+)if(*p = 0 & *q = 0)return (1);return (0);JPNode *Find_Name(JPNode *s, char *parent)/定位家谱中的成员。返回其指针(地址)static JPNode *here = NULL;if(s = NULL)return here;if(Equal(s-Name,parent) =

17、 1)return (here=s);9源朗汽M冬伤课程设计（论文）here = Find_Name(s-child,parent);here = Find_Name(s-next,parent);return here;void Print_FILE(JPNode *p,FILE *fp)static int level=0;int i;if(p != NULL)for(i=0;iName);else return;level+;Print_FILE(p-child,fp);level-;Print_FILE(p-next,fp);void ADD_number(JPNode *p) / 在

18、家谱中添加新成员，并写入文件char parentNAME_length,nameNAME_length;FILE *fp = NULL;JPNode *here = NULL;JPNode *s = (JPNode *)malloc( 2*sizeof(void *) + strlen(name) + 1 );s-next = s-child = NULL;printf(请输入要添加的新成员的双亲姓名:); scanf(%s,parent);printf(请输入要添加的新成员的姓名:); scanf(%s,name);strcpy(s-Name,name);here = Find_Name(

19、p,parent);if(here-child = NULL)here-child = s;elsehere = here-child;while(here-next != NULL)here = here-next;here-next = s;fp = fopen(jiapu_data.txt,w);Print_FILE(p,fp);fclose(fp);15四 程序的调试与运行结果说明1 .实验结果截图：D:Program FilesMicrosoft Visual StudioMyProjectsDebugjia_pu.exew2追。辈 朝开口蓄* 好尊员 笛员有族曲在所 m加庭 瞳添家

20、成辈？ 史至正定作 F雷定出出 frii二 1 2 3 4 = 二大甘* H雪舞吴正权双姓 员员 成成 的的 口 口 工力力 套添添Q DAProg ram FilesMicrosoft Visual StudioMyProj eel DebugXi ia jpu.exe露定出出在所添家成辈，MM中定定定代加开口蓄 号.%员 席员有斐*,请选择:4你想要查看那一辈的成员,4该家族中辈分为4的成员有吴鲸吴鹏吴德峰吴莹吴德红吴德龙吴昊吴星吴花2 .调试时遇到的问题（1）当选择功能3（添加新成员），添加完成员后，写回文件时出现了错误, 原本添加的为其中一个结点的孩子，结果写回文件时却成了该结点的孙子

21、，也 就是本是要添加为此结点的孩子的兄弟，结果却成了其孩子的孩子。最后经过 单步跟踪发现写入文件的函数编写错误，缺少判断条件，经过修改后，此问题得到了解决。（2）当选择功能0 （显示此家谱），没有按照事先存储在txt中的文件显示, 通过认真检查程序中显示成员的函数 （按层遍历）、不断调试，发现并不是该显 示函数的错误，因为在功能4 （输出指定家庭的所有成员）中，也是通过调用该 函数实现输出功能，于是，检查txt文件中事先存储的家谱成员，发现是由于 “（”与“）”没有匹配好，导致没有按照预期想法创建二叉树造成的错误，通 过修改txt文件，使得错误得以解决。五课程设计总结本组的课程任务为简易家谱，

22、在组长的带领下，经过我们共同的努力，本 程序主要任务已基本完成。另外本程序功能完善，具有良好的交互性，可以满 足用户多种需求。美中不足的是本系统没有采用之前我所设想的递归，我们这 次改用队列来建树、查找等，这样代码少有一定的冗余，如果时间充分，我们 会更加精进，争取采用代码量相对较少的递归算法，另外更加完善一些功能， 包括增加日志功能，给不同级别的人员设置管理权限，比如说家谱管理员在获 得本族长的同意下修改某个成员的信息，而其他成员只具备浏览的功能。在本程序简易家谱的创作过程中，我们组员各抒己见，意见很不一致，包 括是采用递归算法，还是采用队列；数据成员的结构如何定义，甚至包括成员 的名字，大

23、家的意见都不统一。但是在探讨的过程中，我们也理解自己思维的 不足，也见识了另外不同的编程思想，这也让我体会到了交流的魅力。只有我 们大家坦诚布公的把自己想法说出来，然后我们在理性的分析算法的优劣与可 行性，这样就能结合大家共同的智慧，组织大家共同的力量，为共同的目标努 力奋斗。次大作业的推荐学时是20个学时，但回想起来，光这篇报告就写了有 三四个学时，由于我本身编程能力不强，构思，写代码，修改，调试的时间加 起来绝对是有余了。虽然付出不少，但在前期的设计组织中，中期的代码编写 和后期的修改调试中都学到了不少。起初我的家谱中数据并不是以结构的形式打包，读入，写出操作的时候代 码异常繁琐，这是恰好

24、看到一本编程书上有用结构输入输出的范例，深深感到 结构化确实是方便多了，而且读写不容易出错。当时我的代码本已经写了有一 大半，思虑再三，还是决定进行大换血， 家谱数据的改变让程序来了个大换血， 提高了效率的同时，代码几乎变了一多半。我想，当时唯一不变的就只有对整 个程序越来越清醒地认识和对将要完成的代码的更准确地把握。代码完成之后，一编译，至少有五六十个错误提示，而且最末debug一行栏的最后一行提示因为先前的错误而中断编译，有的是指针指向错误，有的是 忘了分号，括号，更多的是一些赋值错误，前面的错误都好改，赋值错误就比 较麻烦了，因为要使用赋值的地方太多，逐行改代码虽然也可以，但实在是一 个

25、巨大工程。所谓巧招必是险招一一至少对我是这样一一说来惭愧，我只有尝 试着写以前从未是过的运算符重载函数，为此专门翻找出了大一的C+徽材，温习了 一番运算符重载才战战兢兢地搞定了赋值问题。试运行时出现了更多的问题，而且更具有隐蔽性，几次为了一个逻辑错误 而来回反复地翻看代码，嘿嘿，再加上网上有代码的传说，让人有想直接放弃 的冲动，但一想到写代码的辛苦，觉得放弃了实在可惜。那几天吃饭，睡觉， 走路，看电视，随时随地，都记挂着那几处错误，脑子都会浮现出代码的影子， 不自觉地开始找错误。哎那种感觉！ 不知道是充实还是急迫地烦恼，最后终 于找到了，根本来不急高兴，只有松了一口气和一阵的疲惫。现在程序终于

26、完成了，心里的石头也下了地。至于成绩，不想了 源朗汽M冬伤课程设计(论文)另外，通过本次课程设计，我觉得自己最大的收获就是：(1)学会了怎样将课堂所学知识运用到较为实际的应用中来由于对二叉链表的存储比较感兴趣，我选做的是家谱，开始觉得无从下手，但是经过仔细分析后，渐渐找到一点思路(首先创建，然后分别实现各个功能，最后 利用菜单实现选择功能并输出结果)。(2)锻炼提出问题、解决问题和自学的能力家谱的实现要求读、写文件，于是“如何将文件从文档中读出”，“怎么写入文 件”都是要满足要求必须解决的问题。为此，我查找了很多资料，最后自学、解 决这一问题(3)增加了对编程的热爱和兴趣本次编写家谱程序的过程

27、中，我体验到了编程的酸甜苦辣：开始， 由于即将运用 所学知识设计实际问题而激动兴奋； 后来编写程序过程中，在想不出算法如何实 现或者追求空间、时间上高效率的算法时会比较纠结；以及遇到 BUGf,追踪数 据的痛苦；当然，还有解决问题后的激动与自豪。 所有这些都增强了我对编程的 热爱、提高了我对计算机专业的兴趣。#源朗汽M冬伤课程设计（论文）21附录一：程序源代码#include#include static JPNode *last = NULL;#include#include#define NAME_length 50 /#define LINE_length 100 / typedef s

28、truct cc struct cc *child, *next;/next char Name口；JPNode;void clear(char p口,int n) /while(n- 0)*p+ = 0;名字最大长度文本行最大长度指向同辈份的人物清空字符数组pstatic int last_level = 0;void AddJP(JPNode *head, char const name口，int level) JPNode *s = head, *r = NULL;JPNode *p = (JPNode *)malloc( 2*sizeof(void *) + strlen(name)

29、+ 1 );p-child = p-next = NULL;strcpy(p-Name,name);if( *s = NULL)*s = p;last = p;return;if(level - last_level = 1) last-child = p; last =p;last_level = level;return;if(level = last_level) & (*s != NULL)last-next = p; last =p;last_level = level;return;r = *s;/r指向家谱树last_level = level;while( level- 0)

30、/ 找到相同的辈分while(r-next != NULL)r = r-next;r = r-child;/以兄弟连接while( r-next != NULL) r = r-next;r-next = p;last = p;void CreatJP(JPNode *head)char nameNAME_length=, lineLINE_length=;char *p = NULL;int level=0,i=0;/辈分，以制表符个数表示FILE *fp = NULL;fp = fopen(jiapu_data.txt,r);if(fp = NULL) printf(open error!n

31、); exit(1); while(level=0, i=0, fgets(line,LINE_length,fp) != NULL)p = line;while(*p+ = t)level+; /计算辈分,计算完后p指向名字开始处while(linei+ != n)；linei-1=0;/读入的换行符用字符串结束标识符替换strcpy(name,p-1);AddJP(head,name,level);clear(name,NAME_length); clear(line,LINE_length);fclose(fp);void DispJP(JPNode *p)/ 从p指向的结点显示该家族s

32、tatic int level=0;int i;if(p != NULL)for(i=0;iName);else return;level+;DispJP(p-child);level-;DispJP(p-next);/ /*在家谱中添加新成员，并追加到文件中*/int Equal(char const *p,char const q)/判断两个字符串是否相等while(*p+ = *q+)if(*p = 0 & *q = 0)return (1);return (0);JPNode *Find_Name(JPNode *s, char *parent)/定位家谱中的成员。返回其指针(地址)s

33、tatic JPNode *here = NULL;if(s = NULL)return here;if(Equal(s-Name,parent) = 1)return (here=s);here = Find_Name(s-child,parent);here = Find_Name(s-next,parent);return here;void Print_FILE(JPNode *p,FILE *fp)static int level=0;int i;if(p != NULL) for(i=0;iName);else return;level+;Print_FILE(p-child,fp

34、);level-;Print_FILE(p-next,fp);void ADD_number(JPNode *p) /在家谱中添加新成员，并写入文件char parentNAME_length,nameNAME_length;FILE *fp = NULL;JPNode *here = NULL;JPNode *s = (JPNode *)malloc( 2*sizeof(void *) + strlen(name) + 1 );s-next = s-child = NULL;printf(请输入要添加的新成员的双亲姓名:); scanf(%s,parent);printf( 请输入要添加的新

35、成员的姓名:); scanf(%s,name);strcpy(s-Name,name);here = Find_Name(p,parent);if(here-child = NULL)here-child = s;elsehere = here-child;while(here-next != NULL)here = here-next;here-next = s;fp = fopen(jiapu_data.txt,w);Print_FILE(p,fp);fclose(fp);/*输出指定家庭的所有成员*/void Dis_Family(JPNode *p)char nameNAME_leng

36、th;JPNode *here = NULL;printf(请输入该家庭的首个成员：)； scanf(%s,name);here = Find_Name(p,name);if(here = NULL) printf( 无该家庭!n); return;printf(n);DispJP(here);/*确定指定成员在家族中的辈份*/int beifen(JPNode *p, char name口)static int n = 1;static int level = 0;if(p = NULL )return level;if(Equal(p-Name,name) = 1)return (leve

37、l=n);n+; beifen(p-child,name);n-; beifen(p-next,name); / 向右查询n不必加(先加后减)! return level;void Bei_Fen(JPNode *p)char nameNAME_length;int n=0;printf(请输入要查明辈分的人的姓名:); scanf(%s,name);n = beifen(p,name);源朗汽M冬伤课程设计(论文)if(n = 0)printf(该家族中无此人！n）;else printf(n %s 是 s 家族中的第 蟀 n,name,p-Name,n);/ /*输出指定辈的所有成员*/void chabei(JPNode *p, int bei)static int n = 1;static int tag = 0;if(p = NULL )return;if(bei = n)tag = 1;pr