所有文章 分类 标签 笔记 文档 关于 简体中文

目录

查找算法和对应的数据结构

KKKPSJKEY 收录于 Learning 笔记
   约 8632 字   预计阅读 18 分钟    次阅读  
/search-algorithm-note/featured-image.jpg
目录

七大查找算法

1. 顺序查找

  • 顺序查找适合于存储结构为顺序存储或链接存储的线性表，时间复杂度为O(n)

2. 二分查找

  • 元素必须是有序的，如果是无序的则要先进行排序操作。

3. 插值查找

  • 基于二分查找算法，将查找点的选择改进为自适应选择，mid=low+(key-a[low])/(a[high]-a[low])*(high-low)，适合表长较大，而关键字分布又比较均匀的查找表

4. 斐波那契查找

  • 二分查找的一种提升算法，通过运用黄金比例的概念在数列中选择查找点进行查找，要求开始表中记录的个数为某个斐波那契数小1，及n=F(k)-1;开始将k值与第F(k-1)位置的记录进行比较(及mid=low+F(k-1)-1)。如果>，low=mid+1,k-=2;如果<，high=mid-1,k-=1。

5. 树表查找

（1）二叉查找树与平衡二叉树（AVL）

（2）平衡查找树之2-3查找树**（2-3 Tree）** ：其实和B树很像，只不过限定了m=3，节点只有1个或者2个key

./1.png

./2.png

效率：

./3.png

（3）平衡查找树之红黑树（Red-Black Tree）

　　2-3树实现起来比较复杂，于是就有了一种简单实现2-3树的数据结构，即红黑树（Red-Black Tree）。

　**基本思想：**红黑树的思想就是对2-3查找树进行编码，尤其是对2-3查找树中的3-nodes节点添加额外的信息。红黑树中将节点之间的链接分为两种不同类型，红色链接，他用来链接两个2-nodes节点来表示一个3-nodes节点。黑色链接用来链接普通的2-3节点。特别的，**使用红色链接的两个2-nodes来表示一个3-nodes节点，并且向左倾斜，即一个2-node是另一个2-node的左子节点。**这种做法的好处是查找的时候不用做任何修改，和普通的二叉查找树相同。

　　红黑树是一种具有红色和黑色链接的平衡查找树，同时满足：

  • 红色节点向左倾斜
  • 一个节点不可能有两个红色链接
  • 整个树完全黑色平衡，即从根节点到所以叶子结点的路径上，黑色链接的个数都相同。

　　下图可以看到红黑树其实是2-3树的另外一种表现形式：如果我们将红色的连线水平绘制，那么他链接的两个2-node节点就是2-3树中的一个3-node节点了。

./4.png

　　红黑树的特性:

  • （1）每个节点或者是黑色，或者是红色。
  • （2）根节点是黑色。
  • （3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
  • （4）如果一个节点是红色的，则它的子节点必须是黑色的。
  • （5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点。

下图是一个典型的红黑树，从中可以看到最长的路径(红黑相间的路径)是最短路径的2倍：平均高度大约为logn

./5.png

红黑树这种数据结构应用十分广泛，在多种编程语言中被用作符号表的实现，如：

  • Java中的java.util.TreeMap,java.util.TreeSet；
  • C++ STL中的：map,multimap,multiset；
  • .NET中的：SortedDictionary,SortedSet 等。

（4）B树和B+树（B Tree/B+ Tree）

平衡查找树中的2-3树以及其实现红黑树。2-3树中，一个节点最多有2个key，而红黑树则使用染色的方式来标识这两个key。B树，概括来说是一个节点可以拥有多于2个子节点的二叉查找树。与自平衡二叉查找树不同，B树为系统最优化大块数据的读和写操作。B-tree算法减少定位记录时所经历的中间过程，从而加快存取速度。普遍运用在数据库和文件系统。

所以B树其实是对*2-3树的扩展*

*B+树是对B树的变形：*

./6.png

B+ 树的优点在于：

  • 由于B+树在内部节点上不好含数据信息，因此在内存页中能够存放更多的key。 数据存放的更加紧密，具有更好的空间局部性。因此访问叶子几点上关联的数据也具有更好的缓存命中率。
  • B+树的叶子结点都是相链的，因此对整棵树的便利只需要一次线性遍历叶子结点即可。而且由于数据顺序排列并且相连，所以便于区间查找和搜索。而B树则需要进行每一层的递归遍历。相邻的元素可能在内存中不相邻，所以缓存命中性没有B+树好。

