软件基础第4章 查找和排序.pptVIP

第4章 查 找 和 排 序 4.1 线性表查找 4.1.1 顺序查找 4.1.2 折半查找 4.2 二叉排序树的查找 4.3 排序 4.3.1 直接插入排序 4.3.2 简单选择排序 4.3.3 冒泡排序 4.1 线性表查找 查找(Searching)，也称检索，亦即查表，就是在大量的信息集中寻找一个“特定的”信息元素。人们几乎每天都要做“查找”工作，如查寻电话号码、查字典、查图书目录卡片等。为确切定义查找，先引入几个概念。 查找表：由同一类型的数据元素(或记录)构成的集合。 关键字(key)：数据元素中可以惟一标识一个数据元素的数据项。例如在学校中，将每一个学生的数据信息作为一个记录，其中包括学号、姓名、性别、民族等。若要唯一地标识一个学生的记录，则必须用“学号”作为关键字；若用“姓名”，可能有重名而失去唯一性。查找就是根据给定的关键字的值，在一组数据中确定一个其关键字等于给定值的数据元素的过程。若存在这样的数据元素，则称查找是成功的，否则称查找不成功。 决定查找操作的是关键字，因此这里讨论时，只关注记录中的关键字域，而一概忽略记录中其它诸域的信息。 4.1.1 顺序查找 顺序查找是最简单、常用的查找技术。其基本思想是：从表的一端开始，依次将每个元素的关键字同给定值K进行比较，若某个元素的关键字等于给定值K，则表明查找成功，返回该元素的下标；反之，若直到所有元素都比较完毕，仍找不到关键字为K的元素，则表明查找失败，返回特定的值(常用?1表示)。 顺序查找方法既适用于以顺序存储结构组织的查找表的查找，也适用于以链式存储结构组织的查找表的查找。在本章的有关查找和排序算法中，假设线性表均采用顺序存储结构，其类型说明为： #define MAXLEN n /* n为查找表中元素个数的最大可能值*/ struct element{ int key; /*设关键字的类型为整型*/ int otherterm; /*为说明起见，除关键字外只有一个整型数据项*/ }; typedef struct element DATATYPE; DATATYPE table[MAXLEN]; 算法4-1 顺序查找算法。 int seqsearch1(DATATYPE A[], int k) /*返回关键字等于k的元素在表中的位置*/ { int i; i=0; while((A[i].key!=k)(iMAXLEN)) i++; if(A[i].key==k) return i; /*查找成功，返回被查元素在表中的相对位置*/ else return –1; /*查找失败，返回–1*/ } 若对此算法进行一些改进，在表尾增加一个关键字为指定值K的记录，可避免每“比较”一次，就要判别查找是否结束。当n很大时，大约可节省一半的时间。 算法4-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(iMAXLEN?1) return i; /*查找成功，返回被查元素在表中的相对位置*/ else return –1; /*查找失败，返回?1*/ } 将A[MAXLEN?1]称作监视哨，这个增加的记录起到了边界标识的作用。 下面对改进后的算法进行一下性能分析，计算它的平均查找长度。 为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值称为查找算法在查找成功时的平均查找长度。 　　 对于含有n个数据元素的查找表，查找成功的平均查找长度为：ASL=∑PiCi (i=1,2,3,…,n)可以简单以数学上的期望来这么理解。 其中：Pi 为查找表中第i个数据元素的概率，Ci为找到第i个数据元素时已经比较过的次数。 从顺序查找的过程看，Ci取决于所查元素在表中的位置，对于第一个记录只要比较一次，对第n个记录，需要比较n次，查找记录A[i-1]时，比较i次。设每个记录的查找概率相等，则Pi=1/n 。故此算法在等概率情况下查找成功的平均查找长度为 4.1.2 折半查找(二分查找) 如果查找表中的记录按关