数据结构课程设计家族关系

课程名称课程名称 数据结构数据结构 课程设计课程设计 课程设计题目课程设计题目 家族关系查询系统家族关系查询系统 姓姓 名名 周楠周楠 院系院系 计算机学院计算机学院 专专 业业 软件工程软件工程 年年 级级 20112011 学学 号号 E01114323E01114323 指导教师指导教师 王爱平王爱平 20132013 年年 9 9 月月 2525 日日 目目 录录 1 1 课程设计的目的课程设计的目的 2 2 需求分析需求分析 3 3 课程设计报告内容课程设计报告内容 3 13 1 概要设计概要设计 3 23 2 详细设计详细设计 3 33 3 调试分析调试分析 3 43 4 用户手册用户手册 3 53 5 测试结果测试结果 3 63 6 程序清单程序清单 4 4 小结小结 5 5 参考文献参考文献 1 1 课程设计的目的课程设计的目的 1 1 熟练使用熟练使用 C C 语言编写程序 解决实际问题语言编写程序 解决实际问题 2 2 了解并掌握数据结构与算法的设计方法 具备初步的独立分析和设计能力了解并掌握数据结构与算法的设计方法 具备初步的独立分析和设计能力 3 3 初步掌握软件开发过程的问题分析 系统设计 程序编码 测试等基本方初步掌握软件开发过程的问题分析 系统设计 程序编码 测试等基本方 法和技能法和技能 4 4 提高综合运用所学的理论知识和方法独立分析和解决问题的能力提高综合运用所学的理论知识和方法独立分析和解决问题的能力 2 2 需求分析需求分析 随着社会发展 人们使用纸质的家谱已经非常不方便而且不利于在家谱里进行随着社会发展 人们使用纸质的家谱已经非常不方便而且不利于在家谱里进行 添加和修改 而用算法设计一个家族关系查询系统则可以解决这个问题 数据添加和修改 而用算法设计一个家族关系查询系统则可以解决这个问题 数据 结构的二叉树刚好满足家谱的基本结构 首先建立一个文件作为家谱 然后在结构的二叉树刚好满足家谱的基本结构 首先建立一个文件作为家谱 然后在 文件中输入字符串 实现了在文件中按照数据的逻辑关系进进输入便可建立相文件中输入字符串 实现了在文件中按照数据的逻辑关系进进输入便可建立相 应的三叉链表 然后就是进行数据的存储 删除及查找工作 应的三叉链表 然后就是进行数据的存储 删除及查找工作 3 3 算法分析算法分析 本次设计研究的是建立家族关系 实现对家族成员关系相关查询的问题 在设本次设计研究的是建立家族关系 实现对家族成员关系相关查询的问题 在设 计中使用的数据结构为树状结构 树状结构采用三叉链表实现 我们在建立好计中使用的数据结构为树状结构 树状结构采用三叉链表实现 我们在建立好 家族关系后将其存储在文件中 在文件中家族关系是以树的形式存储 运用树家族关系后将其存储在文件中 在文件中家族关系是以树的形式存储 运用树 的操作使家族关系得以准确建立 的操作使家族关系得以准确建立 家族关系查询系统可分为六大模块 分别是家族关系查询系统可分为六大模块 分别是 创建 修改 查询 保存 退出等 建立家族关系模块 建立家族关系并存入创建 修改 查询 保存 退出等 建立家族关系模块 建立家族关系并存入 文件 建立时首先输入家族关系的名称 以此名称为名建立文本文件 接下来文件 建立时首先输入家族关系的名称 以此名称为名建立文本文件 接下来 按层输入成员姓名 输入一个在文件中写入一个字符串 以回车键结束 打开按层输入成员姓名 输入一个在文件中写入一个字符串 以回车键结束 打开 一个家族关系 在界面输入选项名 以家族关系名为文件名打开文件 如果家一个家族关系 在界面输入选项名 以家族关系名为文件名打开文件 如果家 族关系不存在 返回空 如果存在 打开文件 读取文件 向家族中添加一个族关系不存在 返回空 如果存在 打开文件 读取文件 向家族中添加一个 新成员 添加的新成员要根据其父亲确定其在家族中的位置 首先判断该父亲新成员 添加的新成员要根据其父亲确定其在家族中的位置 首先判断该父亲 是否在此家族关系中 若存在 则查找其父亲 将新节点插入其父亲的最后一是否在此家族关系中 若存在 则查找其父亲 将新节点插入其父亲的最后一 个孩子之后 若没有孩子 直接作为左孩子插入 以写入的方式打开文件 更个孩子之后 若没有孩子 直接作为左孩子插入 以写入的方式打开文件 更 新数组中的信息 然后将数组中的信息写入文件保存 关闭文件 查找功能模新数组中的信息 然后将数组中的信息写入文件保存 关闭文件 查找功能模 块 查找一个成员的所有祖先及其兄弟 查找一个成员的所有祖先路径 需要块 查找一个成员的所有祖先及其兄弟 查找一个成员的所有祖先路径 需要 从它的父亲一直向上查找带根结点 查找一个成员的兄弟 一个成员的兄弟为从它的父亲一直向上查找带根结点 查找一个成员的兄弟 一个成员的兄弟为 其父亲除了该结点以外的所有孩子 对于要操作的结点 先判断它是否是根结其父亲除了该结点以外的所有孩子 对于要操作的结点 先判断它是否是根结 点 若是根结点 则无兄弟 若不是根结点 则找到该结点的父亲 接着判断点 若是根结点 则无兄弟 若不是根结点 则找到该结点的父亲 接着判断 父亲的兄弟是否都存在 如果都不存在 则无兄弟 如果都存在 对父亲的孩父亲的兄弟是否都存在 如果都不存在 则无兄弟 如果都存在 对父亲的孩 子操作 子操作 4 4 源程序源程序 include include include include include include include include typedeftypedef charchar TElemType TElemType typedeftypedef intint status status typedeftypedef structstruct BiTPNode BiTPNode TElemTypeTElemType data 10 data 10 structstruct BiTPNodeBiTPNode parent lchild rchild parent lchild rchild 父亲及左右孩子指针父亲及左右孩子指针 BiTPNode BiPTree BiTPNode BiPTree BiPTreeBiPTree P P BiPTreeBiPTree T T 家谱的创建家谱的创建 intint Cre Cre system cls system cls FILEFILE fp fp 声明指向文件的指针声明指向文件的指针 charchar filename 40 str 10 filename 40 str 10 printf printf 请输入家谱名称请输入家谱名称 getchar getchar gets filename gets filename 输入家谱名称输入家谱名称 while filename 0 NULL while filename 0 NULL printf printf 家谱名不能为空家谱名不能为空 请重新输入请重新输入 gets filename gets filename if fp fopen filename w NULL if fp fopen filename w NULL printf sprintf s 家谱创建失败家谱创建失败 n filename n filename returnreturn 0 0 printf printf 请输入家谱内容请输入家谱内容 n n whilewhile strlen gets str 0 strlen gets str 0 fputs str fp fputs str fp 向文件写入字符串向文件写入字符串 putc n fp putc n fp fclose fp fclose fp 关闭文件关闭文件 printf printf 按任一键继续按任一键继续 getch getch returnreturn 1 1 statusstatus loc BiPTreeloc BiPTree T BiPTreeT BiPTree P T 字符串的比较字符串的比较 if strcmp name T data if strcmp name T data returnreturn 1 1 if loc T lchild P name if loc T lchild P name returnreturn 1 1 if loc T rchild P name if loc T rchild P name returnreturn 1 1 elseelse returnreturn 0 0 构造二叉树构造二叉树 statusstatus inittree BiPTreeinittree BiPTree malloc sizeof BiTPNode if T if T returnreturn 0 0 T lchild NULL T lchild NULL T rchild NULL T rchild NULL T parent NULL T parent NULL returnreturn 1 1 载入家谱载入家谱 statusstatus Crt BiPTreeCrt BiPTree fp BiPTreeBiPTree Q R M N Q R M N charchar filename 40 name 10 filename 40 name 10 system cls system cls 清屏清屏 R BiTPNodeR BiTPNode malloc sizeof BiTPNode malloc sizeof BiTPNode 分配存储空间分配存储空间 M BiTPNodeM BiTPNode malloc sizeof BiTPNode malloc sizeof BiTPNode N BiTPNodeN BiTPNode malloc sizeof BiTPNode malloc sizeof BiTPNode printf printf 请输入家谱名请输入家谱名 getchar getchar gets filename gets filename while filename 0 NULL while filename 0 NULL printf printf 家谱名不能为空家谱名不能为空 请重新输入请重新输入 gets filename gets filename if fp fopen filename r NULL if fp fopen filename r NULL printf sprintf s 家谱打开失败家谱打开失败 n filename n filename returnreturn 0 0 inittree T inittree T fscanf fp s name fscanf fp s name 从文件读入姓名从文件读入姓名 strcpy T data name strcpy T data name T lchild NULL T lchild NULL T rchild NULL T rchild NULL T parent NULL T parent NULL fclose fp fclose fp if fp fopen filename r NULL if fp fopen filename r NULL printf printf 家谱打开失败家谱打开失败 n filename n filename returnreturn 0 0 fscanf fp s name fscanf fp s name while feof fp while feof fp if loc T P name if loc T P name fscanf fp s name fscanf fp s name Q BiTPNodeQ BiTPNode malloc sizeof BiTPNode malloc sizeof BiTPNode strcpy Q data name strcpy Q data name P lchild Q P lchild Q 构建孩子构建孩子 Q parent P Q parent P Q lchild NULL Q lchild NULL Q rchild NULL Q rchild NULL N P N P elseelse if loc T P name if loc T P name Q BiTPNodeQ BiTPNode malloc sizeof BiTPNode malloc sizeof BiTPNode R N R N R R lchild R R lchild while R while R M R M R R R rchild R R rchild strcpy Q data name strcpy Q data name M rchild Q M rchild Q Q parent M Q parent M Q lchild NULL Q lchild NULL Q rchild NULL Q rchild NULL fscanf fp s name fscanf fp s name printf printf 信息载入成功信息载入成功 按任一键继续按任一键继续 getch getch returnreturn 1 1 添加成员添加成员 statusstatus in BiPTreein BiPTree father 10 name 10 BiPTreeBiPTree Q M Q M system cls system cls printf printf 请输入要添加到该家谱中的人的父亲姓名请输入要添加到该家谱中的人的父亲姓名 getchar getchar gets father gets father while loc T P father while loc T P father printf sprintf s 不在该家谱中不在该家谱中 请重新输入请重新输入 father father gets father gets father printf printf 请输入要添加到该家谱中的人的姓名请输入要添加到该家谱中的人的姓名 gets name gets name Q BiTPNodeQ BiTPNode malloc sizeof BiTPNode malloc sizeof BiTPNode M BiTPNodeM BiTPNode malloc sizeof BiTPNode malloc sizeof BiTPNode strcpy Q data name strcpy Q data name Q lchild NULL Q lchild NULL Q rchild NULL Q rchild NULL if P lchild if P lchild P lchild Q P lchild Q Q parent P Q parent P elseelse P P lchild P P lchild while P while P M P M P P P rchild P P rchild M rchild Q M rchild Q Q parent M Q parent M printf printf 成员添加成功成员添加成功 按任一键继续按任一键继续 getch getch returnreturn 1 1 删除成员删除成员 statusstatus de BiPTreede BiPTree name 10 system cls system cls printf printf 请输入要删除的人的姓名请输入要删除的人的姓名 getchar getchar gets name gets name while loc T P name while loc T P name printf sprintf s 不在该家谱中不在该家谱中 请重新输入请重新输入 name name gets name gets name if P rchild if P rchild if P parent lchild P if P parent lchild P P parent lchild NULL P parent lchild NULL elseelse P parent rchild NULL P parent rchild NULL free P free P elseelse if P rchild if P rchild if P parent lchild P if P parent lchild P P parent lchild P rchild P parent lchild P rchild elseelse P parent rchild P rchild P parent rchild P rchild free P free P printf printf 成员删除成功成员删除成功 按任一键继续按任一键继续 getch getch returnreturn 1 1 statusstatus Show TElemTypeShow TElemType e 10 e 10 printf sprintf s e e returnreturn 1 1 二叉树的遍历二叉树的遍历 statusstatus pre BiPTreepre BiPTree T status visit TElemType 10 T status visit TElemType 10 if T if T ifif visit T data visit T data ifif pre T lchild visit pre T lchild visit ifif pre T rchild visit pre T rchild visit returnreturn 1 1 returnreturn 0 0 elseelse returnreturn 1 1 家族成员查询家族成员查询 statusstatus Sea BiPTreeSea BiPTree T T charchar name 10 name 10 BiPTreeBiPTree N N N BiTPNodeN BiTPNode malloc sizeof BiTPNode malloc sizeof BiTPNode system cls system cls printf printf 请输入要查寻的人的姓名请输入要查寻的人的姓名 getchar getchar gets name gets name while loc T P name while loc T P name printf sprintf s 不在该家谱中不在该家谱中 请重新输入请重新输入 name name gets name gets name N P N P if P T if P T printf sprintf s 的父亲在该家谱中没有记载的父亲在该家谱中没有记载 n P data n P data elseelse while N parent rchild N while N parent rchild N N N parent N N parent printf sprintf s 的父亲是的父亲是 s n P data N parent data s n P data N parent data N P N P if P T if P T printf sprintf s 没有兄弟没有兄弟 n P data n P data elseelse if P rchild n P data elseelse printf sprintf s 的兄弟有的兄弟有 n name n name while N rchild while N rchild printf sprintf s N rchild data N rchild data N N rchild N N rchild N P N P while N parent rchild N while N parent rchild N printf sprintf s N parent data N parent data N N parent N N parent printf n printf n if P T if P T printf sprintf s 的祖先在该家谱中没有记载的祖先在该家谱中没有记载 n name n name elseelse printf sprintf s 的祖先是的祖先是 s n name T data s n name T data N P N P if P lchild if P lchild printf sprintf s 没有孩子没有孩子 n name n name printf sprintf s 没有后代没有后代 n name n name elseelse printf sprintf s 的孩子有的孩子有 n name n name printf sprintf s P lchild data P lchild data N N lchild N N lchild while N rchild while N rchild printf sprintf s N rchild data N rchild data N N rchild N N rchild printf n printf n printf sprintf s 的后代有的后代有 n name n name pre P lchild Show pre P lchild Show printf n printf n printf printf 按任一键继续按任一键继续 getch getch returnreturn 1 1 文件的创建文件的创建 statusstatus write BiPTreewrite BiPTree T charT char filename 40 filename 40 FILEFILE fp fp if fp fopen filename a NULL if fp fopen filename a NULL printf sprintf s 文件创建失败文件创建失败 n filename n filename returnreturn 0 0 fprintf fp sfprintf fp s T data T data T T lchild T T lchild while T while T fprintf fp sfprintf fp s T data T data T T rchild T T rchild fprintf fp n fprintf fp n 输出输出 fclose fp fclose fp returnreturn 1 1 statusstatus prewrite BiPTreeprewrite BiPTree T status visit BiPTree char 40 charT status visit BiPTree char 40 char filename 40 filename 40 if T if T ifif T lchild T lchild visit T filename visit T filename prewrite T lchild visit filename prewrite T lchild visit filename prewrite T rchild visit filename prewrite T rchild visit filename returnreturn 1 1 elseelse returnreturn 1 1 statusstatus wrong wrong charchar a a scanf c scanf c printf printf 无此选项无此选项 请重新选择请重新选择 按任一键继续按任一键继续 getch getch returnreturn 1 1 家谱的存储家谱的存储 statusstatus Sav BiPTreeSav BiPTree T T FILEFILE fp fp charchar filename 40 filename 40 system cls system cls printf printf 请输入新的文件名请输入新的文件名 getchar getchar gets filename gets filename while filename 0 NULL while filename 0 NULL printf printf 家谱名不能为空家谱名不能为空 请重新输入请重新输入 gets filename gets filename prewrite T write filename prewrite T write filename printf sprintf s 家谱保存成功家谱保存成功 按任一键继续按任一键继续 filename filename getch getch returnreturn 1 1 修改家谱修改家谱 statusstatus Upd Upd system cls sys