logo资料库

数据结构 家谱系统.doc

发布时间：2022-06-08 发布人：admin 分类：说明书 资料大小：0.73M 资料格式：doc 举报 版权申诉
第1页 / 共26页
第2页 / 共26页
第3页 / 共26页
第4页 / 共26页
第5页 / 共26页
第6页 / 共26页
第7页 / 共26页
第8页 / 共26页
资料共26页，剩余部分请下载后查看
    摘 要 在本次家谱课程设计中采用二叉树来表示家谱关系,由于在家谱中每 个家族成员的子女不止一个,而双亲只有一个,所以采用二叉树结构来描述 家族成员之间的关系。在家谱课程设计中还用到单链表,在设计中要将二叉 树存储在文件中,最终要读取文件中的记录,要将文件中的数据还原到内存 中组成二叉树结构,而文件中元素与元素之间的结构是线性,而且直接对文 件中的数据操作很不方便，所以将文件中的元素存储在单链表中,再对单链 表操作还原成内存中的二叉树。 在对家谱的文件操作中，为了还原家谱方便，采用按层遍历的顺序保 存二叉树中各结点的信息，在层次遍历中，使用队列来实现二叉树的层次 遍历。 本家谱主要包括两个模块，第一个是文件操作功能模块，此模块实现 了家谱记录输入、读取存盘记录、清除家谱存盘记录、添加成员、存盘 、修改家谱成员信息、删除家谱成员等七大功能；第二个是家谱操作功能 模块，实现了查找某人记录、查找某人的孩子、查找某人的祖先、用括号 表示法输出家谱、用凹入表示法输出家谱等六大功能。 关键词： Binarytnode save search addRecord del change clear 1
    本程序功能框架图 家谱管理系统 文件操作功能 家谱操作功能 家 谱 记 录 输 入 读 取 存 盘 记 录 清 除 家 谱 存 盘 记 录 存 盘 添 加 成 员 删 除 家 谱 成 员 查 找 某 人 记 录 修 改 家 谱 成 员 信 查 找 某 人 的 孩 子 查 找 某 人 的 祖 先 用 括 号 表 示 法 输 出 用 凹 入 表 示 法 输 出 2
    1． 项目总体设计 1.1 需求分析 (1) 文件操作功能：记录输入、记录输出、清除全部文件记录和将家 谱记录存盘。初始化：用户可输入一个家族的族谱，输入完成之后可保存 在文件中。在其后的操作中，可从文件里读取族谱信息、增加新的家族成 员、修改已有的家族成员、删除已存在的家族成员、可清除所有的家族成 员信息。操作完成之后可保存在文件中。 (2) 家谱操作功能：用括号表示法和凹入法输出家谱二叉树，并能查 找某人的配偶、所有孩子、所有祖先、兄弟等功能。 1.2 系统功能模块设计： 一．问题描述 本课程设计的主要问题是选择一种数据结构来描述家谱中家族成员之 间的关系，在此数据结构上加之一些操作，选用特定的算法来实现家 谱操作的功能和文件操作的功能。 二．基本要求 设计要求：编写一个程序，采用一棵二叉树表示一个家谱关系。 具体要求： (1) 文件操作功能：记录输入、记录输出、清除全部文件记录和将家 谱记录存盘。 (2) 家谱操作功能：用括号表示法和凹入法输出家谱二叉树，并能查 找某人所有的儿子，查找某人的所有祖先。 三．概要设计 1．数据结构的设计 3
    在家谱课程设计中采用二叉树来表示家谱关系,由于在家谱中每个 家族成员的子女不止一个,而双亲只有一个,所以采用二叉树结构来描 述家族成员之间的关系。在家谱课程设计中还用到单链表,在设计中要 将二叉树存储在文件中,最终要读取文件中的记录,要将文件中的数据 还原到内存中组成二叉树结构,而文件中元素与元素之间的结构是线性, 而且直接对文件中的数据操作很不方便，所以将文件中的元素存储在 单链表中,再对单链表操作还原成内存中的二叉树。 在对家谱的文件操作中，为了还原家谱方便，采用按层遍历的顺 序保存二叉树中各结点的信息，在层次遍历中，使用队列来实现二叉 树的层次遍历。 2．算法的设计 本设计从总体上主要分 2 个模块，分别是家谱操作模块和文件操 作模块。 家谱操作模块： 1）Binarytnode* Binarytree::bulid(Binarytnode* p,int num)； //输入家谱，形参 p 为二叉树根结点的地址，形参 num 为结点的编号， 建立二叉树并返回这棵二叉树的根结点的地址。 算法：首先先建立一个二叉树结点，提示用户输入该结点的姓名，将 用户输入的姓名写入到该结点的成员变量 name 中，将形参 num 写入 到该结点的成员变量 number 中，将双亲结点的地址赋给结点的成员变 量的双亲指针，提示用户是否有左孩子，若有左孩子则递归调用通过 形参将双亲结点的地址传递过去，递归调用返回的地址赋给它的双亲 结点的左孩子指针，右孩子的建立同理可得，通过递归来建立整棵二 4
    叉树。 2）Binarytnode* Binarytree::searchRecord(string name)； //形参 name 要查找的姓名，按姓名查找某人记录，若找到记录则返 回该节点的地址，反之，则返回一个空指针。 算法：通过层次遍历来和每个结点的成员变量 name 比较若姓名匹配 则返回该节点的地址。首先判断二叉树的根结点是否为为空，若为空 则不进行查找。反之，则将根结点入队列，然后进入一个循环体，使 循环为真的条件是队列不为空，循环体语句是取队头元素，然后对该 元素的判断它的成员变量 name 是否与查找的姓名相匹配。若匹配则返 回该结点的地址，若不匹配，则删除队头元素将它的左右孩子入队列 （左右孩子不空的情况下），进行循环。若直到遍历完整棵子树都还没 找到，则返回一个空指针。 3）void Binarytree::searchChild(string name)； //形参 name 要查找的姓名，按姓名查找某人的孩子，若找到记录则 显示该节点孩子的姓名，反之，则提示未找到信息。 算法：调用 Binarytnode* searchRecord(string name)函数查找与参数 name 相匹配的记录，然后判断其返回的地址是否为空，若为空则不进 行查找其子女，若不为空，则输出其左右孩子（左右孩子不空的情况 下）。 4）void Binarytree::searchParent(string name)； //形参 name 要查找的姓名，按姓名查找某人的祖先，若找到记录则 按辈份从小到大显示该节点的祖先，反之，则提示未找到信息。 算法：调用 Binarytnode* searchRecord(string name)函数查找与参数 5
    name 相匹配的记录，然后判断其返回的地址是否为空，若为空则不进 行查找其双亲，若不为空，则用循环通过双亲指针按辈分从小到大输 出双亲的姓名，直到双亲的地址为空，结束循环。 5）void Binarytree::addRecord(string parent,string name)； //插入家族成员记录，形参 parent 为要插入的家族成员的双亲姓名， 形参 name 为要插入家族成员的姓名。 算法：调用 Binarytnode* searchRecord(string name)函数查找与参数 name 相匹配的记录，然后判断其返回的地址是否为空，若为空则不进 行插入操作，若不为空，则判断其是否左子树是否为空，若为空则建 立一个结点将参数 name 赋给结点的成员变量 name 中去，然后通过它 的双亲结点的编号计算出它的编号为 2*number，将编号、双亲的地址 分别赋给它的成员变量 number、parent 。若不为空，再判断它的右子 树是否为空，若为空则按建立左孩子的同样的方法建立右孩子。若还 为空，则说明左右子树都不为空，则不允许添加记录。 6）void Binarytree::change(string name)； //修改家族成员的信息，行参 name 为要修改的家族成员的姓名。 算法：调用 Binarytnode* searchRecord(string name)函数查找与参数 name 相匹配的记录，然后判断其返回的地址是否为空，若为空则不进 行修改操作，若不为空，则将参数 name 赋给它的成员变量 name 中。 7）void Binarytree::del(string name)； //删除家族成员，行参为要删除的家族成员的姓名。 算法：调用 Binarytnode*searchRecord(string name)函数查找与参数 name 相匹配的记录，然后判断其返回的地址是否为空，若为空则不进 6
    行删除操作，若不为空，则判断其左右子树是否为空，若左右子树都 为空，则将其双亲结点的对应的左或右孩子指针赋为空，释放其结点 的空间。反之，则不删除该结点。该函数只允许删除叶子结点。 8） Binarytnode* Binarytree::load(node* head, Binarytnode* parent) // 读取存盘记录，将单链表还原为二叉树，返回该二叉树的根结点的 地址。 算法：通过递归调用来重建二叉树。首先，调用函数 node* node:: read()，该函数的作用是将文件中二叉树的信息存放在单链表中，返回 单链表的头指针的地址。若返回的指针为空，则，不进行读取存盘记 录操作，若不空，则建立一个二叉树结点，取单链表的的一个节点， 将其结点的信息写入到二叉树结点的相应的成员变量中，通过编号计 算出该左孩子的的编号（由于孩子的编号肯定小于双亲的编号，而编 号在单链表是从小到大排列的）从当前单链表的结点往下寻找编号相 匹配的结点 若找到，则将该结点的地址和二叉树结点的地址通过函数的参数递 归调用该函数返回的地址赋给二叉树的左孩子指针，右子树的建立同 左子树的建立同理。建立完整个二叉树后，返回该二叉树根结点的地 址。 9）void Binarytree::displaytree1(Binarytnode* root) //括号法显示, 形参 root 为根结点的的地址。 算法：用递归来实现二叉树的括号法表示。首先，判断二叉树根结 点是否为空，若为空，则不显示二叉树，若不为空，则显示根结点的 数据，输出′(′,再递归调用显示它的左孩子（左孩子不空的情况下）， 7
    然后输出′，′，再递归调用显示它的右孩子（右孩子不空的情况下）， 然后输出′）′。 10）void Binarytree::displaytree2(Binarytnode* root,int n); //凹入法显示，形参 root 为根结点的地址,行参 n 为缩进量。 算法：用递归来实现二叉树的凹入法表示。首先，判断二叉树是否 为空，若为空，则不显示二叉树，设置输出宽度（由形参 n 决定），递 归显示它的左孩子输出宽度为它双亲结点的输出宽度的 2 倍，换行， 通力递归显示它的右孩子，换行。 文件操作模块: 1） void Binarytree::save(Binarytnode* root) //存盘，将家谱保存到文件中，行参为二叉树根结点的地址。 算法：为了还原二叉树方便采用按层次遍历（其记录按编号由从小大 到大的顺序存储在文件中）的顺序来保存二叉树的信息。首先，先清 空原来文件的内容，判断二叉树根结点的是否为空，若为空，则不进 行存盘操作，若不为空，将根结点入队列，进入循环，循环为真的条 件是对列为空，循环体为，取队头元素，将对头元素的姓名和编号写 入文件，然后删除对头元素，再将其左子树和右子树入队列（若左右 子树存在的情况下）。当循环结束的时候，整棵二叉树都保存在文件中 （遍历结束）。 2）void Binarytree::clear()；//清除文件内容。 算法：删除存档文件 jiapu.txt。并建立一个空文件 jiapu.txt。 2） node* node:: read()； //将文件中二叉树的信息存放在单链表中，返回单链表的头指针的地址 8
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料