例如要找关键字为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）是计算机程序设计中的一种重要操作，它 的功能是将一个数据元素（或记录）的任意序列，重 新排列成一个按关键字有序的序列。 由于待排序的记录数量不同，使得排序过程中涉及的存 储器不同，可将排序方法分为两大类：一类是内部排 序，指的是待排序记录存放在计算机存储器中进行的 排序过程；另一类是外部排序，指的是待排序记录的 数量很大，以致内存一次不能容纳全部记录，在排序 过程中对外存进行访问的排序过程