实验名称：数据结构与算法题 目：平衡二叉树学生信息管理系统院 系：光电学院班 级：网络学 号：学生姓名：何俊扬指导教师：邓桂英设计周数：成 绩：日 期：
上海理工大学
课程设计报告
( 2011—2012年度第2学期)
01 1212470833 2周
2014 年 7 月 18 日
一、课程设计的目的与要求
(一)．目的: 应用数据结构和算法来设计相应的程序，培养学生问题求解模块的框 架设计和详细设计、相关程序实现
和调试能力，完成创新能力和实践能力的训练。
(二). 要求: 用高级程序设计语言C编码，用VC++开发平台调试。
二、设计正文
（一）、课程设计题目
用二叉平衡树实现学生基本信息管理，功能如下：
1:插入 2:前序遍历 3:层次遍历 4:查找 5:统计 6.排序 7.删除 8.退出 要求：基本信息包括（姓名，学号，宿舍，科目，成绩）
（二）、需求分析
本演示程序在DOS环境用C语言编写，完成平衡二叉树的生成，插入、删除，查找，显示，排序。
1） 输入的形式和输入值的范围：插入元素时需要输入插入元素的基本信息； 删除元素时输入删除元素的关键字学号；查找操作时需要输入元素的姓名。在所有输入中，元素的值都是字符型数组。
2）输出的形式：在所有操作中都显示操作的结果。其中删除操作后显示删除的元素的值，查找操作后显示根据关键字查得的学生基本信息。
3）程序所能达到的功能：完成单平衡二叉树的创建（通过插入操作）、插入、 删除、查找，显示等操作。 4） 测试数据：
1. 创建3个学生信息
605 1212470520 aaa 数据结构 90 大英 85 606 1212470521 bbb 大英 85 607 1212470525 ccc 高数 703
2. 删除1个学生信息输入 1212470521则删除该结点信息 3. 查找学生信息 输入1212470520 则显示该生基本信息
（三）、概要设计
1）本程序主要包含9个函数：
1. 主函数 main( )
2. 创建二叉树函数 createtree( ) 3. 创建分数函数 createscore( ) 4. 创建姓名函数 createname( ) 5. 查找函数 search( ) 6. 统计函数 total( ) 7. 删除结点函数 del( ) 8. 排序函数 paixu( ) 9. 插入函数 add( )
2）程序调用示意图如下：
（四）、详细设计
1． 二叉平衡树的遍历
二叉平衡树的显示，查找，结点信息修改，保存等操作均基于二叉平衡树的遍历操作，代码如下 int level1(bitree t,int b) { bitree p=t; bitree y[10]; linklist1 q; linklist2 r; int front,rear; front=rear=0; y[rear]=t; rear=(rear+1)%10; while(front!=rear) { p=y[front]; front=(front+1)%10; if(p!=NULL)
{ q=p->head; while(q!=NULL&&b!=q->num) q=q->next; if(q!=NULL) { printf(\"宿舍号:%d 姓名:%s\\n\ r=q->head; while(r!=NULL) { printf(\"科目:%s,学期:%d,成绩:%d\\n\ r=r->next; } return 0; } } if(p->lchild!=NULL) { y[rear]=p->lchild; rear=(rear+1)%10; } if(p->rchild!=NULL) { y[rear]=p->rchild; rear=(rear+1)%10; } } return 1; }
int level2(bitree t,char *c) { bitree p=t; bitree y[10]; linklist1 q; linklist2 r; int front,rear; front=rear=0; y[rear]=t; rear=(rear+1)%10; while(front!=rear) { p=y[front]; front=(front+1)%10; if(p!=NULL) { q=p->head; while(q!=NULL&&(strcmp(c,q->name)!=0)) q=q->next; if(q!=NULL) {
printf(\"宿舍号:%d 学号:%d\\n\ r=q->head; while(r!=NULL) { printf(\"科目:%s,学期:%d,成绩:%d\\n\ r=r->next; } return 0; } } if(p->lchild!=NULL) { y[rear]=p->lchild; rear=(rear+1)%10; } if(p->rchild!=NULL) { y[rear]=p->rchild; rear=(rear+1)%10; } } return 1; }
void preorder(bitree t) { bitree p=t; linklist1 q; linklist2 r; if(p!=NULL) { printf(\"宿舍号:%d\\n\ q=p->head; while(q!=NULL) { printf(\"学号:%d,姓名:%s\\n\ r=q->head; while(r!=NULL) { printf(\"科目:%s,学期:%d,成绩:%d\\n\ r=r->next; } q=q->next; } preorder(p->lchild); preorder(p->rchild); } }
void level(bitree t) {
printf(\"层次序输出为:\\n\"); bitree x[10],p=t; linklist1 q; linklist2 r; int front,rear; front=rear=0; x[rear]=t; rear=(rear+1)%10; while(front!=rear) { p=x[front]; front=(front+1)%10; printf(\"宿舍号:%d\\n\ q=p->head; while(q!=NULL) { printf(\"学号:%d,姓名:%s\\n\ r=q->head; while(r!=NULL) { printf(\"科目:%s,学期:%d,成绩:%d\\n\ r=r->next; } q=q->next; } if(p->lchild!=NULL) { x[rear]=p->lchild; rear=(rear+1)%10; } if(p->rchild!=NULL) { x[rear]=p->rchild; rear=(rear+1)%10; } } }
2． 二叉平衡树的插入操作代码 void createtree(bitree &t) { int a; bitree p,f=NULL; p=t; printf(\"请输入需要插入的宿舍号:\"); scanf(\"%d\ while(p!=NULL&&p->rnum!=a) { f=p; if(a>p->rnum) p=p->rchild; else
p=p->lchild; } if(p==NULL) { p=(bitree)malloc(sizeof(tnode)); p->rnum=a; p->lchild=p->rchild=NULL; p->head=NULL; } if(t==NULL) t=p; if(f!=NULL) { if(a>f->rnum) f->rchild=p; else f->lchild=p; } printf(\"插入完毕\\n\"); }
void createname(bitree &t) { int a; bitree p=t; printf(\"请输入学生所在宿舍号:\"); scanf(\"%d\ while(p!=NULL&&p->rnum!=a) { if(a>p->rnum) p=p->rchild; else p=p->lchild; } if(p==NULL) printf(\"不存在此宿舍号\\n\"); else { linklist1 q; q=(linklist1)malloc(sizeof(lnode1)); printf(\"请输入学生的学号:\"); scanf(\"%d\ printf(\"请输入学生的姓名:\"); scanf(\"%s\ q->head=NULL; q->next=p->head; p->head=q; printf(\"插入完毕\\n\"); } }
void createscore(bitree &t) { int a; bitree p=t; printf(\"请输入学生所在宿舍号:\"); scanf(\"%d\ while(p!=NULL&&p->rnum!=a) { if(a>p->rnum) p=p->rchild; else p=p->lchild; } if(p==NULL) printf(\"不存在此宿舍号\\n\"); else { int b; char c[10]; linklist1 q; printf(\"请输入学生的学号和姓名:\"); scanf(\"%d%s\ q=p->head; while(q!=NULL) { if(b==q->num&&(strcmp(c,q->name)==0)) { linklist2 r; r=(linklist2)malloc(sizeof(lnode2)); printf(\"请输入该学生的科目:\"); scanf(\"%s\ printf(\"请输入该学期:\"); scanf(\"%d\ printf(\"请输入该科目的成绩:\"); scanf(\"%d\ r->next=q->head; q->head=r; printf(\"插入完毕\\n\"); break; } q=q->next; } if(q==NULL) printf(\"无此学生\\n\"); } }
3． 二叉平衡树的删除操作代码 void del(bitree &t) { int a,b,front,rear,z,o; bitree p1=t,p2=t,p3,x[10],s; linklist1 q1,q2,q; linklist2 r1,r2; char c[10]; printf(\"1:删除宿舍节点 2:删除学生节点 3:删除成绩节点\\n\"); scanf(\"%d\ switch(a) { case 1: printf(\"请输入删除宿舍号:\"); scanf(\"%d\ z=1; while(p1!=NULL) { if(p1->rnum>b) { p2=p1; p1=p1->lchild; } else if(p1->rnum p2->rchild=p1->rchild; free(p1); z=0; break; } else { p2->lchild=p1->rchild; free(p1); z=0; break; } } else if(p1->lchild!=NULL&&p1->rchild==NULL) { if(p1->rnum>p2->rnum) { p2->rchild=p1->lchild; free(p1); z=0; break; } else { p2->lchild=p1->lchild; free(p1); z=0; break; } } else if(p1->lchild!=NULL&&p1->rchild!=NULL) { if(p1->rnum>p2->rnum) { p2->rchild=p1->lchild; p3=p1->lchild; while(p3->rchild!=NULL) p3=p3->rchild; p3->rchild=p1->rchild; free(p1); z=0; break; } else { p2->lchild=p1->lchild; p3=p1->lchild; while(p3->rchild!=NULL) p3=p3->rchild; p3->rchild=p1->rchild; free(p1); z=0; break; } } } } if(z==1) printf(\"无此宿舍\\n\"); if(z==0) printf(\"删除完毕\\n\"); break; case 2: printf(\"请输入删除学生的学号和姓名:\"); scanf(\"%d%s\ z=1; rear=front=0; x[rear]=t; rear=(rear+1)%10; while(front!=rear) { p1=x[front]; front=(front+1)%10; q1=p1->head; while(q1!=NULL) { if(q1->num==b&&(strcmp(c,q1->name)==0)) { if(q1==p1->head) { p1->head=q1->next; free(q1); z=0; break; } else { q2->next=q1->next; free(q1); z=0; break; } } q2=q1; q1=q1->next; } if(p1->lchild!=NULL) { x[rear]=p1->lchild; rear=(rear+1)%10; } if(p1->rchild!=NULL) { x[rear]=p1->rchild; rear=(rear+1)%10; } } if(z==0) printf(\"删除完毕\\n\"); if(z==1) printf(\"无此学生\\n\"); break; case 3: printf(\"请输入删除成绩的学生的学号和姓名:\"); scanf(\"%d%s\ rear=front=0; z=1; o=1; x[rear]=t; rear=(rear+1)%10; while(front!=rear) { p1=x[front]; front=(front+1)%10; q=p1->head; while(q!=NULL) { if(q->num==b&&(strcmp(c,q->name)==0)) { o=0; r1=q->head; printf(\"请输入删除成绩的科目和学期:\"); scanf(\"%s%d\ while(r1!=NULL) { if(r1->term==b&&(strcmp(r1->subject,c)==0)) { if(r1==q->head) { q->head=r1->next; free(r1); z=0; break; } else { r2->next=r1->next; free(r1); z=0; break; } } r2=r1; r1=r1->next; } } } q=q->next; } if(p1->lchild!=NULL) { x[rear]=p1->lchild; rear=(rear+1)%10; } if(p1->rchild!=NULL) { x[rear]=p1->rchild; rear=(rear+1)%10; } } if(o==1) printf(\"无此学生\\n\"); if(o==0&&z==1) printf(\"无此科目\\n\"); if(o==0&&z==0) printf(\"删除完毕\\n\"); break; } （五）、使用说明 程序名为 学生基本信息管理.exe，运行环境为DOS。程序执行后显示 ***********平衡二叉树实现学生基本信息管理*********** **************************************************** 1:插入 2:前序遍历 3:层次遍历 4:查找 5:统计 6.排序 7.删除 8.退出 输入操作选项(0--8)\\n\") （七）、测试结果 1） 选择2重新创建学生信息，则得到以下菜单 2） 插入：选择1输入宿舍信息信息 3） 查找：选择4输入1212470520则显示其基本信息 4） 前序输出： 5） 层序输出： 6） 排序 7） 查找： 8） 删除： 三、课程设计总结或结论 通过课程设计，用平衡二叉树实现了学生基本信息管理，实现的基本功能主要包括平衡二叉树的创建，插入新的结点，删除结点，根据结点关键字查询结点信息，修改结点信息，平衡二叉树的层序遍历和前序遍历。 四、参考文献 程序借鉴于杨杰同学 部分资料参考百度 手工题 一、基本概念 B-树又称为多路平衡查找树。 一棵度为m的B-树称为m阶B_树。一个结点有k个孩子时，必有k-1个关键字才能将子树中所有关键字划分为k个子集。B-树中所有结点的孩子结点最大值称为B-树的阶，通常用m表示。从查找效率考虑，一般要求m≥3。一棵m阶的B-树或者是一棵空树，或者是满足下列要求的m叉树： （1）根结点或者为叶子，或者至少有两棵子树，至多有m棵子树。 （2）除根结点外，所有非终端结点至少有ceil(m/2)棵子树，至多有m棵子树。 （3）所有叶子结点都在树的同一层上。 （4）每个结点的结构为： （n，A0，K1，A1，K2，A2，„ ，Kn，An） 其中，Ki(1≤i≤n)为关键字，且Ki n为结点中关键字的个数，满足ceil(m/2)-1≤n≤m-1。 比如，一棵3阶B-树，m=3。它满足： （1）每个结点的孩子个数小于等于3。 （2）除根结点外，其他结点至少有=2个孩子。 （3）根结点有两个孩子结点。 （4）除根结点外的所有结点的n大于等于=1，小于等于2。 （5）所有叶结点都在同一层上。 二、B-树查找的算法思想 1、B-树的查找 B-树的查找过程：根据给定值查找结点和在结点的关键字中进行查找交叉进行。首先从根结点开始重复如下过程： 若比结点的第一个关键字小，则查找在该结点第一个指针指向的结点进行；若等于结点中某个关键字，则查找成功；若在两个关键字之间，则查找在它们之间的指针指向的结点进行；若比该结点所有关键字大，则查找在该结点最后一个指针指向的结点进行；若查找已经到达某个叶结点，则说明给定值对应的数据记录不存在，查找失败。 2. B-树的插入 插入的过程分两步完成： （1）利用前述的B-树的查找算法查找关键字的插入位置。若找到，则说明该关键字已经存在，直接返回。否则查找操作必失败于某个最低层的非终端结点上。 （2）判断该结点是否还有空位置。即判断该结点的关键字总数是否满足n<=m-1。若满足，则说明该结点还有空位置，直接把关键字k插入到该结点的合适位置上。若不满足，说明该结点己没有空位置，需要把结点分裂成两个。 分裂的方法是：生成一新结点。把原结点上的关键字和k按升序排序后，从中间位置把关键字（不包括中间位置的关键字）分成两部分。左部分所含关键字放在旧结点中，右部分所含关键字放在新结点中，中间位置的关键字连同新结点的存储位置插入到父结点中。如果父结点的关键字个数也超过（m-1），则要再分裂，再往上插。直至这个过程传到根结点为止。 3、B-树的删除 在B-树上删除关键字k的过程分两步完成： （1）利用前述的B-树的查找算法找出该关键字所在的结点。然后根据 k所在结点是否为叶子结点有不同的处理方法。 （2）若该结点为非叶结点，且被删关键字为该结点中第i个关键字key[i]，则可从指针son[i]所指的子树中找出最小关键字Y，代替key[i]的位置，然后在叶结点中删去Y。 因此，把在非叶结点删除关键字k的问题就变成了删除叶子结点中的关键字的问题了。 在B-树叶结点上删除一个关键字的方法是 首先将要删除的关键字 k直接从该叶子结点中删除。然后根据不同情况分别作相应的处理，共有三种可能情况： （1）如果被删关键字所在结点的原关键字个数n>=ceil(m/2)，说明删去该关键字后该结点仍满足B-树的定义。这种情况最为简单，只需从该结点中直接删去关键字即可。 （2）如果被删关键字所在结点的关键字个数n等于ceil(m/2)-1，说明删去该关键字后该结点将不满足B-树的定义，需要调整。 调整过程为：如果其左右兄弟结点中有“多余”的关键字,即与该结点相邻的右（左）兄弟结点中的关键字数目大于ceil(m/2)-1。则可将右（左）兄弟结点中最小（大）关键字上移至双亲结点。而将双亲结点中小（大）于该上移关键字的关键字下移至被删关键字所在结点中。 （3）如果左右兄弟结点中没有“多余”的关键字，即与该结点相邻的右（左）兄弟结点中的关键字数目均等于ceil(m/2)-1。这种情况比较复杂。需把要删除关键字的结点与其左（或右）兄弟结点以及双亲结点中分割二者的关键字合并成一个结点,即在删除关键字后，该结点中剩余的关键字加指针，加上双亲结点中的关键字Ki一起，合并到Ai（是双亲结点指向该删除关键字结点的左（右）兄弟结点的指针）所指的兄弟结点中去。如果因此使双亲结点中关键字个数小于ceil(m/2)-1，则对此双亲结点做同样处理。以致于可能直到对根结点做这样的处理而使整个树减少一层。 总之，设所删关键字为非终端结点中的Ki，则可以指针Ai所指子树中的最小关键字Y代替Ki，然后在相应结点中删除Y。对任意关键字的删除都可以转化为对最下层关键字的删除。 如图示： a、被删关键字Ki所在结点的关键字数目不小于ceil(m/2)，则只需从结点中删除Ki和相应指针Ai，树的其它部分不变。 b、被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。调整过程如上面所述。 c、被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，假设该结点有右兄弟，且其右兄弟结点地址由其双亲结点指针Ai所指。则在删除关键字之后，它所在结点的剩余关键字和指针，加上双亲结点中的关键字Ki一起，合并到Ai所指兄弟结点中（若无右兄弟，则合并到左兄弟结点中）。如果因此使双亲结点中的关键字数目少于ceil(m/2)-1，则依次类推。 三、B-树的C语言描述 1、存储结构 2、插入 3、查找 四、B-树的C语言实现 #include \"stdio.h\" #include \"stdlib.h\" #include \"math.h\" #define OK 1 #define ERROR -1 #define m 3 //3阶树 #define N 16 //数据元素个数 #define MAX 5 //字符串最大长度＋1 typedef int KeyType; struct Others //记录的其它部分 { char info[MAX]; }; struct Record { KeyType key; //关键字 Others others; //其它部分 }; typedef struct BTNode { int keynum; //结点中关键字个数 BTNode *parent;//指向双亲节点 struct Node //结点向量类型 { KeyType key; //关键字向量 BTNode *ptr;//子树指针向量 Record *recptr; //记录向量指针 }node[m+1]; //key,recptr的0号单元未用 }BTNode,*BTree; struct Result //B树的查找结果类型 { BTNode *pt; //指向找到的结点 int i; //在节点中关键字序号，1...m int tag; //1表示查找成功，0表示查找失败。 }; int InitDSTable(BTree &DT) { DT=NULL; return OK; }//InitDSTable void DestroyDSTable(BTree &DT) { int i; if(DT) //非空树 { for(i=0;i<=DT->keynum;i++) DestroyDSTable(DT->node[i].ptr); free(DT); DT=NULL; }//if }//DestroyDSTable int Search(BTree p,KeyType K) {//在p->node[1...keytype].key中查找i,使得p->node[i].key<=K< //p->node[i+1].key int i=0,j; for(j=1;j<=p->keynum;j++) if(p->node[j].key<=K) i=j; return i; }//Search void Insert(BTree &q,int i,Record *r,BTree ap) {//将r->key、r和ap分别插入到q->key[i+1]、 //q->recptr[ i+1]和q->ptr[i+1]中 int j; for(j=q->keynum;j>i;j--) //空出q->node[i+1] q->node[j+1]=q->node[j]; q->node[i+1].key=r->key; q->node[i+1].ptr=ap; //前加入的结点，还没有儿子结点 q->node[i+1].recptr=r; q->keynum++; }//Insert void NewRoot(BTree &T,Record *r,BTree ap) {// 生成含信息(T,r,ap)的新的根结点*T，原T和ap为子树指针 BTree p; p=(BTree)malloc(sizeof(BTNode)); p->node[0].ptr=T; T=p; if(T->node[0].ptr) T->node[0].ptr->parent=T; T->parent=NULL; T->keynum=1; T->node[1].key=r->key; T->node[1].recptr=r; T->node[1].ptr=ap; if(T->node[1].ptr) T->node[1].ptr->parent=T; }//NewRoot void split(BTree &q,BTree &ap) {// 将结点q分裂成两个结点，前一半保留，后一半移入新生结点ap int i,s=(m+1)/2; ap=(BTree)malloc(sizeof(BTNode));//生成新结点ap ap->node[0].ptr=q->node[s].ptr;//原来结点中间位置关键字相应指针指向的子树放到 //新生成结点的0棵子树中去 for(i=s+1;i<=m;i++) //后一半移入ap { ap->node[i-s]=q->node[i]; if(ap->node[i-s].ptr) ap->node[i-s].ptr->parent=ap; }//for ap->keynum=m-s; ap->parent=q->parent; q->keynum=s-1; // q的前一半保留，修改keynum }//split void InsertBTree(BTree &T,Record *r,BTree q,int i) {//在m阶B树T上结点*q的key[i]与key[i+1]之间插入关键字K的指针r。若引起 // 结点过大,则沿双亲链进行必要的结点分裂调整,使T仍是m阶B树。 BTree ap=NULL; int finished=false; int s; Record *rx; rx=r; while(q&&!finished) { Insert(q,i,rx,ap);//将r->key、r和ap分别插入到q->key[i+1]、 //q->recptr[i+1]和q->ptr[i+1]中 if(q->keynum split(q,ap);//将q->key[s+1..m],q->ptr[s..m]和q->recptr[s+1..m] //移入新结点*ap q=q->parent; if(q) i=Search(q,rx->key);//在双亲结点*q中查找rx->key的插入位置 }//else }//while if(!finished) //T是空树(参数q初值为NULL)或根结点已分裂为 //结点*q和*ap NewRoot(T,rx,ap); }//InsertBTree Result SearchBTree(BTree T,KeyType K) {// 在m阶B树T上查找关键字K，返回结果(pt,i,tag)。若查找成功，则特征值 // tag=1，指针pt所指结点中第i个关键字等于K；否则特征值tag=0，等于K的 // 关键字应插入在指针Pt所指结点中第i和第i+1个关键字之间。 BTree p=T,q=NULL; //初始化，p指向待查结点，q指向p的双亲 int found=false; int i=0; Result r; while(p&&!found) { i=Search(p,K);//p->node[i].key≤K p=p->node[i].ptr;//在子树中继续查找 }//else }//while r.i=i; if(found) { r.pt=p; r.tag=1; }//if else { r.pt=q; r.tag=0; }//else return r; }//SearchBTree void print(BTNode c,int i) // TraverseDSTable()调用的函数 { printf(\"(%d,%s)\}//print void TraverseDSTable(BTree DT,void(*Visit)(BTNode,int)) {// 初始条件: 动态查找表DT存在，Visit是对结点操作的应用函数 // 操作结果: 按关键字的顺序对DT的每个结点调用函数Visit()一次且至多一次 int i; if(DT) //非空树 { if(DT->node[0].ptr) // 有第0棵子树 TraverseDSTable(DT->node[0].ptr,Visit); for(i=1;i<=DT->keynum;i++) { Visit(*DT,i); if(DT->node[i].ptr) // 有第i棵子树 TraverseDSTable(DT->node[i].ptr,Visit); }//for }//if }//TraverseDSTable void InputBR(BTree &t,Record r[]) { Result s; for(int i=0;i InsertBTree(t,&r[i],s.pt,s.i); } }//InputBR void UserSearch(BTree t) { int i; Result s; printf(\"\\n请输入待查找记录的关键字: \"); scanf(\"%d\s=SearchBTree(t,i); if(s.tag) print(*(s.pt),s.i); else printf(\"没找到\"); printf(\"\\n\"); }//UserSearch void DeleteIt(BTree t,BTNode *dnode,int id) { if(dnode->keynum>=ceil(m/2)) { dnode->keynum--; dnode->node[id].ptr=NULL; }//if被删关键字Ki所在结点的关键字数目不小于ceil(m/2)，则只需从结点中删除Ki和相应指针Ai，树的其它部分不变。 else if((dnode->keynum==(ceil(m/2)-1))&&((id+1)<(m-1))&&dnode->parent->node[id+1].ptr->keynum>(ceil(m/2)-1)) { for(int i=1;i dnode->parent->node[1].key=dnode->parent->node[id+1].ptr->node[1].key; (dnode->parent->node[id+1].ptr->keynum)--; }//else if 被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。本次为与右兄弟调整 else if((dnode->keynum==(ceil(m/2)-1))&&((id-1)>0 )&&dnode->parent->node[id-1].ptr->keynum>(ceil(m/2)-1)) { for(int i=1;i dnode->parent->node[id-1].ptr->node[dnode->parent->node[id-1].ptr->keynum].key;i++) dnode->node[i].key=dnode->parent->node[i].key; dnode->parent->node[1].key=dnode->parent->node[id-1].ptr->node[dnode->parent->node[id-1].ptr->keynum].key; (dnode->parent->node[id-1].ptr->keynum)--; }//2-else if被删关键字Ki所在结点的关键字数目等于ceil(m/2)-1，则需调整。本次为与左兄弟调整 else if((dnode->keynum==(ceil(m/2)-1))&&((id+1)<(m-1))&&dnode->parent->node[id+1].ptr->keynum==(ceil(m/2)-1)) { do { BTree tmp; tmp=dnode; dnode->parent->node[id+1].ptr->node[2]=dnode->parent->node[id+1].ptr->node[1]; dnode->parent->node[id+1].ptr->node[1]=dnode->parent->node[1]; dnode->parent->node[id+1].ptr->keynum++; dnode->parent->node[id+1].ptr->node[0].ptr=dnode->node[1].ptr; dnode->parent->keynum--; dnode->parent->node[id].ptr=NULL; tmp=dnode; if(dnode->parent->keynum>=(ceil(m/2)-1)) dnode->parent->node[1]=dnode->parent->node[2]; dnode=dnode->parent; free(tmp); }while(dnode->keynum<(ceil(m/2)-1)); //双亲中keynum< }//3-else if被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，本次假设右兄弟存在 else if((dnode->keynum==(ceil(m/2)-1))&&(id-1)>0 &&dnode->parent->node[id-1].ptr->keynum==(ceil(m/2)-1)) { do { BTree tmp; tmp=dnode; dnode->parent->node[id-1].ptr->node[2]=dnode->parent->node[id-1].ptr->node[1]; dnode->parent->node[id-1].ptr->node[1]=dnode->parent->node[1]; dnode->parent->node[id-1].ptr->keynum++; dnode->parent->node[id-1].ptr->node[0].ptr=dnode->node[1].ptr; dnode->parent->keynum--; dnode->parent->node[id].ptr=NULL; tmp=dnode; if(dnode->parent->keynum>=(ceil(m/2)-1)) dnode->parent->node[1]=dnode->parent->node[2]; dnode=dnode->parent; free(tmp); }while(dnode->keynum<(ceil(m/2)-1)); //双亲中keynum< }//4-else if被删关键字Ki所在结点和其相邻兄弟结点中的的关键字数目均等于ceil(m/2)-1，本次假设左兄弟存在 else printf(\"Error!\"); //出现异常 }//DeleteIt void UserDelete(BTree t) { KeyType date; Result s; printf(\"Please input the date you want to delete:\\n\"); scanf(\"%d\s=SearchBTree(t,date); if(!s.tag) printf(\"Search failed,no such date\\n\"); else DeleteIt(t,s.pt,s.i); }//UserDelete int main() { Record r[N]={{24,\"1\{50,\"6\{3,\"11\ {7,\"16\ BTree t; InitDSTable(t); InputBR(t,r); printf(\"按关键字的顺序遍历B_树:\\n\"); TraverseDSTable(t,print); UserSearch(t); UserDelete(t); TraverseDSTable(t,print); DestroyDSTable(t); return 1; } 五、复杂度分析 B-树查找包含两种基本动作： ●在B-树上查找结点 ●在结点中找关键字 前一操作在磁盘上进行，后一操作在内存进行。因此查找效率主要由前一操作决定。在磁盘上查找的次数取决于关键字结点在B-树上的层次数。 定理：若n≥1，m≥3，则对任意一棵具有n个关键字的m阶B-树，其树高度h至多为logt((n+1)/2)+1，t= ceil(m/2)。也就是说根结点到关键字所在结点的路径上涉及的结点数不超过logt((n+1)/2)+1。推理如下： 因篇幅问题不能全部显示，请点此查看更多更全内容