C程序设计C程序设计 (65).pdf

《C程序设计C程序设计 (65).pdf》由会员分享，可在线阅读，更多相关《C程序设计C程序设计 (65).pdf（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、C C程序设计程序设计Programming in CProgramming in C实现查找算法实现查找算法1、顺序查找法2、二分查找法3、插值查找法4、斐氏查找法C C程序设计程序设计程序设计程序设计3 36.5 6.5 数组应用程序举例数组应用程序举例（1）顺序查找法顺序查找的基本思想是让关键字与序列中的数逐个比较，直到找出与给定关键字相同的数为止或序列结束，一般应用于无序序列查找。4 46.5 6.5 数组应用程序举例数组应用程序举例【例6.14】编写顺序查找函数Search，从一个无序数组中查找数据的位置。5 56.5 6.5 数组应用程序举例数组应用程序举例例6.141#inclu

2、de#include 2 intint SearchSearch(intint A A,intint n n,intint findfind)3 /顺序查找 n=序列元素个数 find=欲查找数据/顺序查找 n=序列元素个数 find=欲查找数据4 intint i i;5 forfor(i i=0 0;i i=0 0)printfprintf(A%d=%d(A%d=%dnn,i i,findfind););15 elseelse printfprintf(not found(not foundnn););6 66.5 6.5 数组应用程序举例数组应用程序举例例6.1416 returnret

3、urn 0 0;17 7 76.5 6.5 数组应用程序举例数组应用程序举例例6.141#include#include 2 int Search(int A,int n,int find)int Search(int A,int n,int find)3 /顺序查找 n=序列元素个数 find=欲查找数据/顺序查找 n=序列元素个数 find=欲查找数据4 int i;int i;5 for(i=0;in;i+)if(Ai=find)return i;for(i=0;i=0)printf(A%d=%dn,i,find);if(i=0)printf(A%d=%dn,i,find);15 els

4、e printf(not foundn);else printf(not foundn);A4=101101程序运行屏幕8 86.5 6.5 数组应用程序举例数组应用程序举例（2）二分查找法对于有序序列，可以采用二分查找法进行查找。它的基本思想是：升序排列的n个元素集合A分成个数大致相同的两部分，取An/2与欲查找的find作比较，如果相等则表示找到find，算法终止。如果findAn/2，则在A的后半部继续搜索find。9 96.5 6.5 数组应用程序举例数组应用程序举例【例6.15】编写二分查找函数BinarySearch，从一个有序数组中查找数据的位置。10106.5 6.5 数组应用

5、程序举例数组应用程序举例例6.151#include#include 2 intint BinarySearchBinarySearch(intint A A,intint n n,intint findfind)3 /二分查找 n=序列元素个数 find=欲查找数据/二分查找 n=序列元素个数 find=欲查找数据4 intint lowlow,upperupper,midmid;5 lowlow=0 0,upperupper=n n-1 1;/左右两部分/左右两部分6 whilewhile(lowlow=upperupper)7 midmid=lowlow+(+(upperupper-lo

6、wlow)/)/2 2;/不用(upper+low)/2，避免upper+low溢出/不用(upper+low)/2，避免upper+low溢出8 ifif(A A midmid findfind)upperupper=midmid-1 1;/左半部分/左半部分10 else returnelse return midmid;/找到/找到11 12 returnreturn-1 1;/未找到/未找到13 14#define N 10#define N 1011116.5 6.5 数组应用程序举例数组应用程序举例例6.1515 intint mainmain()()16 17 intint A

7、A N N=8 8,2424,3030,4747,6262,6868,8383,9090,9292,9595,i i,findfind;18 scanfscanf(%d,&(%d,&findfind););19 i i=BinarySearchBinarySearch(A A,N N,findfind););20 ifif(i i=0 0)printfprintf(A%d=%d(A%d=%dnn,i i,findfind););21 elseelse printfprintf(not found(not foundnn););22 returnreturn 0 0;23 12126.5 6.5

8、 数组应用程序举例数组应用程序举例例6.151#include#include 2 int BinarySearch(int A,int n,int find)int BinarySearch(int A,int n,int find)3 /二分查找 n=序列元素个数 find=欲查找数据/二分查找 n=序列元素个数 find=欲查找数据4 int low,upper,mid;int low,upper,mid;5 low=0,upper=n-1;/左右两部分low=0,upper=n-1;/左右两部分6 while(low=upper)while(low=upper)7 mid=low+(u

9、pper-low)/2;/不用(upper+low)/2，避免upper+low溢出mid=low+(upper-low)/2;/不用(upper+low)/2，避免upper+low溢出8 if(Amid find)low=mid+1;/右半部分if(Amid find)upper=mid-1;/左半部分else if(Amid find)upper=mid-1;/左半部分10 else return mid;/找到else return mid;/找到11 12 return-1;/未找到return-1;/未找到13 14#define N 10#define N 10A8=9292程序

