单击此处编辑母版标题样式,单击此处编辑母版文本样式,查找：,根据给定的关键字值，在一组数据,元素中确定一个其关键字,值等于给定值的数据元素的过程。若存在这样的数据元素，则称查找成功；若不存在这样的数据元素，则称查找失败。,关键字:,指数据元素中可以标识该数据元素的一组数据项。例如学生记录中的学号；公民记录中的身份证号码等。,查找表：,指一组待查数据元素的集合。它具有一定存储结构，如顺序表结构、链式结构、树形结构等。,2.6 查找,查找：2.6 查找,1)查找的方法,查找某个数据元素依赖于查找表中数据元素的组织方式。按照数据元素的组织方式决定采用某种查找方法；反之,为了提高查找方法的效率，又要求数据元素采用某些特殊的组织方式。因此，在研究各种查找方法时，必须弄清各种查找方法所适用的组织方式。,2)查找算法的评价,衡量一个算法的标准主要有两个：时间复杂度和空间复杂度。,而在查找算法中，基本运算是给定值与关键字值的比较，即算法的,主要时间是花费在“比较”上的，所以，用,平均查找长度,作为评价查,找算法好坏的依据。,对于含有n个数据元素的查找表，查找成功的平均查找长度为,ASL=,其中：P,i,为查找第i个数据元素的概率；C,i,为查找到第i个数,据元素时，需进行的比较次数。,1)查找的方法ASL=其中：Pi为查找第i个数据元,*查找方法分类,线性查找法,顺序查找法,对半查找法,分块查找法,基于树的查找法,二叉排序树,B树,计算式查找法哈希法,顺序存储的查找方法,链式存储的查找方法,散列存储的查找方法,*查找方法分类线性查找法顺序存储的查找方法链式存储的查找方,2.6.1,顺序查找法,基本思想是：从数组的第一个元素开始，与查找的关键字逐个比对，直到找到关键字所在的位置或遇到数组的结尾为止，若找到，则返回关键字在数组中的位置，否则返回-1(因为C#的数组下标不可能为-1)。,public int search(int keyValue),int i=0；,while(),i+;,if(),return(i);,else,return(-1);,假设每个元素等概率查找,则平均查找次数为(n+1)/2,ilength&,datai!=keyValue,iamid,则取表的后半部分作为新表再去查找。,（3）若kamid,则取表的前半部分作为新表再进行查找。,这个过程一直进行到查找成功或子表的长度为0为止。,对半查找是基于关键字比较的最优方法。,2.6.2 对半查找法对半查找是基于关键字比较的最优方法。,public int binSearch(int keyValue),int low,high,mid;,low=0;,high=length-1;,while(),mid=(low+high)/2;,if(datamid=keyValue),;,else if(datamid keyValue),;,else,;,return(-1);,low=high,return(mid),low=mid+1,high=mid-1,对半查找成功时比较次数最多为log,2,n+1,public int binSearch(int keyVa,*分块查找(索引顺序查找）,“分块有序”表特点：,(1)表中数据分块(2),块中,数据不必有序(3),块间,有序,“分块有序”表的结构有两部分：,(1)顺序存储结构的线性表,(2)索引表（由每块的最大元素组成）,分块查找过程：,(1)用对半查找法查找索引表，确定待查项x 所在的块。,(2)在相应的块中用顺序查找法查找待查项x。,*分块查找(索引顺序查找）,2.6.3 二叉排序树及查找,若线性表中的结点经常插入和删除，就应设计成把链表和二分法结合的查找方法。,二叉排序树是将线形表中的元素组织成二叉树的形式，以达到与对半查找相同的查找效率。,1、二叉排序树定义：,（1）若它的左子树不空，则左子树上所有的关键字均小于它的根结点的关键字；,（2）若它的右子树不空，则右子树上所有的关键字均大于或等于它的根结点的关键字；,（3）它的左、右子树也是二叉排序树。,如果按中序遍历二叉排序树，可得到一个递增排列的序列。,2.6.3 二叉排序树及查找,5,2,6,4,8,1,9,3,7,中序遍历序列：1、2、3、4、5、6、7、8、9,二叉排序树示例：,526481937中序遍历序列：1、2、3、4、5、6、7、,/TreeNode类,public class TreeNode,public char data;,public TreeNode leftChild;,public TreeNode rightChild;,public TreeNode(char c),data=c;,leftChild=null;,rightChild=null;,/BiTree类,public class BiTree,private TreeNode root;,public BiTree(),root=null;,public void insBTree(char k),/二叉排序树创建,public TreeNode banSearch(char k),/二叉排序查找方法,二叉排序树代码表示：,/TreeNode类/BiTree类二叉排序树代码表示：,2、查找算法及实现,在给定的二叉排序树t中查找给定待查关键字k：,从根结点出发,（1）如果树t为空，那么查找失败。算法结束；否则，转（2）,（2）如果t.data等于k，则查找成功。算法结束。否则转（3）,（3）如果k k),;,else,;,return(p);,(p!=null)&(p.data!=k),p=p.leftChild,p=p.rightChild,public TreeNode banSearch(cha,假设一组数据元素的关键字序列如下：,45，24，53，12，37，93，30，40，80 分析查找元素40,如何创建二叉排序树？,假设一组数据元素的关键字序列如下：如,3、创建二叉排序树,通过在初始为空的树中不断插入数k来建立二叉排序树，步骤：,（1）若二叉排序树为空，则插入结点应为根结点,（2）若二叉排序树非空，根据关键字比较的结果确定是在左子树还是在右子树中继续查找插入位置，直至某个结点的左子树或右子树空为止，则插入结点应为该结点的左孩子或右孩子。,3、创建二叉排序树,假定由整数序列10，6，19，22，8，2生成一棵二叉排序树，可以采用逐个元素插入的方法实现。(1)首先将10作为根结点(2)然后插入6时，通过比较知610，所以将6作为10的 左孩子插入；(3)同理将19作为10的右孩子插入；(4)整数22通过和10、19比较后，作为19的右孩子插入。(5)依次插入剩余的其他元素,假定由整数序列10，6，19，22，8，2生成一棵,public void insBTree(char k),/,将k插入到二叉排序树,TreeNode p,q;,q=new TreeNode(k);,if(root=null),/树为空，该节点即根节点,root=q;,return;,p=root;,/,从根开始开始找位置,while(p.leftChild!=q)&(p.rightChild!=q)/,尚未插入新节点,if(k 1，则执行第1步，否则结束排序,初始状态 45 21 34 19 52 60 34 24,第1趟（i=1）,19,21 34 45 52 60,34,24,第2趟（i=2）,19,21,34 45 52 60,34,24,第3趟（i=3）,19,21 24,45 52 60,34,34,第4趟（i=4）,19,21 24,34,52 60 45 34,第5趟（i=5）,19,21 24,34,34,60 45 52,第6趟（i=6）,19,21 24,34,34 45,60 52,第7趟（i=7）,19,21 24,34,34 45 52,60,可见，,选择排序是一种不稳定的排序,。,2.7.1 选择排序第1步：在N个元素的排序表中选择最小元素,具体算法描述如下:,public void selectSort(),int i,j,k;,for(i=0;i length-1;i+),;,for(j=i+1;j n;j+),if(),k=j;/,记录最小元素的位置,if(),int x=datai;,datai=datak;,datak=x;,k=i,dataj datak,k!=i,具体算法描述如下:k=idataj datak,2.6.2 交换排序,1、冒泡排序,将待排序文件中的记录两两比较，若为逆序，则进行交换。按此方法将文件从头到尾处理一遍称作一趟起泡。一趟起泡的结果是将关键字最大的记录交换到了表尾。对余下n-1个记录，重复此过程，直至文件排好序为止。若某一趟起泡过程中没有任何交换发生，则表明此时文件已经排好序了，不必再继续重复起泡过程。初始状态 45 21 34 19 52 60,34,24,第一趟 21 34 19 45 52,34,24 60,第二趟 21 19 34 45,34,24 52 60,第三趟 19 21 34,34,24 45 52 60,第四趟 19 21 34 24,34,45 52 60,第五趟 19 21 24 34,34,45 52 60,第六趟 19 21 24 34,34,45 52 60,可见，,冒泡算法是稳定,的。,2.6.2 交换排序可见，冒泡算法是稳定的。,public void bubSort(),bool needChange=true;,int j=length-1;,while(),needChange=false;/,先假定不需要交换,for(int i=0;i datai+1),;,int temp=datai;,datai=datai+1;,datai+1=temp;,j-;,needChange的作用是当前内循环无交换时，即终止程序的运算。,needChange&j 0,needChange=true,public void bubSort()needChan,*直接插入排序,基本思想：,将n个待排序元素看成为一个有序表和一个无序表。开始有序表只有一个元素，无序表中则有n-1个元素。排序过程中每次从无序表中取出第一个元素，将其关键字与有序表的关键字比较，将其插入到适当位置，使之成为新的有序表。,插入步骤：,（1）将无序表中的第一个元素存入辅助变量temp中。,（2）将temp和有序表中从最后一个元素开始进行比较，若小于有序表中的元素，则有序表中该元素后移一位，同时继续和前一元素比较。否则插入到该元素的后面。,*直接插入排序基本思想：,初始状态,45 21 34 19 52 60,34,24,第一趟,21 45 34 19 52 60,34,24,第二趟,21 34 45 19 52 60,34,24,第三趟,19 21 34 45 52 60,34,24,第四趟,19 21 34 45 52 60,34,24,第五趟,19 21 34 45 52 60,34,24,第六趟,19 21 34,34,45 52 60 24,第七趟,19 21 24 34,34,45 52 60,有序文件,19 21 24 34 34 45 52 60,插入排序是稳定的排序,初始状态 45 21 34 19 52,public void insertSort(),int i,j,temp;,for(i=1;i=0&tempdataj),;,j-;,;,dataj+1=dataj,dataj+1=temp,temp=datai,public void insertSort()dataj,2.6.4 快速排序,基本思想：,在待排序的n个元素中任取一个元素R，以该元素排序码k为准，将所有剩下的n-1个元素分割为两个子序列：,第一个子序列中每个元素的排序码均小于或等于k；第二个子序,列中每个元素的排序码均大于或等于k。然后将