数据结构与算法基础

查找

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

• 查找：根据给定的某个值，在查找表中确定一个其关键字等于给定值的数据元素或（记录）。

• 关键字：用来标识一个数据元素（或记录）的某个数据项的值。

  • 主关键字：可唯一地表示一个记录的关键字是主关键字；
  • 次关键字：反之，用识别若干记录的关键字是次关键字。

• 查找表可以分为两类

  • 静态查找表

    仅作查询

  • 动态查找表

    可以作插入和删除

• 查找算法的评价指标：

  • 关键字的平均比较次数，也称平均查找长度ASL

线性表的查找

顺序查找（线性查找）

• 顺序表或线性链表表示的静态查找表

• 表内元素之间无序

算法：

• 在顺序表中查找值为key的数据元素（从最后一个元素开始比较）

• int Search_Seq(SSTable ST,KeyType key)
  {
  	for(i = ST.length;i>=1;--i)
  	{
  		if(ST.R[i].key==key)
  		{
  			return i;
  		}
  	}
  	return 0;
  }
  

• 其他形式：

  int Search_Seq(SSTable ST,KeyType key)
  {
  	for(i = ST.length;ST.R[i].key!=key;--i)
  	{
  		if(i<=0)
  		{
  			break;
  		}
  	}
  	if(i>0)
  	{
  		return 0;
  	}
  	else return 0;
  }
  

改进

• 把待查关键字key存入表头（“哨兵”“监视哨”），从后往前进行比较，可以面区查找过程重每一步都要检测是否查找完毕，加快速度。

int Search_Seq(SSTable ST,KeyType key)
{
    ST.R[0].key = key;
	for(i=ST.length;ST.R[i].key!=key;--i)
	{
		if(i<=0)
		{
			break;
		}
		if(i>0)
		{
			return i;
		}
		else return 0;
	}
}

• 查找表存储记录原则——按照查找概率高低存储

  • 查找概率越高，比较次数越少
  • 查找概率越低，比较次数越多

• 记录的查找概率无法测定时如何提高查找效率？

  方法——按查找概率动态调整记录顺序：

  • 在每一个记录中设一个访问频度域；
  • 始终保持记录按非递增有序的次序序列；
  • 每次查找后均将刚查到的记录直接移至表头。

特点

• 算法简单，逻辑次序无要求，且不同存储结构均适用
• 缺点，时间效率太低

折半查找

• 每次将待查记录所在区间缩小一半。

设计方法

• 设表长为n，low，high和mid分别指向待查元素所在区间的上界、下界和中点，key为给定的要查找的值：
• 初始时，令low=1，high=n，mid=[(low+high)/2]
• 让key与mid指向的记录进行比较
  • 若key==R[mid].key,查找成功
  • 若key<R[mid].key,则high=mid-1
  • 若key>R[mid].key,则low=mid+1
• 重复上述操作，直至low>high时,查找失败

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

递归折半

int Search_Bin(SSTable ST,keyType key,int low,int high)
{
	if(low>high) return 0;
    mid = (low+high)/2;
    if(key == ST.elem[mid].key) return mid;
    else if(key<ST.elem[mid].key)
    {
        ...//递归，在前半区间进行查找
    }
    else
    {
        ...//递归，在后半区间进行查找
    }
    
}

• 优点：效率比顺序查找要高
• 缺点：只适用于有序表，且仅限于顺序存储结构（对线性链表无效）

分块查找

• 条件：
  • 将表分成几块，且表或者有序，或者分块有序。
  • 建立“索引表”（每个结点含有最大关键字域和指向本块第一个结点的指针，且按关键字有序）
• 查找过程：
  • 先确定待查记录所在块（顺序或折半查找），索引再在块内查找（顺序查找）
• 分块查找优缺点
  • 优点：插入和删除比较容易，无需进行大量移动
  • 缺点：要增加一个索引表的存储空间并对初始索引表进行排序运算
  • 适用情况：如果线性表纪要快速查找又要经常动态变化，则可采用分块查找。

树表的查找

