第九章查找与排序 顺序查找是一种最基本和最简单的查找方法。它 的思路是,从表中的第一个元素开始,将给定 的值与表中逐个元素的关键字进行比较,直到 两者相符,查到所要找的元素为止。否则就是 表中没有要找的元素,查找不成功。对于表中 记录的关键字是无序的表,只能采用这种方法 描述顺序査找的算法见框图8-1。其中n是表r的 长度,k是要查的元素的关键字,请到的元素 的序号。 道闹最
返回本章首页 下一页 上一页 第九章查找与排序 顺序查找是一种最基本和最简单的查找方法。它 的思路是，从表中的第一个元素开始，将给定 的值与表中逐个元素的关键字进行比较，直到 两者相符，查到所要找的元素为止。否则就是 表中没有要找的元素，查找不成功。对于表中 记录的关键字是无序的表，只能采用这种方法。 描述顺序查找的算法见框图8-1。其中n是表r的 长度，k是要查的元素的关键字，i查到的元素 的序号。 上一章 下一章 返回目录
折半查找又称二分查找,是针对有序表进行查找的简单 有效而又较常用的方法。所谓有序表,即要求表中的 各元素按关键字的值有序(升序或降序)存放 折半查找不像顺序查找那样,从第一个记录开始逐个顺 序搜索,其基本思想是:首先选取表中间位置的记录 将其关键字与给定关键字k进行比较,若相等,则查找 成功;否则,若k值比该关键字值大,则要找的元素 定在表的后半部分(或称右子表),则继续对右子表 进行折半查找;若k值比该关键字值小,则要找的元素 定在表的前半部分(左子表),同样应继续对左子 表进行折半查找。每进行一次比较,要么找到要查拌 的元素,要么将査找的范围缩小一半。如此递推, 到査找成功或把要查找的范围缩小为空(查找失败)。 设表的长度为n,表的被查找部分的头为low,尾为bign, 初始时,low=1,high=nk为关键净的 下一顶
返回本章首页 下一页 上一页 折半查找又称二分查找，是针对有序表进行查找的简单、 有效而又较常用的方法。所谓有序表，即要求表中的 各元素按关键字的值有序（升序或降序）存放。 折半查找不像顺序查找那样，从第一个记录开始逐个顺 序搜索，其基本思想是：首先选取表中间位置的记录， 将其关键字与给定关键字k进行比较，若相等，则查找 成功；否则，若k值比该关键字值大，则要找的元素一 定在表的后半部分（或称右子表），则继续对右子表 进行折半查找；若k值比该关键字值小，则要找的元素 一定在表的前半部分（左子表），同样应继续对左子 表进行折半查找。每进行一次比较，要么找到要查找 的元素，要么将查找的范围缩小一半。如此递推，直 到查找成功或把要查找的范围缩小为空（查找失败）。 设表的长度为n，表的被查找部分的头为low，尾为high， 初始时，low=1,high=n,k为关键字的值
lowthi gh (1)计算中间记录的序号md[2 ,取整; (2)若k=r[md]key,成功,否则 若k<rmid]key,则high=mid-1,重复(1) 若k>rmid]key,则ow=mid+1,重复(1) 直到成功或不成功(此时 w>high)。 具体算法如下: Void binsrch(struct node r[ l, int n, int k) i int mid, low, high, find low-l: high-n, find=0 /置区间初值* while((low<=high)&&(find)) i mid=(low+high)/2 /求中点* if(k==r[]. key) find=1 己查到* else if(krImid] key low=mid+1;/*在后半区间查找* else high=mid-1 /*在前半区间查找* if(find) return(mid) 查找成功,返回找到元素的位置* else return(O) 查找 下一顶
返回本章首页 下一页 上一页 （2）若k=r[mid].key,成功，否则： 若 k<r[mid].key, 则high=mid―1,重复（1）； 若k>r[mid].key, 则low=mid+1,重复（1）； 直到成功或不成功（此时low>high）。 具体算法如下： Void binsrch(struct node r[ ],int n,int k) { int mid,low,high,find; low=1; high=n;find=0; /*置区间初值*/ while ((low<=high) && (!find)) { mid=(low+high)/2; /*求中点*/ if (k= = r[mid].key) find=1; /*已查到*/ else if(k>r[mid].key ) low=mid+1; /*在后半区间查找*/ else high=mid-1; /*在前半区间查找*/ } if (find) return (mid); /*查找成功，返回找到元素的位置*/ else return (0); /*查找不成功，返回0标记*/ }
采用折半查找,当查找成功时,最少比较次数为 次,如在上例中查找关键字值为18的结点, 只需一次比较。最多经过log2n次比较之后,待 查找子表要么为空,要么只剩下一个结点,所 以要确定查找失败需要log2n次或lg2n+1次比 较。可以证明,折半查找的平均查找长度是: 从折半查找的平均查找长度ASL来看,当表的长 度n很大时,该方法尤其能显示出其时间效率。 但由于折半查找的表仍是线性表,若经常要进 行插入、删除操作,则元素排列费时太多,因 此折半查找比较适合于一经建立就很少改动而 又需要经常査找的线性表,较少查找而又经常 需要改动的线性表可以采用链接存储,使 序查找。 下一顶
返回本章首页 下一页 上一页 采用折半查找，当查找成功时，最少比较次数为 一次，如在上例中查找关键字值为18的结点， 只需一次比较。最多经过log2n次比较之后，待 查找子表要么为空，要么只剩下一个结点，所 以要确定查找失败需要log2n次或log2n+1次比 较。可以证明，折半查找的平均查找长度是： 从折半查找的平均查找长度ASL来看，当表的长 度n很大时，该方法尤其能显示出其时间效率。 但由于折半查找的表仍是线性表，若经常要进 行插入、删除操作，则元素排列费时太多，因 此折半查找比较适合于一经建立就很少改动而 又需要经常查找的线性表，较少查找而又经常 需要改动的线性表可以采用链接存储，使用顺 序查找
分块查找 在处理线性表时,如果既希望能够快速查找,又要经常 动态变化,则可以采用分块査找方法。分块查找又称 索引顺序查找,要求将待查的元素均匀的分成块,块 间按大小排序,块内不排序。因此需要建立一个块的 最大(或最小)关键字表,称之为“索引表”。 具体而言,假设我们按结点元素关键字升序方式组织表 中各块,则要求第一块中任一结点的关键字值都小于 第二块中所有结点的关键字值:第二块中任一结点的( 关键字值都小于第三块中所有结点的关键字值;如此 类推。然后选择每块中的最大(或最小)关键字值组 成索引表。换言之,索引表中的结点个数等于线 被分割的块数 下一顶
返回本章首页 下一页 上一页 分块查找 在处理线性表时，如果既希望能够快速查找，又要经常 动态变化，则可以采用分块查找方法。分块查找又称 索引顺序查找，要求将待查的元素均匀的分成块，块 间按大小排序，块内不排序。因此需要建立一个块的 最大（或最小）关键字表，称之为“索引表” 。 具体而言，假设我们按结点元素关键字升序方式组织表 中各块，则要求第一块中任一结点的关键字值都小于 第二块中所有结点的关键字值；第二块中任一结点的 关键字值都小于第三块中所有结点的关键字值；如此 类推。然后选择每块中的最大（或最小）关键字值组 成索引表。换言之，索引表中的结点个数等于线性表 被分割的块数