目录
1. 列表法
2. 作图法
3. 逐差法
4. 最小二乘法

1. 列表法
2. 作图法
3. 逐差法
（）优点：

充分利用测量数据，保持多次测量取平均值减小误差的优越性
可以绕过某些定值未知量求得测量结果。

（）要求：

两个物理量的函数关系可表达为多项式；
自变量必须是等间距变化，且较因变量有更高的测量准确度。

4. 最小二乘法

散列表的概念

散列表的两个例子



散列表存储的方法，主要是哈希函数

术语：冲突

术语：同义词

处理冲突的4种方法，以下只介绍两种

（一）开地址法，开地址法常用办法又分为三种


1.线性探测法




2.二次探测法


3.伪随机探测法


（二）链地址法（拉链法）
1.基本概念



2.链地址法建立散列表步骤



3.链地址法优点


散列表的查找





散列表查找效率

结论

散列表（空间换时间）
散列函数的构建
①直接定址法

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

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

例：Hash（key）=a*key+b（a、b是常数）
②除留余数法（优）

Hash（key）=key % p（p是一个整数）

关键：如何选取p？

技巧：设表长为m，取p<=m且为质数
处理冲突的方法
①开放地址法（开地址法）

思想：有冲突时就去找下一个为空的位置

例：除留余数法 Hi=（Hash（key）+di）% m ，( di为增量序列)

常用方法：

a：线性探测法
di为1,2,3,4，，，，m-1
b：二次探测法
di为1^2

-1^2，

2^2，

-2^2

，，，，

q^2
c：伪随机探测法
di为伪随机数序列
②链地址法（拉链法）（优）

思想：相同散列地址的记录链成一个单链表，然后一个数组将m个单链表的表头指针。

优点：非同义词（散列函数的值相同）不会冲突。

链表上的结点空间为动态申请，适合于结点数量不确定的
散列表的查找
过程：给定 k 值–>计算Hash(k)–>判断地址是否非空–>比对关键字（空就查找失败）–>按处理冲突的方法计算Hi

查找
文章目录
查找
概述
线性表查找
顺序查找
改进后的顺序查找
优点
缺点
折半查找
条件
基本思想
实现
折半查找判定树
定义
构造
性能分析
索引顺序查找
查找过程
要求
树表查找
动态查找表的特点
二叉排序树
性质
查找
路径
插入
构造
删除
三种情况
删除叶子节点
删除有一棵子树的节点
删除有两棵子树的节点
性能分析
平衡二叉树
定义
基本思想
调整
性能
B-树
定义&&查找
散列表
基本思想
散列函数
数字分析法
折叠法
除留余数法
随机数法
总结
冲突处理
开放定址法
线性探测法
二次探测法
随机探测法
链地址法
基本思想
算法
公共溢出区
基本思想
性能分析

概述


查找 ：在具有相同类型的记录构成的集合中找出满足给定条件的记录。


查找的结果 ：若在查找集合中找到了与给定值相匹配的记录，则称查找成功；否则，称查找失败。


关键码：可以标识一个记录的某个数据项。


键值：关键码的值。


主关键码：可以唯一地标识一个记录的关键码。


次关键码：不能唯一地标识一个记录的关键码。


静态查找：不涉及插入和删除操作的查找 。(在查找过程中不进行插入删除等操作)


动态查找：涉及插入和删除操作的查找。 (涉及插入和删除操作)


查找结构 ：面向查找操作的数据结构 ，即查找基于的数据结构。


线性表：适用于静态查找，主要采用顺序查找技术、折半查找技术。


树表：适用于动态查找，主要采用二叉排序树的查找技术。


散列表：静态查找和动态查找均适用，主要采用散列技术。


平均查找长度：将查找算法进行的关键码的比较次数的数学期望值定义为平均查找长度。或者说是自1到n求和 查找第 i 个记录的概率*查找第 i 个记录所需的关键码的比较次数


线性表查找
顺序查找
int SeqSearch1(int r[ ], int n, int k){	// 数组r[1] ~ r[n]存放查找集合   
     int i=n;
     while (i>0 && r[i]!=k)
         i--;
     return i;
}

