nets:[[../else/数据结构]] 课程笔记

7.1 概述

何为查找表

查找表是由同一类型的数据元素（或记录）构成的集合。
由于“集合”中的数据元素之间存在着松散的关系，因此查找表是一种应用灵便的结构。

对查找表进行的操作

查询某个“特定的”数据元素是否在查找表中
检索某个特定的数据元素的各种属性
在查找表中插入一个数据元素
在查找表中删除某个数据元素

查找表的分类

静态查找表

仅作查询和检索操作的查找表。

动态查找表

有时在查询之后，还需要将“查询”结果为“不在查找表
中”的数据元素插入到查找表中；或者，从查找表中删除其“查询”结果为“在查找表中”的数据元素。

关键字

关健字是数据元素（或记录）中某个数据项的值，用以标识
(识别)一个数据元素（或记录）。
若此关键字可以识别唯一的一个记录，则称之谓“主关键字”。
若此关键字能识别若干记录，则称之谓“次关健字”。

查找

根据给定的某个值，在查找表中确定一个其关键字等于
给定值的数据元素或（记录)。
若查找表中存在这样一个记录，则称“查找成功”。查找结果给出整个记录的信息，或指示该记录在查找表中的位置；否则称“查找不成功”。查找结果给出“空记录”或“空指针”。

如何进行查找？

查找的方法取决于查找表的结构。
由于查找表中的数据元素之间不存在明显的组织规律，因此不便于查找。
为了提高查找的效率，需要在查找表中的元素之间人为地附加某种确定的关系，换句话说，用另外一种结构来表示查找表。

7.2 静态查找表

一、抽象数据类型及其实现

ADT StaticSearchTable{
数据对象D:
D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。
数据关系R:
数据元素同属一个集合。
基本操作P:
Create(&ST,n);Destroy(&ST);
Search(ST,key);Traverse(ST,VisitO);
}ADT StaticSearchTable

Create(&ST,n):
操作结果：构造一个含个数据元素的静态查找表ST
Destroy(&ST):
初始条件：静态查找表ST存在；
操作结果：销毁表ST。
Search(ST,key):
初始条件：静态查找表ST存在，ky为和查找表中元素的关键字类型相同的给定值；
操作结果：若ST中存在其关键字等于ky的数据元素，则函数值为该元素的值或在表中的位置，否则为“空”
Traverse(ST,Visit()):
初始条件：静态查找表ST存在，Visit是对元素操作的应用函数；
操作结果：按某种次序对ST的每个元素调用函数Visit()一次且仅一次，一旦Visit()失败，则操作失败。

typedef struct{
ElemType *elem;
//数据元素存储空间基址，建表时
//按实际长度分配，0号单元留空
int length;//表的长度
}SSTable;

typedef struct{
keyType key;//关键字域
··· ···//其它属性域
}ElemType

二、顺序查找表

以顺序表或线性链表表示静态查找表
回顾顺序表的查找过程：
假定给值定值e=64,要求ST.elem[k]=e,问k=？

int location(SqList L,ElemType&e,Status (*compare)(ElemType,ElemType)){
	k=1;p=L.elem;
	while (k<=L.length &&!(*compare)(*p++,e)))k++;
	if(k<=L.length) return k;
	else return 0;
}//location

int Search Seq(SSTable ST,KeyType key){
//在顺序表ST中顺序查找其关键字等于key的数据元素。
//若找到，则函数值为该元素在表中的位置，否则为0。
ST.elem[0].key=key;//哨兵”
for(i=ST.length,ST.elem[i].key!=key;--i);//从后往前找
return i;//找不到时，i为0
}//Search Seq

分析顺序查找的时间性能

定义：查找算法的平均查找长度(Average Search Length)
为确定记录在查找表中的位置，需和给定值进行比较的关键字个数的期望值.

