第九章查找与排序 顺序查找是一种最基本和最简单的查找方法。它 的思路是,从表中的第一个元素开始,将给定 的值与表中逐个元素的关键字进行比较,直到 两者相符,查到所要找的元素为止。否则就是 表中没有要找的元素,查找不成功。对于表中 记录的关键字是无序的表,只能采用这种方法 描述顺序査找的算法见框图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,成功,否则 若krmid]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,成功，否则： 若 kr[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 ((lowr[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很大时，该方法尤其能显示出其时间效率。 但由于折半查找的表仍是线性表，若经常要进 行插入、删除操作，则元素排列费时太多，因 此折半查找比较适合于一经建立就很少改动而 又需要经常查找的线性表，较少查找而又经常 需要改动的线性表可以采用链接存储，使用顺 序查找
分块查找 在处理线性表时,如果既希望能够快速查找,又要经常 动态变化,则可以采用分块査找方法。分块查找又称 索引顺序查找,要求将待查的元素均匀的分成块,块 间按大小排序,块内不排序。因此需要建立一个块的 最大(或最小)关键字表,称之为“索引表”。 具体而言,假设我们按结点元素关键字升序方式组织表 中各块,则要求第一块中任一结点的关键字值都小于 第二块中所有结点的关键字值:第二块中任一结点的( 关键字值都小于第三块中所有结点的关键字值;如此 类推。然后选择每块中的最大(或最小)关键字值组 成索引表。换言之,索引表中的结点个数等于线 被分割的块数 下一顶
返回本章首页 下一页 上一页 分块查找 在处理线性表时，如果既希望能够快速查找，又要经常 动态变化，则可以采用分块查找方法。分块查找又称 索引顺序查找，要求将待查的元素均匀的分成块，块 间按大小排序，块内不排序。因此需要建立一个块的 最大（或最小）关键字表，称之为“索引表” 。 具体而言，假设我们按结点元素关键字升序方式组织表 中各块，则要求第一块中任一结点的关键字值都小于 第二块中所有结点的关键字值；第二块中任一结点的 关键字值都小于第三块中所有结点的关键字值；如此 类推。然后选择每块中的最大（或最小）关键字值组 成索引表。换言之，索引表中的结点个数等于线性表 被分割的块数
例如要找关键字为k的元素,则先用折半查找法由索引表查出k所在的块,再 用顺序查找法在对应的块中找出k。在图8-2中若要找关键字值为41的元 素,则先由索引表查出41在第二块中(29<41<64),再在第二块中找到 由此我们可以总结:分块査找分两步进行,第一步确定要查找结点在表中的 哪一块,第二步在确定的块中找到该结点。 分块查找的平均查找长度为: ASL=ASLb+ASLe 其中ASLb是折半查找的平均查找长度,ASLe是用顺序查找法查块内元素的 平均查找长度。设每块中有s个元素,可以近似的得到: 可以看出分块查找的平均查找长度位于顺序查找和折半查找之间。 下面我们简单的对以上几种查找方法做出比较: (1)平均查找长度:折半查找最小,分块查找次之,顺序查找最大 (2)表的结构:顺序查找对有序表、无序表均适用;折半查找仅适用于 序表:分块查找要求表中元素是逐段有序的,就是块与块之间的记录↓ 关键字有序 (3)存储结构:顺序查找和分块查找对向量和线性链表结构均适用;折半 查找只适用于向量存储结构的表,因而要求表中元素基本不变 要插入或删除运算时,要移动元素,才能保持表的有序性,所以影响 查找效率
返回本章首页 下一页 上一页 例如要找关键字为k的元素，则先用折半查找法由索引表查出k所在的块，再 用顺序查找法在对应的块中找出k。在图8-2中若要找关键字值为41的元 素，则先由索引表查出41在第二块中（29<41<64），再在第二块中找到 41。 由此我们可以总结：分块查找分两步进行，第一步确定要查找结点在表中的 哪一块，第二步在确定的块中找到该结点。 分块查找的平均查找长度为： ASL=ASLb+ASLe 其中ASLb是折半查找的平均查找长度，ASLe是用顺序查找法查块内元素的 平均查找长度。设每块中有s个元素，可以近似的得到： 可以看出分块查找的平均查找长度位于顺序查找和折半查找之间。 下面我们简单的对以上几种查找方法做出比较： （1）平均查找长度：折半查找最小，分块查找次之，顺序查找最大； （2）表的结构：顺序查找对有序表、无序表均适用；折半查找仅适用于有 序表；分块查找要求表中元素是逐段有序的，就是块与块之间的记录按 关键字有序； （3）存储结构：顺序查找和分块查找对向量和线性链表结构均适用；折半 查找只适用于向量存储结构的表，因而要求表中元素基本不变，而在需 要插入或删除运算时，要移动元素，才能保持表的有序性，所以影响了 查找效率
哈希法 哈希法又名散列法,因其英文单词Hash而得名,是一种完全不同的查找方法 前面我们所介绍的三种查找方法的共同特点在于:通过对关键字的一系 列比较,逐步缩小査找范围,直到确定结点的存储位置或确定査找失败 而哈希法则希望不经过任何比较,一次存取就能得到所査元素,因此必 须在记录的存储位置和它的关键字之间建立一个确定的对应关系,使得 每个关键字和结构中一个唯一的存储位置相对应,这样查找时只需对结 点的关键字进行某种运算就能确定结点在表中的位置。因此哈希法的平 均比较次数和表中所含结点的个数无关。 打个比方让我们更清楚的认识哈希法的不同。假定某教室有35个座位,如果 不加限定让学生任意就座,则要找某个学生时就要将待找学生与当前座 位上的学生二一做比较,这就是我们前面所介绍的查找方法的大致思路( 而哈希法则要限定学生所坐的位置,比如可规定学生座位的编号应与其 学号的末两位相同,则学号为993605的学生应坐编号为5的座位。这样我 们要找某个学生时只需根据其学号的末两位到相应座位上去找即可 必 比较了。在这个例子里,学生好比记录学号则为关键字对 键字进行的操作则是取其末两位,用以确定记录的
返回本章首页 下一页 上一页 哈希法 哈希法又名散列法,因其英文单词Hash而得名,是一种完全不同的查找方法。 前面我们所介绍的三种查找方法的共同特点在于：通过对关键字的一系 列比较，逐步缩小查找范围，直到确定结点的存储位置或确定查找失败。 而哈希法则希望不经过任何比较，一次存取就能得到所查元素，因此必 须在记录的存储位置和它的关键字之间建立一个确定的对应关系，使得 每个关键字和结构中一个唯一的存储位置相对应，这样查找时只需对结 点的关键字进行某种运算就能确定结点在表中的位置。因此哈希法的平 均比较次数和表中所含结点的个数无关。 打个比方让我们更清楚的认识哈希法的不同。假定某教室有35个座位，如果 不加限定让学生任意就座，则要找某个学生时就要将待找学生与当前座 位上的学生一一做比较，这就是我们前面所介绍的查找方法的大致思路。 而哈希法则要限定学生所坐的位置，比如可规定学生座位的编号应与其 学号的末两位相同，则学号为993605的学生应坐编号为5的座位。这样我 们要找某个学生时只需根据其学号的末两位到相应座位上去找即可，不 必一一比较了。在这个例子里，学生好比记录，学号则为关键字，对关 键字进行的操作则是取其末两位，用以确定记录的位置
哈希函数的构造方法 个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内,以尽可能减 少冲突。但鉴于实际问题中关键字的不同,没法构造出统一的哈希函数。从而构 造哈希函数的方法多种多样,这里只介绍一些比较常用的、计算较为简便的方法 1.自身函数 关键字自身作为哈希函数,即H(k)=k,也可自身加上一个常数作为哈希函数,即 H(k=k+c。例如上例中建立的哈希函数H(学号=学号-9900采用的就是这样的方法。 但这种函数只适用于给定的一组关键字为关键字集合中的全体元素的情况,故不 常用。 2.除余法 选择一个适当的正整数m,用m去除关键字,取其余数作为散列地址,即H(y =key%m。上例中后来所设定的函数H(学号)学号%10.用的就是除余法。 但是在这种方法中,m的选择是值得研究的。如果选择关键字内部代码基数的幂次 除关键字,其结果必定是关键字的低位数字均匀性较差。若取m为任意偶数,则 当关键字内部代码为偶数时,得到的哈希函数值为偶数;若关键字内部代码为奇 数,则哈希函数值为奇数。因此,m为偶数也是不好的。理论分析和试 证明m应取小于存储区容量的素数。 下一顶
返回本章首页 下一页 上一页 哈希函数的构造方法 一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减 少冲突。但鉴于实际问题中关键字的不同，没法构造出统一的哈希函数。从而构 造哈希函数的方法多种多样，这里只介绍一些比较常用的、计算较为简便的方法。 1．自身函数 关键字自身作为哈希函数，即H（k）=k，也可自身加上一个常数作为哈希函数，即 H(k)=k+c。例如上例中建立的哈希函数H(学号)=学号-9900采用的就是这样的方法。 但这种函数只适用于给定的一组关键字为关键字集合中的全体元素的情况，故不 常用。 2．除余法 选择一个适当的正整数m，用m去除关键字，取其余数作为散列地址，即H（key） =key%m。上例中后来所设定的函数H(学号)=学号%10采用的就是除余法。 但是在这种方法中，m的选择是值得研究的。如果选择关键字内部代码基数的幂次来 除关键字，其结果必定是关键字的低位数字均匀性较差。若取m为任意偶数，则 当关键字内部代码为偶数时，得到的哈希函数值为偶数；若关键字内部代码为奇 数，则哈希函数值为奇数。因此，m为偶数也是不好的。理论分析和试验结果均 证明m应取小于存储区容量的素数
查找:根据给定的某个值,在表中确定一个关键字等于给定值的记录或数据 元素。 关键字( Keyword):一个或一组能唯一标识该记录的数据项称为该记录的关 键字。 平均查找长度( Average Search Length):为确定记录在表中的位置所进行 的和关键字的比较的次数的期望值称之为査找算法的平均查找长度,简 称ASI 有序表:表中的各元素按关键字的值有序(升序或降序)存放。 哈希表:将结点的关键字key作为自变量,通过一个确定的函数关系H,计算 出相应的函数值H(key),然后以Hkey)作为该结点的存储单元地址。用这 种方式建立起来的线性表称为哈希表或叫散列表 哈希函数:把结点关键字转换为该结点存储单元地址的函数H称为哈希函数 或叫散列函数。 在学习这些概念的基础上,我们先后学习了三种基于将待查元素的关键字 表中元素的关键字进行比较的查找算法,即顺序查找、折半查找和分块(上X 查找,并对它们做出比较。我们也学习了一种不同的查找算法,即哈希 法,它的基本思路是:在记录的存储位置和它的关键字之间建立一个确 定的对应关系,使得每个关键字和结构中—个唯一的存储位置相对应 这样査找时只需对结点的关键字进行某种运算就能确定结点在表中 置,其间我们知道了如何构造哈希函数和如何解决冲突问题。读应熟 悉各种查找算法的思路、算法及性能分桕,以灵活应于各种实示问题
返回本章首页 下一页 上一页 查找：根据给定的某个值，在表中确定一个关键字等于给定值的记录或数据 元素。 关键字(Keyword)：一个或一组能唯一标识该记录的数据项称为该记录的关 键字。 平均查找长度（Average Search Length）：为确定记录在表中的位置所进行 的和关键字的比较的次数的期望值称之为查找算法的平均查找长度，简 称ASL。 有序表：表中的各元素按关键字的值有序（升序或降序）存放。 哈希表：将结点的关键字key作为自变量，通过一个确定的函数关系H，计算 出相应的函数值H(key)，然后以H(key)作为该结点的存储单元地址。用这 种方式建立起来的线性表称为哈希表或叫散列表 哈希函数：把结点关键字转换为该结点存储单元地址的函数H称为哈希函数 或叫散列函数。 在学习这些概念的基础上，我们先后学习了三种基于将待查元素的关键字和 表中元素的关键字进行比较的查找算法，即顺序查找、折半查找和分块 查找，并对它们做出比较。我们也学习了一种不同的查找算法，即哈希 法，它的基本思路是：在记录的存储位置和它的关键字之间建立一个确 定的对应关系，使得每个关键字和结构中一个唯一的存储位置相对应， 这样查找时只需对结点的关键字进行某种运算就能确定结点在表中的位 置，其间我们知道了如何构造哈希函数和如何解决冲突问题。读者应熟 悉各种查找算法的思路、算法及性能分析，以灵活应用于各种实际问题 中
排序 排序( sorting)是计算机程序设计中的一种重要操作,它 的功能是将一个数据元素(或记录)的任意序列,重 新排列成一个按关键字有序的序列 由于待排序的记录数量不同,使得排序过程中涉及的存 储器不同,可将排序方法分为两大类:一类是内部排 序,指的是待排序记录存放在计算机存储器中进行的 排序过程;另一类是外部排序,指的是待排序记录的( 数量很大,以致内存一次不能容纳全部记录,在排序 过程中对外存进行访问的排序过程。 下一顶
返回本章首页 下一页 上一页 排序 排序（sorting）是计算机程序设计中的一种重要操作，它 的功能是将一个数据元素（或记录）的任意序列，重 新排列成一个按关键字有序的序列。 由于待排序的记录数量不同，使得排序过程中涉及的存 储器不同，可将排序方法分为两大类：一类是内部排 序，指的是待排序记录存放在计算机存储器中进行的 排序过程；另一类是外部排序，指的是待排序记录的 数量很大，以致内存一次不能容纳全部记录，在排序 过程中对外存进行访问的排序过程
