《软件技术基础教程》第3章 查找与排序技术

第3章查找与排序技术 3,1线性表的查线技术 3,.2Hash表技术 3.3线性表的雄房技术 3.4素引查线 3.5拓扑外分类 PT PRESS 单击鼠标左键换页

第3章 查找与排序技术 3.1 线性表的查找技术 3.2 Hash表技术 3.3 线性表的排序技术 3.4 索引查找 3.5 拓扑分类

在数据处理领域中,最常见的运算是 在给定的数据结构中查找所需要处理的数 据元素。 另一常见的运算是对给定的数据结构 进行重新分类,或按数据元素的大小重新 进行排序,以方便对数据元素的处理。 查找与排序是数据处理的基本技术。 本章主要介绍线性表查找与排序的基本方 法,以及索引存储结构下的查找技术。 PT PRESS 单击鼠标左键换页

在数据处理领域中，最常见的运算是 在给定的数据结构中查找所需要处理的数 据元素。 另一常见的运算是对给定的数据结构 进行重新分类，或按数据元素的大小重新 进行排序，以方便对数据元素的处理。 查找与排序是数据处理的基本技术。 本章主要介绍线性表查找与排序的基本方 法，以及索引存储结构下的查找技术

31线性表的查找技术 3..1颁序字查龙 顺序查找的基本方法是,从线性表的第 个元素开始,依次将线性表中的元素与被查元素 进行比较,若遇到线性表中某位置上的元素与被 查元素相等,则表示找到(即查找成功);若线 性表中所有的元素与被查元素进行比较都不相等, 则表示线性表中不存在需要找的元素(即查找失 败)。 PT PRESS 单击鼠标左键换页

3.1 线性表的查找技术 3.1.1 顺序查找 顺序查找的基本方法是，从线性表的第一 个元素开始，依次将线性表中的元素与被查元素 进行比较，若遇到线性表中某位置上的元素与被 查元素相等，则表示找到（即查找成功）；若线 性表中所有的元素与被查元素进行比较都不相等， 则表示线性表中不存在需要找的元素（即查找失 败）

对于大的线性表来说,顺序查找的效 率是很低的。 3.1.2有序表的分查找 虽然顺序查找的效率不高,但在下列 两种情况下也只能采用顺序查找。 ①线性表为无序表(即表中元素的排 列是无序的) ②采用链式存储结构的有序线性表 PT PRESS 单击鼠标左键换页

对于大的线性表来说，顺序查找的效 率是很低的。 3.1.2 有序表的对分查找 虽然顺序查找的效率不高，但在下列 两种情况下也只能采用顺序查找。 ① 线性表为无序表（即表中元素的排 列是无序的） ②采用链式存储结构的有序线性表

先将线性表中的元素按值非递减进行 重新排列。 这样的线性表称为有序表。 设有序线性表的长度为n,被查元素 为x,则对分查找的方法如下 将x与线性表的中间项进行比较: 若被查元素x与该线性表的中间项的 值相等,则说明查到,查找结束 PT PRESS 单击鼠标左键换页

先将线性表中的元素按值非递减进行 重新排列。 这样的线性表称为有序表 。 设有序线性表的长度为n，被查元素 为x，则对分查找的方法如下。 将x与线性表的中间项进行比较： 若被查元素x与该线性表的中间项的 值相等，则说明查到，查找结束；

若被查元素x小于该线性表的中间项 的值,则取线性表的前半部分作为子表 (即取中间项以前的部分,而不再考虑线 性表后半部分的元素)以相同的方法进行 查找; 若被查元素x大于该线性表的中间项 的值,则取线性表的后半部分作为子表 (即取中间项以后的部分,而不再考虑线 性表前半部分的元素)以相同的方法进行 查找 PT PRESS 单击鼠标左键换页

若被查元素x小于该线性表的中间项 的值，则取线性表的前半部分作为子表 （即取中间项以前的部分，而不再考虑线 性表后半部分的元素）以相同的方法进行 查找； 若被查元素x大于该线性表的中间项 的值，则取线性表的后半部分作为子表 （即取中间项以后的部分，而不再考虑线 性表前半部分的元素）以相同的方法进行 查找

这个过程一直进行到查找成功或子表 长度为0(说明线性表中没有这个元素) 为止。 当有序线性表为顺序存储时才能采用 对分查找,并且,对分查找的效率要比顺 序査找高得多。 PT PRESS 单击鼠标左键换页

这个过程一直进行到查找成功或子表 长度为0（说明线性表中没有这个元素） 为止。 当有序线性表为顺序存储时才能采用 对分查找，并且，对分查找的效率要比顺 序查找高得多

32Hash表技术 3.2.1Hash表的基本概念 1.直接查找技术 设表的长度为n。 如果存在一个函数=i(k),对于 表中的任意一个元素的关键字k,满足 以下条件: PT PRESS 单击鼠标左键换页

3.2 Hash表技术 3.2.1 Hash表的基本概念 1．直接查找技术 设表的长度为n。 如果存在一个函数i = i(k)，对于 表中的任意一个元素的关键字k，满足 以下条件：

①1n。 ②对于任意的元素关键字k1≠k2, 恒存在i(k1)≠i(k2) 则称此表为直接查找表。 其中函数i=i(k)称为关键字k的映 象函数。 PT PRESS 单击鼠标左键换页

① 1≤i≤n。 ② 对于任意的元素关键字k1≠k2， 恒存在i(k1)≠i(k2)。 则称此表为直接查找表。 其中函数i = i(k)称为关键字k的映 象函数

对直接查找表的操作主要有以下两种 (1)直接查找表的填入 (2)直接查找表的取出 PT PRESS 单击鼠标左键换页

对直接查找表的操作主要有以下两种 （1）直接查找表的填入 （2）直接查找表的取出