其中：n为表长，P:为查找表中第i个记录的概率，且∑P=1,Ci为找到该记录时，曾和给定值比较过的关键字的个数。
等概率查找时顺序表查找的平均查找长度为：(n+1)/2；
在不等概率查找的情况下，ASL在Pn≥Pn-1≥…≥P2≥P时取极小值。
若查找概率无法事先测定，则查找过程采取的改进办法是，在每次查找之后，将刚刚查找到的记录直接移至表尾的位置上。

三、有序查找表

上述顺序查找表的查找算法简单，但平均查找长度较大，特别不适用于表长较大的查找表。

若以有序表表示静态查找表，则查找过程可以基于“折半”进行。

int Search_Bin (SSTable ST,KeyType key )
	low=1;high=ST.length;//置区间初值
	while (low <=high){
		mid (low high)/2;
		if (EQ (key,ST.elem[mid].key))return mid;//找到待查元素
		else if (LT (key,ST.elem[mid].key))
			high=mid-1;//继续在前半区间进行查找
		else low=mid+l;//继续在后半区间进行查找
}
return 0;
//顺序表中不存在待查元素
}//Search Bin

折半查找的平均查找长度

一般情况下，表长为n的折半查找的判定树的深度和含有n个结点的完全二叉树的深度相同。

可见，折半查找的效率比顺序查找高，但折半查找只适用于有序表，且限于顺序存储结构（对线性链表无法有效地进行折半查找）

四、索引查找表

索引顺序表查找过程：
1)由索引确定记录所在区间；
2)在顺序表的某个区间内进行查找。

可见，索引顺序查找的过程也是一个“缩小区间”的查找过程

索引顺序查找的平均查找长度=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度

索引表的结构定义

typedef struct{//索引项类型
keytype key;//块内最大关键字
int stadr;//块的起始位置
}IndexItem;
typedef struct{//索引表结构
IndexItem*elem;//索引表基址
int blknum;//索引表元素个数，即块的数目
}IndexTable;

索引顺序表的存储结构定义

typedef struct{//数据元素类型
keytype key;//关键字类型
··· ···//其它数据项
}ElemType;
typedef struct{//顺序表结构
ElemType*elem;//顺序表基址
int length;//顺序表元素个数
}IndexSqList;

int Search-Idx(IndexSqList ST,IndexTable ID,KeyType
kval){
//在索引顺序表ST中查找其关键字等于kva1的数据元素，
//若找到，则函数值为该元素在表中的位置，否则为0。
	low=1;high=ST.index.blknum;
	found=false;//置区间初值和查找标志
	while (low <high&&!found){//折半查找索引表，确定查找区间
		mid=(low+high)/2;
	if (kval<ID.elem[mid].key)
		high=mid-1;//继续在前半区间内进行查找
	else if (kval=ID.elem[mid].key)
	low=mid+1;//继续在后半区间内进行查找
	else {found=true;low=mid}
	}//while
	s=ID.elem[low].stadr;//定位在第1ow块，s为下界
	if (highl<ID.blknum)
		t=D.elem[low+1].stadr-1;
		//t为上界
	else t=ID.blknum
		if(kval =ST.elem[t].key)
			return t;
		else{//在ST.elem[s]和ST.elem[t]区间内顺序查找
		ST.elem=[0]ST.elem[t+1];
		//暂存ST.e1em[t+1]
		ST.elem[t+1].key kval;
		//设置监视哨
		for k=s;ST.elem [k].key !kval;k++);
			ST.elem[t+1]ST.elem [0];
			//恢复暂存值
			if (k !=t+1) return k;//找到
			else return 0;//未找到
		}//else
}//Search-Idx

索引顺序查找的平均查找长度（在前两表之间）

=查找“索引”的平均查找长度+查找“顺序表”的平均查找长度

一般情况下，为进行分块查找，可以将长度为的表均匀地分
成b块，每块含有s个纪录，即b=n/s
又假定表中每个纪录的查找概率相等，则每块查找的概率为
1/b,块中每个纪录的查找概率为1/s。

可得如下结论：
1)从查找性能看，最好情况能达O(logn),此时要求表有序；
2)从插入和删除的性能看，最好情况能达O(1)),此时要求存储
结构是链表。