　　但是B树也有优点，其优点在于，由于B树的每一个节点都包含key和value，因此经常访问的元素可能离根节点更近，因此访问也更迅速。

B/B+树常用于文件系统和数据库系统中，它通过对每个节点存储个数的扩展，使得对连续的数据能够进行较快的定位和访问，能够有效减少查找时间，提高存储的空间局部性从而减少IO操作。它广泛用于文件系统及数据库中，如：

  • Windows：HPFS文件系统；
  • Mac：HFS，HFS+文件系统；
  • Linux：ResiserFS，XFS，Ext3FS，JFS文件系统；
  • 数据库：ORACLE，MYSQL，SQLSERVER等中。

树表查找总结：

　　二叉查找树平均查找性能不错，为O(logn)，但是最坏情况会退化为O(n)。在二叉查找树的基础上进行优化，我们可以使用平衡查找树。平衡查找树中的2-3查找树，这种数据结构在插入之后能够进行自平衡操作，从而保证了树的高度在一定的范围内进而能够保证最坏情况下的时间复杂度。但是2-3查找树实现起来比较困难，红黑树是2-3树的一种简单高效的实现，他巧妙地使用颜色标记来替代2-3树中比较难处理的3-node节点问题。红黑树是一种比较高效的平衡查找树，应用非常广泛，很多编程语言的内部实现都或多或少的采用了红黑树。

　　除此之外，2-3查找树的另一个扩展——B/B+平衡树，在文件系统和数据库系统中有着广泛的应用。

6. 分块查找

  • 分块查找又称索引顺序查找，它是顺序查找的一种改进方法。

7. 哈希查找

  • 散列查找（直接定址），哈希函数构造方法（尽量减少冲突）+解决冲突的方法（开放定址和拉链法）

以空间换时间，map的本质就是Hash表

./7.png

字符串匹配算法：KMP（从O（mn）降低到O（m+n））

KMP如何借助next数组移位 　　道理其实很简单，如果目标串和模式串的字符匹配，那么就同时移动两者的下标；如果不能匹配，就使用next数组来获得移动的数目。但编程方法实现的话，next数组我们需要再修改一下，这样就能够直接获得当前失配位置应当对应的新的模式串字符下标（因为我们关注的是在失配字符之前有几个匹配的字符）。

所以，next数组来对每个位置找到最长公共前缀

适合主串和子串有很多部分匹配的情况

大致求next数组的代码：注意这里是设置最开始是-1和0，也可以设置0，1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

void kmp(const string& match, const string& pattern) {
    int posP = -1, posM = -1, lenM = match.length(), lenP = pattern.length();
    while (posP < lenP && posM < lenM) {
        if (posP == -1 || pattern[posP] == match[posM]) {
            posP++;
            posM++;
        } else {
            posP = nextArr[posP];
        }
    }
}

查找数据结构

查找概论

查找表

定义

查找表（Search Table）是同一类型的数据元素（或记录）的集合。

查找表分类
静态查找表

静态查找表（Static Search Table）：只做查找操作的查找表。

它的主要操作有：

  1. 查找某个“特定的”数据元素是否存在于查找表中。
  2. 检索某个“特定的”数据元素和各种属性。
动态查找表

动态查找表（Dynamic Search Table）：在查找过程中同时插入不存在的数据元素， 或在查找过程中删除已经存在的数据元素。

它的主要操作有：

  1. 查找时插入数据元素。
  2. 查找时删除数据元素。

关键字

关键字（Key）是数据元素中某个数据项的值，又称为键值。（难理解）

若此关键字可以唯一地标识一个记录，则称此关键字为主关键字（Primary key）。

可以识别多个数据元素（或记录）的关键字，是次关键字（Secondary Key）。 意思是根据次关键字可以查询到多条数据元素吗？

查找定义

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

若查找到了数据元素，则查找成功；否则，查找失败。

查找结构

面向查找操作的数据结构叫做查找结构。

顺序表查找

概念

