数据结构课设电子版部分参考模版.doc

沈阳航空航天大学课程设计报告 I 目目 录录 1 需求分析需求分析 1 2 系统设计系统设计 2 2 1 数据结构设计 2 2 2 函数设计 2 2 3 关键流程 3 2 3 1 系统主流程 3 2 3 2 查找函数流程 4 2 3 3 插入函数流程 4 3 调试分析调试分析 8 4 测试及运行结果测试及运行结果 9 参考文献参考文献 10 附附 录录 11 沈阳航空航天大学课程设计报告 1 1 需求分析 2 3 树不是一种二叉树 但他的形状满足以下性质 1 一个节点包含一个或两个键值 2 每个内部节点有两个子节点 如果它有一个键值 或三个子节点 如果它有两个键值 3 所有叶节点都在树结构的同一层 因此树的高度总是平衡的 对于每个结点 左子树中所有后继结点的值都小于第一个键的值 而其中间子树中所有结点 的值都大于或等于第一个键的值 如果结点有右子树的话 相应地 结点存储两个键值 那么其中间子树中所有后继结点的值都小于第二个键的值 而其右子树中所有后继结点的值 都大于或等于第二个键的值 同时 同一层的键值从左到右增大 2 3 树的查找方法与二分查找树相似 从根节点出发 如果在根节点找到查找值则查找成功 返回 否则根据节点键的规则递归地查找下去 直到找到或返回失败 在 2 3 树中插入新值时并不为其开辟一个新的叶子节点来存储 也就是说 2 3 树不是向下 生长的 插入算法首先找到一个合适的叶子节点来存放该值 使树的性质不被破坏 如果该 叶子节点只包含一个值 每个节点都最多有两个值 则简单将该值放入叶子节点即可 如 果叶子结点本身已经包含两个值了 则需要为前加入的叶子开辟新的空间 设节点 L 为插入 节点 但是已经满了 也就是 这个节点因为包含了三个值 所以必须进行分裂 设新分裂 出来的节点为 L 则 L 将存储这三个值中最小的那个值 而 L 则存储这三个值中最大的那 个 处于中间的值将得到提升 作为插入值晋升到父节点去 如果父节点只包含一个键值 该值直接放入节点即可 否则 同样的 分裂 晋升 过程将在该父节点进行 一直递归到根 节点为止 2 3 的插入实现中利用了一个函数 split 它接收被插入节点的指针和插入的数据 并将指向 L 指针和被往上传的值通过引用传回来 当插入结点已满时便启用这个函数 从 2 3 树删除一个节点 有三种可能情况需要考虑 最简单的情况是 如果删除的值存储在 有两个键值的节点上 直接删除该值并不影响树的性质与结构 如果被删除的值所在的节点 只有它一个键值 被删除后该节点将为空 因此通过向兄弟节点借一个记录 并修改父节点 来解决 如果兄弟节点不够借 则需要合并相邻节点 并影响双亲 可能导致树的高度下降 如果被删除的值是树的内部节点 则将被删除记录用右边子树中的最小键值代替 然后再根 据第一 二种情况将该值删除 第一种情况的实现相当简单 只需要考虑如果删除的是左键 值 那么要把右键值移过来而已 被借的情况由六个不同的转动和合并子程序实现 沈阳航空航天大学课程设计报告 2 2 系统设计 2 1 数据结构设计数据结构设计 typedef struct Tree23Node 定义 2 3 树的节点类型 int datal 有两个数据域 用来存放节点内数据 int datar Tree23 lchild mchild rchild 三个指针域 分别指向左中右三个孩子 Tree23Node 2 2 函数设计函数设计 本系统所设计的函数见表 2 1 表表 2 12 1 函数列表函数列表 函数名称函数原型功能描述 mainvoid main 系统主程序 compareint compare int x Tree23 t 比较输入数和节点中数的大小关系 createNodeTree23 createNode int key 建立一个新节点 newRoot void newRoot Tree23 root int key Tree23 midSub 新建一棵 2 3 树 isleafbool isleaf Tree23 root 判断是否为叶子节点 findNodeTree23 findNode Tree23 root int key 寻找节点 putvoid put Tree23 root int key Tree23 q 向未满的节点插入一个数 splitvoid split Tree23 p int key Tree23 q 对节点的插入操作 delTree23 del 删除空节点的具体操作 insert23void insert23 Tree23 root int key 建立 2 3 树的主要过程 visitvoid visit Tree23 T 通过使用 分隔层与层 inOrdervoid inOrder Tree23 T 与 visit 函数共同作用控制格式 search23Tree23 search23 Tree23 root int key 查找一个数在 2 3 树中的位置 min23Tree23 min23 Tree23 root 找当前树中最小值 deletexvoid deletex Tree23 t int key 删除节点里的一个数据 leftRotate void leftRotate Tree23 typedef struct Tree23Node Tree23 typedef struct Tree23Node int datal int datar Tree23 lchild mchild rchild Tree23Node define INT MAX 0 x3f3f3f3f 沈阳航空航天大学课程设计报告 12 stack s int compare int x Tree23 t if x datal return 1 else if x t datar return 3 else if x datar else return 4 Tree23 createNode int key Tree23 t new Tree23Node t datal key t datar INT MAX t lchild t mchild t rchild NULL 沈阳航空航天大学课程设计报告 13 return t void newRoot Tree23 root int key Tree23 midSub Tree23 t createNode key t lchild root t mchild midSub root t bool isleaf Tree23 root if root return false Tree23 findNode Tree23 root int key Tree23 t NULL 沈阳航空航天大学课程设计报告 14 while root if isleaf root s push root if isleaf root t root switch compare key root case 1 root root lchild break case 2 root root mchild break case 3 root root rchild break case 4 return NULL return t void put Tree23 root int key Tree23 q if key datal 沈阳航空航天大学课程设计报告 15 root datar root datal root datal key root rchild root mchild root mchild q else root datar key root rchild q void split Tree23 p int key Tree23 q Tree23 t createNode INT MAX if key datal t datal p datar swap key and p datal p datar key key p datal p datal p datar 沈阳航空航天大学课程设计报告 16 set p datar to non sense p datar INT MAX else if key p datar t datal key key p datar p datar INT MAX else t datal p datar p datar INT MAX t lchild p rchild p rchild NULL t mchild q q t Tree23 del if s empty 沈阳航空航天大学课程设计报告 17 Tree23 t s top s pop return t return NULL void insert23 Tree23 root int key Tree23 p q temp if root NULL tree is empty newRoot root key NULL else insert into an empty tree p findNode root key if p NULL cout The key is currently in the tree datar INT MAX two sub node put break else three sub node split p if p root split the root newRoot root key q break else remove a node from stack p del 沈阳航空航天大学课程设计报告 19 void visit Tree23 T if T datar INT MAX cout datal datar datal INT MAX cout datal else cout void inOrder Tree23 T if T visit T cout lchild NULL return 沈阳航空航天大学课程设计报告 20 cout lchild cout mchild cout rchild cout lchild break case 2 root root mchild break case 3 root root rchild 沈阳航空航天大学课程设计报告 21 break case 4 return root return NULL Tree23 min23 Tree23 root while root lchild s push root root root lchild s push root return root void deletex Tree23 t int key delete key from node t if key t datal delete first key 沈阳航空航天大学课程设计报告 22 if t datar datal t datar t datar INT MAX else two sub node t datal INT MAX else delete second key t datar INT MAX void leftRotate Tree23 r datal q datal q datal q datar q datar INT MAX 沈阳航空航天大学课程设计报告 23 p mchild q lchild q lchild q mchild q mchild q rchild q rchild NULL void leftCombine Tree23 p datar q datal p mchild q lchild p rchild q mchild delete q if r datar INT MAX r is two sub node r datal INT MAX r mchild NULL else r datal r datar r datar INT MAX 沈阳航空航天大学课程设计报告 24 r mchild r rchild r rchild NULL void middleRotate Tree23 r datal q datar q datar INT MAX p mchild q rchild q rchild NULL void middleCombine Tree23 q rchild p lchild delete p if r datar datal r datar r datar INT MAX r mchild r rchild r rchild NULL else r datal INT MAX r mchild NULL void rightRotate Tree23 r datar q datar q datar INT MAX p mchild q rchild q rchild NULL 沈阳航空航天大学课程设计报告 26 void rightCombine Tree23 r datar INT MAX q rchild p lchild del