7.3 动态查找树表

一、动态查找表的抽象数据类型

ADT DynamicSearchTable
数据对象D:
D是具有相同特性的数据元素的集合。每个数据元素含有类型相同的关键字，可唯一标识数据元素。
数据关系R:
数据元素同属一个集合。
基本操作P:
InitDSTable(&DT)
DestroyDSTable(&DT)
SearchDSTable(DT,key);
InsertDSTable(&DT,e);
DeleteDSTable(&T,key);
TraverseDSTable(DT,VisitO);
}ADT DynamicSearchTable

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存在，ky为和关键字类型相同的给定值；
操作结果：若DT中存在其关键字等于ky的数据元素，则删除之。
TraverseDSTable(DT,VisitO):
初始条件：动态查找表DT存在，Vst是对结点操作的应用函数；
操作结果：按某种次序对DT的每个结，点调用函数Vist0一次且至多一次。一旦Visit0失败，则操作失败。

二、二叉排序树

1. 定义

定义：二叉排序树或者是一棵空树；或者是具有如下特性的二叉树
(1)若它的左子树不空，则左子树上所有结点的值均小于根结点的值；
(2)若它的右子树不空，则右子树上所有结点的值均大于根结点的值；
(3)它的左、右子树也都分别是二叉排序树。

typedef struct BiTNode{//结点结构
TElemType data;
struct BiTNode*lchild,*rchild;//左右孩子指针
}BiTNode,*BiTree;

2. 查找算法

若二叉排序树为空，则查找不成功；否则，
1)若给定值等于根结点的关键字，则查找成功；
2)若给定值小于根结点的关键字，则继续在左子树上进行查找；
3)若给定值大于根结点的关键字，则继续在右子树上进行查找。

Status SearchBST (BiTree T,Key Type key,BiTree f,BiTree &p){
//在根指针T所指二叉排序树中递归地查找其关键字等于key的数据元素
//若查找成功，则返回指针p指向该数据元素的结点，并返回函数值为TRUE
//否则表明查找不成功，返回指针卫指向查找路径上访问的最e后一个结点，
//并返回函数值为FALSE,指针f指向当前访问的结点的双亲，其初始调用值为NULL
if (T)
{p=f,return FALSE;}//查找不成功
else if(EQ(key,T->data.key))
{p=T,return TRUE;}//查找成功
else if (LT(key,T->data.key))
SearchBST(T->lchild,.key,T,p);//在左子树中继续查找
else
SearchBST(T->rchild,key,T,p);//在右子树中继续查找
}//SearchBSTR

3. 插入算法

根据动态查找表的定义，“插入”操作在查找不成功时才进行；

若二叉排序树为空树，则新插入的结点为新的根结点；否则，新
插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。