改进后的顺序查找
int SeqSearch2(int r[ ], int n, int k) {	//数组r[1] ~ r[n]存放查找集合   
    r[0]=k;		// 即让0号元素一定会被查到，从而避免了判断是否越界 
    i=n;
    while (r[i]!=k)
        i --;
    return i;
}

在计算ASL的时候，有个奇葩的规定(之后待考证)，就是假设成功失败的可能都是1/2
优点

使用面广，算法简单
对存储没有任何要求，顺序和链式均可
对记录有序性也无要求，无论记录是否按照关键码有序

缺点

平均查找长度大，查找效率低

折半查找
条件

线性表中的记录必须按关键码有序
必须采用顺序存储

基本思想
在有序表中，取中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值小于中间记录的关键码，则在中间记录的左半区继续查找；若给定值大于中间记录的关键码，则在中间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失败。
实现
// 非递归实现
int BinSearch1(int r[ ], int n, int k){	//数组r[1] ~ r[n]存放查找集合 
    low=1;
    high=n;
    while (low<=high) {		// 此处一定要记住终止条件
        mid=(low+high)/2;            
        if (k<r[mid])  high=mid-1;
        else if (k>r[mid])  low=mid+1; 
        else return mid;
    }
    return 0;	// 其实是失败了
}

// 递归实现
int BinSearch2(int r[ ], int low, int high, int k){	//数组r[1] ~ r[n]存放查找集合    
    if (low>high) return 0;  // 终止条件
    else {
        mid=(low+high)/2;
        if (k<r[mid])	// 其实就是将前文的赋值改成了递归 
            return BinSearch2(r, low, mid-1, k);
        else  if (k>r[mid]) 
            return BinSearch2(r, mid+1, high, k); 
        else return mid;
     }
 }

折半查找判定树
定义
折半查找的过程可以用二叉树来描述，树中的每个结点对应有序表中的一个记录，结点的值为该记录在表中的位置。通常称这个描述折半查找过程的二叉树为折半查找判定树，简称判定树。
构造


当n=0时，折半查找判定树为空；


当n＞0时，折半查找判定树的根结点是有序表中序号为mid=(n+1)/2的记录，根结点的左子树是与有序表r[1] ~ r[mid-1]相对应的折半查找判定树，根结点的右子树是与r[mid+1] ~ r[n]相对应的折半查找判定树。


性能分析

具有n个结点的折半查找判定树的深度为  [log2n]+1   ([]表示向下取整)(n个节点的判定树和n个节点的完全二叉树深度相同)
查找成功：在表中查找任一记录的过程，即是折半查找判定树中从根结点到该记录结点的路径，和给定值的比较次数等于该记录结点在树中的层数。
查找不成功：查找失败的过程就是走了一条从根结点到外部结点的路径，和给定值进行的关键码的比较次数等于该路径上内部结点的个数，即使是失败了，其关键字比较个数最多也不会超过 [log2n]+1   ([]表示向下取整)

$ASL = \frac{n+1}{n}log_2(n+1)-1$
当n较大时，可近似为

$log_2(n+1)-1$
索引顺序查找

索引顺序查找即以索引顺序表表示静态查找表，又叫分块查找。

查找过程


由索引确定记录所在区间；(由于区间的索引是有序的，所以此处可以折半查找)


在顺序表的某个区间内进行查找。


要求


关键字项是子表中的最大关键字


指针项是子表中首记录的地址


分块有序，后面子表中的所有关键字均大于前面子表的最大关键字。


可以将长度为n的表均匀分成b块，每块含有s个记录，又假定表中每个记录的查找概率相等，则每块查找的概率为1/b,块中每个记录的查找概率为1/s.
若两者均采取顺序查找，则有如下公式，其在s=√n的时候取最小值√n+1

$ASL = \frac{1}{2}(\frac{n}{s}+s)+1$

若在索引中采取折半查找，在子表中使用顺序查找

$ASL = log_2(\frac{n}{s}+1)+\frac{s}{2}$


树表查找
动态查找表的特点

表结构本身在查找过程中动态生成
关键字查找成功则返回
否则插入关键字

二叉排序树
性质


或者是空的二叉树


或者是具有一下性质的二叉树


