第八篇 查找.pptVIP

8.1 查找的基本概念 查找——也叫检索，是根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据元素 关键字——是数据元素中某个数据项的值，它可以标识一个数据元素 查找方法评价 查找速度 占用存储空间多少 算法本身复杂程度 平均查找长度ASL(Average Search Length)：为确定记录在表中的位置，需和给定值进行比较的关键字的个数的期望值叫查找算法的平均查找长度ASL= 8.1 查找的基本概念 若查找每个元素的概率相同，则平均查找长度的计算公式可简化为： ASL= 例如，在具有n个元素的线性表上顺序查找其关键字等于K的元素时，ci=i，所以平均查找长度为： 对应的时间复杂度为O(n)。 8.2 顺序表查找 顺序查找是一种最简单的查找方法。其基本思想是将查找表作为一个线性表，可以是顺序表，也可以是链表，依次用查找条件中给定的值与查找表中数据元素的关键字值进行比较，若某个记录的关键字值与给定值相等，则查找成功，返回该记录的存储位置，反之，若直到最后一个记录，其关键字值与给定值均不相等，则查找失败，返回查找失败标志。 8.2 顺序表查找 int Seqsch(struct ElemType A[], int n, KeyType K) { int i; /*从表头元素A[0]开始顺序向后查找，查找成功则退出循环*/ for(i=0; in; i++) if(A[i].key==K) break; /*查找成功则返回该元素的下标i，否则返回-1*/ if(in) return i; else return -1; } 8.2 顺序表查找 int Seqsch(struct ElemType A[], int n, KeyType K) { int i=0; A[n].key=K; while(A[i].key!=K) i++; if(in) return i; else return -1; } 8.2 顺序表查找 首先以整个查找表作为查找范围，用查找条件中给定值k与中间位置结点的关键字比较，若相等，则查找成功，否则，根据比较结果缩小查找范围，如果k的值小于关键字的值，根据查找表的有序性可知查找的数据元素只有可能在表的前半部分，即在左半部分子表中，所以继续对左子表进行折半查找；若k的值大于中间结点的关键字值，则可以判定查找的数据元素只有可能在表的后半部分，即在右半部分子表中，所以应该继续对右子表进行折半查找。每进行一次折半查找，要么查找成功，结束查找，要么将查找范围缩小一半，如此重复，直到查找成功或查找范围缩小为空即查找失败为止。 8.2 顺序表查找 8.2 顺序表查找 8.2 顺序表查找 int Binsch(struct ElemType A[], int n, KeyType K) { int low=0,high=n-1; while(low=high) { int mid=(low+high)/2; if (k==A[mid].key) return mid; else if (kA[mid].key) high=mid-1; else low=mid+1; } return –1; } 8.2 顺序表查找 8.3 索引查找 索引存储的基本思想是：首先把一个集合或线性表(它们对应为主表)按照一定的函数关系或条件划分成若干个逻辑上的子表，为每个子表分别建立一个索引项，由所有这些索引项构成主表的一个索引表，然后，可采用顺序或链接的方式来存储索引表和每个子表。索引表中的每个索引项通常包含三个域(至少包含前两个域)：一是索引值域(Index)，用来存储标识对应子表的索引值，它相当于记录的关键字，在索引表中由此索引值来惟一标识一个索引项，亦即惟一标识一个子表；二是子表的开始位置域(Start)，用来存储对应子表的第一个元素的存储位置；三是子表长度域(Length)，用来存储对应子表的元素个数。 8.3 索引查找 索引项的类型和顺序存储的索引表的类型可分别定义为： struct IndexItem {IndexKeyType index; int start; int lengt