• 在线性表上进行插入等操作时，为了维护表的有序性，需要移动表重的很多记录。
  • 改用动态查找表——几种特殊的树
  • 表结构在查找过程中动太生成
  • 对于给定值key
  • 若表中存在，则成功返回；
  • 否则，插入关键字等key的记录。

二叉排序树

• 二叉排序树或是空树，或是满足如下性质的二叉树

  • 若其左子树非空，则左子树上所有结点的值均小于根结点的值；
  • 若其右子树非空，则右子树上所有节点的值均大于根结点的值；
  • 其左右子树本身又各是一棵二叉排序树

• 中序遍历非空的二叉排序树所得到的数据元素序列是一个按关键字排列的递增有序序列。

• 算法：

  typedef struct
  {
  	KeyType key;//关键字项
  	InfoType otherinfo;//其他数据域
  }ElemType
  

  typedef struct BSTNode
  {
  	ElemType data;//数据域
  	struct BSTNode *lchild,*rchild;//左右孩子指针
  }BSTNode,*BSTree;
  
  BSTree T;//定义二叉排序树T
  

• 若查找的关键字等于根结点，成功

• 否则

  • 若小于根结点，查其左子树
  • 若大于根结点，查其右子树

• 在左右子树上的操作类似

核心思想

• 若二叉排序树为空，则查找失败，返回空指针
• 若二叉排序树非空，将给定值key与根结点的关键字T->data.key进行比较：
  • 若key等于T->data.key,则查找成功，返回根结点地址
  • 若key小于T->data.key，在京一部查找右子树
  • 若key大于T->data.key,则京一部查找右子树

BSTree SearchBST(BSTree T,KeyType key)
{
	if(!T||KEY==T->data.key) return T;
	else if(key<T->data.key)
			return SearchBST(T->lchild,key);//在左子树重继续查找
	else return SearchBST(T->rchild,key);//在右子树重继续查找
}

• 二叉排序树上查找某关键字等于给定值的结点过程，其实就是走了一条从根到该结点的路径。

  • 比较的关键字次数 = 此结点所在层次数

• 含有n个结点的二叉排序树的平均查找长度和树的形态有关

  • 最好情况：树的深度为：[log2n] + 1;与折半查找重的判定树相同。（形态比较均衡）。O（log2n）

  • 最坏情况：插入的n个元素从一开始就有序，——变成单支树的形态！

    此时树的深度为n，ASL = （n+1）/2，查找效率与顺序查找情况相同：O（n）

插入

• 若二叉排序树为空，则插入结点作为根结点插入到空树重
• 否则，继续在其左、右子树上查找
  • 树中已有，不再插入
  • 树中没有
    • 查找直至某个叶子结点的左子树或右子树或右子树为空为止，则插入结点应该为该叶子结点的左孩子或右孩子
• 插入的元素一定在叶结点上。

生成

• 从空树出发，经过一系列的查找、插入操作之后，生成一棵二叉排序树。
• 一个无序序列可以通过构造二叉排序树而变成一个有序序列。构造树的过程就是对无序序列进行排序的过程。
• 插入的结点均为叶子结点。故无需移动其他结点。相当于在有序序列上插入记录而无需移动其他记录。

删除

• 从二叉排序树中删除一个结点，不能把以该结点为根的子树都删去，只能删掉该结点，并且还应保证删除后所得的二叉树仍然满足二叉排序树的性质不变。
• 由于中序遍历二叉排序树可以得到一个递增有序的序列。那么，在二叉排序树中删去一个结点相当于删去有序序列中的一个结点。
  • 将因删除结点而断开的二叉链表重新链接起来
  • 防止重新链接后树的高度增加
• 作为叶子结点可以直接删除
• 被删除的结点只有左子树或者只有右子树，勇其左子树或者右子树替换它（结点替换）
• 被删除的结点既有左子树又有右子树
  • 以中序前趋值替换之（值替换），然后再删除该前趋结点。前趋结点是左子树中最大的结点。
  • 也可以用中序遍历的后继结点替换之，然后再删除该结点的后继结点。后继是右子树中最小的结点。

平衡二叉树

• 问题：如何提高形态不均衡的二叉排序树的查找效率？

• 解决方法：做“平衡化”处理，即尽量让二叉树的形态均衡。

• 高度：子树的层数

