郑州科技学院算法与数据结构课程设计题目家族关系查询系统学生姓名专业班级学号所在系指导教师完成时间、郑州科技学院算法与数据结构课程设计任务书专业：班级：学号：姓名：一、设计题目：家族关系查询系统二、基本要求1、建立家族关系并能存储到文件；2、对于建立的家族关系能够遍历家族成员，输入两个人的名字能够确定二人的关系；3、实现家族成员的添加。

4、可以查询家族成员的双亲、祖先、兄弟、孩子和后代等信息。

三、设计任务1、根据问题分析，实现树的的存储结构。

2、将家族中各个成员保存到自己命名的文件中。

3、创建遍历、查找、添加等函数，实现函数基本的一些功能。

四、设计时间2010 年12月 19日至 2011 年 12 月 25 日指导教师：教研室主任：目录1、课程设计分析 (3)1.1课程设计内容 (3)1.2课程设计要求 (3)1.3课程设计性质 (3)1.4课程设计目的 (4)2、课程设计原理 (4)2.1课程设计题目分析2.1.1程序执行的命令包括 (4)2.12程序中的四大模块 (4)2.2 课程设计原理图分析 (5)2.2.1 功能模块图 (5)2.2.2 流程图分析 (6)3、数据结构分析 (10)3.1 存储结构 (11)3.2 算法描述 (11)4、调试与分析 (12)4.1 调试过程 (12)4.2执行过程 (12)4.3运行时的界面 (13)结束语 (16)致谢 (17)参考文献 (18)附录 (19)1、课程设计介绍1．1、课程设计内容运用队列的存储结构，构建家族关系树。

输入家族的名称，以此名称作文件的名称，建立文本文件。

按层次输入结点信息，在文件中每个人的信息占一行，同时保存到树的存储结构中。

输入一个结点，若此结点有多个兄弟，以“@”作为兄弟结点的结束标志，结点若无孩子，直接以“@”作为标志，依次输入各个结点的信息，以“#”作为结束的标志。

输入结点的序列为zhangxianzu，@，zhangguoyu，zhangguojun，zhangguoqiang，@，zhangyongzhi，@，zhangyongrui，zhangyongming，@，zhangwende，zhangwenjia，@，#。

建立家族关系树后，对树进行一些基本操作。

首先，对家族关系树遍历，确定家族成员已存入文件，并检验是否成功建立家族关系树。

输入两个人的姓名，判断此二人是否属于此家族，若属于就判断此二人的关系。

最后，能够成功退出家族关系查询系统。

1．2、课程设计要求构建家族关系树。

使用队列的存储结构，建立家族关系查询系统树。

采用指针数组作为队列，保存结点输入的地址。

能够遍历家族关系树。

遍历家族成员，检验输出信息是否满足要求。

成功地判断所输入的两个人是否是家族中得人，如果属于就判断两人的关系。

最后，若选择退出，能够成功退出家族关系查询系统。

否则，继续输入相关操作。

1．3、课程设计的性质通过数据结构的学习，使自己对软件编程能力有一定的提高。

数据结构学习是锻炼学生在进一步掌握模块化、结构化程序设计的方法的同时，培养自己运用已学知识分析问题、解决问题及编写实用程序的能力，通过对线性化、层次化、网络化数据结构的了解进一步掌握自然数据的结构方式及组织方式，让自己深入体会存储在计算机中的数据及程序，如何运用数据实现编程。

加深自己对该课程所学内容的进一步的理解与巩固，是将计算机课程与实际问题相联接的关键步骤。

通过课程设计，能够提高自己分析问题、解决问题，从而运用所学知识解决实际问题的能力。

1．3、课程设计的目的主要目的如下：1、培养学生运用算法与数据结构的基本知识解决实际编程中的数据结构设计和算法设计问题。

2、培养学生独立设计程序与解决问题的能力，培养学生团队协作集成程序模块及调试能力。

3、培养学生初步的软件设计及软件测试的能力。

2、课程设计原理2.1、课程设计题目分析演示程序以用户和计算机的对话的方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入相应的数据（即每个人都所持的密码），每个人的序号由程序自动分配。

2.1.1程序执行的命令包括：（1）构造家族关系查询系统（使用树的存储结构）；（2）根据提示及使用者的需求，用户选择相关选项，输入相关数据；（3）执行用户所选的选项对应的程序，满足用户需求，实现相关功能；（4）退出家族关系查询系统，结束操作。

2.1.2程序中的四个大模块（本程序共有六个模块，其中查找模块又分为六个）：（1）家族成员信息录入（构造家族关系查询系统）模块。

此模块将对家族关系树初始化，根据用户输入的信息构造家族关系查询系统树，并提醒用户再次输入数据以便后续程序的使用。

（2）遍历家族成员模块。

此模块将满足用户遍历家族关系查询系统树中的各个成员。

另外，可以检测用户输入的信息是否正确，以及浏览家族中的人员。

（3）确定两个家族成员的关系模块。

由用户输入两个人的名字，此模块实现在整个程序中查找，确定是否有用户输入的人。

如果有，则输出两人的之间的关系（即他们相差几代）。

（4）主程序中的退出模块。

根据用户输入的信息管理控制变量，根据控制变量判断是否退出程序。