Status Insert BST(BiTree &T,ElemType e
{
//当二叉排序树中不存在关键字等于e.key的数据元素时，指入元素值
//为e的结点，并返回TRUE;否则，不进行插入并返回FALSE
if (!SearchBST (T,e.key,NULL,p)){
	S=(BiTree)malloc(sizeof(BiTNode);//为新结点分配空间
	s->data e;
	s->Ichild =s->rchild NULL:
	if(!p)T=S;//插入s为新的根结点
	else if(LT(e.key,p->data.key)) p->lchild s;//插入*s为*p的左孩子
	else p->rchild=s;//插入*s为*p的右孩子
	return TRUE;//插入成功
}
else return FALSE;
}//Insert BST

4. 删除算法

和插入相反，删除在查找成功之后进行，并且要求在删除二叉排序树上某个结点之后，仍然保持二叉排序树的特性。
可分三种情况讨论：
(1)被删除的结点是叶子；
(2)被删除的结，点只有左子树或者只有右子树；
(3)被删除的结点既有左子树，也有右子树。

5. 查找性能的分析

对于每一棵特定的二叉排序树，均可按照平均查找长度的定义来求它的ASL值，显然，由值相同的个关键字，构造所得的不同形态的各棵二叉排序树的平均查找长度的值不同，甚至可能差别很大。

不失一般性，假设长度为的序列中有k个关键字小于第一个关键字，则必有-k-1个关键字大于第一个关键字，由它构造的二叉排序树：的平均查找长度是n和k的函数P(n,k) (0≤k≤n-1)。

三、二叉平衡树

1. 何为平衡二叉树

二叉平衡树是二叉查找树的另一种形式，其特点为：
树中每个结点的左、右子树深度之差的绝对值不大于1。

2. 如何构造“二叉平衡树”

构造二叉平衡（查找）树的方法是：在插入过程中，采用平衡旋转技术。

二叉排序树的平衡化

当生成二叉排序树的关键字序列非随机时，所生成的二叉排序树有可能偏向于单支，从而使其查找性能接近于顺序表。在这种情况下，需要在生成二叉排序树的过程中进行“平衡化”处理，使得在任何时刻二叉排序树的形态都是“平衡”的。

平衡二叉树的概念

称二叉排序树为“平衡”指的是，它或是空树，或具有下列特性：其左子树和右子树都是平衡二叉排序树，且左右子树深度之差的绝对值不大于1

平衡因子

平衡因子定义为平衡二叉树中左子树的深度减去右子树的深度。换句
话说，平衡树上所有结，点的平衡因子的绝对值均不大于1。

二叉平衡排序树的构造

每当插入一个结点时，首先检查是否因插入而破坏了树的平衡性，如果是因插入结点而破坏了树的平衡性，则找出其中最小不平衡子树，在保持排序树特性的前提下，调整最小不平衡子树中各结，点之间的连接关系，以达到新的平衡。通常将这样得到的平衡二叉排序树简称为AVL树。

最小不平衡子树

所谓最小不平衡子树是指：以离插入结点最近、且平衡因子绝对值大于1的结，点作根结点的子树。可归纳为下列四种情况：① LL型② RR型③ LR型④ RL型

3. 二叉平衡树的查找性能分析

平衡树的查找性能分析：在平衡树上进行查找的过程和二叉排序树相同，因此，查找过程中和给定值进行比较的关键字的个数不超过平衡树的深度。

问：含n个关键字的二叉平衡树可能达到的最大深度是多少？

四、B-树

五、B+树

7.4 哈希表

以上两节讨论的表示查找表的各种结构的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系，
查找的过程为给定值依次和关键字集合中各个关键字进行比较，
查找的效率取决于和给定值进行比较的关键字个数。
用这类方法表示的查找表，其平均查找长度都不为零。
不同的表示方法，其差别仅在于：关键字和给定值进行比较的顺序不同。

一、哈希表的概念

对于频繁使用的查找表，希望ASL=0。
只有一个办法：预先知道所查关键字在表中的位置，
即，要求：记录在表中位置和其关键字之间存在一种确定的关系。

因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以f(key)作为关键字为key的记录在表中的位置，通常称这个函数f(key)为哈希函数.

哈希函数是一个映象，即：将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；
由于哈希函数是一个压缩映象，因此，在一般情况下，很容易产生“冲突”现象，即：key1≠key2,而f(key1)=f(key2).
很难找到一个不产生冲突的哈希函数。
一般情况下，只能选择恰当的哈希函数，使冲突尽可能少地产生。

因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”（尽可能少产生冲突）的哈希函数之外；还需要找到一种“处理冲突”的方法。

哈希表的定义：

根据设定的哈希函数H(key)和所选中的处理冲突的方法，将一组关
键字映象到一个有限的、地址连续的地址集（区间）上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“哈希表”。

二、构造哈希函数的方法

对数字的关键字可有下列构造方法：

直接定址法
1. 哈希函数为关键字的线性函数H(key)=key/H(key)=a* key+b
2. 此法仅合适于：地址集合的大小= =关键字集合的大小
数字分析法
1. 假设关键字集合中的每个关键字都是由S位数字组成(u1, u2,,un),分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。
2. 此法合适于：能预先估计出全体关键字的每一位上各种数字出现的频度。
平方取中法
1. 以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各位的影响。
2. 此法合适于：关键字的每一位都有某些数字重复出现频度很高
折叠法
1. 将关键字分割成若干部分，然后取它们的叠加和为哈希地址。有两种叠加处理的方法：移位叠加和间界叠加。
2. 此法合适于：关键字的数字位数特别多
除留余数法
1. 设定哈希函数为： H(key)=key MOD p 其中，p≤m(表长)并且p应为不大于m的素数或是不含20以下的质因子
2. 限制p的原因：减少冲突
随机数法
1. 设定哈希函数为：H(key)=Random(key)其中，Random为伪随机函数
2. 通常，此方法用于对长度不等的关键字构造哈希函数
  
  若是非数字关键字，则需先对其进行数字化处理。

实际造表时，采用何种构造哈希函数的方法取决于建表的关键字集合的情况包括关键字的范围和形态)，总的原则是使产生冲突的可能性降到尽可能地小。

三、处理冲突的方法

“处理冲突”的实际含义是：为产生冲突的地址寻找下一个哈希地址。

开放定址法
1. 为产生冲突的地址H(key)求得一个地址序列Ho,H1,H2,,H1≤s≤m-1其中：H,=H(key)Hi=(H(key)+di)MOD m,i=1,2,…S
2. 对增量d有三种取法：
  1)线性探测再散列：d,=cxi最简单的情况c=1
  2)二次探测再散列：d=12,-12,22,-22,,
  3)随机探测再散列：d是一组伪随机数列
