c语言数据结构查找算法大全

《c语言数据结构查找算法大全》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、查找9.1基本概念查找是指从一组记录集合中找出满足给定条件的记录。查找表在讨论查找时，通常假设被查找的对象是由一组同一类型的记录构成的集合，称这个集合为查找表。关键字是指记录的某个数据项，用它可以标识一个记录。若此关键字可以唯一地标识一个记录，则称此关键字为主关键字；反之，把可以识别若干记录的关键字称为次关键字。查找是指根据某个给定的值，在查找表中查找一个其关键字值等于给定值的记录。若表中存在这样的一个记录，则称查找成功；若表中不存在关键字值等于给定值的记录，则称查找失败。查找技术分为：1静态查找表技术顺序查找、折半查找、索引顺序查找2动态查找表技术二叉查找树3哈希表技术哈希表技术在查

2、找一个记录时所做的主要操作是关键字的比较，所以通常把查找过程中对关键字的平均比较次数作为衡量一个查找算法效率优劣的标准，并称平均比较次数为平均查找长度（AverageSearchLength）。平均查找长度的定义为：ASL=其中，n为元素的个数；ci是查找第i个记录需进行的比较次数；pi是查找第i个记录的概率，一般可认为查找每个记录的概率是相等的，即p1=p2=…=pn=1/n。※查找算法的衡量指标当ASL不易计算时，使用最大查找长度MSL来衡量算法。9.2静态查找表——基于线性表的查找此类查找主要有顺序查找、折半查找和索引顺序查找三种方法。为简便起见，假设查找表中的记录为整型，记录的

3、关键字即为该整数，记录的个数为N，存放在数组R中。查找表的C语言定义如下：#defineN100intR[N+1];/*使用的地址空间[1..N]*/9.2.1顺序查找基本思想：从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；否则，说明查找表中不存在关键字值为给定值的记录，则称查找失败。※顺序查找算法如下:intseqsearch(intR[],intk)/*元素存放在R的1-N处*//*在查找表R中查找关键字为k的记录，查找成功，返回记录在R中的下标值，否则返回0*/{inti;R[0]=k;/*将k放入R[0]中*/i=N

4、;/*从最后一个元素开始查找*/while(R[i]!=k)/*R[0]用来控制循环退出，起“监视哨”的作用*/i--;return(i);/*若i为0，表示查找失败，否则R[i]为要找的记录*/}※顺序查找算法性能分析:在顺序查找中，比较次数ci取决于所查记录在表中的位置。如查找记录R[n]时，仅需比较一次，而查找记录R[1]时，则需比较n次。一般来说，查找第i个记录的比较次数为ci=n-i+1，因此，查找成功的平均查找长度为：在等概率情况下，即pi=1/n时，查找成功的平均查找长度为（n+1）/2。若关键字不在表中，则必须经过n+1次比较后才能确定查找失败。所以查找失败的平均查找长

5、度为n+1。这个结果表明：顺序查找的查找长度是与记录的个数n成正比的。结论：顺序查找的优点是算法简单，且对表的结构没有任何要求。它的缺点是查找效率低，因此，当表中元素个数比较多时，不宜采用顺序查找。ASL成功=pi×ci=pi×(n-i+1)已知含有10个整数的查找表如下：（9，13，15，7，45，32，56，89，60，36），从键盘上输入一个整数，用顺序查找的方法在查找表中查找该整数。若存在，输出该元素的下标值，否则，给出相应的信息。程序如下:例9-1#include#defineN10main(){intx,p;inta[N+1]={0,9,13,15,7,4

6、5,32,56,89,60,36};scanf("%d",&x);p=seqsearch(a,x);/*调用顺序查找算法*/if(p==0)printf("Thisnumberdoesnotexistinthisarray.");elseprintf("a[%d]=%d",p,x);}9.2.2折半查找(二分查找)使用折半查找必须具备两个前提条件:（1）要求查找表中的记录按关键字有序(设,从小到大有序)（2）只能适用于顺序存储结构基本思想：先取查找表的中间位置的关键字值与给定关键字值作比较，若它们的值相等，则查找成功；如果给定值比该记录的关键字值大，说明要查找的记录一定在查找表

7、的后半部分，则在查找表的后半部分继续使用折半查找；若给定值比该记录的关键字值小，说明要查找的记录一定在查找表的前半部分，则在查找表的前半部分继续使用折半查找。…直到查找成功，或者直到确定查找表中没有待查找的记录为止，即查找失败。设有一个11个记录的有序表的关键字值如下：812263745566472818995假设指针low和high分别指示待查元素所在区间的下界和上界，指针mid指示区间的中间位置。查找关键字值为26的过程：812263745