第三章查找与排序技术

第三章

查找与排序技术1河海大学能源与电气学院3.1基本的查找技术

查找是数据处理领域的一个重要内容,查找的效率将直接影响到数据处理的效率.

所谓查找是指在一个给定的数据结构中查找某个指定的元素.通常,根据不同的数据结构,应采用不同的查找方法.2河海大学能源与电气学院基本的查找技术包括:顺序查找有序表的对分查找分块查找3河海大学能源与电气学院3.1.1顺序查找顺序查找又称顺序搜索.顺序查找一般是指在线性表中查找指定的元素.基本方法:

从线性表的第一个元素开始查找,依次将线性表中的元素与要查找的元素进行比较,如相等则查找成功,否则继续查找直到线性表的最后元素,若线性表的所有元素与被查元素都不相等,则表示线性表中没有要查的元素(查找失败).4河海大学能源与电气学院

当要查找的元素在线性表中比较靠前的位置时,顺序查找效率较高,查找的元素在线性表中比较靠后的位置时,顺序查找效率较低.

在平均情况下,利用顺序查找法在线性表中查找一个元素,大约要与线性表中一半的元素进行比较.5河海大学能源与电气学院

对于大的线性表来说,顺序查找的效率是比较低的,但在以下两种情况下也只能采用顺序查找:(1)线性表为无序表(表中的元素的排列是无序的),则顺序存储和链式存储结构都只能采用顺序查找.(2)即使是有序线性表,如果采用链式存储结构,只能采用顺序查找.6河海大学能源与电气学院顺序查找算法的C++实现实例:#include<stdio.h>#defineMAXL100/*定义表中最多记录个数*/typedef

int

KeyType;typedefcharInfoType[10];typedef

struct

{KeyTypekey;/*KeyType为关键字的数据类型*/

InfoTypedata;/*其他数据*/}NodeType;

typedef

NodeType

SeqList[MAXL];/*顺序表类型*/int

SeqSearch(SeqList

R,int

n,KeyTypek)/*顺序查找算法*/{inti=0;while(i<n&&R[i].key!=k){printf("%d",R[i].key);i++;/*从表头往后找*/}if(i>=n)return-1;else{printf("%d",R[i].key);returni;}}7河海大学能源与电气学院voidmain(){SeqListR;

intn=11;

KeyTypek=90;

inta[]={16,74,60,43,54,90,46,31,29,88,77},i;for(i=0;i<n;i++)/*建立顺序表*/

R[i].key=a[i];

printf("\n");if((i=SeqSearch(R,n,k))!=-1)

printf("\n元素%d的位置是%d\n",k,i);else

printf("\n元素%d不在表中\n",k);

printf("\n");}

顺序查找a[]数组,要查找的数是k.本例16,74,60,43,54,90,46,31,29,88,77中查找90.8河海大学能源与电气学院3.1.2有序表的对分查找对分查找只适用于顺序存储的有序表(线性表中的元素按值非递减排列的,从小到大,但允许相邻元素值相等)

设有序线性表的长度为n,被查元素为x,对分查找的方法如下:

将x与线性表的中间项进行比较:若中间项的值等于x,则查到,查找结束,若x小于中间项的值,则在线性表的前半部分以相同的方法查找;若x大于中间项的值,则在线性表的后半部分以相同的方法查找.

直到查找成功或子表长度为0(线性表没有这个元素)为止.9河海大学能源与电气学院

当然这种查找是以线性表为有序为前提的,相比于顺序查找,对长度为n的有序线性表进行查找,最坏情况下,对分查找只要比较,而顺序查找要比较n次.10河海大学能源与电气学院对分查找流程图:YYN开始i

1,j

10计算midd(mid)=key?Ni

mid+1j

mid-1N继续查找？输出“未找到”Y输出找到的信息结束i≤jmid=(i+j)\211河海大学能源与电气学院3.1.3分块查找分块查找又称索引顺序查找.它是一种顺序查找的改进方法,用于在分块有序表中进行查找.

