有关C++查找的方法.doc

查找顺序查找Int seqsch (ElemTYpe a, int n, KeyType k)for (int I = 0; I n; l+)if (al.key = k)Break;If ( I n)return I;elsereturn -1;顺序查找的改进法，改进后的算法省略了对下标越界的检查，所以提高了速度：Int seqsch (ElemTYpe a, int n, KeyType k)An.key = k; / 设置岗哨for (int I = 0; l+)if (al.key = k)Break;If ( I n)return I;elsereturn -1; 二分查找（又称折半查找）1. 递归法Int Binsch(ElemType a, int left, int right, KeyType k) left 和 right的值分别为 0 n-1If (left = hight)Int mid = (left+right)/2; 中间位置If (k = amid.key)return mid;else if (k amid.key)return Binsch(a, mid + 1, right k);/ 在右子表上查找ElseReturn -1; 查找失败 2. 非递归Int Binsch(ElemType a, KeyType k) left 和 right的值分别为 0 n-1Int left = 0, right = n-1;while (left = hight)Int mid = (left+right)/2; 中间位置If (k = amid.key)return mid;else if (k amid.key)left = mid + 1; / 在右子表上查找ElseReturn -1; 查找失败 插入排序(直接插入排序)Void InsertSort (ElemType a, int n)ElemType x;Int I,j;for (i=1; i=0; j-)If (x.stn =1;d/=2)/按不同分量进行排序for (I = d; i=0;j-=d)/ 在组内向前顺序进行比较和移动If(s.stnaj.stn)Aj+d = aj;elsebreak; / 查找到就退出aj+d=x; / 将ai的值放入到合适位置 直接选择排序Void SelectSort(ElemType a, int n)ElemTYpe x;Int I,j,k;For (i=1;i=n-1;i+)K=i-1; /用K保存当前得到的最小排序码元素下标，初值为i-1For(j=I;j=n-1;j+)/从当前排序区间中顺序查找出具有最小排序码的元素akIf(aj.stn =0; i-)Sift(a,n,i);/建立初始堆For(i=1;i=n-1;i+)/进行n-1次for,完成堆排序X=a0;a0=an-i;an-i=x; / 将树根结点的值同当前区间内最后一个结点的值对换Sift(a,n-I,0); / 筛a0结点，得到n-i个结点堆假定待排序的n相元素存放于一维数组a中，则对ai进行筛选的算法为：Void sift(ElemTYpe a, int n)ElemTYpe x = ai; / 待筛结点暂存于x中Int j = 2*i+1; /aj是ai的左孩子While (j =n-1)/ 当ai的左孩子不为空时循环If (jn-1 & aj.stn aj+1.stn)J+; /若右孩子的排序码较大，则把j修改为右孩子的下标If (x.stn aj.stn)Ai = aj; / 将aj调到双亲位置上I = j; j=2*i+1; / 修改i和j的值，以便继续向下筛ElseBreak; / 若找到x的最终位置，终止Ai = x; / 被筛结点的值放入最终位置 交换排序（气泡排序）Void BubbleSort(ElemType a, int n)ElemType x;Int I,j,flag;For(i=1;i=I; j-) / 进行第i趟排序If(aj.stn aj-1.stn)X = aj-1;aj-1=aj;aj=x;Flag = 1;If (flag = 0)Return ;/ 进行后一趟排序交换排序（快带排序）Void QuickSort(ElemType a, int s, int t) / 采用快速排序方法对数组a中as-at区间进行排序 /开始进行非递归调用时s和t的初值应分别为0和n-1/ 对当前排序区间进行一次划分Int I = s, j = t+1; / 给I 和 j初值ElemType x = as; / 把基准元素的值暂存X中DoDo i+; whie(ai.stn x.stn); / 从后先前顺序查找一个要向前一区间交换的元素If(ij)/ 当条件成立时交换ai aj的值ElemType temp = ai;Ai = aj; aj = temp;While(ij); / 条件成立时继续进行一次划分中的比较和交换As = aj; aj = x; / 交换as和aj的值，得到前后两后两个子区间/ 在当前左区间内超过一个元素的情况下递归处理左区间If (sj-1) QuickSort(a,s,j-1);/ 在当前右区间内超过一个元素的情况下递归处理右区间If (j+1 next)&(head-next-next)/当表中含有结点数大于1 p=head-next-next;/p指向第二个节点 head-next=NULL; q=head;/指向插入位置的前驱节点 while(p)&(q-next)&(p-keynext-key) q=q-next; if (p) s=p;p=p-next;/ 将要插入结点摘下 s-next=q-next;/插入合适位置：q结点后 q-next=s; 二分法查找、排序以及库函数bsearch的用法二分法查找1、二分查找(Binary Search) 二分查找又称折半查找，它是一种效率较高的查找方法。 二分查找要求：线性表是有序表，即表中结点按关键字有序，并且要用向量作为表的存储结构。不妨设有序表是递增有序的。2、二分查找的基本思想 二分查找的基本思想是：（设Rlow.high是当前的查找区间） （1）首先确定该区间的中点位置： （2）然后将待查的K值与Rmid.key比较：若相等，则查找成功并返回此位置，否则须确定新的查找区间，继续二分查找，具体方法如下： 若Rmid.keyK，则由表的有序性可知Rmid.n.keys均大于K，因此若表中存在关键字等于K的结点，则该结点必定是在位置mid左边的子表R1.mid-1中，故新的查找区间是左子表R1.mid-1。 类似地，若Rmid.keyK，则要查找的K必在mid的右子表Rmid+1.n中，即新的查找区间是右子表Rmid+1.n。下一次查找是针对新的查找区间进行的。 因此，从初始的查找区间R1.n开始，每经过一次与当前查找区间的中点位置上的结点关键字的比较，就可确定查找是否成功，不成功则当前的查找区间就缩小一半。这一过程重复直至找到关键字为K的结点，或者直至当前的查找区间为空(即查找失败)时为止。3、二分查找算法 int BinSearch(SeqList R，KeyType K) /在有序表R1.n中进行二分查找，成功时返回结点的位置，失败时返回零 int low=1，high=n，mid； /置当前查找区间上、下界的初值 while(lowK) high=mid-1; /继续在Rlow.mid-1中查找 else low=mid+1； /继续在Rmid+1.high中查找 return 0； /当lowhigh时表示查找区间为空，查找失败 /BinSeareh 二分查找算法亦很容易给出其递归程序【参见练习】4、二分查找算法的执行过程设算法的输入实例中有序的关键字序列为 (05，13，19，21，37，56，64，75，80，88，92)要查找的关键字K分别是21和85。具体查找过程【参见动画演示】5、二分查找判定树 二分查找过程可用二叉树来描述：把当前查找区间的中间位置上的结点作为根，左子表和右子表中的结点分别作为根的左子树和右子树。由此得到的二叉树，称为描述二分查找的判定树(Decision Tree)或比较树(Comparison Tree)。 注意： 判定树的形态只与表结点个数n相关，而与输入实例中R1.n.keys的取值无关。 【例】具有11个结点的有序表可用下图所示的判定树来表示。 （1）二分查找判定树的组成圆结点即树中的内部结点。树中圆结点内的数字表示该结点在有序表中的位置。外部结点：圆结点中的所有空指针均用一个虚拟的方形结点来取代，即外部结点。树中某结点i与其左(右)孩子连接的左(右)分支上的标记、)表示：当待查关键字KRi.key)时，应走左(右)分支到达i的左(右)孩子，将该孩子的关键字进一步和K比较。若相等，则查找过程结束返回，否则继续将K与树中更下一层的结点比较。（2）二分查找判定树的查找二分查找就是将给定值K与二分查找判定树的根结点的关键字进行比较。若相等，成功。否则若小于根结点的关键字，到左子树中查找。若大于根结点的关键字，则到右子树中查找。【例】对于有11个结点的表，若查找的结点是表中第6个结点，则只需进行一次比较；若查找的结点是表中第3或第9个结点，则需进行二次比较；找第1，4，7，10个结点需要比较三次；找到第2，5，8，11个结点需要比较四次。 由此可见，成功的二分查找过程恰好是走了一条从判定树的根到被查结点的路径，经历比较的关键字次数恰为该结点在树中的层数。若查找失败，则其比较过程是经历了一条从判定树根到某个外部结点的路径，所需的关键字比较次数是该路径上内部结点的总数。 【例】待查表的关键字序列为：(05，13，19，21，37，56，64，75，80，88，92)，若要查找K=85的记录，所经过的内部结点为6、9、10，最后到达方形结点9-10，其比较次数为3。 实际上方形结点中i-i+1的含意为被查找值K是介于Ri.key和Ri+1.key之间的，即Ri.keyKRi+1.key。（3）二分查找的平均查找长度 设内部结点的总数为n=2h-1，则判定树是深度为h=lg(n+1)的满二叉树(深度h不计外部结点)。树中第k层上的结点个数为2k-1，查找它们所需的比较次数是k。因此在等概率假设下，二分查找成功时的平均查找长度为： ASLbnlg(n+1)-1二分查找在查找失败时所需比较的关键字个数不超过判定树的深度，在最坏情况下查找成功的比较次数也不超过判定树的深度。即为： 二分查找的最坏性能和平均性能相当接近。6、二分查找的优点和缺点虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费O(nlgn)的时间。二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找。二分法排序#include #include void TwoInsertSort(int array,int n) int left,right,num; int middle,j,i; for(i = 1;i = left)/ 二分法查找插入位置 middle = ( left + right ) / 2; /指向已排序好的中间位置 if( num = left;j- )/后移排序码大于Ri的记录 arrayj+1 = arrayj; arrayleft = num;/ 插入 int rcmp( const int *a, const int *b) return (*a-*b);void main() int array50; int i; printf(The original array is :n); for( i=0; i50; i+ )/数组初始化并显示 arrayi = 50-i; printf(array%d:%dn, i, arrayi); TwoInsertSort(array,sizeof(array)/sizeof(int);/二分法排序 printf(