【软件技术基础】查找与排序技术.ppt
《【软件技术基础】查找与排序技术.ppt》由会员分享,可在线阅读,更多相关《【软件技术基础】查找与排序技术.ppt(81页珍藏版)》请在三一文库上搜索。
1、第3章 查找与排序技术,3.1 线性表的查找技术 3.2 Hash表技术 3.3 线性表的排序技术 3.4 索引查找 3.5 拓扑分类,在数据处理领域中,最常见的运算是在给定的数据结构中查找所需要处理的数据元素。 另一常见的运算是对给定的数据结构进行重新分类,或按数据元素的大小重新进行排序,以方便对数据元素的处理。 查找与排序是数据处理的基本技术。本章主要介绍线性表查找与排序的基本方法,以及索引存储结构下的查找技术。,3.1 线性表的查找技术,3.1.1 顺序查找 顺序查找的基本方法是,从线性表的第一个元素开始,依次将线性表中的元素与被查元素进行比较,若遇到线性表中某位置上的元素与被查元素相等
2、,则表示找到(即查找成功);若线性表中所有的元素与被查元素进行比较都不相等,则表示线性表中不存在需要找的元素(即查找失败)。,对于大的线性表来说,顺序查找的效率是很低的。 3.1.2 有序表的对分查找 虽然顺序查找的效率不高,但在下列两种情况下也只能采用顺序查找。 线性表为无序表(即表中元素的排列是无序的) 采用链式存储结构的有序线性表,先将线性表中的元素按值非递减进行重新排列。 这样的线性表称为有序表 。 设有序线性表的长度为n,被查元素为x,则对分查找的方法如下。 将x与线性表的中间项进行比较: 若被查元素x与该线性表的中间项的值相等,则说明查到,查找结束;,若被查元素x小于该线性表的中间
3、项的值,则取线性表的前半部分作为子表(即取中间项以前的部分,而不再考虑线性表后半部分的元素)以相同的方法进行查找; 若被查元素x大于该线性表的中间项的值,则取线性表的后半部分作为子表(即取中间项以后的部分,而不再考虑线性表前半部分的元素)以相同的方法进行查找。,这个过程一直进行到查找成功或子表长度为0(说明线性表中没有这个元素)为止。 当有序线性表为顺序存储时才能采用对分查找,并且,对分查找的效率要比顺序查找高得多。,3.2 Hash表技术,3.2.1 Hash表的基本概念 1直接查找技术 设表的长度为n。 如果存在一个函数i = i(k),对于表中的任意一个元素的关键字k,满足以下条件:,
4、1in。 对于任意的元素关键字k1k2,恒存在i(k1)i(k2)。 则称此表为直接查找表。 其中函数i = i(k)称为关键字k的映象函数。,对直接查找表的操作主要有以下两种 (1)直接查找表的填入 (2)直接查找表的取出,2Hash表 Hash表技术是直接查找技术的推广,其主要目标是提高查找效率。 如果按照直接查找表的填入方法,填入结果如表3.1所示。,设表的长度为n。 如果存在一个函数i = i(k),对于表中的任意一个元素的关键字k,满足1in,则称此表为Hash表。 其中函数i = i(k)称为关键字k的Hash码。,Hash表技术的关键是要处理好表中元素的冲突问题,它主要包括以下两
5、方面的工作: (1)构造合适的Hash码,以便尽量减少表中元素冲突的次数。 即Hash码的均匀性要比较好。 (2)当表中元素发生冲突时,要进行适当的处理。,3Hash码的构造 在实际设计Hash码时,要考虑以下两方面的因素: 使各关键字尽可能均匀地分布在Hash表中 。 Hash码的计算要尽量简单。,比较简单的Hash码的构造方法。 (1)截段法 (2)分段叠加法 (3)除法 (4)乘法,3.2.2 几种常用的Hash表 1线性Hash表 设线性Hash表的长度为n,对线性Hash表的查找过程如下。 (1)线性Hash表的填入 (2)线性Hash表的取出,线性Hash表的优点是简单,但它有以下
6、两个主要缺点。 当Hash码的冲突较多时,在线性Hash表中会存在“堆聚”现象,即许多关键字被连续登记在一起,从而会降低查找效率。,2随机Hash表 当Hash表的长度n设计成n = 2k时,还可以定义另外一种Hash表随机Hash表。 随机Hash表的填入与取出的过程。 (1)随机Hash表的填入 (2)随机Hash表的取出,3溢出Hash表 前面所介绍的线性Hash表与随机Hash表均存在两个致命的缺点:一是在Hash表填入过程中不顾后效,从而在填入过程中其冲突的机会在不断增多;二是当Hash表填满时,不能正常地进行查找。,如果将冲突的元素安排在另外的空间内,不占用Hash表本身的空间,就
7、不会产生新的冲突。 这就是溢出Hash表。 溢出Hash表包括Hash表和溢出表两部分。,溢出Hash表的填入与取出的过程。 (1)溢出Hash表的填入 (2)溢出Hash表的取出,4拉链Hash表 拉链Hash表又分为外链Hash表与内链Hash表。 外链Hash表由Hash表及表外结点组成。 Hash表的第i项登记着Hash码为i的所有关键字的表外结点。 在初始状态下,Hash表中的所有指针为空。,外链Hash表的填入与取出过程如下。 (1)外链Hash表的填入 填入后的外链Hash表如图3.1所示。 (2)外链Hash表的取出,5指标Hash表 指标Hash表包括指标表与内容表两部分。,
8、3.3 线性表的排序技术,排序是指将一个无序序列整理成按值非递减顺序排列的有序序列。 排序的方法有很多,根据待排序序列的规模、存储结构以及对数据处理的要求,可以采用不同的排序方法。 本节主要介绍针对顺序表的常用排序法。,3.3.1 互换排序 互换排序是指借助数据元素之间的互相交换进行排序的一种方法。 1冒泡排序 冒泡排序是通过相邻数据元素的交换逐步将线性表变成有序。,冒泡排序的基本方法如下。 首先,从表头开始往后扫描线性表,在扫描过程中逐次比较相邻两个元素的大小。 然后,从后到前扫描剩下的线性表,同样,在扫描过程中逐次比较相邻两个元素的大小。,在上述排序过程中,对线性表的每一次来回扫描,都将其
9、中的最大者沉到了表的底部,最小者像气泡一样冒到表的前头,冒泡排序由此而得名。 冒泡排序又称下沉排序。 图3.2是冒泡排序的示意图。,2快速排序 快速排序的关键是对线性表的分割,以及对各分割出的子表再进行分割,这个过程如图3.3所示。 快速排序在最坏情况下需要n(n 1)/2次比较,但实际的排序效率要比冒泡排序高得多。,3.3.2 插入排序 插入排序是指将无序序列中的各元素依次插入到已经有序的线性表中。 1简单插入排序 首先将第j个元素放到一个变量T中。然后从有序子表的最后一个元素(即线性表中第j 1个元素)开始,往前逐个与T进行比较,将大于T的元素均依次向后移动一个位置,直到发现一个元素不大于
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 软件技术基础 软件技术 基础 查找 排序 技术
链接地址:https://www.31doc.com/p-11886587.html