分块有序查找是指将长度为n的线性表分为m个子表,m个子表长度可以相等或不等,但要求后一个子表中的每一个元素均大于前一个子表中的所有元素.12河海大学能源与电气学院分块有序表的结构分为两部分:(1)线性表本身采用顺序存储结构.(2)建立一个索引表.在索引表中对线性表的每一个子表建立索引结点,结点包括两个域:一数据域,存放对应子表的最大元素值,二指针域,用于指示对应子表的第一个元素在整个线性表中的序号.13河海大学能源与电气学院根据分块有序表的结构,其过程分为以下两步:(1)先查找索引表，因其有序，故可采用二分法查找，以确定待查记录在哪一块.(2)在已确定的块中进行顺序查找.

14河海大学能源与电气学院3.2哈希表技术

在3.1节中介绍的查找方法都是通过被查元素与表中的元素进行直接比较.本节将要介绍Hash表技术是另一类重要的查找技术.Hash表技术的基本思想是对被查元素的关键字做某种运算后直接确定所要查找项目在表中的位置.15河海大学能源与电气学院1.直接查找技术设表的长度为n.如果存在一个函数i=i(k),对于表中的任意一个元素的关键字k,满足以下条件:①1≤i≤n②对于任意的元素关键字k1≠k2,恒存在i(k1)≠i(k2),称此表为直接查找表.函数i=i(k)称为关键字k的印象函数.16河海大学能源与电气学院对直接查找表的操作主要有以下两种:(1)直接查找表的填入①计算关键字k的印象函数i=i(k).②将关键字k及有关元素信息填入到表的第i项.(2)直接查找表的取出.①计算关键字k的印象函数i=i(k)②检查表中的第i项:

若第i项为空,则说明表中没有关键字为k的元素;否则取出第i项中的元素即可.17河海大学能源与电气学院2.Hash表

Hash表技术是直接查找技术的推广,其主要目标是提高查找效率.Hash表技术的关键是要处理好表中元素的冲突问题,它主要包括以下两方面的工作:(1)构造合适的Hash码,以便尽量减少表中元素的冲突的次数,即Hash码的均匀性要比较好.(2)当表中元素发生冲突时,要进行适当的处理.18河海大学能源与电气学院3Hash码的构造

Hash表技术的主要目标是提高查找效率,即要缩短查表的时间.因此,在实际设计Hash码时,要考虑以下两方面的因素.(1)使各关键字尽可能地分布在Hash表中,即Hash码的均匀性比较好,以便减少冲突发生的机会.(2)Hash码的计算要尽量简单.

通常以上两个方面在实际应用中是相互矛盾的,因此在实际设计Hash码时,要根据具体情况,选择一个合理的方案.19河海大学能源与电气学院下面介绍一些比较简单的Hash码的构造方法:(1)截断法截断法,是指与关键字对应的数字串中的一段(一般选取低位数)作为该关键字的Hash码.(2)分段叠加法分段叠加法是将关键字的编码串分割为若干段,然后把他们叠加后再进行截断.(3)除法这种方法是将关键字的编码除以表的长度,最后所得的余数作为Hash码,即取Hash码为20河海大学能源与电气学院

为关键字,n为Hash表的长度,mod为模余运算符.(4)乘法将关键字编码与一个常数相乘后,再除以表长度n,取其余数作为Hash码,即或者将关键字编码与相乘后,取乘积低位段中的若干二进制(进行截断)作为Hash码.21河海大学能源与电气学院3.2.2几种常用的哈希表1.线性Hash表线性Hash表是一种最简单的Hash表.设线性Hash表的长度为n,对线性Hash表的查找过程如下所述:(1)线性Hash表的填入①计算关键字k的Hash码②检查表中第i项的内容i=i(k)若第i项为空,则将关键字k及有关信息填入该项.22河海大学能源与电气学院

若第i项不空,则令i=mod(i+1,n),转②继续检查.(2)线性Hash表的取出.①计算关键字k

的Hash码i=i(k)②检查表中第i项的内容:若第i项登记着关键字k则取出该项元素即可;若第i项为空,则表示在Hash表中没有该关键字的信息;若第i项不为空,且登记的不是关键字k

