8.2线性表的查找 821顺序查找 工顺查找的基本思想 顺序查找是一种最简单的查找方法,它的基本思想是: 从表的一端开始,顺序扫描线性表,依次将扫描到的 结点关键字和待找的值K相比较,若相等,则查找成 功,若整个表扫描完毕,仍末找到关键字等于K的元 素,则查找失败 顺序查找既适用于顺序表,也适用于链表。若用顺序 表,查找可从前往后扫描,也可从后往前扫描,但若 采用单链表,则只能从前往后扫描。另外,顺序查找 的表中元素可以是无序的 下面以顺序表的形式来描述算法
8．2 线性表的查找 8.2.1 顺序查找 1．顺序查找的基本思想 顺序查找是一种最简单的查找方法，它的基本思想是： 从表的一端开始，顺序扫描线性表，依次将扫描到的 结点关键字和待找的值Ｋ相比较，若相等，则查找成 功，若整个表扫描完毕，仍末找到关键字等于Ｋ的元 素，则查找失败。 顺序查找既适用于顺序表，也适用于链表。若用顺序 表，查找可从前往后扫描，也可从后往前扫描，但若 采用单链表，则只能从前往后扫描。另外，顺序查找 的表中元素可以是无序的。 下面以顺序表的形式来描述算法
2.顺序查找算法实现 const int n=maxn /n为表的最大长度 struct node elemtype key;/key为关键字,类型设定为 Teletype int seqsearch(node R[+ll,elemtype k) 在表R 中查找关键字值为K的元素 (RIOJ key=k; int i=n ∥从人表尾开始向前扫描 while(r[i]. key!=k) return 1;)
2．顺序查找算法实现 const int n=maxn //n为表的最大长度 struct node {… elemtype key; //key为关键字，类型设定为elemtype }; int seqsearch (node R[n+1],elemtype k) //在表Ｒ 中查找关键字值为Ｋ的元素 {R[0].key=k; int i=n; //从表尾开始向前扫描 while(R[i].key!=k) i--; return i;}
它?在函数 seqsearch中,若返回的值为0表示查找不成功, 否则查找成功。函数中查找的范围从R[n到R[1], R[0]为监视哨,起两个作用,其一,是为了省去判 定 while循环中下标越界的条件讼1,从而节省比较时 间,其二,保存要找值的副本,若査找时,遇到它, 表示查找不成功。若算法中不设立监视哨R[O],程序 花费的时间将会增加,这时的算法可写为下面形式。 int seqsearch( node r[n+l], elemtype k) while(R[i]key!=k)&&(1>=1)1-; return 当然上面算法也可以改成从表头向后扫描,将监视哨设在右 边,这种方法请读者自己完成
在函数seqsearch中，若返回的值为０表示查找不成功， 否则查找成功。函数中查找的范围从Ｒ[n]到Ｒ[１]， Ｒ[０]为监视哨，起两个作用，其一，是为了省去判 定 while循环中下标越界的条件i≥1，从而节省比较时 间，其二，保存要找值的副本，若查找时，遇到它， 表示查找不成功。若算法中不设立监视哨R[0]，程序 花费的时间将会增加，这时的算法可写为下面形式。 int seqsearch(node R[n+1]，elemtype k) {int i=n; while(R[i].key!=k)&&(i>=1) i--; return i; } 当然上面算法也可以改成从表头向后扫描，将监视哨设在右 边，这种方法请读者自己完成
3顺序查找性能分析 偎设在每个位置查找的概率相等,即有p=1/n,由于查 找是从后往前扫描,则有每个位置的查找比较次数C=1, Ca2,,C=n,于是,查找成功的平均查找ASL= ∑p:c→(n-+l)=2,即它的时间复杂度为O(n 这就是说,查找成功的平均比较次数约为表长的一半。 若k值不在表中,则必须进行n+1次比较之后才能确定查 入找失败。另处,从ASL可知,当n较大时,ASL值较大, 查找的效率较低。 顺序查找的优点是算法简单,对表结构无任何要求,无 论是用向量还是用链表来存放结点,也无论结点之间是 否按关键字有序或无序,它都同样适用。顺序查找的缺 点是查找效率低,当n较大时,不宜采用顺序查找,而 必须寻求更好的查找方法
3.顺序查找性能分析 假设在每个位置查找的概率相等，即有pi =1/n，由于查 找是从后往前扫描，则有每个位置的查找比较次数Cn =1， Cn-1 =2，…，C1=n，于是，查找成功的平均查找ASL= = = = ,即它 的时间复杂度为O(n)。 这就是说，查找成功的平均比较次数约为表长的一半。 若k值不在表中，则必须进行n+1次比较之后才能确定查 找失败。另处，从ASL可知，当n较大时，ASL值较大， 查找的效率较低。 = n i i i p c 1 = − + n i n n i 1 1 [ ( 1)] 2 n+1 顺序查找的优点是算法简单，对表结构无任何要求，无 论是用向量还是用链表来存放结点，也无论结点之间是 否按关键字有序或无序，它都同样适用。顺序查找的缺 点是查找效率低，当n较大时，不宜采用顺序查找，而 必须寻求更好的查找方法
822二分查找 1三分找的基本想 二分查找,也称折半查找,它是一种高效率的查找方法。 但二分查找有条件限制:要求表必须用向量作存贮结构, 且表中元素必须按关键字有序(升序或降序均可)。我们不 妨假设表中元素为升序排列。二分查找的基本思想是: 首先将待查值K与有序表R[]到R[n的中点md上的关键 字Rrmd]key进行比较,若相等,则查找成功;否则,若 R[md]key>k,则在R[到R[mid-1中继续查找,若有 R[md]key<k,则在R[md+1到R[n中继续查找。每通 过一次关键字的比较,区间的长度就缩小一半,区间的 个数就增加一倍,如此不断进行下去,直到找到关键字 为K的元素;若当前的查找区间为空(表示查找失败)
8.2.2二分查找 1.二分查找的基本思想 二分查找，也称折半查找，它是一种高效率的查找方法。 但二分查找有条件限制：要求表必须用向量作存贮结构， 且表中元素必须按关键字有序(升序或降序均可)。我们不 妨假设表中元素为升序排列。二分查找的基本思想是： 首先将待查值K与有序表R[1]到R[n]的中点mid上的关键 字R[mid].key进行比较，若相等，则查找成功；否则，若 R[mid].key>k ， 则在R[1]到R[mid-1]中继续查找，若有 R[mid].key<k ， 则在R[mid+1]到R[n]中继续查找。每通 过一次关键字的比较，区间的长度就缩小一半，区间的 个数就增加一倍，如此不断进行下去，直到找到关键字 为K的元素；若当前的查找区间为空(表示查找失败)