记住哦，本站网址是：http://www.7139.com
梦幻网络
导航图标
您现在的位置： 梦幻网络 >> 技术学院 >> 程序设计 >> C C语言 >> 正文

B-

来源：互联网 收集：梦幻网络 本站网址：www.7139.com 点击数： 【字体：减小 增大】

12345678910
B-树//////////////////////////////////////////////////////////////////////////// File: b-tree.h// Date: 2005 / 07 / 10// Author: centaurus// Email: vim_user@126.com//////////////////////////////////////////////////////////////////////////#ifndef __BSubtractTree_H__#define __BSubtractTree_H__#include using namespace std;template class BSubtractTree{private://data: 0 1 2 ...// | | | |//child: 0 1 2 3 ... typedef struct TNode // 树结点，如上结构 { T *data; // 结点数据序列，假设增序排列 struct TNode **child; // 子结点指针数组 struct TNode *parent; // 父结点指针 int key_num; // 结点数据个数 }TNode; typedef struct Location // 查找关键字结果 { TNode *node; // 所在结点 int offset; // 所在结点数据偏移量 }Location;private: TNode *head; // 树头 int tnode_num; const int LIMIT; // 阶，结点数据最多个数 T *array; const int SIZE;private: // 得到一新结点 TNode *GetNode(); // 在指定结点p、结点数据偏移量*i处插入关键字 void Add(TNode *p, int *i, T key, TNode *new_node); // 自结点p、分割点partition以右的数据，分割出一新结点 void Split(TNode *p, int partition, TNode **new_node); // 修改head void NewRoot(T key, TNode *new_node); // 在结点数据序列中查找关键字 int SearchKey(TNode *p, T key); // 查找树结点 bool SearchNode(T key, Location *position); // 中序遍历显示树结点 void InOrder(TNode *n); // 先序遍历 void PreOrder(TNode *n);public: BSubtractTree(); BSubtractTree(T *a, int s, int l); // 在查找结果处插入关键字 void Insert(T key, Location *position); void InOrderShow(); void PreOrderShow(); void Delete(T key, Location *position); ~BSubtractTree();};#endif//////////////////////////////////////////////////////////////////////////// File: b-tree.h// Date: 2005 / 07 / 10// Author: centaurus// Email: vim_user@126.com//////////////////////////////////////////////////////////////////////////#ifndef __BSubtractTree_Fun_Def_H__#define __BSubtractTree_Fun_Def_H__#include "b-tree.h"template int BSubtractTree:: SearchKey(TNode *p, T key){ int i; if(key > p->data[p->key_num - 1]) // 关键字小于序列最小值 return p->key_num; else if(key data[0]) // 大于最大值 return 0; else if(key >= p->data[0] && key data[p->key_num - 1]) // 关键字在序列中 { for(i = 0; i key_num; i++) { if(key data[i]) // 返回等于或小于序列数据的下标 { break; } } } return i;}template bool BSubtractTree:: SearchNode(T key, Location *position){ TNode *p = head; TNode *pre = NULL; bool found = false; int i = 0; while(p && !found) { i = SearchKey(p, key); if(i > 0 && p->data[i] == key) found = true; else { pre = p; p = p->child[i]; } } if(found) // 找到返回true，offset指向该值下标 { position->node = p; position->offset = i; return true; } else // 未找到，offset指向第一个大于key的下标 { position->node = pre; position->offset = i; return false; }}template BSubtractTree:: TNode* BSubtractTree:: GetNode(){ int i; TNode *temp = new TNode; temp->parent = NULL; temp->key_num = 0; temp->data = new T [LIMIT]; for(i = 0; i data[i] = 0; } temp->child = new TNode* [LIMIT + 1]; for(i = 0; i child[i] = NULL; } tnode_num++; return temp;}template void BSubtractTree:: Add(TNode *p, int *i, T key, TNode *new_node){ int _i; for(_i = p->key_num; _i > *i; _i--) // 将数据序列*i及其以后数值向后挪一位 { p->data[_i] = p->data[_i - 1]; } p->data[_i] = key; // 在*i位插入关键字 for(_i = p->key_num + 1; _i > *i + 1; _i--) // 挪动child指针数组 { p->child[_i] = p->child[_i - 1]; } p->child[_i] = new_node; // 插入子结点，子结点为NULL或分割结点 p->key_num++; if(new_node) new_node->parent = p;}template void BSubtractTree:: Split(TNode *p, int partition, TNode **new_node){ *new_node = GetNode(); // 存放新结点地址 int _i; int j = 0; int m = p->key_num; for(_i = partition + 1; _i data[j++] = p->data[_i]; (*new_node)->key_num++; p->data[_i] = 0; p->key_num--; } j = 0; for(_i = partition + 1; _i child[j] = p->child[_i]; if(p->child[_i]) (*new_node)->child[j]->parent = *new_node; p->child[_i] = NULL; j++; }}template void BSubtractTree:: NewRoot(T key, TNode *new_node){ TNode *temp = GetNode(); temp->data[0] = key; temp->key_num = 1; temp->child[0] = head; temp->child[1] = new_node; if(head) head->parent = temp; if(new_node) new_node->parent = temp; head = temp;}template void BSubtractTree:: Insert(T key, Location *position){ TNode *p = position->node; int i = position->offset; T k = key; int partition; TNode *new_node = NULL; bool condition = false; while(p && !condition) { Add(p, &i, k, new_node); if(p->key_num data[partition]; p->data[partition] = 0; p->key_num--; p = p->parent; if(p) i = SearchKey(p, k); } } if(!condition) // 为空树或将树头结点进行了分割 NewRoot(k, new_node);}template BSubtractTree:: BSubtractTree() : SIZE(0), LIMIT(0){ head = NULL; tnode_num = 0; array = NULL;}template BSubtractTree:: BSubtractTree(T *a, int s, int l) : SIZE(s), LIMIT(l){ head = NULL; tnode_num = 0; int i; Location position; array = new T [SIZE]; for(i = 0; i < SIZE; i++) { array[i] = a[i]; } for(i = 0; i < SIZE; i++) { if(!SearchNode(array[i], &position)) // 查找关键字失败则插入关键字 { Insert(array[i], &position); } }}template void BSubtractTree:: Delete(T key, Location *position){}template BSubtractTree:: ~BSubtractTree(){ Location position; for(int i = 0; i < SIZE; i++) { if(SearchNode(array[i], &position)) { Delete(array[i], &position); } }}template void BSubtractTree:: InOrder(TNode *n){ if(n) { int i; for(i = 0; i key_num + 1; i++) { InOrder(n->child[i]); if(i key_num) cout child[i]); } }}template void BSubtractTree:: InOrderShow(){ cout << "InOrder List : " << endl; InOrder(head);}template void BSubtractTree:: PreOrderShow(){ cout << "PreOrder List : " << endl; PreOrder(head);}#endif//////////////////////////////////////////////////////////////////////////// File: b-tree.h// Date: 2005 / 07 / 10// Author: centaurus// Email: vim_user@126.com//////////////////////////////////////////////////////////////////////////#include using namespace std;#include "b-tree_fun_def.cpp"void main(){ int a[10] = ; BSubtractTree test(a, 10, 3); test.InOrderShow(); //test.PreOrderShow();}（完）计算机基础教程网


Google
【更新时间：2006-7-12 17:41:03】【打印此文】【关闭窗口】
  • 上一篇教程：
  • 下一篇教程：
    • 搜索