则令i=mod(i+1,n)

转②继续检查.23河海大学能源与电气学院线性Hash表的这种处理冲突的方法又称为开放法.线性Hash表的优点是简单,但是它有以下两个主要缺点:(1)在线性Hash表填入的过程中,当发生冲突时,首先考虑的是下一项,因此,当Hash码的冲突较多时,在线性Hash表中会存在”堆聚”现象,即许多关键字被连续登记在一起,从而会降低查找效率.(2)在线性Hash表的填入过程中,处理冲突会带来新的冲突.24河海大学能源与电气学院

在线性Hash表中,查找一个关键字的平均查找次数为:其中称为Hash表的填满率(也称为装填因子),它定义为其中n为Hash表的长度,m为Hash表中实际存在的关键字个数.25河海大学能源与电气学院例3.3将关键字(09,31,26,19,01,13,02,11,27,16,05,21)依次填入长度为n=12的线性Hash表中.设Hash码为i=INT(k/3)+1.填入后的Hash表如下表:线性Hash表26河海大学能源与电气学院2.随机Hash表当Hash表的长度n设计成时,还可以定义另外一种Hash表－随机Hash表.随机Hash表与线性Hash表的不同之处在于:一旦发生元素冲突时,表项序号i的改变不是采用加1取模的方法,而是用某种伪随机数来改变.随机Hash表的填入和取出的过程:(1)随机Hash表的填入①计算关键字k的Hash码,且令②伪随机数序列初始化,令j=1.③检查表中第i项的内容:27河海大学能源与电气学院

若第i项为空,则将关键字k及有关信息填入该项;

若第i项不空,则令,并令j=j+1,转③继续检查.(2)随机Hash表的取出①计算关键字k的Hash码,且②伪随机数序列初始化,令j=1.③检查表中第i项的内容:28河海大学能源与电气学院

若第i项登记着关键字k,则取出该项元素即可.

若第i项为空,则表示在Hash表中没有该关键字的信息.若第i项不空,则令,并令j=j+1,转③继续检查.在随机Hash表中,查找一个关键字的平均查找次数为29河海大学能源与电气学院

其中为Hash表的填满率.显然,当随机Hash表被填满(=1)后,其填入与取出过程均不能正常终止.因此,与线性Hash表一样,随机Hash表一般也不能填满.30河海大学能源与电气学院例3.4将关键字序列(09,31,26,19,01,13,02,11,27,16,05,21)依次填入长度为n=16的随机Hash表中.设Hash码为i=INT(k/3)+1.伪随机数序列为:1,6,15,12,13,2,11,8,9,14,7,4,5,10,3,0.填入后的随机Hash表为:随机Hash表31河海大学能源与电气学院3.溢出Hash表前面所介绍的线性Hash表和随机Hash表都存在两个缺点,一是Hash表填入过程不顾后效,冲突机会不断增多;二是Hash表填满时,不能正常地进行查找.

将冲突的元素安排在另外的空间内,而不占用Hash表本身的空间,则不会产生新的冲突,这就是溢出Hash表.32河海大学能源与电气学院溢出Hash表的填入和取出的过程:(1)溢出Hash表的填入.①计算关键字k的Hash码i=i(k)②检查表中第i项的内容:

若第i项为空,则将关键字k及有关信息填入该项;

若第i项不空,则将关键字k及有关信息填入溢出表中的自由项;(2)溢出Hash表的取出①计算关键字k的Hash码i=i(k)

33河海大学能源与电气学院②检查表中第i项的内容:

若第i项登记着关键字k,则取出该项元素即可.

若第i项为空,则表示在Hash表中没有该关键字的信息.

若第i项不空,且登记的不是关键字k,则转入在溢出表中进行顺序查找.34河海大学能源与电气学院例3.5将关键字序列(09,31,26,19,01,13,02,11,27,16,05,21)依次填入长度为n=12的溢出Hash表中.设Hash码为i=INT(k/3)+1.填入后的溢出Hash表为:Hash表和其溢出表35河海大学能源与电气学院4.拉链Hash表拉链Hash表是一种最常用又最有效的Hash表.拉链Hash表又分为外链Hash表与内链Hash表.