10、运行屏幕13136.5 6.5 数组应用程序举例数组应用程序举例（3）插值查找法如果欲查找的数据分布平均时，可以使用插值法（Interpolation），或称为插补法来进行查找，在查找的数据对象大于500时，插值查找法会比二分查找法来得快速。14146.5 6.5 数组应用程序举例数组应用程序举例插值查找法是以数据分布的近似直线来作比例运算，以求出中间的索引并进行数据比对，如果取出的值小于要寻找的值，则提高下界，如果取出的值大于要寻找的值，则降低下界，如此不断地减少查找的范围。15156.5 6.5 数组应用程序举例数组应用程序举例所以插值查找法的原理与二分查找法是相同的，至于中间值的寻找是通

11、过比例运算。如下所示，其中K是指定要寻找的对象，而m则是可能的索引值：lulKKmlKKul11()1uKKmulKK16166.5 6.5 数组应用程序举例数组应用程序举例【插值查找法举例】编写查找函数InterpolationSearch，从一个数组中查找数据的位置。17176.5 6.5 数组应用程序举例数组应用程序举例例6.611#include#include 2#include#include 3#include#include 4 intint InterpolationSearchInterpolationSearch(intint A A,intint n n,intint

12、findfind)5 6 intint lowlow,upperupper,midmid;7 lowlow=0 0;8 upperupper=n n-1 1;9 whilewhile(lowlow=upperupper)10 midmid=(=(upperupper-lowlow)*()*(findfind-A A lowlow)/()/(A A upperupper-A A lowlow)+)+lowlow;11 ifif(midmid upperupper)breakbreak;12 ifif(findfind A A midmid)lowlow=midmid+1 1;14 else re

13、turnelse return midmid;15 18186.5 6.5 数组应用程序举例数组应用程序举例例6.6116 returnreturn-1 1;17 18 voidvoid QuickSortQuickSort(intint A A,intint n n,intint leftleft,intint rightright)19 /快速排序 n为数组元素个数 left=数组左边界 right=数组右边界/快速排序 n为数组元素个数 left=数组左边界 right=数组右边界20 intint i i,j j,t t;21 ifif(leftleft rightright)/一趟快

14、速排序/一趟快速排序22 i i=leftleft;j j=rightright+1 1;23 whilewhile(1 1)24 whilewhile(i i+1 1 n n&A A+i iA A leftleft););/向后搜索 降序/向后搜索 降序25 whilewhile(j j-1 1-1 1&A A-j jA A leftleft););/向前搜索 升序 升序=j j)breakbreak;27 t t=A A i i,A A i i=A A j j,A A j j=t t;/交换/交换28 29 t t=A A leftleft,A A leftleft=A A j j,A A

15、 j j=t t;/交换/交换30 QuickSortQuickSort(A A,n n,leftleft,j j-1 1););/关键数据左半部分递归/关键数据左半部分递归19196.5 6.5 数组应用程序举例数组应用程序举例例6.6131 QuickSortQuickSort(A A,n n,j j+1 1,rightright););/关键数据右半部分递归/关键数据右半部分递归32 33 34#define N 100#define N 10035 intint mainmain()()36 37 intint A A N N,i i;38 intint findfind;39 sra

16、ndsrand(unsigned intunsigned int)timetime(0 0););/设置随机数种子/设置随机数种子40 forfor(i i=0 0;i i N N;i i+)+)/随机产生N个数/随机产生N个数41 A A i i=randrand()%()%10001000;42 QuickSortQuickSort(A A,N N,0 0,N N-1 1););43 forfor(i i=0 0;i i=)=0 0)47 printfprintf(found:%d(found:%dnn,i i););48 elseelse49 printfprintf(not found

17、(not foundnn););50 returnreturn 0 0;51 21216.5 6.5 数组应用程序举例数组应用程序举例（4）斐氏查找法二分查找法每次查找时，都会将查找区间分为一半，所以其查找时间为O(log2n)，这里要介绍的斐氏查找，其利用斐波那契(Fibonacci)数列作为间隔来查找下一个数，所以区间收敛的速度更快，查找时间为O(logn)。22226.5 6.5 数组应用程序举例数组应用程序举例斐氏查找使用斐波那契(Fibonacci)数列来决定下一个数的查找位置，所以必须先制作斐波那契数列；1,1,2,3,5,8,13,21,34,55,89,144,233,377,

18、610,987,1597,.23236.5 6.5 数组应用程序举例数组应用程序举例第一个查找数的位置可以由下面公式求得，其中n为查找对象的个数，Fy为第y个斐式数，必须大于等于n，若算出x值，则使用Fx作为第一个查找下标，也就是第x个斐式数：Fy+m=nFy=n+1x=y-124246.5 6.5 数组应用程序举例数组应用程序举例以10个查找对象来说：Fy+m=10取Fy=8,m=2，对照斐波那契数列得到8是第六个斐式数，所以y=6，因而x得5，也就是使用第五个斐式数的值（也就是5）作为下标开始查找。25256.5 6.5 数组应用程序举例数组应用程序举例如果数组在下标5处的值大于指定的查找

