数据结构及应用算法教程（修订版） 数据结构_第8章查找表习题.ppt

《数据结构及应用算法教程（修订版） 数据结构_第8章查找表习题.ppt》由会员分享，可在线阅读，更多相关《数据结构及应用算法教程（修订版） 数据结构_第8章查找表习题.ppt（14页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、第8章 查找表习题,习题8.2:,low,mid,high,low,mid,high,low,mid,high,low,mid,high,查找 f,查找 e,查找 g,习题8.3:,low,mid,high,ASLsucc=(1+2*2+3*4+4*3)/10=2.9,习题8.4:,ASLsucc=(1+2*2+3*3+4*3+5*2+6*1)/12=3.5,Jan,(1),习题8.4:,ASLsucc=(1+2*2+3*4+4*5)/12=37/123.08,(2),习题8.5: typedef struct LNode ElemType data; struct LNode *next;

2、LNode,*LinkList; typedef struct LNode *h; /h指向最小元素 LNode *t; /t指向上次查找的结点 CSList;,习题8.5: LNode *Search_CSList(CSList /Search_CSList分析:由于题目中假定每次查找都是成功的,所以本算法中没有关于查找失败的处理.,习题8.6:,习题8.7:,H(k)=(3k) MOD 11 di=i ( (7k) MOD 10+1) (i=1,2,3,) m=p=11 开放地址法双散列探测处理冲突： Hi=(Hi-1+di) MOD 11 关键字序列 （22,41,53,46,30,13

3、,01,67）,H(22)=(3*22) MOD 11=0 H(41)=(3*41) MOD 11=2 H(53)=(3*53) MOD 11=5 H(46)=(3*46) MOD 11=6 H(30)=(3*30) MOD 11=2 d1=(7*30) MOD 10+1=1 H1=3 H(13)=(3*13) MOD 11=6 d1=(7*13) MOD 10+1=2 H1=8 H(01)=(3*01) MOD 11=3 d1=(7*01) MOD 10+1=8 H1=0,8,5,2,10 H(67)=(3*67) MOD 11=3 d1=(7*67) MOD 10+1=10 H1=2,1

4、ASLsucc=(1+1+1+1+2+2+6+3)/8=17/8,30,13,01,01,01,01,01,67,67,习题8.8:,解：根据装填因子的定义可得表长m16，取m=16，p=13,设哈希函数：H(k)=关键字首字母序号/2 ，采用开放地址法线性探测处理冲突构造散列表。 关键字序列: （ZHAO,QIAN,SUN,LI,ZHOU,WU,CHEN,WANG,CHANG,CHAO,YANG,JIN）,习题8.8:,H(ZHAO)=26/2=13 H(QIAN)=17/2=8 H(SUN)=19/2=9 H(LI)=12/2=6 H(ZHOU)=26/2=13 Hi=(H(ZHOU)+d

5、i) MOD 13 =1 H(WU)=23/2=11 H(CHEN)=3/2=1 Hi=(H(CHEN)+di) MOD 13 =2 H(WANG)=23/2=11 Hi=(H(WANG)+di) MOD 13 =12 H(CHANG)=3/2=1 Hi=(H(CHANG)+di) MOD 13 =2,3 H(CHAO)=3/2=1 Hi=(H(CHAO)+di) MOD 13 =2,3,4 H(YANG)=25/2=12 Hi=(H(YANG)+di) MOD 13 =0 H(JIN)=10/2=5 ASLsucc=(1*6+2*3+3*1+4*1)/12=18/12=1.5,习题8.9:

6、/- 链地址法存储结构 -/ typedef struct ElemType data; LHNode *next; LHNode,*LHNodeptr; typedef struct LHNodeptr*elem; intcount;/记录数 intsizeindex; /哈希表容量 LHashTable;,习题8.9: Status Build_Hash(LHashTable ,习题8.9: n=H(key); if(!T.elemn) T.elemn=q; /作为链表的第一个结点 else for (p=T.elemn; p-next; p=p-next ) ; p-next=q; /插入链表尾部. T.count+; cinkey; /while return OK; /Build_Hash,