《按照算法导论中伪代码转化》由会员分享，可在线阅读，更多相关《按照算法导论中伪代码转化（9页珍藏版）》请在金锄头文库上搜索。
1、按照算法导论中伪代码转化，其中删除过程算法导论没有给出伪代码，所以对删除相关函数做了说明。另外B-Tree本来是用于硬盘的，但为了简便只阐明B-Tree的基本流程，没有加入硬盘扇区的直接读写操作，全部在内存中进行。1.头文件（B-Tree.h）#ifndef BTREE_JOHN_DMRC#define BTREE_JOHN_DMRC/* Class BTreeNode */template class BTreeNodepublic:BTreeNode(int, bool);BTreeNode();/ Variesint t;int len;bool leaf;T* key;BTreeNod
2、e* child;/* Class BTree template class BTreepublic:BTree(int);BTree();bool BTree_Search(T);void BTree_Insert(T);bool BTree_Delete(T);/ debug startvoid print_root();/ debug endprivate:bool btree_search(BTreeNode*, T);void delete_tree(BTreeNode*);void btree_split_child(BTreeNode*, int, BTreeNode*);voi
3、d btree_insert_nonfull(BTreeNode*, T);void btree_merge_child(BTreeNode*, int);void btree_rotate_child(BTreeNode*, int, bool);bool btree_delete_nonfew(BTreeNode*, T);BTreeNode* root;int t;#endif2 cpp文件（B-Tree.cpp）#include B-Tree.h/* Class BTreeNode /template BTreeNode:BTreeNode(int a, bool b)this -t
4、= a;this -len = 0;this -leaf = b;this -key = new int2 * a - 1;this -child = new BTreeNode*2 * a;template BTreeNode:BTreeNode()delete this -key;delete this -child;/* Class BTree / C & Dtemplate BTree:BTree(int a)this -t = a;this -root = new BTreeNode(a, true);template BTree:BTree()this -delete_tree(t
5、his -root);template void BTree:delete_tree(BTreeNode* p)if(!p -leaf)for(int i = 0; i len + 1; i +)this -delete_tree(p -childi);delete p;/ Searchtemplate bool BTree:BTree_Search(T k)return this -btree_search(this -root, k);template bool BTree:btree_search(BTreeNode* x, T k)int i;if(x -leaf)for(i = 0;
6、 i len; i +)if(x -keyi = k)return true;return false;elsefor(i = 0; i len; i +)if(x -keyi k)break;return this -btree_search(x -childi, k);/ Insert seriestemplate void BTree:BTree_Insert(T k)BTreeNode* r = this -root;if(this -root -len = 2 * this -t - 1)BTreeNode* s = new BTreeNode(this -t, false);thi
7、s -root = s;s -child0 = r;this -btree_split_child(s, 0, r);this -btree_insert_nonfull(s, k);elsethis -btree_insert_nonfull(r, k);template void BTree:btree_split_child(BTreeNode* x, int i, BTreeNode* y)BTreeNode* z = new BTreeNode(this -t, y -leaf);int j;z -len = this -t - 1;for(j = 0; j keyj = y -ke
8、ythis -t + j;if(!y -leaf)for(j = 0; j childj = y -childthis - t + j;y -len = this -t - 1;for(j = x -len; j i + 1; j -)x -childj + 1 = x -childj;x -childi + 1 = z;for(j = x -len - 1; j i; j -)x -keyj + 1 = x -keyj;x -keyi = y -keythis -t - 1;x -len +;template void BTree:btree_insert_nonfull(BTreeNode
9、* x, T k)int i = x -len;if(x -leaf)while(i 0 & k keyi - 1)x -keyi = x -keyi - 1;i -;x -keyi = k;x -len +;elsewhile(i 0 & k keyi - 1)i -;if(x -childi -len = 2 * this -t - 1)this -btree_split_child(x, i , x -childi);if(k x -keyi)i +;this -btree_insert_nonfull(x -childi, k);/ Delete seriestemplate bool
10、 BTree:BTree_Delete(T k)BTreeNode* p = this -root;if(this -root -len = 1 & !this -root -leaf& this -root -child0 -len = this -t - 1& this -root -child1 -len = this -t - 1)this -btree_merge_child(this -root, 0);this -root = this -root -child0;delete p;return this -btree_delete_nonfew(this -root, k);r
11、eturn this -btree_delete_nonfew(p, k);/* FUNCTION: btree_merge_child() * x : point to the parent* i : merge child(i) and child(i+1) of x into child(i)*/template void BTree:btree_merge_child(BTreeNode* x, int i)int j;BTreeNode* y = x -childi;BTreeNode* z = x -childi + 1;/ assert deleteif(y -len != this -t - 1 | z -len != this -t - 1)printf(Error delete!n);exit(0);y -len = this -t * 2 - 1; for(j = 0; j t - 1; j +)y -keythis -t + j = z -keyj;y -keythis -t - 1 = x -keyi;if(!z -leaf)for(j = 0; j t; j +)y -childthis -t + j = z -childj;for(