• 定义

  • 又称为AVL树
  • 一棵平衡二叉树或者是空树，或者是具有下列性质的二叉排序树
    • 左子树与右子树的高度之差的绝对值小于等于1；
    • 左子树和右子树也是平衡二叉排序树。

• 为了方便起见，给每个结点附加一个数字，给出该结点左子树与右子树的高度差。这个数字称为结点的平衡因子（BF）

  • 平衡因子 = 结点左子树的高度-结点右子树的高度
  • 左右子树一样的话为0
  • 左子树比较高的话为1，
  • 右子树比较高的话为-1.

• 如果在一棵AVL树种插入一个新结点后造成失衡，则必须重新调整树的结构，使之恢复平衡。

• 平衡调整的四种类型，LL，LR,RL,RR

  • 调整原则：
    • 降低高度
    • 保持二叉排序树性质

LL型调整

• 中间结点带左子树α一起上升
• 原来最上面结点成为原来中间结点的右孩子
• 原来中间节点结点的右子树β作为原来最上面的左子树

RR型调整

• 中间结点带着右子树β一起上升
• 将原来最上面的结点作为自己的左孩子
• 原来中间结点的左孩子作为原来最上面节点的右子树

LR型调整

• 将最下面的结点上升到最上面
• 让原来中间的结点成为原来最下面结点的左孩子
• 让原来最上面的结点作为原来最下面结点的右孩子
• 原来最下面的结点的左子树β作为原来中间结点的右子树
• 原来最下面结点的右子树α作为原来最上面结点的左子树

RL型调整

与LR型同理

散列表

• 记录的存储位置与关键字之间存在对应关系。

  • 对应关系——hash函数

• 散列方法（杂凑法）

  • 选取某个函数，依该函数按关键字计算元素的存储位置，并按此存放；
  • 查找时，由同一个函数对给定值K计算地址，将k与地址单元种元素关键码进行比，确定查找是否成功。

• 散列函数（杂凑函数）：散列方法种使用的转换函数。

• 散列表（杂凑表）：按照上述思想构造的表。

• 冲突：不同的关键码映射到同一个散列地址

  key1 ！=key2，但是H（key1） = H（key2）

• 同义词：具有相同函数值的多个关键字

• 在散列查找方法种，冲突是不可能避免的，只能尽可能减少。

要解决的问题：

• 构造好散列函数
  • 所选取的函数尽可能简单，以边提高转换速度；
  • 所选函数对关键码计算出的地址，应在散列地址集中致均匀分布，以减少空间浪费。
• 制定一个好的解决冲突的方案
  • 查找时，如果从散列函数计算出的地址中查不到关键码，则应当译据解决冲突的规则，有规律的查询其他相关单元。

散列函数的构造方法

• 直接定址法

  优点：以关键码key的某个线性数值为散列地址，不会产生冲突

  缺点：要占用连续的地址空间，空间效率低。

• 数字分析法

• 平方取种法

• 折叠法

• 除留余数法

• 随机数法

处理冲突的方法：

• 开放定址法（开地址法）

  • 有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。
  • 如，用除留余数法得到的地址如果已经被占用，那么在这个地址的位置加一个数字
  • 加数的常用方法：
    • 线性探测法
    • 二次探测法
    • 伪随机探测法

• 链地址法（拉链法）

  • 相同散列地址的记录链成一个单链表
  • m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构
  • 建立方法
    • 取数据元素的关键字key，计算其散列函数值（地址）。若该地址对应的链表为空，则将该元素插入此链表；否则执行Step2解决冲突。
    • 根据选择的冲突处理方法，计算关键字key的下一个存储地址。若该地址对应的链表不为空，则利用链表的前插法或后插法将该元素插入此链表。

• 再散列法（双散列函数法）

• 建立一个公共溢出区

散列表的查找效率分析：

ASL取决于：

• 散列冲突
• 处理冲突的方法
• 散列表的装填因子α

装填因子=表中填入的记录数/哈希表的长度

• α越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较的次数就越多。

结论

• 散列表技术具有很好的平均性能，优于一些传统的技术
• 链地址法由于开地址法
• 除留余数法作散列表由于其他类型函数