(2)
AUG
AUG APR R FEB JAN MAR L JUN MAY JUL (一) JAN MAR APR FEB JUN MAY R SEP L OCT JUL （二）
(三)
JAN R AUG MAR R APR FEB JUN OCT JUL MAY SEP NOV MARJAN COT
（四）
ASL=(1*1+2*2+4*3+4*4+1*5)/12=38/12 9.9 10 9.10
AUG JUG MAY SEP FEB APR DEC NOV 50 L 40 10 R 30 (LL型) 40 20 40 40 30 L 50 20 50 R L 10 30 L 55 (RL型) 40 60 90 (LR型) 20 20 55 55 50 60 10 R 30 50 70 30 70 R 60 80 (RR 型) 80 G C I M
（1）插入关键字B后，B-树的结点无变化 G K
A B C I M A B D E H J K N O D E H J L N O
（2）插入关键字L后，结点E 和G产生分裂
（3）插入关键字P后，结点H产生分裂
G K
C I
G K C I M O A B D E H J L N P M O A B D E H J L N P Q
（4）插入关键字Q后，结点不变
A B C G K O I M Q D E H J L N P R
（5）插入关键字R后，三个层次结点产生分裂，使B-树增高 9.11 hegtype hashdelete(hashtable ht,hegtype k)
//ht是拉链法解决冲突的散列表，本算法删除关键字 //为k的指定结点，若删除成功，返回K；否则 //返回null
{设I=H(heg);//I为关键字k用指定哈希函数计算的哈希地址
if(ht[i]=null) {printf(“ 没有关键字k”);return(null);}
else{p=ht[i];pre=p;while(p&&p->data!=k){pre=p;p=p->next;}
if(p= =null){printf(“没有关键字k”);return(null);}
else{pre->next=p->next;free(p);return(k);} }
}//hashdelete 9.12 （1）
0 1 2 3 4 5 6 7 8 9 10 11 12
14 1
01 2
68 1
27 4
55 3
19 1
20 84 79 23 1 3 9 1
11 1
10 3
H(19)=19=6 H(14)=14=1 H(23)=23=10
H(01)=01=1 冲突，2次成功 H(68)=68=3 H(20)=20=7
H(84)=84=6 冲突，3次成功 H(27)=27=1 冲突，4次成功 H(55)=55=3 冲突，3次成功 H(11)=11=11
H(10)=10=10 冲突，3次成功 H(79)=79=1 冲突，9次成功
成功时的平均查找长度=（1*6+1*2+3*3+1*4+1*9）/12=30/12
查找不成功时的平均查找长度=（1+13+12+11+10+9+8+7+6+5+4+3+2+1）/13=92/13 （2）
0 ^ 1 2 ^ 3 4 ^ 5 ^ 6 7 8 ^ 9 ^ 10 11 23 11 ^ 10 ^ 19 20 84 ^ 14 01 27 79 ^ 68 55 ^ 12 ^
查找成功时平均查找长度=（1*6+4*2+1*3+1*4）/12=21/12
查找不成功时的平均查找长度=（1*7+2*2+3*3+1*5）/13=25/13
9.13 各种查找方法均有优点和缺点，不能笼统地说某种方法的好坏。 顺序查找的时间为o（n），在n较小时使用较好，它对数据元素的排列没有要求；二
分查找时间为o（log2n），效率高但它要求数据元素有序排列；散查找时间为o（1），它只能按关键字随机查找（使用散列函数），不能顺序查找，也不能折半查找。