《数据结构课设电子版部分参考模版》由会员分享，可在线阅读，更多相关《数据结构课设电子版部分参考模版（32页珍藏版）》请在金锄头文库上搜索。
1、沈阳航空航天大学课程设计报告 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）每个内部节点有两个子节点（如果它有一个键值）或三个子节点（如
2、果它有两个键值）（3）所有叶节点都在树结构的同一层，因此树的高度总是平衡的。对于每个结点, 左子树中所有后继结点的值都小于第一个键的值, 而其中间子树中所有结点的值都大于或等于第一个键的值。如果结点有右子树的话( 相应地, 结点存储两个键值) , 那么其中间子树中所有后继结点的值都小于第二个键的值, 而其右子树中所有后继结点的值都大于或等于第二个键的值。同时，同一层的键值从左到右增大。2-3 树的查找方法与二分查找树相似，从根节点出发，如果在根节点找到查找值则查找成功返回，否则根据节点键的规则递归地查找下去，直到找到或返回失败。在 2-3 树中插入新值时并不为其开辟一个新的叶子节点来存储，也就
3、是说，2-3 树不是向下生长的。插入算法首先找到一个合适的叶子节点来存放该值，使树的性质不被破坏。如果该叶子节点只包含一个值（每个节点都最多有两个值），则简单将该值放入叶子节点即可。如果叶子结点本身已经包含两个值了，则需要为前加入的叶子开辟新的空间。设节点 L 为插入节点，但是已经满了，也就是，这个节点因为包含了三个值，所以必须进行分裂，设新分裂出来的节点为 L，则 L 将存储这三个值中最小的那个值，而 L则存储这三个值中最大的那个。处于中间的值将得到提升，作为插入值晋升到父节点去。如果父节点只包含一个键值，该值直接放入节点即可，否则，同样的“分裂-晋升”过程将在该父节点进行，一直递归到根节点
4、为止。2-3 的插入实现中利用了一个函数 split，它接收被插入节点的指针和插入的数据，并将指向 L指针和被往上传的值通过引用传回来。当插入结点已满时便启用这个函数。从 2-3 树删除一个节点，有三种可能情况需要考虑：最简单的情况是，如果删除的值存储在有两个键值的节点上，直接删除该值并不影响树的性质与结构。如果被删除的值所在的节点只有它一个键值，被删除后该节点将为空，因此通过向兄弟节点借一个记录，并修改父节点来解决。如果兄弟节点不够借，则需要合并相邻节点，并影响双亲，可能导致树的高度下降。如果被删除的值是树的内部节点，则将被删除记录用右边子树中的最小键值代替，然后再根据第一、二种情况将该值删
5、除。第一种情况的实现相当简单，只需要考虑如果删除的是左键值，那么要把右键值移过来而已。被借的情况由六个不同的转动和合并子程序实现。沈阳航空航天大学课程设计报告 - 2 -2 系统设计2.1 数据结构设计typedef struct Tree23Node /定义 2-3 树的节点类型int datal; /有两个数据域，用来存放节点内数据int datar; Tree23 lchild, mchild, rchild; /三个指针域，分别指向左中右三个孩子 Tree23Node;2.2 函数设计本系统所设计的函数见表 2.1。表 2.1 函数列表函数名称 函数原型 功能描述main void m
6、ain(); 系统主程序compare int compare(int x, Tree23 t); 比较输入数和节点中数的大小关系createNode Tree23 createNode(int key); 建立一个新节点newRoot void newRoot(Tree23 *root, int key, Tree23 midSub); 新建一棵 2-3 树isleaf bool isleaf(Tree23 root); 判断是否为叶子节点findNode Tree23 findNode(Tree23 root, int key); 寻找节点put void put(Tree23 *root
7、, int key, Tree23 q); 向未满的节点插入一个数split void split(Tree23 p, int *key, Tree23 *q); 对节点的插入操作del Tree23 del() 删除空节点的具体操作insert23 void insert23(Tree23 *root, int key) 建立 2-3 树的主要过程visit void visit(Tree23 T) 通过使用“（） ”分隔层与层inOrder void inOrder(Tree23 T) 与 visit 函数共同作用控制格式search23 Tree23 search23(Tree23 ro
8、ot, int key) 查找一个数在 2-3 树中的位置min23 Tree23 min23(Tree23 root) 找当前树中最小值deletex void deletex(Tree23 t, int key) 删除节点里的一个数据leftRotate void leftRotate(Tree23 &p, Tree23 &q, Tree23 &r) 将一个数据插入树中的六种情况沈阳航空航天大学课程设计报告 - 3 -leftCombine void leftCombine(Tree23 &p, Tree23 &q, Tree23 &r) 将一个数据插入树中的六种情况middleRotat
9、e void middleRotate(Tree23 &p, Tree23 &q, Tree23 &r) 将一个数据插入树中的六种情况middleCombine void middleCombine(Tree23 &p, Tree23 &q, Tree23 &r) 将一个数据插入树中的六种情况rightRotate void rightRotate(Tree23 &p, Tree23 &q, Tree23 &r) 将一个数据插入树中的六种情况rightCombine void rightCombine(Tree23 &p, Tree23 &q, Tree23 &r) 将一个数据插入树中的六种情
10、况delete23 bool delete23(Tree23 *root, int key) 从树中删除一个数据2.3 关键流程2.3.1 系统主流程主函数主要保证程序能够多次输入正确的数据，起到开始和停止的作用。流程图如下。图 2.1沈阳航空航天大学课程设计报告 - 4 -2.3.2 查找函数流程因为 2-3 树的节点元素与子树上元素的大小上有一定关系，因此，通过指针和查找结点程序的递归调用，实现搜素整个树。流程图如下图 2.22.3.3 插入函数流程在 2-3 树中插入新值时并不为其开辟一个新的叶子节点来存储，也就是说，2-3 树不是向下生长的。插入算法首先找到一个合适的叶子节点来存放该值
11、，使树的性质不被破坏。如果该叶子节点只包含一个值（每个节点都最多有两个值），则简单将该值放入叶子节点即可。如果叶子结点本身已经包含两个值了，则需要为前加入的叶子开辟新的空间。设节点 L 为插入节点，但是已经满了，也就是，这个节点因为包含了三个值，所以必须进行分裂，设新分沈阳航空航天大学课程设计报告 - 5 -裂出来的节点为 L，则 L 将存储这三个值中最小的那个值，而 L则存储这三个值中最大的那个。处于中间的值将得到提升，作为插入值晋升到父节点去。如果父节点只包含一个键值，该值直接放入节点即可，否则，同样的“分裂- 晋升”过程将在该父节点进行，一直递归到根节点为止。往 2-3 树中插入元素和往二叉查找树中插入元素一样，首先要进行查找，然后将节点挂到未找到的节点上。2-3 树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态
