数据结构(二叉树)家谱管理系统

数学与计算机学院 课程设计说明书 课 程 名 称 数据结构与算法课程设计 课 程 代 码 题 目 二叉树生成家谱 年级 专业 班 学 生 姓 名 学 号 开 始 时 间 20152015 年 1212 月 0909 日 完 成 时 间 20152015 年 1212 月 2929 日 课程设计成绩 学习态度及平 时成绩 30 技术水平与实 际能力 20 创新 5 说明书 计算书 图纸 分析报告 撰写质量 45 总 分 100 指导教师签名 年 月 日 二叉树生成家谱 3 25 目 录 小三黑体 居中 1 1 需求分析需求分析 6 6 1 1 任务与分析 6 1 2 测试数据 6 2 2 概要设计概要设计 7 7 2 1 ADT 描述 7 2 2 程序模块结构 8 2 3 各功能模块 9 3 3 详细设计详细设计 1010 3 1 结构体定义 10 3 2 初始化 11 3 3 插入操作 13 3 4 查询操作 15 4 4 调试分析调试分析 1818 5 5 用户使用说明用户使用说明 1818 6 6 测试结果测试结果 1818 结结 论论 2323 附附 录录 2424 参考文献参考文献 2525 二叉树生成家谱 4 25 摘摘 要要 随着计算机科学技术 计算机产业的迅速发展 计算机的应用普 及也在以惊人的速度发展 计算机应用已经深入到人类社会的各个 领域 计算机的应用早已不限于科学计算 而更多地应用在信息处 理方面 计算机可以存储的数据对象不再是纯粹的数值 而扩展到 了字符 声音 图像 表格等各种各样的信息 对于信息的处理也 不再是单纯的计算 而是一些如信息存储 信息检索等非数值的计 算 那么 现实世界的各种数据信息怎样才能够存储到计算机的内 存之中 对存入计算机的数据信息怎样进行科学处理 这涉及计算 机科学的信息表示和算法设计问题 为解决现实世界中某个复杂问 题 总是希望设计一个高效适用的程序 这就需要解决怎样合理地 组织数据 建立合适的数据结构 怎样设计适用的算法 以提高程 序执行的时间效率和空间效率 数据结构 就是在此背景下逐步形 成 发展起来的 在各种高级语言程序设计的基本训练中 解决某一实际问题的步 骤一般是 分析实际问题 确定数学模型 编写程序 反复调试程 序直至得到正确结果 所谓数学模型一般指具体的数学公式 方程 式等 如牛顿迭代法解方程 各种级数的计算等 这属于数值计算 的一类问题 而现实生活中 更多的是非数值计算问题 如手机中 的通讯录 人们对它的操作主要是查找 增加 删除或者修改电话 记录 再如 人们经常在互联网上查阅各种新闻 或查阅电子地图 人们可以在某城区地图上查找自己所需的街道或店铺 其操作主要 是搜索和查询 下面再来分析几个典型实例 它们的主要特点是 不同实例的数据元素之间存在不同的关系 对数据信息的处理主要 有插入 删除 排序 检索等 关键词 关键词 网络化 计算机 对策 二叉树 二叉树生成家谱 5 25 引 言 课程设计的目的 通过本项课程设计 培养学生独立思考 综合运用所学 有关相应知识的能力 使学生巩固 数据结构 课程学习的内容 掌握工程软 件设计的基本方法 强化上机动手编程能力 闯过理论与实践相结合的难关 为了培养学生综合运用所学知识 独立分析和解决实际问题的能力 培养创意 识和创新能力 使学生获得科学研究的基础训练 为后续各门计算机课程的学 习和毕业设计打下坚实基础 同时 可以利用这次机会来检验自己的 c c 数 据结构水平 提高自己的写作水平 锻炼自己的动手能力 而此次课程设计的意义在于 增强自己的动手能力 熟悉和掌握二叉树各种遍 历的算法 以及递归在遍历二叉树中的应用 增强自己的调试程序和测试程序 的能力 二叉树生成家谱 6 25 1 1 需求分析需求分析 1 11 1 任务与分析任务与分析 1 建立输入文件以存放最刜家谱中各成员的信息 2 成员的信息中均应包含以下内容 姓名 出生日期 婚否 地址 健在 否 死亡日期 若其已死亡 也可附加其它信息 但不是必需的 3 能对修改后的家谱存盘以备以后使用 4 能从文件中读出已有的家谱 形成树状关系 5 家谱建立好之后 以图形方式显示出来 6 显示第 n 代所有人的信息 7 按照姓名查询 输出成员信息 包括其本人 父亲 孩子的信息 8 按照出生日期查询成员名单 9 输入两人姓名 确定其关系 10 给某人添加孩子 11 删除某人 若其还有后代 则一并删除 12 修改某人信息 13 用括号法输出家谱成员信息 1 21 2 测试数据测试数据 1 徐朝嬴 m 1938 1 20 1 彭代芳 0 此人相当的 热心 0 2 3 4 5 10000 2 徐廷文 m 1964 8 3 2 李太群 1 此人相当有 责任心 0 6 7 10000 3 徐素华 w 1966 4 6 2 李奉光 1 此人很好 0 10000 4 徐军华 m 1969 7 8 2 曲舞 1 此人很有正 二叉树生成家谱 7 25 义感 0 10000 5 徐廷国 m 1972 9 2 2 木玛 1 此人心的很 善良 0 10000 6 徐光勇 m 1989 1 27 3 Nomarry 2 此人很牛逼 0 10000 7 徐光超 m 1992 9 5 3 Nomarry 2 此人亦很牛 逼 0 10000 2 2 概要设计概要设计 2 12 1 ADTADT 描述描述 1 1 ADT Person 数据对象 D Pj Pj 姓名 出生日期 婚否 地址 健在否 如过世 还应有其死亡日 期 j 0 1 2 n 其中 n 0 数据关系 R 基本操作 无 ADT Person 2 2 ADT FamilytreeFile 数据对象 D Aj Aj 属于 Person j 1 2 3 n 其中 n 1 数据关系 D 中每个对象用换行符隔开 R Aj 属于 D j 1 2 3 n 其中 n 1 String 属于字符串类型 为 Aj 父亲姓名 若 String 1 Aj 无父亲 若 String Aj 的姓名 表示家谱文件结束 基本操作 1 打开家谱类型文件 并建立兄弟 孩子二叉树 2 从 内存中读取兄弟 孩子二叉树 并建立家谱类型文件 ADT FamilytreeFlie 3 3 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 后代与祖先关系 child 兄弟之间关系 sibling 基本操作 1 显示某人信息 2 修改某人信息 3 增加某人孩子 二叉树生成家谱 8 25 4 删除某人 5 通过某人查找其双亲 孩子 兄弟 ADT Familytree 2 22 2 程序模块结构程序模块结构 2 2 12 2 1 结构体定义结构体定义 struct People 定义结构体 People int num char name 20 char sex char borndate 15 int generation char matename 20 int parent char infor 100 LinkList child struct Node 定义结构体 Node int a struct Node next struct LinkList 定义链表 NodePoint La struct Tree 定义树 PeoplePoint Tr int Length int TREE INIT SIZE 二叉树生成家谱 9 25 2 32 3 各功能模块各功能模块 void InitTree Tree 在树已定义的情况下 初始化树 TR LinkList InitLinkList void 在什么都没有的情况下 初始化一个带头结 点的链表并返回链表 L void AddLinkList LinkList p 对带头结点的链表 pl 添加一个节点为 m 的节点在表头 void CreatFamilyTree Tree 在什么都没有的情况下 创建一个家谱 TR 并返回 TR void PrintPeople PeoplePoint p 已知某节点的指针 p 输出 people p 的相关信息 void PrintLinkList LinkList p 已知链表 p 输出链表 p 中的信息 int CompareNum PeoplePoint p int num 已知某节点的指针 p 和一个编号 num 比较 p 的 num 和 num 如果相等返回 1 否则返回 0 int CompareName PeoplePoint p char a 已知某节点的指针 p 和一个姓 名 a 比较 p 的 name 如果两者相等返回 1 否则返回 0 void TraveTreePrint Tree TR 已知树 TR 按规定输出节点信息 根据编 号 姓名 孩子输出 新 建 家 谱 模 块 查 找 功 能 模 块 添 加 成 员 模 块 修 改 婚 姻 信 息 退 出 程 序 模 块 件 读 取 文 件 读 取 模 块 全部功能模块 读 取 家 谱 模 块 保 存 家 谱 模 块 void Prin tPeo ple Peop lePo int p void AddP eopl e Tr ee void Marr yCha nge Tree TR c har name 20 Exit 1 void Init Tree Tre e void Prin tTre e Tr ee TR void Open Tre e void Save Tre e TR 输 出 成 员 模 块 二叉树生成家谱 10 25 void AddPeople Tree 已知树 TR 当有人出生时 添加一个节点 void MarryChange Tree TR char name 20 已知树 TR 和一个人的姓名 name 因为结婚需要改变节点中的配偶一栏 void Open Tree 打开保存家谱信息的文件 void Save Tree TR 保存家谱信息到指定文件 void PrintTree Tree TR 输出家谱中所有成员的信息 3 3 详细设计详细设计 3 13 1 结构体定义结构体定义 struct People 定义结构体 People int num char name 20 char sex char borndate 15 int generation char matename 20 int parent char infor 100 LinkList child struct Node 定义结构体 Node int a struct Node next struct LinkList 定义链表 NodePoint La struct Tree 定义树 PeoplePoint Tr int Length int TREE INIT SIZE 二叉树生成家谱 11 25 3 3 2 2 初始化初始化 void InitTree Tree TR Tr peop TR Length 0 TR TREE INIT SIZE INIT SIZE LinkList InitLinkList void 在什么都没有的情况下 初始化一个带头结点 的链表并返回链表 L LinkList L NodePoint Head Head NodePoint malloc sizeof Node Head a 0 Head next NULL L La Head return L void CreatFamilyTree Tree TR Tr peop TR Length 0 TR TREE INIT SIZE INIT SIZE int i 0 n j k c cout n TR Length n for i 0 i n i peop i num i 1 cout peop i name cout peop i sex cout peop i borndate cout peop i generation cout peop i matename cout peop i parent cout peop i infor LinkList L NodePoint Head Head NodePoint malloc sizeof Node Head a 0 Head next NULL L La Head peop i child L lp peop i child cout k 二叉树生成家谱 13 25 for j 0 j k j cout c AddLinkList lp c 3 33 3 插入操作插入操作 void AddPeople Tree 结束 判断格式是否正确 是 否 二叉树生成家谱 14 25 int k c j m LinkList L L1 L2 NodePoint Head PeoplePoint p1 p2 p3 if TR Length TR TREE INIT SIZE TR Tr PeoplePoint realloc TR Tr TR TREE INIT SIZE TREEINCREMENT L EN if TR Tr exit OVERFLOW p1 peop p2 p1 TR Length p2 num TR Length 1 cout name cout p2 sex cout p2 borndate cout p2 generation cout matename cout p2 parent cout infor gets p2 infor 二叉树生成家谱 15 25 Head NodePoint malloc sizeof Node Head a 0 Head next NULL L La Head p2 child L L1 p2 child cout k for j 0 j k j cout c AddLinkList L1 c m p2 parent 1 p3 p1 m L2 p3 child AddLinkList L2 p2 num TR Length TR Length 1 cout 添加成功 n 3 4 查询操作查询操作 二叉树生成家谱 16 25 void TraveTreePrint Tree TR 已知树 TR 按规定输出节点信息 根据编号 姓名 孩子输出 PeoplePoint p int i j k Flag char name1 15 name2 15 p TR Tr printf 根据编号查找请输入 1 根据姓名查找请输入 2 根据孩子查找请输入 3 n scanf d if i 1 printf 请输入该节点的编号 n scanf d 进入函数 结束 PrintPeople p j PrintPeople p j PrintPeople p peop j pa rent 1 选择功能 A 1 A 2 A 3 输出信息 输出信息 输出信息 二叉树生成家谱 17 25 for j 0 j TR Length j Flag CompareNum p j k if Flag PrintPeople p j if i 2 printf 请输入该人的姓名 n gets name1 gets name1 for j 0 j TR Length j Flag CompareName p j name1 if Flag PrintPeople p j if i 3 printf 请输入其孩子的姓名 n gets name2 gets name2 for j 0 j TR Length j if strcmp peop j name name2 0 二叉树生成家谱 18 25 PrintPeople p peop j parent 1 4 4 调试分析调试分析 在调试时 遇到的几个问题如下 1 建立树时 由于新申请结点的孩子指针 兄弟指针 及双亲指针均未赋 空值 而在以后的函数中对树迚行递归操作时均以这些指针值中的一个或几个 是否为空 作为递归结束条件 从而导致调用这些函数时出现系统保护异常 使 用了不安全 的指针 2 刚开始初除结点时 只考虑到初除其本身结点的情况 而初除其孩子结 点的 情况未考虑到 故在初除某些结点时使树出现了 断链 现象 故在程序 代码中 对初除某一结点迚行操作时 首先要刞断此结点是否有孩子及兄弟 然 后迚行相 应操作 本程序的编译环境为 Microsoft Visual C 6 0 在 Windows 8 下编译通 过 5 5 用户使用说明用户使用说明 用户在打开软件后即可使用本软件 傻瓜式操作 界面简单易懂 用户在使 用本软件过程中若出现隐私泄露或受到任何损失 与作者无关