19、值，则第一个查找位置就是下标5的位置，如果小于指定的查找值，则第一个查找位置必须加上m，也就是F5+m=5+2=7，也就是下标7的位置，其实加上m的原因，是为了要让下一个查找值刚好是数组的最后一个位置。26266.5 6.5 数组应用程序举例数组应用程序举例例如若在下面的数组中查找（为了计算方便，通常会将下标0当作无限小的数，而数组由下标1开始）：-1 3 5 7 9 13 15 17 19 2027276.5 6.5 数组应用程序举例数组应用程序举例如图所示：-135791315171920F4=3F2=1F3=228286.5 6.5 数组应用程序举例数组应用程序举例如果要查找5的话，则由

20、下标F5（F5表示第5个斐波那契数作为下标，也就是5）开始查找，接下来如果数列中的数大于指定查找值时，就往左找，小于时就向右，每次找的间隔是F4（第4个斐波那契数作为下标，也就是3）、F3（第3个斐波那契数作为下标，也就是2）、F2（第2个斐波那契数作为下标，也就是1）来寻找，当斐波那契数为0时还没找到，就表示寻找失败。29296.5 6.5 数组应用程序举例数组应用程序举例如果要查找19，由于第一个查找值下标F5处的值小于19，所以此时必须对齐数列右方，也就是将第一个查找值的下标改为F5+2=7，然后用上述的方式进行查找，如下所示：30306.5 6.5 数组应用程序举例数组应用程序举例斐波

21、那契查找除了收敛快速之外，由于其本身只会使用到加法与减法，在运算上也可以加快。31316.5 6.5 数组应用程序举例数组应用程序举例【斐氏查找法举例】编写查找函数FibSearch，从一个数组中查找数据的位置。32326.5 6.5 数组应用程序举例数组应用程序举例例6.621#include#include 2#include#include 3#include#include 4#define N 10#define N 105 intint FibSearchFibSearch(intint A A,intint findfind)6 /斐波那契查找/斐波那契查找7 intint i

22、i,x x,m m;8 intint FibFib N N=-=-9999999999;9 FibFib 0 0=0 0;10 FibFib 1 1=1 1;11 forfor(i i=2 2;i i N N;i i+)+)/建立斐波那契数列/建立斐波那契数列12 FibFib i i=FibFib i i-1 1+FibFib i i-2 2;13 x x=0 0;14 whilewhile(FibFib x x=N N+1 1)x x+;+;/找x值/找x值15 x x-;-;/Fib不大于N+1的x/Fib不大于N+1的x33336.5 6.5 数组应用程序举例数组应用程序举例例6.62

23、16 m m=N N-FibFib x x;/差值/差值17 x x-;-;/左边界/左边界18 i i=x x;19 ifif(A A i i0 0)21 ifif(A A i i findfind)i i=i i-FibFib-x x;/查找前半段/查找前半段23 else returnelse return i i;/找到/找到24 25 returnreturn-1 1;26 27 voidvoid QuickSortQuickSort(intint A A,intint n n,intint leftleft,intint rightright)28 /快速排序 n为数组元素个数 l

24、eft=数组左边界 right=数组右边界/快速排序 n为数组元素个数 left=数组左边界 right=数组右边界29 intint i i,j j,t t;30 ifif(leftleft rightright)/一趟快速排序/一趟快速排序34346.5 6.5 数组应用程序举例数组应用程序举例例6.6231 i i=leftleft;j j=rightright+1 1;32 whilewhile(1 1)33 whilewhile(i i+1 1 n n&A A+i iA A leftleft););/向后搜索 降序/向后搜索 降序34 whilewhile(j j-1 1-1 1&A

25、 A-j jA A leftleft););/向前搜索 升序 升序=j j)breakbreak;36 t t=A A i i,A A i i=A A j j,A A j j=t t;/交换/交换37 38 t t=A A leftleft,A A leftleft=A A j j,A A j j=t t;/交换/交换39 QuickSortQuickSort(A A,n n,leftleft,j j-1 1););/关键数据左半部分递归/关键数据左半部分递归40 QuickSortQuickSort(A A,n n,j j+1 1,rightright););/关键数据右半部分递归/关键数据

26、右半部分递归41 42 43 intint mainmain()()44 45 intint A A N N=0 0;35356.5 6.5 数组应用程序举例数组应用程序举例例6.6246 intint i i,findfind;47 srandsrand(unsigned intunsigned int)timetime(0 0););/设置随机数种子/设置随机数种子48 forfor(i i=0 0;i i N N;i i+)+)/随机产生N个数/随机产生N个数49 A A i i=randrand()%()%100100;50 QuickSortQuickSort(A A,N N,0 0,N N-1 1););51 forfor(i i=0 0;i i=)=0 0)55 printfprintf(found:%d(found:%dnn,i i););56 elseelse57 printfprintf(not found(not foundnn););58 returnreturn 0 0;59 结束结束