2.2、课程设计原理图分析2.2.1、功能模块图2.2.2、流程图分析1、此部分是家族关系查询系统的主函数。

首先，初始化程序中所需要的变量；在输出提示性的语句，等待用户输入将要进行的操作的选项，根据用户输入的数据调用相关的函数。

2、此部分是创建家族关系树函数，并且保存到文件。

用队列的存储结构辅助创建树。

3、此部分是遍历家族成员函数。

采用递归的思想，对家族关系树进行遍历。

N4、此部分是确定家族成员中两人关系的函数。

由用户输入两个人的姓名，系统调用Confirm（）函数判断此二人是否属于此家族。

若属于，判断两人的关系。

3、数据结构分析3.1、存储结构根据要求首先应该建立一个队列，用队列的存储结构辅助实现家族关系树的建立。

树是n（>=0）个结点的有限集。

在任意一棵非空树中：（1）有且仅有一个特定的称为根的结点；（2）当n>1时，其余结点可分为m个互不相交的有限集，其中每个集合本身又是一棵树。

设置结构体存储节点：用结构体存储每一个家族成员的基本信息，及结点的左右孩子指针和双亲指针；再使用结构体存储表示队列结点。

树的结点结构体：typedef struct TNode{char name[M];struct TNode *parent;struct TNode *lchild;struct TNode *rchild;}Tree;队列结点结构体：typedef struct Node{Tree *info;struct Node *next;}Node;typedef struct{struct Node *front;struct Node *rear;}LQ;3.2、算法描述1、用户进入家族关系查询系统，根据提示输入要进行的操作所对应的选项，用户输入的数据被d接收，系统判断d是否大于7并小于1，如果是，则提醒用户重新输入。

否则调用相关函数，执行相应的功能。

若用户输入的d的值在1-6之间，如果用户第一次输入的数值大于1，则系统会提醒用户先建立家族关系树。

2、建立家族关系树。

用户输入家族名称，系统根据家族名称建立对应的文件，用户输入结点信息，系统先将信息保存到文件和fname[M]数组中。

在建树时，将结点的信息从fname[M]数组中复制给str，系统判断str[0]是否等于’#’,并且是否等于’@’,直接执行下面的语句，第一次传入结点时，root等于NULL，建立头结点，再次传入结点时，如果str[0]等于‘@’，内部循环结束，接着出入结点，再次此判断str[0]是否等于‘@’，不等于的话，执行内部循环，取对头元素，判断flag是否等于0，如果等于0，将结点接在所取对头的左孩子上，否则接在右孩子上。

在执行外循环时，如果start2不等于0时，删除对头元素。

3、查询两个家族成员的关系。

由用户输入两个人的姓名，Relation()函数调用Confirm（）函数，确认用户所输入成员姓名是否属于此家族中的成员。

如果属于，用x[M]存放对应的结点，并令全局变量z等于1，在执行Relation（）函数时，判断z的值，确定此人是否属于这个家族。

若属于，令结点不停的指向它的父亲结点，直到父亲结点是根结点，同时应整数形式的w[M]控制执行的次数，作为判断是第几代的根据。

最后，根据w[M]判断两人相差几代。

4、退出家族关系查询系统。

在主函数中，用户选择退出选项在（即输入6），系统执行flag等于0，即控制外循环的变量为0，循环结束，成功退出家族关系查询系统。

4、调试与分析4.1、调试过程在调试程序是主要遇到一下几类问题：1、当输入此函数时出现了与&相关的错误，例如后面缺少括号以及分号等等以下的错误；2、输入每个家庭成员的的信息时，兄弟之间没有用“@”区分，导致建立家族关系树时错误。

另外输入不正确，程序有可能出现停止；3、在一些函数前不加返回值变量类型，调试时出现逻辑错误；4、在定义结构体时，定义结构体指针变量，但在程序运行时出现了定义的结构体指针不起作用。

5、在运行程序时，由于没有声明变量，或对于指针变量没有初始化，无法执行程序。

4.2、执行过程进入家族关系查询系统，系统提示用户输入相关操作：输入要进行的操作：1输入家族的名称：zhang输入家族成员姓名：zhangxianzu输入家族成员姓名：@输入家族成员姓名：zhangguoyu输入家族成员姓名：zhangguojun输入家族成员姓名：zhangguoqiang输入家族成员姓名：@输入家族成员姓名：zhangyongzhi输入家族成员姓名：@输入家族成员姓名：zhangyongrui输入家族成员姓名：zhangyongming输入家族成员姓名：@输入家族成员姓名：@输入家族成员姓名：zhangwende输入家族成员姓名：zhangwenjia输入家族成员姓名：@输入家族成员姓名：#家族关系成功建立！（系统接着提示用户输入）输入要进行的操作：2（输入结果）zhangxianzu zhangguoyu zhangyongzhi zhangwende，zhangwenjia zhangguojun zhangyongrui zhangyongmingzhangguoqiang（系统接着提示用户输入）输入要进行的操作：6（输入结果）成功退出家族关系查询系统！4.3、运行时界面1、运行主函数时。

2、输入要进行的操作。

3、接着根据提示输入相应的操作，输入数据遍历家族关系查询系统中的成员。

4、根据提示选择确定两人关系选项，输入两个人的姓名。

5、若输入的人不时家族中得人，运行情况如下。