3.算法设计 算法1:假定不使用监视哨r[0] 基本思想:将关键字k依次与记录的关键字 r[n].key,r[n-1].key,,.,r[1].key比较, 如果找到一个记录r[i],有r[i].key=k(1≤i≤n),则查找 成功,停止比较,返回记录的下标i;否则,查找失败,返回0。 int sequsearch(struct arecord r[, int n, keytype k) inti=n;//从第n个记录开始查找 while (i>=1 & k!=r[i]. key) //继续扫描 if(i) printf(" SuccessⅦn〃);//查找成功 else printf("fail\n) //查找失败 return 1 //返回记录的下标i
3.算法设计 算法1：假定不使用监视哨r[0] 基本思想：将关键字k依次与记录的关键字 r[n].key,r[n-1].key，...,r[1].key 比较, 如果找到一个记录r[i],有r[i].key＝k (1≤i≤n)，则查找 成功，停止比较,返回记录的下标i；否则,查找失败,返回0。 int sequsearch(struct arecord r[],int n,keytype k) { int i=n； //从第n个记录开始查找 while (i>=1 && k!=r[i].key) i--； //继续扫描 if (i) printf(”success\n”)； //查找成功 else printf(”fail\n”)； //查找失败 return i； //返回记录的下标i }
算法2:假定使用监视哨r[0] 基本思想:先将关键字k存入r[0].key,再将k依次与 r[n].key,r[n-1].key,,..,r[1].key,r[0].key进行比较, 如果找到一个记录,有k=r[i].key,(0≤i≤n),则停止比较。 如果i>0,则查找成功;否则,查找失败。 int sequsearch (struct arecord r[, int n, keytype k) int l-n: /从第n个记录开始查找 r[o]. key=k; //k填入r[O].key while(k=rLi]. key //继续扫描 if(i!=0) printf(" successⅦn〃);/查找成功 else printf("fai1Ⅶn) //查找失败 return 1 //返回记录的下标i
算法2：假定使用监视哨r[0] 基本思想：先将关键字k存入r[0].key,再将k依次与 r[n].key,r[n-1].key，...,r[1].key, r[0].key进行比较, 如果找到一个记录,有k=r[i].key, (0≤i≤n)，则停止比较。 如果 i>0,则查找成功；否则,查找失败。 int sequsearch(struct arecord r[],int n,keytype k) { int i=n； //从第n个记录开始查找 r[0].key=k； //k填入r[0].key while( k!=r[i].key ) i-- ； //继续扫描 if (i!=0) printf(”success\n”)； //查找成功 else printf(”fail\n”)； //查找失败 return i； //返回记录的下标i }
4查找算法性能分析: 对n个记录的表,所需比较关键字的次数 ●若查找成功:最少为1,最多为n 假定每个记录的查找概率相等,即P1=P2 1/n ASL=∑P;Ci (n+(n-1)+..+1)=(n+1)/2 n i=l ●若查找失败:使用监视哨r[0],为n+1 不使用监视哨r[0],为n 假定查找成功和失败的机会相同,对每个记录的查找概率相 等,P;=1/(2*n),则 ASL=--∑ 2n (+h+1n+1n+1 =3(n+1)/4 24
4 查找算法性能分析： 对n个记录的表,所需比较关键字的次数 ● 若查找成功: 最少为1,最多为n 假定每个记录的查找概率相等，即 P1 = P2 = ... = Pn =1/n n 1 n 1 ASL=∑ PiCi =-- ∑ Ci =--(n+(n-1)+...+1)=(n+1)/2 i=1 n i=1 n ● 若查找失败: 使用监视哨r[0],为 n+1 不使用监视哨r[0],为 n 假定查找成功和失败的机会相同，对每个记录的查找概率相 等，Pi=1/(2*n), 则 1 n n+1 n+1 n+1 ASL=-- ∑ Ci + --- =--- + --- =3(n+1)/4 2n i=1 2 4 2
9.1.2有序的顺序表的查找与折半查找法 1.有序表 r[1].key≤r[2].key≤..≤r[n].key 2.折半查找( binary search,对半查找,二分查找) 假定k=10 1012182025304010w=1,hig=8 12345678 mid=(lowthig)/2=4 hi 51012 1820253040 low=l, hig=3 mid=(low+hig)/ 2=2 12345678 low mid hig
9.1.2 有序的顺序表的查找与折半查找法 1.有序表 r[1].key≤r[2].key≤...≤r[n].key 2.折半查找(binary search,对半查找，二分查找) 假定 k=10 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=1,hig=8 mid=(low+hig)/2=4 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=1,hig=3 mid=(low+hig)/2=2
假定k=40 510 1820253040 low=l, hig=8 mid=(low+hig)/2=4 2345678 low id hi 510 12 low=5, hig=8 1820|253040 mid=(lowthig)/2=6 12345678 low mid hig low=7, hig=8 510121820253040 mid=(lowhig)/ 2=7 low mid hig
假定k=40 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=1,hig=8 mid=(low+hig)/2=4 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ ↑ low mid hig low=5,hig=8 mid=(low+hig)/2=6 5 10 12 18 20 25 30 40 1 2 3 4 5 6 7 8 ↑ ↑ low mid hig low=7,hig=8 mid=(low+hig)/2=7 ↑