数据结构程序员考试 第九章查找表.docx
《数据结构程序员考试 第九章查找表.docx》由会员分享，可在线阅读，更多相关《数据结构程序员考试 第九章查找表.docx（30页珍藏版）》请在冰点文库上搜索。
数据结构程序员考试第九章查找表
第九章查找表
查找表
是由同一类型的数据元素（或记录）构成的集合。
对查找表经常进行的操作:
1）查询某个“特定的”数据元素是否在查找表中；
2）检索某个“特定的”数据元素的各种属性；
3）在查找表中插入一个数据元素；
4）从查找表中删去某个数据元素。
静态查找表
仅作上述1）和2）操作的查找表
动态查找表
有时在查询之后，还需要将“查询”结果为“不在查找表中”的数据元素插入查找表；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素
关键字
是数据元素（或记录）中某个数据项的值，用以标识（识别）一个数据元素（或记录）
若此关键字可以识别唯一的一个记录，则称之谓“主关键字”
若此关键字能识别若干记录，则称之谓“次关键字”
查找
根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）
若查找表中存在这样一个记录，则称“查找成功”，查找结果：
给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”，查找结果：
给出“空记录”或“空指针”
如何进行查找？
取决于查找表的结构，即：
记录在查找表中所处的位置。
然而，查找表本身是一种很松散的结构，因此，为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。
本章讨论的重点：
查找表的各种表示方法及其相应的查找算法
9.1静态查找表
ADTStaticSearchTable{
数据对象D：
D是具有相同特性的数据元素的集
合。
每个数据元素含有类型相同的
关键字，可唯一标识数据元素。
数据关系R：
数据元素同属一个集合。
基本操作P：
Create（&ST,n）;
操作结果：
构造一个含n个数据元素的静态查找表
ST。
Destroy（&ST）;
初始条件：
静态查找表ST存在；
操作结果：
销毁表ST。
Search（ST,key）;
初始条件：
静态查找表ST存在，key为和查找表中
元素的关键字类型相同的给定值；
操作结果：
若ST中存在其关键字等于key的数据元
素，则函数值为该元素的值或在表中的位
置，否则为“空”。
Traverse（ST,Visit（））;
初始条件：
静态查找表ST存在，Visit是对元素操作
的应用函数；
操作结果：
按某种次序对ST的每个元素调用函数
Visit（）一次且仅一次，一旦Visit（）失败，则
操作失败。
}ADTStaticSearchTable
C++的语言描述：
template
classSSTable
{
public:
virtualElem*Search（KeyTypekey）;
//若静态查找表中存在其关键字和key相等的
//元素，则返回指向该元素的指针，否则返回
//“空”指针。
virtualvoidTraverse（voidvisit（Elem&item））;
//按某种次序对静态查找表中每个元素调用
//函数visit（）一次且仅一次。
};//SSTable
下面讨论静态查找表的各种实现方法
一、顺序查找表
以顺序表或线性链表表示静态查找表
template
classSqSTable:
publicSSTable
{
private:
SqListST;
public:
SqSTable（intsize）;//构造函数
SqSTable（SqSTablera）;//复制构造函数
SqSTable（intsize,constElem*elemVal）;
//构造一个含size个元素的静态查找表，
//其元素值由elemVal给出。
~SqSTable（void）{};//析构函数
virtualElem*Search（KeyTypekey）;
//若顺序查找表中存在其关键字和key相等
//的数据元素，则返回指向该元素的指针，
//否则返回“空指针”。
virtualvoidTraverse（voidvisit（Elem&item））;
//对顺序查找表中每个元素，依次顺序调用函数
//visit一次，并且仅调用一次
};//SqSTable
在此重点讨论“查找”算法的实现。
template
Elem*SqSTable:
:
Search（KeyTypekey）
{
inti;
ifST.location（key,i）returngetElem（i）
elsereturnNULL
}
回顾顺序表的查找算法：
template
intSqList:
:
location（constElem&e）{
Elem*p;
intk=1;
p=elemPtr;
while（k<=cursize&&（compare（*p++,e）））
k++;if（k<=cursize）returnk;elsereturn0;}//location
上述算法中的基本操作是：
compare，为了避免“出界”，同时需作k<=cursize的判断，在表长>1000时，将使算法的执行时间几乎增加一倍。
为此，改写顺序表的查找算法如下：
template
intSqList:
:
Search_Seq（constKeyTypekey）
{
//在顺序表ST中顺序查找其关键字等于key的数
//据元素。
若找到，则函数值为该元素在表中的位
//置，否则为0。
elemPtr[0].key=key;//设“哨兵”
inti=cursize;//令i指向表尾，从后往前搜索
while（compare（elemPtr[i].key,key））i--;returni;//找不到时，i为0
}//Search_Seq
定义：
查找算法的平均查找长度（AverageSearchLength）
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值
其中:
n为表长，Pi为查找表中第i个记录的概率，
且
Ci为找到该记录时，曾和给定值比较过的
关键字的个数
对顺序表而言，Ci=n-i+1
ASL=nP1+（n-1）P2++2Pn-1+Pn
在等概率查找的情况下，
顺序表查找的平均查找长度为：
在不等概率查找的情况下，ASLss在
PnPn-1P2P1
时取极小值
若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。
二、有序查找表
上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表
以有序表表示静态查找表
template
classOrdSTable:
publicSSTable
{
pravite:
OrderedListST;
…
};//OrdSTable
此时的查找算法可基于折半查找来完成
intOrderedList:
:
Search_Bin（KeyTypekey）
{
//在有序表中折半查找其关键字等于key的记录。
//若找到，则返回该记录在表中的位置，否则为0。
low=1;high=ST.length;//置区间初值
while（low<=high）{
mid=（low+high）/2;//取查找区间的中间位置
if（EQ（key,elemPtr[mid].key））returnmid;
//找到待查记录
elseif（LT（key,elemPtr[mid].key））high=mid-1;
//继续在前半区间进行查找
elselow=mid+1;//继续在后半区间进行查找
}
return0;//有序表中不存在待查记录
}//Search_Bin
分析折半查找的平均查找长度
先看一个具体的情况，假设：
n=11
i
1
2
3
4
5
6
7
8
9
10
11
Ci
3
4
2
3
4
1
3
4
2
3
4
构造一棵二叉树，将Ci=i的结点放在这棵树的第i层
用以描述折半查找的过程，称之谓“判定树”
例如:
折半查找在n=11时的判定树
6
39
14710
25811
一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同
假设n=2h-1并且查找概率相等
则
在n>50时，可得近似结果
三、静态查找树表
在不等概率查找的情况下，折半查找不是最好的查找方法
例如:
关键字:
ABCDE
Pi:
0.20.30.050.30.15
Ci:
23123
此时的ASL=2.4
若改变Ci的值21323
则ASL=1.9
定义:
使
达最小的判定树称为最优二叉树，
其中:
构造最优二叉树的时间复杂度为（n3）
介绍一种次优二叉树的构造方法:
令wi=pi
选择二叉树的根结点，
使
达最小
构造次优二叉树的算法
StatusSecondOptimal（BiTree&T,ElemTypeR[],
floatsw[],intlow,inthigh）{
//由有序表R[low..high]及其累计权值表sw
//（其中sw[0]==0）递归构造次优查找树T。
i=low;min=abs（sw[high]-sw[low]）;
dw=sw[high]+sw[low-1];
for（j=low+1;j<=high;++j）
//选择最小的ΔPi值
ifabs（dw-sw[j]-sw[j-1]）i=j;min=abs（dw-sw[j]-sw[j-1]）;
}
if（!
（T=（BiTree）malloc（sizeof（BiTNode））））
returnERROR;
T->data=R[i];//生成结点
if（i==low）T->lchild=NULL;//左子树空
elseSecondOptimal（T->lchild,R,sw,low,i-1）;
//构造左子树
if（i==high）T->rchild=NULL;//右子树空
elseSecondOptimal（T->rchild,R,sw,i+1,high）;
//构造右子树
returnOK;
}//SecondOptimal
次优查找树采用二叉链表的存储结构
template
classSOSTable:
publicSSTable
{
pravite:
SOSTreeST;
…
};//SOSTable
SOSTable:
:
SOSTable（OrderedListst）{
//由有序表st构造一棵次优查找树ST
//ST的数据元素含有权域weight
if（st.length=0）T=NULL;
else{
FindSW（sw,ST）;//按照有序表ST中
//各数据元素的weight域
//求累计权值表sw
SecondOpiamal（T,ST.elem,sw,1,ST.length）;
}
returnOK;
}//SOSTree
四、索引顺序表
对比顺序表和有序表的查找性能之差别：
顺序表有序表
表的特性无序表有序表
存储结构顺序结构或链表结构链表结构
插删操作易于进行需移动元素
ASL值大小
索引顺序表=索引+顺序表
一般情况下，索引是一个有序表
查找方法：
1）由索引确定记录所在区间；
2）在顺序表的某个区间内进行查找。
所以，这也是一种缩小区间的查找方法
索引顺序表的平均查找长度为在索引中进行查找的平均查找长度和在顺序表中进行查找的平均查找长度之和。
抽象数据类型动态查找表的定义如下：
ADTDynamicSearchTable{
数据对象D：
D是具有相同特性的数据元素的集合。
每个数据元素含有类型相同的关键字，
可唯一标识数据元素。
数据关系R：
数据元素同属一个集合。
基本操作P：
InitDSTable（&DT）;
操作结果：
构造一个空的动态查找表DT。
DestroyDSTable（&DT）;
初始条件：
动态查找表DT存在；
操作结果：
销毁动态查找表DT。
SearchDSTable（DT,key）;
初始条件：
动态查找表DT存在，key为和关键字类
型相同的给定值；
操作结果：
若DT中存在其关键字等于key的数据
元素，则函数值为该元素的值或在表中
的位置，否则为“空”。
InsertDSTable（&DT,e）;
初始条件：
动态查找表DT存在，e为待插入的数据
元素；
操作结果：
若DT中不存在其关键字等于e.key的
数据元素，则插入e到DT。
DeleteDSTable（&T,key）;
初始条件：
动态查找表DT存在，key为和关键字
类型相同的给定值；
操作结果：
若DT中存在其关键字等于key的数据
元素，则删除之。
TraverseDSTable（DT,Visit（））;
初始条件：
动态查找表DT存在，Visit是对结点
操作的应用函数；
操作结果：
按某种次序对DT的每个结点调用函数
visit（）一次且至多一次。
一旦visit（）失败，
则操作失败。
}ADTDynamicSearchTable
C++的语言描述：
template
classDSTable
{
public:
virtualStatusSearch（Elem&e,Elem*p）;
//若动态查找表中存在其关键字和key相等的
//记录，则以p带回指向该记录的指针，并返
//回“TRUE”，否则以p带回指向插入位置
//的指针，并返回“FALSE”。
virtualStatusInsert（constElem&e）;
//若动态查找表中不存在其关键字和e.key
//相等的记录，则插入之并返回“TRUE”，
//否则，返回“FALSE”。
virtualStatusDelete（constElem&e）;
//若动态查找表中存在其关键字和e.key
//相等的记录，则删除之并返回“TRUE”，
//否则，返回“FALSE”。
virtualvoidTraverse（voidvisit（Elem&item））;
//按某种次序对动态查找表中每个元素调用
//函数visit（）一次且仅一次。
};//DSTable
下面讨论动态查找表的各种实现方法
9.2动态查找树表
综合上一节讨论的几种查找表的特性：
查找插入删除
无序顺序表（n）
（1）（n）
无序线性链表（n）
（1）
（1）
有序顺序表（logn）（n）（n）
有序线性链表（n）
（1）
（1）
静态查找树表（logn）（nlogn）（nlogn）
可得如下结论：
1）从查找性能看，最好情况能达（logn），此时要求表有序；
2）从插入和删除的性能看，最好情况能达
（1），此时要求存储结构是链表。
静态查找树表也可以看成是一个有序表。
其有序的特性表现在：
根结点元素的值是其左、右子树的分界值。
这个特性正是以后要讨论的查找树的特征
本节介绍动态查找表的第一类表示方法----动态查找树表
一、二叉排序树（二叉查找树）
1．定义：
二叉排序树或者是一棵空树；或者是具有如下特性的二叉树：
（1）若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
（2）若它的右子树不空，则右子树上所有结点的值均大于根结点的值；（3）它的左、右子树也都分别是二叉排序树。
例如：
通常，可取二叉链表作为二叉排序树的存储结构
2．二叉排序树的查找算法：
若二叉排序树为空，则查找不成功；否则
1）若给定值等于根结点的关键字，则查找成功；
2）若给定值小于根结点的关键字，则继续在左子树上进行查找；
3）若给定值大于根结点的关键字，则继续在右子树上进行查找。
StatusSearchBST（BiTreeT,KeyTypekey,
BiTreef,BiTree&p）{
//在根指针T所指二叉排序树中递归地查找
//其关键字等于key的数据元素，若查找成功，
//则指针p指向该数据元素结点，并返回TRUE，
//否则指针p指向查找路径上访问的最后一个结点
//并返回FALSE，指针f指向T的双亲，其初始
//调用值为NULL
if（!
T）{p=f;returnFALSE;}//查找不成功
elseif（EQ（key,T->data.key））
{p=T;returnTRUE;}//查找成功
elseif（LT（key,T->data.key））
SearchBST（T->lchild,key,T,p）;
//在左子树中继续查找
elseSearchBST（T->rchild,key,T,p）;
//在右子树中继续查找
}//SearchBST
3．二叉排序树的插入算法
对于动态查找表，在查找不成功的情况下，尚需插入关键字等于给定值的记录，并且从查找的过程容易得出插入的算法：
若二叉排序树为空树，则新插入的结点为根结点；
否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程中得到。
StatusInsertBST（BiTree&T,ElemTypee）{
//当二叉排序树T中不存在关键字等于e.key
//的数据元素时，插入e并返回TRUE，
//否则返回FALSE
if（!
SearchBST（T,e.key,NULL,p）{//查找不成功
s=（BiTree）malloc（sizeof（BiTNode））;
s->data=e;s->lchild=s->rchild=NULL;
if（!
p）T=s;//插入s为新的根结点
elseif（LT（e.key,p->data.key））p->.lchild=s
//插入s为左孩子
elsep->.rchild=s;//插入s为右孩子
returnTRUE;
}
elsereturnFALSE;
//树中已有关键字相同的结点，不再插入
}//InsertBST
4．二叉排序树的删除算法
和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。
可分三种情况讨论：
（1）被删除的结点是叶子；
（2）被删除的结点只有左子树或者只有右子树；
（3）被删除的结点既有左子树，也有右子树。
StatusDeleteBST（BiTree&T,KeyTypekey）{
//若二叉排序树T中存在关键字等于key的
//数据元素时，则删除该数据元素结点p，
//并返回TRUE；否则返回FALSE
if（!
p）returnFALSE;
//不存在关键字等于key的数据元素
else{
if（EQ（key,T->data.key））Delete（T）;
//找到关键字等于key的数据元素
elseif（LT（key,T->data.key））
DeleteBST（T->lchild,key）;
elseDeleteBST（T->rchild,key）;
returnTRUE;
}
}//DeleteBST
其中删除操作过程如下所描述：
voidDelete（BiTree&p）{
//从二叉排序树中删除结点p，并重接它的
//左或右子树
if（!
p->rchild）{//右子树空则只需重接它的左子树
q=p;p=p->lchild;free（q）;
}
elseif（!
p->lchild）{//只需重接它的右子树
q=p;p=p->rchild;free（q）;
}
else{//左右子树均不空
q=p;s=p->lchild;
while（!
s->rchild）{q=s;s=s->rchild;}
p->data=s->data;//s指向被删结点的前驱
if（q!
=p）q->rchild=s->lchild;
elseq->lchild=s->lchild;//重接*q的左子树
free（s）;
}
}//Delete
5．查找性能的分析
对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的n个关键字构造所得的，不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大，例如：
由关键字序列1，2，3，4，5构造而得的二叉排序树，
ASL=（1+2+3+4+5）/5=3
由关键字序列3，1，2，5，4构造而得的二叉排序树
ASL=（1+2+3+2+3）/5=2.2
一般情况下，考虑含有n个关键字可能出现的n!
种序列出现的可能性相等。
不失一般性，假设某个序列中有k个关键字小于第一个关键字，即有n-k-1个关键字大于第一个关键字，由它构造的二叉排序树的平均查找长度是n和k的函数P（n,k）（0≤k≤n-1）
则含n个关键字的二叉排序树的平均查找长度
而在等概率的情况下，
由此
可类
升级会员 