数据结构b树的图书管理系统

数据结构b树的图书管理系统内容摘要：

pt, i, tag // 若查找成功，则特征值 tag = 1，指针 pt 所指结点中第 i个关键字等于 K； // 否则特征值 tag = 0，等于 K 的关键字应插入在指针 pt 所指结点中第 i和 // 第 i+1 个关键字之间 //顺序查找 // 在结点 pkey[1..keynum]中查找 ,返回 i： pkey[i] = key pkey[i+1] int Search(BTree amp。 p, KeyType key) { for (int i = 1。 i = pkeynum。 i++) { if (pkey[i] key) return i1。 } // for_i return pkeynum。 } // Search Result SearchBTree (BTree T, KeyType key) { BTree p = T, q = NULL。 bool flag = false。 int i = 0。 while (p amp。 amp。 !flag) { i = Search (p, key)。 if (i 0 amp。 amp。 pkey[i] == key) flag = true。 else { q = p。 p = pptr[i]。 } } // while return Result(flag ? p:q, i, flag)。 } // SearchBTree //2 B树插入操作 // 关键字插入的位置必定在最下层的非叶结点，有下列几种情况： // 1）插入后，该结点的关键字个数 nm，不修改指针。 // 2）插入后，该结点的关键字个数 n=m， 则需进行结点分裂， // 令 s = m+1/2，在原结点中保留 ( A0, K1, …… , Ks1, As1 )； // (备注：这里的 (m+1)/2 = (m+1) 1 和 m+1 除以 2 上取整同值可证 ) // 新建结点 (As,Ks+1,…… , Kn, An ).将 ( Ks, p ) 插入双亲结点。 // 3）若双亲为空，则建新的根结点。 // 在 m 阶 B树 T 上结点 *q 的 key[i]与 key[i+1]之间插入关键字 K // 若因起节点过大，则眼双亲链进行必要的节点分裂调整 ,保持 T 的特性 //插入操作 // 将 x和 ap 分别插入到 qkey[i+1]和 qptr[i+1] // 这里涉及到数组元素的移 动的问题，因为这里也是顺序结构表示键值。 // 要插入到 pkey[i+1]我们必须对 i+1 之后的数进行后移，这也是采用 // 顺序结构的弊端 ,但是由于顺序表很短，所以反而更高效。 void insert (BTree amp。 p, int i, KeyType x, BTree ap) { 华东交通大学 08 级软件工程（ 1）班 —— 张志福 6 for (int k = pkeynum + 1。 k i + 1。 k) { pkey[k] = pkey[k 1]。 pptr[k] = pptr[k 1]。 } // for_k pkey[i + 1] = x。 pptr[i + 1] = ap。 if (ap) apparent = p。 pkeynum++。 } // insert //分裂操作 // 将结点 p 分为两个部分 [1..s1]和 [s..m].同时更新每部分 // 这里我们要考虑两种情况， 2. 插入到父节点 void split (BTree amp。 p, int s, BTree amp。 ap) { ap = NULL。 ap = (BTNode *) malloc( sizeof(BTNode) )。 for (int i = s + 1, k = 0。 i = pkeynum。 i++) { apkey[++k] = pkey[i]。 apptr[k] = pptr[i]。 } // for_i apptr[0] = pptr[s]。 apkeynum = pkeynum s。 pkeynum = s 1。 apparent = pparent。 } // split //生成新根节点 // 这里要考虑两种情况： // T 是空树（参数 q 初值为 NULL) 或者 根节点已分配为节点 *q 和 *ap // 生成含有信息（ T,x, ap)的新的根节点 *T, 原 T 和 ap 为子树指针 void NewRoot (BTree amp。 T, BTree amp。 q, KeyType x, BTree amp。 ap) { T = NULL。 T = (BTNode *) malloc ( sizeof(BTNode) )。 for (int i = 0。 i = m。 i++) Tptr[i] = NULL。 Tkey[1] = x。 Tkeynum = 1。 Tparent = NULL。 Tptr[0] = q。 Tptr[1] = ap。 if (q != NULL) qparent = T。 if (ap != NULL) { apparent = T。 for (int j = 0。 j = apkeynum。 j++) { if (apptr[j]) apptr[j]parent = ap。 } // for_j } // if } // NewRoot void InsertBTree (BTree amp。 T, KeyType key, BTree q, int i) { KeyType x = key。 bool flag = false。 BTree ap = NULL, p = NULL。 while (q amp。 amp。 !flag) { insert (q, i, x, ap)。 if (qkeynum m) flag = true。 else { int s = (m + 1) 1。 split(q, s, ap)。 x = qkey[s]。 p = q。 q = qparent。 if (q) i = Search(q, x)。 } //else } // while if (!flag) NewRoot(T, p, x, ap)。 } // InserBTree 华东交通大学 08 级软件工程（ 1）班 —— 张志福 7 //B树的删除操作 /假若我们删除关键字为非终端节点中的 Ki,则可以指针 Ai 所指子树中的最小关键字 Y 代替 // Ki,然后在相应的结点中删去 Y. 下面我们讨论删除最下层非终端节点中的关键字的： // 1. 被删除的关键字所在节点中的关键字的数目不小于 (m+1)/ // 该关键字和相应的指针 Ai，树的其它部分不变 // 2. 被删除关键字所在节点中的关键字数目等于 (m+1)/21,而该节点相 邻的有兄弟 // 或左兄弟节点中的关键字的个数大于（ m+1)/2 1,则只需将其兄弟节点中最小（或最大） // 的关键字上移至双亲节点中，而将双亲节点中小于（或大于）且紧靠上移关键字的关键字 // 下移至被删除关键字所在的节点中。 // 3. 被删除关键字所在节点和其相邻的兄弟节点中的关键字数目均等与（ m+1)/ /设该节点有右兄弟，且其右兄弟节点地址有双亲节点中的指针 Ai。