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

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。

6、表表 2.12.1 函数列表函数列表函数名称函数原型功能描述mainvoid main();系统主程序compareint compare(int x, Tree23 t);比较输入数和节点中数的大小关系createNodeTree23 createNode(int key);建立一个新节点newRootvoid newRoot(Tree23 *root, int key, Tree23 midSub);新建一棵 2-3 树isleafbool isleaf(Tree23 root);判断是否为叶子节点findNodeTree23 findNode(Tree23 root, int key);

7、寻找节点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 se

8、arch23(Tree23 root, int key)查找一个数在 2-3 树中的位置min23Tree23 min23(Tree23 root)找当前树中最小值deletexvoid deletex(Tree23 t, int key)删除节点里的一个数据leftRotatevoid leftRotate(Tree23 &p, Tree23 &q, Tree23 &r)将一个数据插入树中的六种情况沈阳航空航天大学课程设计报告 - 3 -leftCombinevoid leftCombine(Tree23 &p, Tree23 &q, Tree23 &

9、amp;r)将一个数据插入树中的六种情况middleRotatevoid middleRotate(Tree23 &p, Tree23 &q, Tree23 &r)将一个数据插入树中的六种情况middleCombinevoid middleCombine(Tree23 &p, Tree23 &q, Tree23 &r)将一个数据插入树中的六种情况rightRotatevoid rightRotate(Tree23 &p, Tree23 &q, Tree23 &r)将一个数据插入树中的六种情况rightCombinevoid

10、 rightCombine(Tree23 &p, Tree23 &q, Tree23 &r)将一个数据插入树中的六种情况delete23bool delete23(Tree23 *root, int key)从树中删除一个数据2.3 关键流程关键流程2.3.1 系统主流程系统主流程主函数主要保证程序能够多次输入正确的数据，起到开始和停止的作用。流程图如下。图图 2.12.1沈阳航空航天大学课程设计报告 - 4 -2.3.2 查找函数流程查找函数流程因为 2-3 树的节点元素与子树上元素的大小上有一定关系，因此，通过指针和查找结点程序的递归调用，实现搜素整个树。流程图如下

11、图图 .3 插入函数流程插入函数流程在 2-3 树中插入新值时并不为其开辟一个新的叶子节点来存储，也就是说，2-3 树不是向下生长的。插入算法首先找到一个合适的叶子节点来存放该值，使树的性质不被破坏。如果该叶子节点只包含一个值（每个节点都最多有两个值），则简单将该值放入叶子节点即可。如果叶子结点本身已经包含两个值了，则需要为前加入的叶子开辟新的空间。设节点 L 为插入节点，但是已经满了，也就是，这个节点因为包含了三个值，所以必须进行分裂，设新分沈阳航空航天大学课程设计报告 - 5 -裂出来的节点为 L，则 L 将存储这三个值中最小的那个值，而 L则存储这三个值中最大的那个。处

12、于中间的值将得到提升，作为插入值晋升到父节点去。如果父节点只包含一个键值，该值直接放入节点即可，否则，同样的“分裂-晋升”过程将在该父节点进行，一直递归到根节点为止。往 2-3 树中插入元素和往二叉查找树中插入元素一样，首先要进行查找，然后将节点挂到未找到的节点上。2-3 树之所以能够保证在最差的情况下的效率的原因在于其插入之后仍然能够保持平衡状态。如果查找后未找到的节点是一个 2-node 节点，那么很容易，我们只需要将新的元素放到这个 2-node 节点里面使其变成一个 3-node 节点即可。但是如果查找的节点结束于一个 3-node 节点，那么可能有点麻烦。图图 2.2. 3 3往一个

13、 3-node 节点插入一个新的节点可能会遇到很多种不同的情况，下面首先从一个最简单的只包含一个 3-node 节点的树开始讨论。图图 2.42.4如上图，假设 2-3 树只包含一个 3-node 节点，这个节点有两个 key，没有空间来插入第沈阳航空航天大学课程设计报告 - 6 -三个 key 了，最自然的方式是我们假设这个节点能存放三个元素，暂时使其变成一个 4-node节点，同时他包含四个子节点。然后，我们将这个 4-node 节点的中间元素提升，左边的节点作为其左节点，右边的元素作为其右节点。插入完成，变为平衡 2-3 查找树，树的高度从0 变为 1。对于节点是 3-node，父节点是