若它的左子树不空，则左子树上所有结点的值均小于根结点的值；


若它的右子树不空，则右子树上所有结点的值均大于根结点的值；


它的左右子树也都是二叉排序树




即二叉排序树采用递归方法定义，中序遍历二叉排序树可以得到一个按关键码有序的序列
typedef struct BiTNode { // 结点结构
    struct BiTNode  *lchild, *rchild; // 左右孩子指针
} BiTNode, *BiTree;

查找
在二叉排序树中查找给定值k的过程是：

若root是空树，则查找失败；
若k＝root->data，则查找成功；否则进行后续判断
若k＜root->data，则在root的左子树上查找；否则
在root的右子树上查找。

上述过程一直持续到k被找到或者待查找的子树为空，如果待查找的子树为空，则查找失败。
二叉排序树的查找效率在于只需查找两个子树之一。
路径
在查找过程中，生成了一条查找路径：

查找成功：从根结点出发，沿着左分支或右分支逐层向下直至关键字等于给定值的结点。
查找失败:从根结点出发，沿着左分支或右分支逐层向下直至指针指向空树为止。

Status SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p){	// 二叉搜索树
    if(!T){	// 如果是空树，直接返回FALSE，并以查找路径上最后一个访问的节点赋值给p
        p=f;
        return FALSE;
    }else if EQ(key,T->data.key){	// 如果找到了，就把其位置赋值给p
        p=T;
        return True;
    }else if LT(key,T->data.key){	//	如果查找值比当前值小，则递归搜索左子树
        return SearchBST(T->lchild,key,T,p);
    }else 
        return SearchBST(T->rchild,key,T,p);	// 否则搜索右子树
}

插入
根据动态查找表的定义，“插入”操作在查找不成功时才进行；
若二叉排序树为空树，则新插入的结点为新的根结点；否则，新插入的结点必为一个新的叶子结点，其插入位置由查找过程得到。
Status InsertBST(BiTree &T,ElemType e){		// 插入节点
    if(!SearchBST(T,e.key,NULL,p)){		// 未找到插入位置
        s=(BiTree)malloc(sizeof(BiTNode));		
        s->data=e;
        s->lchild=s->rchild=NULL;
        if(!p)
            T=s;
        else if LT(e.key,p->data.key)	// 左子树是插入位置
            p->lchild=s;
        else 
            p->rchild=s;	// 右子树是插入位置
        return TRUE;
    }
    else	// 已经有关键字相同的节点，不能再插入 
        return FALSE;
}

构造
// 可以认为root是一个全局的空指针
BiSortTree(int r[ ], int n){	// 从数组中读入，构建     
    for (i=0; i<n; i++){
       s=new BiNode<int>; 
       s->data=r[i];
       s->lchild=s->rchild=NULL;
       InsertBST(root, s);		// 不断插入
    }
}


一个无序序列可以通过构造一棵二叉排序树而变成一个有序序列;
每次插入的新结点都是二叉排序树上新的叶子结点;
找到插入位置后，不必移动其它结点，仅需修改某个结点的指针；
在左子树/右子树的查找过程与在整棵树上查找过程相同；
新插入的结点没有破坏原有结点之间的关系。

删除
三种情况

删除叶子节点
删除的节点只有一棵子树
删除的节点左右子树都有

删除叶子节点
将双亲结点中相应指针域的值改为空即可，不会影响其他树的其他部分；
删除有一棵子树的节点

若待删除节点p只有左子树，则让p的双亲节点重接p的左子树即可
若待删除节点p只有右子树，则让p的双亲节点重接p的右子树即可

