改进顺序查找算法框图 开始 s search a(A, n, key) 1=0:An=ky设置哨兵 查找key的循环 I++ Ali:=key Y i<n? 上一页 显示“查找失败” 显示“查找成功” 停止放映 下一页 返回 第11页
下一页 上一页 停止放映 第 11 页 改进顺序查找算法框图 i=0 ； A[n]=key s_search_a(A，n，key) A[i]!=key? Y N 查找key的循环 显示“查找失败” 返回 开始 i++ i < n? N Y 显示“查找成功” 设置哨兵
(6)顺序查找算法3-2(改进算法) seg search adv(item, n, key int *item, n, key int 1=0 //?哨兵的作用? item[n]=key;/*设置哨兵*/ while(iem[i]!=key)i++;/*查找key*/ if(i<n)/*如果i=n,没找到* printf(“查找成功!\n”); return(i);} else printf(“查找失败!Ⅷn”); return(1);} 上一页 停止放映注:顺序查找算法中,执行频率最高的是 while语句,改 进后,可以节省近一半的时间。 下一页 ?改进后与改进前的不同之处? 主要是取消了原来I<n的判断 第12页
下一页 上一页 停止放映 第 12 页 (6)顺序查找算法3-2（改进算法） seq_search_adv(item , n , key ) int *item ,n , key ; { int i=0 ; //？哨兵的作用？ item[n]=key ; /* 设置哨兵 */ while ( item[i]!= key ) i++; /* 查找key */ if ( i< n ) /* 如果 i = n，没找到 */ { printf(“查找成功 !\n”); return (i); } else { printf(“查找失败 !\n”); return (-1); } } 注: 顺序查找算法中,执行频率最高的是while语句,改 进后,可以节省近一半的时间。 ?改进后与改进前的不同之处？ 主要是取消了原来I<n的判断
顺序查找算法主程序 # include“ stdio.h” /*S search. c*k/ #define n 7 main t int key, 10c=0; inta[10]=143,15,21,37,2,5,82}; printf( input key scanf(%d”,&key) 上一页 loc=s search adv(a, n, key) if(10c>0) 停止放映 printf(“1oc=%d,key=%d\n”,1oc,key); 下一页 第13页
下一页 上一页 停止放映 第 13 页 顺序查找算法主程序 #include “stdio.h” /*S_search.c*/ #define n 7 main() ｛ int key,loc=0; int a[10]={43,15,21,37,2,5,82}; printf(“Input key:”); scanf(“%d”,&key); loc=s_search_adv(a,n,key); if (loc >0) printf(“loc=%d,key=%d\n ”,loc,key); } 示例
(7)算法评价 ●平均查找长度ASL在等概率的情况下 ASL=2 Pi*Ci=12(n-i+1)=n+ n 2=o(n) 一般情况下 n ASL≤ 优点: 对结点的逻辑次序(不心有序)和存储结构(顺序、链表均可) 无要求; 上一页 当序列中的记录按访问概率“基本有序”或N稙较小时,是 较好的算法; 停止放映 缺点:ASL较长 下页·讨论:能否减少比较次数,以提高效率。 ●例如 a■ 二分法等,(比较学号查找和姓名查找) 第14页
下一页 上一页 停止放映 第 14 页 (7)算法评价 ⚫ 平均查找长度ASL在等概率的情况下 ⚫ 一般情况下 i=1 n 1 2 n+1 n i=1 n ASL = Pi*Ci = (n-i+1) = ⚫ 优点: –对结点的逻辑次序(不必有序)和存储结构(顺序、链表均可） 无要求； –当序列中的记录按访问概率“基本有序”或N值较小时，是 较好的算法； ⚫ 缺点：ASL较长 ⚫ 讨论：能否减少比较次数，以提高效率。 n ASL 2 ⚫ 例如，……二分法等，（比较学号查找和姓名查找） =O(n)
2、折半查找 ●(1)思想: 将有序序列的中点设置为比较对象,如果要找的 元素值小于该中点元素,则将待查序列缩小为左 半部分,否则为右半部分。 即通过一次比较,将查找区间缩小一半。 (2)特点 二分查找是一种高效的查找方法。它可以明显减 少比较次数,提高查找效率。但是,二分查找的 上★先决条件是查找表中的数据元素必须有序 停止放映 下一页 第15页
下一页 上一页 停止放映 第 15 页 2、折半查找 ⚫ (1)思想： 将有序序列的中点设置为比较对象，如果要找的 元素值小于该中点元素，则将待查序列缩小为左 半部分，否则为右半部分。 即通过一次比较，将查找区间缩小一半。 (2)特点： ⚫ 二分查找是一种高效的查找方法。它可以明显减 少比较次数，提高查找效率。但是，二分查找的 先决条件是查找表中的数据元素必须有序