版序查找算法 int SeqSearch ( seqlist r, int n, Key Type k) i int i=0; while(i<n&&R[key!=k)i++;/从表头往后找* if(i>=n) return -1 比较次数=7*2 else 返回结果:i=6 return 找64 例 05 1234567891011 13192137566475808892
顺序查找算法： int SeqSearch(SeqList R,int n,KeyType k) { int i=0; while (i<n && R[i].key!=k) i++; /*从表头往后找*/ if (i>=n) return -1; else return i; } i 例 0 1 2 3 4 5 6 7 8 9 10 11 找64 i i i i 比较次数=7*2 返回结果：i=6 5 13 19 21 37 56 64 75 80 88 92 i i
●改进的版序查找算法: int SeqSearch(seq list r, int n, Key Type k) i int i=0 RIn]key=k;/哨兵免去监测查找完毕的操作 whil(R[lkey!=k)i+;从前往后找 if(i==n return-1 else return i: 比较次数=7 返回结果:i=6 找64 例 01234567891011 51319213756647580889264 监视哨
⚫ 改进的顺序查找算法： int SeqSearch(SeqList R,int n,KeyType k) { int i=0; R[n].key=k; //哨兵,免去监测查找完毕的操作 while( R[i].key!=k) i++; //从前往后找 if(i= =n) return -1; else return i; } i 例 0 1 2 3 4 5 6 7 8 9 10 11 找64 64 监视哨 i i i i 比较次数=7 返回结果：i=6 5 13 19 21 37 56 64 75 80 88 92 i i
平均查长度ASL 对于含有n个纪录的表,查找功时的平均查找长度为: ASL 芝 其中:为查找表中第i个纪录的概率,等概率时P2=1/n C为找到第个记录时,已比较的次数。 ke y ASL (i+1)=(n+1)/2 n i=0
i+1 对于含有n个纪录的表，查找成功时的平均查找长度为： − = = 1 0 n i ASL Pi Ci 其中: Pi 为查找表中第i个纪录的概率,等概率时 pi =1/ n Ci 为找到第i个记录时，已比较的次数。 key i ( 1) ( 1)/ 2 1 1 0 = + = + − = i n n ASL n i 平均查找长度(ASL)
102线性表的查找 版序查物的优缺点: 优点:算法简单且适应面广,对表的结构无 任何要求,对线性链表同样适用。 缺点:平均查找长度较大,特别是当n很大时 查找效率较低
9 顺序查找的优缺点： 优点：算法简单且适应面广，对表的结构无 任何要求，对线性链表同样适用。 缺点：平均查找长度较大，特别是当n很大时， 查找效率较低。 10.2 线性表的查找
102线性表的查找 二.二分查线( Binary Search): 有表:查找表中记录按关键字有序排列的表。 即:r[ikey<=r[i计1keyi=1,2,,n-1 二分查线: 要求:查找表为有序表 查找过程:先确定待查找记录范围; 然后逐步缩小范围; 直到:查找成功或不成功。 10
10 10.2 线性表的查找 二、二分查找（Binary Search)： 有序表：查找表中记录按关键字有序排列的表。 即：r[i].key<=r[i+1].key i=1,2,…,n-1 二分查找： • 要求：查找表为有序表 • 查找过程：先确定待查找记录范围； 然后逐步缩小范围； 直到：查找成功或不成功