删除有两棵子树的节点
先寻找左子树的最小值(右子树最大值也可)， 其实这整个函数采用递归的方式容易解决，因为将此待删除节点与其左子树最大的节点交换后，其左子树的最大节点就一定只有一颗子树。
BinTree Delete(ElementType X,BinTree BST){
    Position Tmp;
    if(!BST)	// 未找到节点
        printf("未找到节点\n");
    else if(X < BST->Data){		// 向左子树中删除
        BST->Left = Delete(X,BST->Left);
    }else if(X > BST->Data){	// 向右子树中删除
        BST->Right = Delete(X,BST->Right);
    }else {		// 找到了要删除的节点，即 X == BST->Data 
        if(BST->Left && BST->Right){	// 左右子树都存在
            Tmp = FindMin(BST->Right);
            BST->Data = Tmp->Data;
            BST->Right = Delete(BST->Data,BST->Right);
        }else {		// 仅存在一个子树或者都不存在
            Tmp = BST;
            if(!BST->Left)	 // 如果不存在左子树，则向上返回其新的根节点，即其右子树的根节点
                BST = BST->Right;
            else if(!BST->Right) // 如果不存在右子树，则向上返回其新的根节点，即其左子树的根节点
                BST = BST->Left;
            free(Tmp);
        } 
    }
    return BST;
}

性能分析
二叉排序树的性能取决于二叉排序树的形状，在O(log2n)和O(n)之间，O(n)即退化成斜树的情况。
平衡二叉树
定义

平衡二叉树：或者是一棵空的二叉排序树，或者是具有下列性质的二叉排序树：

根结点的左子树和右子树的深度最多相差1
根结点的左子树和右子树也都是平衡二叉树


平衡因子：结点的平衡因子是该结点的左子树的深度与右子树的深度之差。 在平衡树中，节点的平衡因子可以是1，0，-1.
最小不平衡子树：在平衡二叉树的构造过程中，以距离插入结点最近的、且平衡因子的绝对值大于1的结点为根的子树。

基本思想

在构造二叉排序树的过程中，每插入一个结点时，首先检查是否因插入而破坏了树的平衡性，若是，则找出最小不平衡子树，在保持二叉排序树特性的前提下，调整最小不平衡子树中各结点之间的链接关系，进行相应的旋转，使之成为新的平衡子树。

调整
设结点A为最小不平衡子树的根结点，对该子树进行平衡调整归纳起来有以下四种情况：

LL型	       左子树的左子树沉
RR型　　右子树的右子树沉
LR型　　左子树的右子树沉
RL型　　右子树的左子树沉

经过手动模拟，发现其含义指的是L(左子树)L(的左子树)被插入了,L(左子树)R(的右子树)被插入了,好吧其实通过模拟…根本没有必要记住特别复杂的公式和条件
对于LL型和RR型背下来,然后对于LR和RL型，则递归求解这个问题，从小的开始，一层一层向上化，大体思路就是右子树沉就左旋，左子树沉就右旋，这个问题日后再深究
性能
时间复杂度 O(logn)
B-树
定义&&查找


树中每个节点至多有m棵子树


若根节点不是叶子节点,则至少有两棵子树


除根之外的所有非终端节点至少有 [m/2]  (向上取整)棵子树


所有的非终端节点中包含以下信息数据
共子树个数个指针,和子树个数-1个关键字


所有的叶子节点都出现在同一层次上,并且不带信息(可以看作是外部节点活着查找失败的节点,实际上这些节点不存在,只想这些节点的指针为空.)


查找过程和二叉排序树相似,即通过关键字的对比查询到应该往哪个子树继续查找,
时间所限,不能继续深究其插入和删除了,后续补充
散列表
基本思想
在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。


散列表：采用散列技术将记录存储在一块连续的存储空间中，这块连续的存储空间称为散列表。


散列函数：将关键码映射为散列表中适当存储位置的函数。


散列地址：由散列函数所得的存储位置址 。


散列主要是面向查找的存储结构。


散列两个关键问题:


散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。


冲突的处理。如何采取合适的处理冲突方法来解决冲突。




冲突：对于两个不同关键码ki≠kj，有H(ki)＝H(kj)，即两个不同的记录需要存放在同一个存储位置,ki和kj相对于H称做同义词。


散列函数设计原则

计算简单。散列函数不应该有很大的计算量，否则会降低查找效率。
函数值即散列地址分布均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。



散列函数
#####　直接定址法
$H(key) = a＊key + b  （a，b为常数）$
    比如取　a= 1/10 , b=0

适用于 事先知道关键码，关键码集合不是很大且连续性较好。
数字分析法

根据关键码在各个位上的分布情况，选取分布比较均匀的若干位组成散列地址。

适用于: 能预先估计出全部关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新分析。
#####　平方取中法