外链Hash表的填入与取出过程如下:(1)外链Hash表的填入①计算关键字k的Hash码i=i(k)②取的一个新的结点p,并将关键字k及有关信息填入结点p36河海大学能源与电气学院③将结点p链入以H(i)为头指针的链表的链头.(2)外链Hash表的取出①计算关键字k的Hash码i=i(k)②在以H(i)为头指针的链表中顺序查找关键字为k的元素.若找到,则从结点中取出元素例3.6见P17837河海大学能源与电气学院5.指标Hash表指标Hash表包括指标表与内容表两部分,在指标Hash表中,所有的关键字及有关信息被登记在内容表中,每个关键字占内容表中一段连续空间.38河海大学能源与电气学院3.3基本的排序技术排序也是数据处理的重要内容.所谓排序是指将一个无序序列整理成按值非递减顺序排列的有序序列.3.3.1冒泡排序与快速排序1.冒泡排序冒泡排序是一种最简单的互换类排序方法,它是通过相邻数据元素的交换逐步将线性表变为有序.39河海大学能源与电气学院40河海大学能源与电气学院冒泡排序C++描述://文件名bub.h#include<iostream>usingnamespacestd;template<classT>voidbub(T

p[],intn){int

m,k,j,I;Td;k=0;m=n-1;

while(k<m){j=m-1;m=0;

for(i=k;i<=j;i++)//从前//往后扫描if(p[i]>p[i+1])//顺序不对,交换{d=p[i];p[i]=p[i+1];p[i+1]=d;m=I;}j=k+1;k=0;for(i=m;i>=j;i--)if(p[i-1]>p[i]){d=p[i];p[i]=p[i-1];p[i-1]=d;k=I;}}Return;}41河海大学能源与电气学院主函数的例子如下:#include”bub.h”#include<iomanip>intmain(){int

i,j;doublep[50],r=1.0;

for(i=0;i<50;i++)//产生50个0到1之间的随机数

{r=2053.0*r+13849.0;j=r/65536.0;r=r-j*65536.0;p[i]=r/65536.0;}

for(i=0;i<50;i++)//产生50个100到300之间的随机数42河海大学能源与电气学院

p[i]=100.0+200.0*p[i];count<<“排序前的序列:”<<endl;

for(i=0;i<10;i++){for(j=0;j<5;j++)cout<<setw(10)<<p[5*i+j];

cout<<endl;}bub(p+10,30);//对原序列中的第11到第40个元素进行排序

cout<<“排序后的序列:”<<endl;

for(i=0;i<10;i++){for(j=0;j<5;j++)cout<<setw(10)<<p[5*i+j];

cout<<endl;}return0;}43河海大学能源与电气学院2.快速排序冒泡排序只对相邻两个元素进行比较,只能消除一个逆序,快速排序可以实现通过一次交换而消除多个序列.

快速排序是一种互换类的排序方法,但由于它比冒泡排序的速度快,因此称为快速排序.（P186）44河海大学能源与电气学院快速排序示意图45河海大学能源与电气学院快速排序函数:template<classT>voidqck(T

p[],intn){int

m,i;T*s;

if(n>10){i=split(p,n);

qck(p,i);s=p+(i+1);m=n-(i+1);

qck(s,m);}else

bub(p,n);Return;}46河海大学能源与电气学院template<classT>staticint

split(T

p[],intn){int

i,j,k,l;Tt;i=0;j=n-1;k=(i+j)/2;if((p[i]>=p[j])&&(p[j]>=p[k]))l=j;elseif((p[i]>=p[k])&&(p[k]>=p[j]))l=k;elsel=i;t=p[l];

p[l]=p[i];

while(i!=j){while((i<j)&&(p[j]>=t))j=j-1;

if(i<j){p[i]=p[j];i=i+1;

while((i<j)&&(p[i]<=t))i=i+1;

if(i<j) {p[j]=p[i];j=j-1;}}}

p[i]=t;return(i);}}47河海大学能源与电气学院3.3.2简单插入排序与希尔排序

