数据结构课程设计实验报告-图书管理

数据结构课程设计实验报告-图书管理内容摘要：

字个数 struct BTNode *parent。 //父亲指针 KeyType key[m+1]。 //关键字数组， 0 号单元未用 struct BTNode *ptr[m+1]。 //子数指针 Record *rec[m+1]。 //记录指针， 0 号单元未用 }BTNode,*BTree。 //B 树节点类型和 B 树类型 typedef struct { BTNode *pt。 //指向找到的结点或应该插入的结点 int i。 //关键字序号 int tag。 //1 表示查找成功， 0 表示查找失败 }Result。 //B 树查找结果类型 B 树基本操作 ： Reselt SearchBTree(BTree T,KeyType k) //在 m 阶 B 树上查找关键字 k，返回结果（ pt， i， tag）。 若查找成功，则特征值 tag=1，指针 pt //所指结点中第 i个关键字等于 k；否则返回特征值 tag=0，等于 k 的关键字应插入在 pt 所指结点 //中第 i和第 i+1 个关键字之间。 Status InsertBTree(BTree amp。 T, KeyType k, BTree q, int i,Record *rec) //在 m 阶 B 树 T 上结点 *q 的 key[i]与 key[i+1]之间插入关键字 k，和记录 rec //若引起结点过大，则沿着双亲链进行必要的结点分裂调整，使 T 仍是 m 阶 B 树 Status DeleteBTree(BTree amp。 T,KeyType k) //在 m 阶 B 树 T 上删除关键字 k 及其对应记录，并返回 OK //如 T 上不存在关键字 k，则返回 ERROR void BTreeTraverse(BTree T,void (*Visi)t(BTree p)) //遍历 B 树 T，对每个结点调用 Visit 函数 void ShowBTree(BTree T,short x = 8) //递归以凹入表形式显示 B 树 T,每层的缩进量为 x，初始缩进量为 x=8 B 树的 基本 操作伪代码： Result SearchBTree(BTree T, KeyType k) //在 m 阶 B 树上查找关键字 k，返回结果（ pt， i， tag）。 若查找成功，则特征值 tag=1，指针 pt //所指结点中第 i个关键字等于 k；否则返回特征值 tag=0，等于 k 的关键字应插入在 pt 所指结点 //中第 i和第 i+1 个关键字之间。 { p = T, q = NULL。 //初始化， p 指向待查结点， q 指向 p 的双亲 found = FALSE。 3681bd1c2b9ef87aa40ba80437378615 第 9 页 共 31 页 while(p amp。 amp。 !found) { i = Search(p, k)。 //查找 k 的位置使 pkey[i]=kpkey[i+1] if(i 0 amp。 amp。 k == pkey[i]) found = TRUE。 else{ //未找到，则查找下一层 q = p。 p = pptr[i]。 } } if(found) return {p, i, 1}。 //查找成功 else return {q, i, 0}。 //查找不成功，返回 k 的插入位置信息 } Status InsertBTree(BTree amp。 T, KeyType k, BTree q, int i,Record *rec) //在 m 阶 B 树 T 上结点 *q 的 key[i]与 key[i+1]之间插入关键字 k，和记录 rec //若引起结点过大，则沿着双亲链进行必要的结点分裂调整，使 T 仍是 m 阶 B 树 { ap = NULL。 finished = FALSE。 if (!q) NewRoot(T, NULL, k, NULL,rec)。 //T 是空树，生成仅含关键字 K 的根结点 *T else{ while (!finished) { Insert(q, i, k, ap,rec)。 //将 k 和 ap 分别插入到 qkey[i+1]和 qptr[i+1] if (qkeynum m) finished = TRUE。 //插入完成 else{ Split(q, (m+1)/2, ap)。 //分裂结点 Q k = qkey[(m+1)/2]。 rec = qrec[(m+1)/2]。 if (qparent) { // 在双亲结点 *q 中查找 k 的插入位置 q = qparent。 i = Search(q, k)。 } else finished = OVERFLOW。 //根节点已分裂为 *q 和 *ap 两个结点 } } if (finished == OVERFLOW) //根结点已分裂为结点 *q 和 *ap NewRoot(T, q, k, ap,rec)。 //需生成新根结点 *T,q 和 ap 为子树指针 } return OK。 } StatusDeleteBTree(BTree amp。 T,KeyType k) //在 m 阶 B 树 T 上删除关键字 k 及其对应记录，并返回 OK //如 T 上不存在关键字 k，则返回 ERROR { 3681bd1c2b9ef87aa40ba80437378615 第 10 页 共 31 页 q,b = NULL。 finished = FALSE,i = 1。 Result res = SearchBTree(T,k)。 //在 T 中查找关键字 k if( == 0 ) return ERROR。 //未搜索到 else { q =。 //q 指向待删结点 i =。 if(qptr[0]) TakePlace(q, i)。 //若 q 的子树不空， (非底层结点 ) //则以其后继代之，且令 q 指向后继所在结点 Del(q,i)。 //删除 q 所指向结点中第 i个关键字及记录 if(qkeynum=(m1)/2||!qparent) //若删除后关键字个数不小于 (m1)/2 或 q 是根节点 { finished = TRUE。 //删除完成 if(qkeynum == 0 ) T = NULL。 //若 q 的关键字个数为 0 ，则为空树 } while(!finished) { if(Borrow(q)) finished = TRUE。 //若 q 的相邻兄弟结点关键字大于 (m1)/2,则从该 //兄弟结点上移一个最大（或最小）关键字到 //父节点，从父节点借一关键字到 q else{ //若 q 相邻兄弟关键字个数均等于┌ m /2┑ 1 Combine(q)。 //将 q 中的剩余部分和双亲中的相关关键字合并至 q 的一个兄弟中 q = qparent。 //检查双亲 if(q == T amp。 amp。 Tkeynum ==0 ) //若被删结点的父节点是根 T 且 T 的关键字个数为 0 { T = Tptr[0]。 //新根 Tparent = NULL。 free(q)。 //删除原双亲结点 finished = TRUE。 } else if(qkeynum = m/2) finished = TRUE。 } //合并后双亲关键字个数不少于 (m1)/2，完成 } } return OK。 } void BTreeTraverse(BTree T,void ( *Visit)(BTree p)) //遍历 B 树 T，对每个结点调用 Visit 函数 { if(!T) return。 Visit(T)。 for(i = 0。 i = Tkeynum。 i++) //递归遍历子树结点 if(Tptr[i]) BTreeTraverse(Tptr[i],Visit)。 } 3681bd1c2b9ef87aa40ba80437378615 第 11 页 共 31 页 void ShowBTree(BTree T,short x = 8) //递归以凹入表形式显示 B 树 T,每层的缩进量为 x，初始缩进量为 x=8 { if(!T) return。 for(i = 0。 i=x。 i++) putchar(39。 39。 )。 //缩进 x for(i = 1。 i = Tkeynum。 i++) printf(%d,Tkey[i])。 for(i = 0。 i = Tkeynum。 i++) //递归显示子树结点关键字 ShowBTree(Tptr[i],x+7)。 } 4. 主函数和其他函数的伪码算法 int main() { RecordLogs(0)。 //记录日志 进入系统 显示欢迎界面 InitLibrary(L)。 //初始化书库 L while(1) { 显示菜单； 1 新书入库， 2 清除库存， 3 图书出借 4 图书归还 5 图书预约， 6 列出著者著作 7 查看图书状态 8 遍历书库， 9 退出系统 cmd = getch()。