对关键码平方后，按散列表大小，取中间的若干位作为散列地址（平方后截取）。

适用于: 事先不知道关键码的分布且关键码的位数不是很大。
折叠法

将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。

适用于: 关键码位数很多，事先不知道关键码的分布。
除留余数法
H(key)= key  mod  p
一般情况下，选p为小于或等于表长（最好接近表长）的最小素数或不包含小于20质因子的合数。
适用情况:除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布.
随机数法
哈希函数: H(key) = Random(key)
其中，Random 为伪随机函数,要保证函数值是在0～m－1之间。
通常，此方法用于对长度不等的关键字构造哈希函数。
总结
采用何种函数取决于建表的关键字集合的情况(包括关键字的范围和形态),考虑因素包括

计算哈希函数所需时间
关键字长度大小
哈希表的大小
关键字的分布情况
记录的查找频率

总的原则是使得产生冲突的可能性降到尽可能地小
冲突处理
开放定址法
由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。用开放定址发处理冲突得到的散列表叫闭散列表
线性探测法
$H_i=(H(key)＋d_i) Mod m   （d_i=1，2，…，m-1）$
线性探测能保证只要哈希表不满,就一定能找到插入的位置
堆积：在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象。可以简单理解为两个词虽然不是同义词,但是在第一次选址失败时,为了处理冲突而又在另一个地方聚集的现象.
int HashSearch1(int ht[ ], int m, int k) {	// 这是查找还是搜索?
    j=H(k);  
    if (ht[j]==k) return j;   //没有发生冲突，比较一次查找成功
    i=(j+1) % m;
    while (ht[i]!=Empty && i!=j)  {
        if (ht[i]==k) return i;  //发生冲突，比较若干次查找成功
        i=(i+1) % m;    //向后探测一个位置
    }
    if (i==j) throw "溢出";	// 遍历了整个数组,也没有位置可以存放
    else ht[i]=k;   //查找不成功时插入
}

二次探测法
当发生冲突时，寻找下一个散列地址的公式为：Hi=(H(key)＋di)% m
di取值均为平方数,1²,-1², 2², -2²…q²,-q²( q<=m/2)
但是,二次探测再散列只有在哈希表长m为形如4*j+3的形式的质数时才有可能做到  只要未满,就可插入.
随机探测法
当发生冲突时，下一个散列地址的位移量是一个随机数列，即寻找下一个散列地址的公式为：  Hi=(H(key)+di)% m（di是一个随机数列i=1，2，……，m-1）
计算机中产生随机数的方法通常采用线性同余法，

a0 = d
an=(b*an-1 + c )mod m   (n>0)

其中，d称为随机种子。当b、c和m的值确定后，给定一个随机种子，产生确定的随机数序列。
链地址法
基本思想

将所有散列地址相同的记录，即所有同义词的记录存储在一个单链表中（称为同义词子表），在散列表中存储的是所有同义词子表的头指针。

用链式处理冲突构造的散列表叫做开散列表。
设n个记录存储在长度为m的散列表中，则同义词子表的平均长度为n /m。
算法
Node<int> *HashSearch2(Node<int> *ht[ ], int m, int k){     
    j=H(k);
    p=ht[j];
    while (p && p->data!=k)
        p=p->next;
    if (p->data= =k) return p;	// 找到了k,则返回其地址
    else { 	// 没找到k,则将其插入到链表中(插表头简单一些)
        q=new Node<int>; q->data=k;
        q->next= ht[j];
        ht[j]=q;  
    }
}

公共溢出区
基本思想

散列表包含基本表和溢出表两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。查找时，对给定值通过散列函数计算散列地址，先与基本表的相应单元进行比较，若相等，则查找成功；否则，再到溢出表中进行顺序查找。

性能分析
在查找过程中，关键码的比较次数取决于产生冲突的概率。而影响冲突产生的因素有：


散列函数是否均匀


处理冲突的方法


散列表的装载因子
α=表中填入的记录数/表的长度


哈希表的查找效率只同装填因子有关，而同哈希表中的数据的个数无关






堆积现象
结构开销
插入删除效率
查找效率
估计容量




开散列表
无
有
高
高
不需要


闭散列表
有
无
低
低
需要