常用数据结构及其运算3.pptVIP

查 找 和 排 序 2.7 查找 2.7.1 顺序查找 2.7.2 折半查找 2.7.3 分块查找 2.7.4 二叉排序树的查找 2.7.5 哈希查找 1. 哈希表的建立 2.处理冲突的方法 3. 哈希查找 2.8 排序 2.8.2 选择排序 2.8.3插入排序 2.8.4交换排序 查找是数据处理中最基本的操作之一，当查找所涉及的数据量很大时，查找方法的效率直接影响数据处理的速度。 在数据处理中，被查找的元素通常是以记录形式出现，即每一个数据元素(记录)由若干个数据项组成，其中能用来唯一标识记录的数据项称为主关键字(Primary Key)。 查找就是根据给定值K，在查找表中确定一个关键字等于给定值K的记录或数据元素。若存在这样的数据元素，则称查找是成功的，否则称查找不成功。 查找算法的评价： 在查找算法中，基本运算是给定值与关键字的比较，所以算法的主要时间是花费在“比较”上。下面给出一个称为平均查找长度的概念，作为评价查找算法好坏的依据。 对于含有n个数据元素的查找表，查找成功时的平均查找长度为 2.7.2 顺序查找（线性查找） 最简单、常用的查找技术。 基本思想：从第一个记录开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于给定值K，则表明查找成功，返回该元素的下标；反之，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则表明查找失败，返回特定的值(常用?1表示)。 本节的有关查找和排序算法中，假设线性表均 采用顺序存储结构，其类型说明为： #define MAXLEN n //查找表中元素个数的最大可能值 struct element{ int key; int otherterm; //除关键字外其他数据项 }; typedef struct element DATATYPE; DATATYPE table[MAXLEN]; 算法2-1 顺序查找算法。 int seqsearch1(DATATYPE A[], int k) { int i; i=0; while((A[i].key!=k)(iMAXLEN)) i++; if(A[i].key==k) return i; /*查找成功，返回被查元素在表中的相对位置*/ else return –1; /*查找失败，返回–1*/ } 若对此算法进行一些改进，在原表长n基础上在表尾增加一个关键字为指定值K的记录，可避免每“比较”一次，就要判别查找是否结束。当n很大时，大约可节省一半的时间。 算法2-2 改进的顺序查找算法。 #define MAXLEN n+1 int seqsearch2(DATATYPE A[],int k) { int i; i=0; A[MAXLEN-1].key=k; while (A[i].key!=k) i++; if(i(MAXLEN-1)) return i; /*查找成功，返回被查元素在表中的相对位置*/ else return –1; /*查找失败，返回?1*/ } 将A[MAXLEN-1](第n+1个记录)称作监视哨。 下面对改进后的算法进行一下性能分析，计算它的平均查找长度。 对含有n个记录的表，查找成功时的平均查找长度为 从顺序查找的过程看，Ci取决于所查元素在表中的位置，对于第一个记录只要比较一次，对第n个记录，需要比较n次，查找记录A[i]时，比较i次。设每个记录的查找概率相等，则Pi=1/n 。故此算法在等概率情况下查找成功的平均查找长度为 2.7.3 对分查找 如果查找表中的记录按关键字有序，则可以采用一种高效率的查找方法——对分查找，也称二分查找。 对分查找的基本思想是：对于有序表，查找时先取表中间位置的记录关键字和所给关键字进行比较，若相等，则查找成功；如果给定值比该记录关键字大，则在后半部分继续进行折半查找；否则在前半部分进行折半查找，直到找到或者查找范围为空而查不到为止。 对分查找的过程实际上是先确定待查元素所在的区域，然后逐步缩小区域，直到查找成功或失败为止。