14、 2-node，和第一种情况一样，我们也可以将新的元素插入到 3-node 节点中，使其成为一个临时的 4-node 节点，然后，将该节点中的中间元素提升到父节点即 2-node 节点中，使其父节点成为一个 3-node 节点，然后将左右节点分别挂在这个 3-node 节点的恰当位置。操作如下图：图图 2.52.5对于节点是 3-node，父节点也是 3-node，当我们插入的节点是 3-node 的时候，我们将该节点拆分，中间元素提升至父节点，但是此时父节点是一个 3-node 节点，插入之后，父节点变成了 4-node 节点，然后继续将中间元素提升至其父节点，直至遇到一个父节点是 2-no

15、de 节点，然后将其变为 3-node，不需要继续进行拆分。沈阳航空航天大学课程设计报告 - 7 -图图 2.62.6当根节点到字节点都是 3-node 节点的时候，这是如果我们要在字节点插入新的元素的时候，会一直查分到跟节点，在最后一步的时候，跟节点变成了一个 4-node 节点，这个时候，就需要将跟节点查分为两个 2-node 节点，树的高度加 1，这个操作过程如下：图图 2.72.7沈阳航空航天大学课程设计报告 - 8 -3 调试分析主要撰写在调试中遇到的典型问题及解决方法，可以按如下格式写。（1）键盘缓存区问题问题描述：在读入键盘输入的数字时，多次读入回车符，导致程序无找到应该插入的位

16、置，从而导致程序错误退出。问题分析：输入时没有清除键盘缓存区，在反复读取时容易产生问题。解决方法：每次输入数字之前加入一条清除键盘缓存区的指令。(2) 无法表示节点之间关系问题问题描述：用“， ”分隔节点非常混乱，不利于辨别层与层之间的关系问题分析：“， ”虽然有分隔的作用，但是没有包络的作用，无法完成层次的区分解决方法：改用“（） ”和“， ”沈阳航空航天大学课程设计报告 - 9 -4 测试及运行结果图图 4.14.1图图 4.24.2沈阳航空航天大学课程设计报告 - 10 -参考文献1 严蔚敏，吴伟民 . 数据结构（c 语言版）. 北京：清华大学出版社，19972 http:/ http:

17、/ http:/ 章节 2.3.3 中流程图来自 http:/ - 11 -附 录源程序文件名清单：iostream.h /标准输入输出流stack.h /栈操作的头文件源.cpp / 源代码源程序清单：#include #include using namespace std;typedef struct Tree23Node * Tree23;typedef struct Tree23Node int datal;int datar;Tree23 lchild, mchild, rchild; Tree23Node;#define INT_MAX 0 x3f3f3f3f沈阳航空航天大学课程

18、设计报告 - 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 & x t-datal)return 2;elsereturn 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

19、 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 & root-datal lchild = NULL &root-mchild = NULL & root-rchild = NULL)return true;return false;Tree23 findNode(Tree23 root, int key)

20、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)

21、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 an

22、d 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;Tr

23、ee23 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

24、currently in the tree. datar = INT_MAX) /* two sub node */put(&p, key, q);break;else /* three sub node */split(p, &key, &q);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_

25、MAX) cout ( datal , datar datal INT_MAX) cout ( datal ,) ;else cout (,) ;void inOrder(Tree23 T)if (T)visit(T);/coutlchild = 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

26、;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;

27、else/* two sub node */t-datal = INT_MAX;else/* delete second key */t-datar = INT_MAX;void leftRotate(Tree23 &p, Tree23 &q, Tree23 &r)p-datal = r-datal;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-

28、rchild = NULL;void leftCombine(Tree23 &p, Tree23 &q, Tree23 &r)p-datal = r-datal;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;elser-datal = r-datar;r-datar = INT_MAX;沈阳航空航天大学课程设计报告 - 24 -r

29、-mchild = r-rchild;r-rchild = NULL;void middleRotate(Tree23 &p, Tree23 &q, Tree23 &r)p-datal = r-datal;r-datal = q-datar;q-datar = INT_MAX;p-mchild = q-rchild;q-rchild = NULL;void middleCombine(Tree23 &p, Tree23 &q, Tree23 &r)q-datar = r-datal;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 &p, Tree23 &q, Tree23