链地址法
将所有哈希地址相同的记录都链接在同一链表中。

ASL=(6* 1+2* 2+3)/9=13/9

四、哈希表的查找

查找过程和造表过程一致。假设采用开放定址处理冲突，则查找过程为：
对于给定值K,计算哈希地址i=HK)
若r[i]=NULL则查找不成功
若r[i]key=K则查找成功
否则“求下一地址H”,直至rH=NULL(查找不成功)
或r[Hi].key=K(查找成功)为止。

#define maxsize 100//定义表长
typedef struct{//定义记录结构
KeyType key;//关键字域
DataType other;//其它数据域
}ElemType;
typedef struct{
Elem Type *elem;
int count;//当前数据元素个数
int hashsize;//为最大容量
}Hash Table;

//线性探测再散列查找
int hash_search(HashTable hstable[],KeyType k)
{//在哈希表中查找关键字为k的记录
int i,d;i=0;//初始化探测序列
d=h(k);//取得哈希地址
while ((hstable[d].key!=k)&&(hstable[d]!=null)&&(i<m))
{i++;
d=(d+i)%m;//线性探测下一个地址}//while
if(hstable[d].key==k)return d;//查找成功
else return-1;//失败返回
}//hash search

//用链地址表解决哈希冲突
typedef struct node
{KeyType key;//关键字域
struct node*next;//指针域
}hsnode;
typedef hsnode *linklist:
typedef linklist hstable[m];

linklist hash seach link(HashTable hst,KeyType k)
{//在哈希表中查找关键字为k的记录
int d;linklist p;
d=h(k);//取得哈希地址
p=hst[d];//取链表的第一个结点
while((p!=NULL)&&(p->key!=k))
p=p->next,//取后继结点
return p;//成功或失败均返回p
}//hash_seach_link

哈希表的平均查找长度

平均查找长度取决于哈希函数、解决冲突的方法和哈希表的装填因子这三个因素。哈希函数影响地址冲突的频度，所以设计一个哈希地址分布均匀的哈希函数是哈希查找的首要任务。

哈希装填因子（越小冲突越小）

总结

1.顺序表和有序表的查找方法及其平均查找长度的计算方法。
2.静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系。
3.理解B-树、B+树等的特点以及它们的建树和查找的过程。
4.熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别。
5.掌握按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。