冒泡排序与快速排序本质上都是通过数据元素交换来逐步消除线性表中逆序.1.简单插入排序简单插入排序是指将无序序列的元素依次插入到已经有序的线性表中.48河海大学能源与电气学院简单插入排序示意图49河海大学能源与电气学院2.希尔排序希尔排序属于插入类排序,但它对简单插入排序做了较大的改进.

其基本思想是将整个无序序列分割成若干小的子序列分别进行插入排序.50河海大学能源与电气学院希尔排序示意图51河海大学能源与电气学院3.3.3简单选择排序与堆排序1.简单选择排序选择排序的基本思想:

扫描整个线性表,从中选出最小元素,将它变换到表的最前面(这是它应有的位置);然后对剩下的子表采用同样的方法,直到子表空为止.

对于长度为n的序列,选择排序需要扫描n-1遍,每一遍扫描均从剩下的子表中选出最小的元素,然后将该元素与子表中的第一个元素进行交换.52河海大学能源与电气学院对于长度为n的序列,选择排序需要扫描n-1遍,每一遍扫描均从剩下的子表中选出最小的元素,然后将该最小的元素与子表中第一个元素进行交换,下图就是这种排序示意图,图中有方框的元素是刚被选出来的最小元素.简单选择排序例53河海大学能源与电气学院2.堆排序堆的定义:堆排序属于选择类的排序方法具有n个元素的序列(h1,h2,…,hn),当且仅当满足54河海大学能源与电气学院(i=1,2,3,…..,n/2)时称为堆.

由堆的定义可以看出,堆顶元素(第一个元素)必为最大值.根据堆的定义,堆排序的方法:(1)首先将一个无序序列建成堆(2)然后将堆顶元素与堆中最后一个元素交换.不考虑已经换到最后的那个元素,只考虑前n-1个元素构成的子序列,显然,该子序列55河海大学能源与电气学院

已不是堆,但左右子树仍为堆,可以将该子序列调整为堆,反复做第(2)步,直到剩下的子序列为空为止.（P194）3.3.4其他排序方法简介(1)归并排序（P197图3.10）(2)基数排序（P200图3.11）56河海大学能源与电气学院3.4二叉排序树及其查找3.4.1二叉排序树的基本概念二叉排序树是指满足下列条件的二叉树:①左子树上的所有结点值均小于根结点值②右子树上的所有结点值均不小于根结点值③左右子树也满足上述两个条件.57河海大学能源与电气学院(a)结点值为数值的二叉排序树(b)结点为字母的二叉排序树58河海大学能源与电气学院3.4.2二叉排序树的插入根据二叉排序树的定义,二叉排序树的插入过程如下:①若当前的二叉树为空,则插入的元素为根结点.②若插入的元素值小于根结点值,则将元素插入到左子树中.③若插入的元素值不小于根结点值,则将元素插入到右子树中.59河海大学能源与电气学院3.4.3二叉排序树的删除为了在二叉排序树中删除一个指定的元素,首先要找到被删元素所在的结点p与它的父结点q.然后分为下面3种情况处理:(1)p为叶子结点(左右子树均为空).此时直接删除该结点.(2)p为单支子树.此时,如果p是q的左子结点,则将p的单支子树链接到q的左指针上,否则将p的单支子树链接到q的右指针上.60河海大学能源与电气学院(3)p的右子树和左子树都不为空.3.4.4二叉排序树查找根据二叉树的定义,查找一个指定元素的方法为:(1)若被查值等于根结点值,查找成功,结束查找.(2)若被查找值小于根结点,则到左子树中查.61河海大学能源与电气学院(3)若被查找值大于根结点,则到右子树中查.3.5多层索引树及其查找索引是提高数据存取效率的基本方法,如果索引本身就很大,对索引的查找代价就很大,所以,通常采用多层索引树.62河海大学能源与电气学院3.5.1B-树

一棵2m+1阶的B-树,或为空,或满足下列特性的度为2m+1的树.(1)树中每个结点最多有