顺序表查找（Sequential Search）又叫线性查找，是最基本的查找技术。它的查找过程是：

  1. 从表中第一个（或最后一个）记录开始，逐个比较记录的关键字和给定值。
  2. 若某个记录的关键字和给定值相等，则查找成功。
  3. 若一直查找到最后一个（或第一个）记录，其关键字都不等于给定值，则查找失败。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int Sequential_search(int *a, int n, int key)
{
    int i;
    for(i = 1; i < n; i++){
        if(a[i] == key){
            return i;
        }
    }
    return 0;
}

顺序表查找代码优化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

int Sequential_search(int *a, int n, int key)
{
    int i;
    a[0] = key;
    i = 1;
    while(a[i] != key){
        i--;
    }
    return i;   // 当i等于0时查找失败
}

或

1
2
3
4
5
6
7
8
9

int Sequential_search(int *a, int n, int key)
{
    int i;
    a[n-1] = key;
    while(a[i] != key){
        i++;
    }
    return i;   // 当i等于n-1时查找失败
}

时间复杂度

$O(n)$

有序表查找

折半查找

摘抄

一看就懂的知识点，一般不再打字记录笔记，直接摘抄书本。

./8.webp

数据结构_查找_折半查找

代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int Binary_search(int *a, int n, int key)
{
    int low, high, mid;
    low = 1;
    high = n;
    while(low <= high){
        /*1*/ mid = (low + high) / 2;
        if(key > a[mid]){
            low = mid + 1;
        }else if(key < a[mid]){
            high = mid - 1;
        }else{
            return mid;
        }
    }
    /*2*/ return 0;
}

第1行，取值相当于PHP中的 floor 函数。

第2行，查找结果不是 mid 就是查找失败。这说明，若查找表中存在要 查找的关键字，那么该关键字的位置一定是某个中间位置。不能理解这点。

差值查找

差值计算公式

$key-a[low]\over a[high]-a[low]$

这个公式是如何得到的？

代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17

int Binary_search(int *a, int n, int key)
{
    int low, high, mid;
    low = 1;
    high = n;
    while(low <= high){
        mid = (key - a[low]) / (a[high] - a[low]);
        if(key > a[mid]){
            low = mid + 1;
        }else if(key < a[mid]){
            high = mid - 1;
        }else{
            return mid;
        }
    }
    /*2*/ return 0;
}
时间复杂度

$O(logn)$

斐波那契查找

代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30

int Fibonacci_Search(int *a, int n, int key)
{
    int low, high, mid, i, k;
    low = 1;
    high = n;
    k = 0;
    /*1*/ while(n>F[k]-1){  // 计算n位于斐波那契数列的位置
        k++;
    }
    for(i = n; i < F[k]-1; i++){    // 将不满的数值补全
        a[i] = a[n];
    }
    while(low <= high){
        mid = low + F[k-1] - 1;     // 计算当前分隔的下标
        if(key < a[mid]){
            high = mid - 1;
            /*2*/ k = k -1; // 斐波那契数列下标减一位
        }else if(key > a[mid]){
            low = mid + 1;
            /*3*/ k = k - 2;    // 斐波那契数列下标减二位
        }else{
            if(mid <= n){
                return mid;     // 若相等则说明mid即为查找到的位置
            }else{
                return n;       // 若mid>n说明是补全数值，返回n
            }
        }
    }
    return 0;
}

理解不了第1行、第2行、第3行。

摘抄

./9.webp

数据结构_查找_斐波那契查找_核心

不理解上图中的范围个数是怎么得到的。

./10.webp

数据结构_查找_斐波那契查找_范围个数示意图

这个图好像有助于理解某些东西。

线性索引查找

摘抄

概念

./11.webp

数据结构_查找_线性索引查找_概念

稠密索引
概念

./12.webp

数据结构_查找_线性索引查找_稠密索引_概念

对于稠密索引的的索引表，索引项一定是按照关键码有序的排列。

分块索引
概念

./13.webp

数据结构_查找_线性索引查找_分块索引_概念

./14.webp

数据结构_查找_线性索引查找_分块索引_例子

时间复杂度（不懂）

./15.webp

数据结构_查找_线性索引查找_分块索引_时间复杂度

倒排索引
概念

./16.webp

数据结构_查找_线性索引查找_倒排索引_概念

存储技巧

./17.webp

数据结构_查找_线性索引查找_倒排索引_存储技巧

二叉排序树

二叉排序树查找操作代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

typedef struct BiTNode
{
    int data;
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

Status SearchBST(BiTree T, int key, BiTree f, BiTree *p)
{
    if(!T){
        *p = f;
        return FALSE;
    }else if(key == T->data){
        *p = T;
        return TRUE;
    }else if(key > T->data){
        return SearchBST(T->rchild, key, T, p);
    }else{
        return SearchBST(T->lchild, key, T, p);
    }
}

二叉排序树插入操作代码

二叉排序树插入操作代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

Status InsertBST(BiTree *T, int key)
{
    BiTree p, s;
    if(!SearchBST(*T, key, NULL, &p)){
        s = (BiTree)malloc(sizeof(BiTNode));
        s->data = key;
        s->lchild = s->rchild = NULL;
        if(!p){
            *T = s;
        }else if(key > p->data){
            p->rchild = s;
        }else{
            p->lchild = s;
        }
        return TRUE;
    }else{
        return FALSE;
    }
}

如果查找到的是叶子结点，插入新的结点很容易。

如果查找到的不是叶子结点，假如此结点刚好有左右孩子结点，如何插入新的结点？

查找停止的情况有两种：找到了和关键字匹配的记录；查找失败。第二种情况，必然 是遍历到了叶子结点。好不能透彻地理解这点，只能大概不确定地得出这样的结论。

创建二叉排序树代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

int CreateBST(void)
{
    int i;
    int a[10] = {62, 88, 58, 47, 35, 73, 51, 99, 37, 93};
    BiTree T = NULL;
    for(i = 0; i < 10; i++){
        InsertBST(T, a[i]);
    }
    
    return 0;
}

二叉排序树删除操作代码

代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

Status Delete(BiTree *p)
{
    BiTree q, s;
    if((*p)->rchild == NULL){
        q = *p;
        *p = (*p)->lchild;
        free(q);
    }else if((*p)->lchild == NULL){
        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;
        if(q != *p){
            q->rchild = s->lchild;
        }else{
            q->lchild = s->lchild;
        }
        free(s);
    }
}

二叉排序树删除结点代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

Status DeleteBST(BiTree *T, int key)
{
    if(!*T){
        return FALSE;
    }else{
        if(key == (*T)->data){
            return Delete(T);
        }else if(key < (*T)->data){
            return DeleteBST(&(*T)->lchild, key);
        }else{
            return DeleteBST(&(*T)->rchild, key);
        }
    }
}

删除操作有四种情况：

  1. 要删除的结点是叶子结点。
  2. 要删除的结点有左孩子。
  3. 要删除的结点有右孩子。
  4. 要删除的结点有左右孩子。理解不了这种情况的代码。
代码解读

./18.webp

数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_7

./19.webp

数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_1

./20.webp

数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_2

./21.webp

数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_3

./22.webp

数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_4

./23.webp

数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_5

./24.webp

数据结构_查找_二叉排序树_二叉排序树删除操作代码_代码解读_6

摘抄

概念

./25.webp

数据结构_查找_二叉排序树_概念

平衡二叉树（AVL树）

概念

平衡二叉树

平衡二叉树（Self-Balancing Binary Search Tree 或 Height-Balanced Binary Search Tree）， 是一种二叉排序树，其中每一个结点的左子树和右子树的高度差至多等于1。

平衡因子

平衡二叉树上的结点的左子树减去右子树的得到的差值，叫做平衡因子（Balance Factor）。

平衡因子可能的值是 -1，0 和 1。

./26.webp

数据结构_查找_平衡二叉树（AVL树）_平衡因子

书中认为图3中，结点58的左子树的高度是2，我认为是3。

最小不平衡子树

距离插入结点最近的、平衡因子的绝对值大于 1 的结点为根的子树，叫做最小不平衡子树。

什么叫插入结点？是指插入新结点的那个位置吗？

./27.webp

数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树

结点58的左子树的高度，我认为是3。

平衡二叉树实现算法代码

旋转操作

树的结点结构

1
2
3
4
5
6

typedef struct BiTNode
{
    int data;
    int bf;     // 结点的平衡因子
    struct BiTNode *lchild, *rchild;
}BiTNode, *BiTree;

右旋转操作代码

1
2
3
4
5
6
7
8

void R_Rotate(BiTree *p)
{
    BiTree L;
    L = (*p)->lchild;   // L指向p的左子树根结点
    (*p)->lchild = L->rchild;   // L的右子树挂结为p的左子树
    L->rchild = (*p);
    *p = L;     // P指向新的根结点
}

左旋操作代码

1
2
3
4
5
6
7
8

void L_Rotate(BiTree *p)
{
    BiTree R;
    R = (*p)->rchild;   // R指向p的右子树根结点
    (*p)->rchild = R->lchild;   // R的左子树挂接为p的右子树
    R->lchild = (*p);
    *p = R;     // p指向新的根结点
}

理解不了。按照我的思路，p 是 R->lchild 的左子树，可是这和左旋转 后的结果不吻合。

重新画了几次，根据代码，可以得到预期效果图了。可是，L 的右子树为何 会变成 p 的左子树？

旋转操作的关键在于：第一步的时候，原树拆成了两棵树。旋转过程见纸质笔记。

左平衡旋转处理函数代码
代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

#define LH +1;      // 左高
#define EH 0;       // 等高
#define RH -1;      // 右高
void LeftBalance(BiTree *T)
{
    BiTree L, Lr;
    L = (*T)->lchild;       // L指向T的左子树根结点
    switch(L->bf){
        case LH:
            /*1*/ (*T)->bf = L->bf = EH;
            R_Rotate(T);
            break;
        case RH:
            Lr = L->rchild;     // Lr指向T的左孩子的右子树的根
            switch(Lr->bf){     // 修改T及其左孩子的平衡因子
                case LH:
                    (*T)->bf = RH;
                    L->bf = EH;
                    break;
                case EH:
                    (*T)->bf = L->bf = EH;
                    break;
                case RH:
                    (*T)->bf = EH;
                    L->bf = LH;
                    break;
            }
            Lr->bf = EH;
            L_Rotate(&(*T)->lchild);    // 对T的左子树作左旋平衡处理
            R_Rotate(T);    // 对T做右旋平衡处理
    }
}
代码解读

./28.webp

数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树_左平衡旋转处理函数代码_代码解读_1

./29.webp

数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树_左平衡旋转处理函数代码_代码解读_2

./30.webp

数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树_左平衡旋转处理函数代码_代码解读_3

./31.webp

数据结构_查找_平衡二叉树（AVL树）_最小不平衡子树_左平衡旋转处理函数代码_代码解读_4

主函数代码
代码
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58

Status InsertAVL(BiTree *T, int e, Status *taller)
{
    if(!T){
        *T = (BiTree)malloc(sizeof(BiTNode));
        (*T)->data = e;
        (*T)->lchild = (*T)->rchild = NULL;
        (*T)->bf = EH;
        *taller = TRUE;
    }else{
        if(e = (*T)->data){
            *taller = FALSE;
            return FALSE;
        }
        if(e <(*T)->data){
            if(!InsertAVL(&(*T)->lchild, e, taller)){
                return FALSE;
            }
            if(taller){
                switch((*T)->bf){
                    case LH:
                        LeftBalance(T);
                        *taller = FALSE;
                        break;
                    case EH:
                        (*T)->bf = LH;
                        *taller = TRUE;
                        break;
                    case RH:
                        (*T)->bf = EH;
                        *taller = FALSE;
                        break;
                }
            }
        }else{
            if(!InsertAVL(&(*T)->rchild, e, taller)){
                return FALSE;
            }
            if(*taller){
                switch((*T)->bf){
                    case LH:
                        (*T)->bf = EH;
                        *taller = FALSE;
                        break;
                    case EH:
                        (*T)->bf = RH;
                        *taller = TRUE;
                        break;
                    case RH:
                        RightBalance(T);
                        *taller = FALSE;
                        break;
                }
            }
        }
    }
    
    return TRUE;
}
代码解读

《大话数据结构》中的代码，好像有很多错误，只可以当作逼真的伪代码去看待。

./32.webp

数据结构_查找_平衡二叉树（AVL树）_平衡二叉树实现算法代码_代码解读_1

./33.webp

数据结构_查找_平衡二叉树（AVL树）_平衡二叉树实现算法代码_代码解读_2

./34.webp

数据结构_查找_平衡二叉树（AVL树）_平衡二叉树实现算法代码_代码解读_3

./35.webp

数据结构_查找_平衡二叉树（AVL树）_平衡二叉树实现算法代码_代码解读_4

多路查找树（B树）

摘抄

必要性

要操作的数据非常大，大到无法在内存中处理。

定义

多路查找树（multi-way search tree）的每一个结点的孩子数可以多于两个，且每一个结点 处可以存储多个元素。元素之间存在某种特定的排序关系。

2-3树
概念

./36.webp

数据结构_查找_多路查找树_23树_概念_1

./37.webp

数据结构_查找_多路查找树_23树_概念_2

2-3树的插入实现

./38.webp

数据结构_查找_多路查找树_23树_插入_1

./39.webp

数据结构_查找_多路查找树_23树_插入_2

./40.webp

数据结构_查找_多路查找树_23树_插入_3

./41.webp

数据结构_查找_多路查找树_23树_插入_4

2-3树的删除实现

./42.webp

数据结构_查找_多路查找树_23树_删除_1

./43.webp

数据结构_查找_多路查找树_23树_删除_2

./44.webp

数据结构_查找_多路查找树_23树_删除_3

./45.webp

数据结构_查找_多路查找树_23树_删除_4

./46.webp

数据结构_查找_多路查找树_23树_删除_5

./47.webp

数据结构_查找_多路查找树_23树_删除_6

./48.webp

数据结构_查找_多路查找树_23树_删除_7

./49.webp

数据结构_查找_多路查找树_23树_删除_8

可以理解这些方法能够保证删除的元素在被删除后，新树仍然是2-3树，但不明白这么做的规律性， 更无能力用代码实现删除操作。

2-3-4树
概念

./50.webp

数据结构_查找_多路查找树_234树_概念

2-3-4树的插入和删除

./51.webp

数据结构_查找_多路查找树_234树_插入删除_1

./52.webp

数据结构_查找_多路查找树_234树_插入删除_2

B树
概念与性质

./53.webp

数据结构_查找_多路查找树_B树_概念与性质_1

./54.webp

数据结构_查找_多路查找树_B树_概念与性质_2

减少内存与外存交换数据的频率的原因

./55.webp

数据结构_查找_多路查找树_B树_减少内存与外存交换数据的频率的原因_1

./56.webp

数据结构_查找_多路查找树_B树_减少内存与外存交换数据的频率的原因_2

B+树
产生原因–优化B树

http://7xt25g.com1.z0.glb.clouddn.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%9F%A5%E6%89%BE_%E5%A4%9A%E8%B7%AF%E6%9F%A5%E6%89%BE%E6%A0%91_B%E6%A0%91_%E4%BA%A7%E7%94%9F%E5%8E%9F%E5%9B%A0.png

数据结构_查找_多路查找树_B加树_产生原因

概念

./58.webp

数据结构_查找_多路查找树_B加树_概念_1

./59.webp

数据结构_查找_多路查找树_B加树_概念_2

与B树的对比

./60.webp

数据结构_查找_多路查找树_B加树_与B树的对比

散列查找表概述

摘抄

定义

./61.webp

数据结构_查找_散列查找表概述_摘抄_定义_1

散列表查找步骤

1.存储时，通过散列函数计算记录的散列地址，并按该存储地址存储这条记录。

2.查找时，通过相同的散列函数计算记录的散列地址，并按该散列地址读取记录。

散列表适用场景

1.最适合的求解问题是查找与给定关键字等值的记录。

2.同样的关键字对应很多记录的问题，不适合用散列表查找。

3.范围查找，不适合用散列表查找。

冲突

./62.webp

数据结构_查找_散列查找表概述_摘抄_冲突

散列函数的构造方法
设计好的散列函数的原则

1.计算简单。

2.散列地址分布均匀。这和“使用连续的存储空间存储记录”有关吗？

直接定址法

概念

http://7xt25g.com1.z0.glb.clouddn.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%9F%A5%E6%89%BE_%E6%95%A3%E5%88%97%E6%9F%A5%E6%89%BE%E8%A1%A8%E6%A6%82%E8%BF%B0_%E7%9B%B4%E6%8E%A5%E5%AE%9A%E5%9D%80%E6%B3%95_%E6%A6%82%E5%BF%B5.png

数据结构_查找_散列查找表概述_摘抄_直接定址法_概念

优缺点

http://7xt25g.com1.z0.glb.clouddn.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84_%E6%9F%A5%E6%89%BE_%E6%95%A3%E5%88%97%E6%9F%A5%E6%89%BE%E8%A1%A8%E6%A6%82%E8%BF%B0_%E7%9B%B4%E6%8E%A5%E5%AE%9A%E5%9D%80%E6%B3%95_%E4%BC%98%E7%BC%BA%E7%82%B9.png

数据结构_查找_散列查找表概述_摘抄_直接定址法_优缺点

数字分析法

./65.webp

数据结构_查找_散列查找表概述_摘抄_数字分析法

只强调了抽取，对散列函数并无固定要求。

平方取中法

./66.webp

数据结构_查找_散列查找表概述_摘抄_平方取中法

折叠法

./67.webp

数据结构_查找_散列查找表概述_摘抄_折叠法

存储标签id时，我常用的方法是，存储“1,2,3,4”这样的字段。有人提出， 计算这4个标签ID的“位运算”，存储“位运算”的结果。具体应用方法已经 忘记。这也是折叠法。它们都减少了占用的存储空间。

除留余数法

./68.webp

数据结构_查找_散列查找表概述_摘抄_除留余数法_1

./69.webp

数据结构_查找_散列查找表概述_摘抄_除留余数法_2

随机数法

./70.webp

数据结构_查找_散列查找表概述_摘抄_随机数法

处理散列冲突的方法

摘抄

开放定址法

./71.webp

数据结构_查找_处理散列冲突的方法_摘抄_开放定址法_1

./72.webp

数据结构_查找_处理散列冲突的方法_摘抄_开放定址法_2

./73.webp

数据结构_查找_处理散列冲突的方法_摘抄_开放定址法_3

再散列函数法

./74.webp

数据结构_查找_处理散列冲突的方法_摘抄_再散列函数法

存储的时候，是否应该记录解决冲突使用的散列函数？若不记录，读取 数据的时候，如何计算存储时候的地址？

链接地址法

./75.webp

数据结构_查找_处理散列冲突的方法_摘抄_链接地址法_1

./76.webp

数据结构_查找_处理散列冲突的方法_摘抄_链接地址法_1

公共溢出法

./77.webp

数据结构_查找_处理散列冲突的方法_摘抄_公共溢出法_1

./78.webp

数据结构_查找_处理散列冲突的方法_摘抄_公共溢出法_2

散列表查找实现

代码

散列表结构

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

#define SUCCESS 1
#define UNSUCCESS 0
#define HASHSIZE 12
#define NULLKEY -32768
typedef struct 
{
    int *elem;      // 数据元素存储基址
    int count;      // 当前数据元素个数
}HashTable;
int m = 0;          // 散列表表长，全局变量

散列表初始化

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

Status InitHashTable(HashTable *H)
{
    int i;
    m = HASHSIZE;
    H->count = m;
    H->elem = (int *)malloc(m*sizeof(int));
    for(i = 0; i < m; i++){
        H->elem[i] = NULLKEY;
    }
    return OK;
}

散列函数

1
2
3
4

int Hash(int key)
{
    return key % m;
}

插入操作

1
2
3
4
5
6
7

void InsertHash(HashTable *H, int key)
{
    int addr = Hash(key);       // 求散列地址
    while(H->elem[addr] != NULLKEY)
        addr = (addr + 1) % m;
    H->elem[addr] = key;
}

查询操作

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void SearchHash(HashTable *H, int key)
{
    int addr = Hash(key);
    while(H->elem[addr] != key){
        addr = (addr + 1) % m;
        if(H->elem[addr] != key  || addr == Hash(key))
        {
            return UNSUCCESS;
        }
    }
    return SUCCESS;
}

if(H->elem[addr] != key || addr == Hash(key)) 中的 addr == Hash(key) 说明 循环回到原点，我不理解这点。

1
2
3
4

if(H->elem[addr] != key  || addr == Hash(key))
{
    return UNSUCCESS;
}

这块代码是否有问题？

当 H->elem[addr] != key 成立时，应该继续计算哈希地址。

散列表查找性能分析

./79.webp

数据结构_查找_散列表查找实现_摘抄_散列表查找性能分析_1

./80.webp

数据结构_查找_散列表查找实现_摘抄_散列表查找性能分析_2

更新于 2021-10-14
阅读原始文档
 DataStructure, Algorithm, Search
返回 | 主页