算法之经典查找算法

偏执的太偏执、 2022-06-06 13:15 231阅读 0赞

# 符号表 #

> 现代计算机和网络使得我们可以访问检索海量的信息。这些信息都存储在符号表（一个抽象的表格）中。实现一张高效的符号表，就是实现高效的查找插入任务。可以利用三种经典的数据结构：二叉查找树，红黑树，散列表实现符号表。
> 
> 符号表：存储键值对（键和值根据不同应用可以不同）的数据结构，支持插入（一组新的键值存入表）和查找（通过给定键获取对应的值）。

![这里写图片描述][SouthEast]

> 有序符号表：符号表中数据按照键有序的顺序存储，这样可以大大扩展操作符号表API，更加容易实现插入和搜索操作（例如递归操作，那么代码简洁高效），后期目标都是实现有序符号表。

# 基于无序链表的顺序查找 #

![这里写图片描述][SouthEast 1]  
sequentialsearchst.cpp

#include "sequentialsearchst.h"
    #include <stdlib.h>
    /* 生成一个单项链表，链接成表 */
    
    static Node first;//创建链表头
    static int N = 0;//链表长度
    static Node NewNode(Key key , Value val , Node next)
    {
    
        Node x = (Node)malloc(sizeof(struct STnode));
        x->key = key;
        x->val = val;
        x->next = next;
        return (x);
    }
    
    int size()
    {
        return N;
    }
    Value get(Key key)//通过键获取值
    {
        Node x;
        for(x = first ; x != NULL ; x = x->next){
            if(equals(x->key , key)){
                return x->val;//命中
            }
        }
        return NULL;//未命中
    }
    void put(Key key , Value val)//插入键-值，否则新建节点。
    {
        Node x;
        for(x = first ; x != NULL ; x = x->next){
       //遍历命中则更新
            if(equals(x->key , key)){
                x->val = val;
                return ;
            }
        }
        first = NewNode(key , val , first);//未命中插入链表前面
        N++;
    }
    bool Delete(Key key)
    {
        Node temp = first;
        Node x = first;
        while(x != NULL){
            if(equals(x->key , key) && x == first){
       //如果是表头
                first = first->next;
                free(temp);
                N--;
                return true;
            }
            if(equals(x->key , key) ){
       //如果不是表头
                temp->next = x->next;
                free(x);//释放x
                N--;
                return true;
            }
                temp = x;
                x = x->next;
        }
        return false;//键不存在
    }

sequentialsearchst.h

#ifndef SEQUENTIALSEARCHST_H
    #define SEQUENTIALSEARCHST_H
    
    typedef char Key;//定义键
    typedef int Value;//定义值
    typedef struct STnode* Node;
    
    struct STnode{
        Key key;
        Value val;
        Node next;
    };
    
    #define equals(key1 , key2) (( key1 == key2 ) ? 1 : 0)
    
    Value get(Key key);
    void put(Key key , Value val);
    bool Delete(Key key);
    int size();
    
    #endif // SEQUENTIALSEARCHST_H

main.cpp

#include "sequentialsearchst.h"
    #include <stdio.h>
    Key   keys[] = {
       'S' , 'E' , 'A' , 'R' , 'C' , 'H' , 'E' , 'X' , 'A' , 'M' , 'P' , 'L' , 'E'};
    Value vals[] = {
       0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,11 ,12};
    int main(void)
    {
        int i = 0;
        for(i = 0 ; i < 12 ; i++)
            put(keys[i] , vals[i]);
        Delete('S');
        printf("STcount = %d , S = %d \n" , size() , get('S') );
        Delete('R');
        printf("STcount = %d , M = %d \n" , size() , get('M') );
        Delete('X');
        printf("STcount = %d , X = %d \n" , size() , get('X') );
        Delete('A');
        printf("STcount = %d , P = %d \n" , size() , get('P') );
        return 0;
    }

仅仅需要链表删除第一个节点和后面节点的区别。  
![这里写图片描述][SouthEast 2]

# 基于有序数组二分查找 #

> 基于无序链表的顺序查找效率低下，使用有序数组（插入过程保持键有序），可以实现有序符号表然后使用二分查找，效率相对前面高了不少。  
> 一般情况下，二分查找比顺序查找块很多，是众多应用程序的实际选择。但是对于大型应用，插入操作太消耗时间了，也不太理想。为了重复实现查找和插入都快速的算法。必须进行适当的优化操作。

数据结构：一对平行的数组，一个存储键一个存储值。  
rank(Key key)：找出符号表小于key键的数量（因为有序，可以通过递归或迭代实现二叉查找）。  
查找：rank以后就可以精确查找。  
插入：当键存在，那么rank可以精确告诉我们在哪里插入新值；当键不存在，移动数组给新键腾出位置并插入数组各自位置。

![这里写图片描述][SouthEast 3]

#include "search.h"
    
    static Key * keys;
    static Value * vals;
    static int STcount = 0;
    
    void BinarySearchST(int capacity)
    {
        keys = (Key *)malloc(capacity * sizeof(Key));//动态数组存储键
        vals = (Value *)malloc(capacity * sizeof(Value));//动态数组存储值
    }
    int BinarySearchST_Size()
    {
        return STcount;
    }
    static int BinarySearchST_Rank(Key key)//因为从小到大有序，所以可以进行二分查找，速度很快
    {
        int lo = 0;//最低索引
        int hi = STcount-1;//最高索引
        while(lo <= hi){
            int mid = lo + (hi  - lo)/2;
            int cmp = key - keys[mid];
            if(cmp < 0) hi = mid -1;//在左边
            else if (cmp >0 ) lo = mid + 1;//在右边
            else return mid;//命中
        }
        return lo;//未命中则返回lo
    }
    
    Value BinarySearchST_Get(Key key)
    {
        if(STcount == 0)//空表，直接返回
            return 0;
        int i = BinarySearchST_Rank(key);
        if(i < STcount && (keys[i] - key) == 0)
            return vals[i];
        else
            return 0;//不在表中
    }
    void BinarySearchST_Put(Key key , Value val)
    {
        int i = BinarySearchST_Rank(key);//key对应的索引，这种方式比一个一个比较快得多。
        int j;
        if(i < STcount && (keys[i] - key) == 0){
       //键存在表中，更新value即可
            vals[i] = val;
            return ;
        }
        for(j = STcount ; j > i ; j--){
       //键不在表中，移动表，给新建腾出位置
            keys[j] = keys[j-1];
            vals[j] = vals[j-1];
        }
        keys[j] = key;
        vals[j] = val;//插入新键值
        STcount++;//表中元素加1
    }
    
    void BinarySearchST_Delete(Key key)
    {
        int i = BinarySearchST_Rank(key);
        for(int j = i;j < STcount ; j++){
            keys[j] = keys[j+1];//重点在于移动数组即可
            vals[j] = vals[j+1];
        }
        STcount--;
    }
    Key BinarySearchST_Min()
    {
        return keys[0];
    }
    Key BinarySearchST_Max()
    {
        return keys[STcount - 1];
    }
    Key BinarySearchST_Select(int k)
    {
        return keys[k];
    }
    Key BinarySearchST_Floor(Key key)
    {
        int i = BinarySearchST_Rank(key);
        return keys[i];
    }
    Key BinarySearchST_Ceiling(Key key)
    {
        int i = BinarySearchST_Rank(key);
        return keys[i];
    }

#include "search.h"
    
    Key   keys[] = {
       'S' , 'E' , 'A' , 'R' , 'C' , 'H' , 'E' , 'X' , 'A' , 'M' , 'P' , 'L' , 'E'};
    Value vals[] = {
       0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,11 ,12};
    int main(void)
    {
        int i = 0;
        BinarySearchST(20);//初始化数组大小
        for(i = 0 ; i < 12 ; i++)
            BinarySearchST_Put(keys[i] , vals[i]);
        BinarySearchST_Delete('S');
        printf("STcount = %d , S = %d \n" , BinarySearchST_Size() , BinarySearchST_Get('S') );
        BinarySearchST_Delete('R');
        printf("STcount = %d , M = %d \n" , BinarySearchST_Size() , BinarySearchST_Get('M') );
        BinarySearchST_Delete('X');
        printf("STcount = %d , X = %d \n" , BinarySearchST_Size() , BinarySearchST_Get('X') );
        BinarySearchST_Delete('A');
        printf("STcount = %d , P = %d \n" , BinarySearchST_Size() , BinarySearchST_Get('P') );
        return 0;
    }

运行结果和前面一样。

# 基于二叉树查找 #

这个就是树数据结构的使用。

> 对于符号表的实现，链表的优点在于插入方便，查找需要遍历降低了效率；有序数组在于查找方便，插入需要整体移动部分元素降低了效率。基于二叉树的实现结合了二者的优点，在插入和查找之间找到了平衡。  
> 二叉查找树（BST）是一颗节点有序的二叉树。每个节点的键都大于其左子树中的任意节点的键而小于右子树任意节点的键。

![这里写图片描述][SouthEast 4]

**二叉树查找动画：**  
![这里写图片描述][SouthEast 5]  
![这里写图片描述][SouthEast 6]

**二叉树插入动画：**

![这里写图片描述][SouthEast 7]

> 实际情况，经过很多次插入和删除之后，由于每次删除都是取右边子树节点，会导致树不再平衡。研究表明经过足够长随机的插入和删除之后，树的高度变成N的开平方而不是lgN。这对于现实的应用就可能不能满足性能要求。这是一个在很长时间内都没有找到一个自然简单且有效解决方案的二元搜索树问题，所以有了下面的改进操作红黑树。

对应代码

#ifndef SEARCH_H
    #define SEARCH_H
    #include <stdlib.h>
    #include <stdio.h>
    /*********************查找公共头文件部分*******************/
    typedef char Key;//定义键
    typedef int Value;//定义值
    /*******************************************************/
    /*******************************************************/
    typedef struct BSTnode* BSTNode;
    struct BSTnode{
        Key key;      //键
        Value val;    //值
        BSTNode left; //指向左子树
        BSTNode right;//指向右子树
        int N;        //以该节点为根的子树中节点个数
    };
    int BST_Size();//以该节点为根的子树中节点个数
    Value BST_Get(Key key);//获取键的值
    void BST_Put(Key key , Value val);//将键值存入表（键为空，则删除）
    void BST_Delete(Key key);//从表中删除键值
    void BST_preorder();//二叉查找树前序遍历
    void BST_inorder();//二叉查找树中序遍历
    void BST_postorder();//二叉查找树后序遍历
    /*********************************××××××******/
    #endif // SEARCH_H

#include "search.h"
    
    /* * 树就对应着递归，使用递归则可以使代码异常的简介出现 */
    /********内部私有方法*********/
    static BSTNode root;//二叉查找树根节点
    static BSTNode NewNode(Key key , Value val , int N)//新建节点
    {
        BSTNode x;
        x = (BSTNode)malloc( sizeof( struct BSTnode ) );
        x->key = key;
        x->val = val;
        x->N = N;
        return x;
    }
    static int Size(BSTNode x)
    {
        if(x == NULL)
            return 0;
        else
            return x->N;
    }
    static BSTNode Put(BSTNode x , Key key , Value val)//关键在于递归大法
    {
        if(x == NULL)
            return NewNode(key , val , 1);//未命中，则插入
        int cmp = key - x->key;
        if(cmp < 0)//比x键小，向坐子树查找
            x->left = Put(x->left , key , val);
        else if(cmp > 0)//比x键大，向右子树查找
            x->right = Put(x->right , key , val);
        else
            x->val = val;//命中更新数值
        x->N = Size(x->left) + Size(x->right) + 1;
        return x;
    }
    static Value Get(BSTNode x , Key key)//以x为根节点的子树中查找，命中返回值，未命中返回NULL
    {
        if(x == NULL)
            return 0;//未命中,返回0
        int cmp = key - x->key;
        if(cmp < 0)//比x键小，向坐子树查找
            return Get(x->left , key);
        else if(cmp > 0)//比x键大，向右子树查找
            return Get(x->right , key);
        else
            return x->val;//命中
    }
    static BSTNode DeleteMin(BSTNode x)
    {
        BSTNode temp;
        if(x->left == NULL){
            //temp = x->right;
            //free(x);//释放最后命中节点占用内存
            return x->right;//返回右边
        }
        x->left = DeleteMin(x->left);//迭代返回链接也全部更新
        x->N = Size(x->left) + Size(x->right) + 1;//更新节点个数
        return x;
    }
    static BSTNode Min(BSTNode x)
    {
        if(x->left == NULL) return x;
        return Min(x->left);//递归找到最小节点
    }
    static BSTNode Delete(BSTNode x , Key key)
    {
        BSTNode temp;
        if(x == NULL)
            return NULL;
        int cmp = key - x->key;
        if(cmp < 0)//继续寻找
            x->left = Delete(x->left , key);
        else if(cmp > 0)
            x->right = Delete(x->right , key);
        else{
       //命中，开始删除
            if(x->right == NULL){
       //只有左边子树,最简单，直接返回右子树节点，并释放内存
                temp = x->left;
                free(x);
                return temp;
            }
            if(x->left == NULL){
       //只有右边子树,最简单，直接返回左子树节点，并释放内存
                temp = x->right;
                free(x);
                return temp;
            }
            BSTNode t = x;//开始删除操作
            x = Min(t->right);//等于右子树最小节点
            x->right = DeleteMin(t->right);//断开右子树最小节点并更新沿路径。
            x->left = t->left;
            free(t);//删除节点信息
        }
        x->N = Size(x->left) + Size(x->right) + 1;
        return x;
    }
    /**************内部私有方法*************************/
    
    /********外部方法**********************************/
    int BST_Size()
    {
        return Size(root);
    }
    void BST_Put(Key key , Value val)//从根节点开始插入
    {
        root = Put(root , key , val);//
    }
    Value BST_Get(Key key)
    {
        return Get(root , key);
    }
    void BST_Delete(Key key)
    {
        Delete(root , key);
    }
    /************************************************/
    
    /**********树的测试********************************/
    /* * 前序遍历伪代码 */
    static void preorder(BSTNode tree)
    {
         if(tree != NULL)
         {
             printf("%c ", tree->key);
             preorder(tree->left);
             preorder(tree->right);
         }
    }
    /* * 中序遍历伪代码 */
    static void inorder(BSTNode tree)
    {
        if(tree != NULL)
        {
            inorder(tree->left);
            printf("%c ", tree->key);
            inorder(tree->right);
        }
    }
    /* * 后序遍历伪代码 */
    static void postorder(BSTNode tree)
    {
        if(tree != NULL)
        {
            postorder(tree->left);
            postorder(tree->right);
            printf("%c ", tree->key);
        }
    }
    void BST_preorder()
    {
        printf("preorder:");
        preorder(root);
        printf("\n");
    }
    void BST_inorder()
    {
        printf("inorder:");
        inorder(root);
        printf("\n");
    }
    void BST_postorder()
    {
        printf("postorder:");
        postorder(root);
        printf("\n");
    }
    /*************************************************/

#include "search.h"
    
    Key   keys[] = {
       'S' , 'E' , 'A' , 'R' , 'C' , 'H' , 'E' , 'X' , 'A' , 'M' , 'P' , 'L' , 'E'};
    Value vals[] = {
       0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,11 ,12};
    int main(void)
    {
        int i = 0;
        for(i = 0 ; i < 12 ; i++)
            BST_Put(keys[i] , vals[i]);
        BST_preorder();
        BST_inorder();
        BST_postorder();
        printf("S = %d \n" , BST_Get('S') );
        printf("R = %d \n" , BST_Get('R') );
        printf("A = %d \n" , BST_Get('A') );
        BST_Delete('A');
        BST_preorder();
        BST_inorder();
        BST_postorder();
        printf("S = %d \n" , BST_Get('S') );
        printf("R = %d \n" , BST_Get('R') );
        printf("A = %d \n" , BST_Get('A') );
        return 0;
    }

![这里写图片描述][SouthEast 8]  
在这个实现过程中，进一步深化了递归调用的含义以及作用。之所以使用递归为了后续更加复杂的算法打基础。

# 基于平衡二叉树查找 #

> 二叉搜索树在随机的情况下工作很好，但是在实际应用中插入的数据并不是随机的导致树高度增加，遍历消耗时间。  
> 平衡二叉树：所有子节点都根的高度都是一样的。这样可以使得搜索和插入复杂时间最小。

## 2-3树模型 ##

**定义：**

> 为了保证树的平衡性，允许一个节点里面含有多个链接。2-节点（一个键两个链接），3-节点（2个键三个链接）。一个完美平衡的2-3查找树所有空链接到根节点的距离应该都是相等的。  
> ![这里写图片描述][SouthEast 9]

**查找操作：**

> 1、先和根节点键比较，如果相等，则命中  
> 2、如果根节点没有命中，则根据比较结果找到相连的节点，并递归地在子树中继续查找。  
> 3、如果是NULL，那么未命中。  
> ![这里写图片描述][SouthEast 10]

**插入操作：**  
![这里写图片描述][SouthEast 11]  
几种情况插入动画演示：  
![这里写图片描述][SouthEast 12]  
![这里写图片描述][SouthEast 13]

**维持2-3树平衡的操作（局部变换）：**

> 为了维持2-3的完美平衡性，必须进行局部变换，也就是节点分裂，4节点分裂成3节点。在实现过程中，只要维持这个条件即可。

**2-3树构建动画：**

![这里写图片描述][SouthEast 14]

**2-3树性能：**

> 性能非常棒，无论如何都可以维持完美平衡性。例如含有10亿个节点的一颗2-3树的高度仅仅在19到30之间，最多仅需要访问30个节点就可以在10亿个键中进行任意查找和插入操作，这是相当惊人的。  
> ![这里写图片描述][SouthEast 15]  
> 但是如果按照上图直接实现2-3树，考虑的情况可能会很多，并且可能为了维持平衡所需要的代价本身就比2-3查找的代价还要大，所以一般使用简单的方法实现2-3树。于是就有了下面的红黑树实现方法。

## 红黑树 ##

**红黑树介绍：**

> 红黑树是一种实现2-3树的简单数据结构。为了理解红黑树必须好好对比2-3树结构。  
> 红黑树的实现代码很优美，好多都可以使用BST的代码。  
> 红链接：两个2-结点连接起来构成一个3-节点，即将3节点**通过一条左倾的红色连接两个2节点**表示。  
> 黑链接：普通的连接。  
> 通过上述方式表示的2-3树的二叉查找树叫做红黑二叉查找树。  
> ![这里写图片描述][SouthEast 16]

**为了维持平衡的三种基本操作**

> ![这里写图片描述][SouthEast 17]
> 
> ![这里写图片描述][SouthEast 18]  
> ![这里写图片描述][SouthEast 19]  
> ![这里写图片描述][SouthEast 20]

**红黑树插入操作实现**

> 插入操作就是为了维持树对应的平衡，通过上述操作既可以实现平衡。  
> ![这里写图片描述][SouthEast 21]

**红黑树构造过程**  
![这里写图片描述][SouthEast 22]

**红黑树性能**

> 基于红黑树符号表的实现，都能保证操作的运行时间的对数级别，无论键的插入顺序是如何的，它都和2-3树一一对应，几乎是完美平衡的。在信息世界的汪洋大海中，表的大小可能上千亿，但是仍然可以确保在几十次比较之内就完成这些操作。Lg10^12 = 12；因为时间复杂度是对数级别，很牛逼。  
> ![这里写图片描述][SouthEast 23]

**源代码**

/***************************红黑树************************************/
    #define RED true
    #define BLACK false
    typedef struct RBtreenode* RBtreeNode;
    struct RBtreenode{
        Key key;      //键
        Value val;    //值
        RBtreeNode left; //指向左子树
        RBtreeNode right;//指向右子树
        int N;        //以该节点为根的子树中节点个数
        bool color;   //其父节点指向它链接的颜色
    };
    int RBtree_Size();         //以该节点为根的子树中节点个数
    Value RBtree_Get(Key key); //获取键的值
    void RBtree_Put(Key key , Value val);//将键值存入表（键为空，则删除）
    void RBtree_preorder();   //红黑树前序遍历
    void RBtree_inorder();    //红黑树中序遍历
    void RBtree_postorder();  //红黑树后序遍历
    /*************************************************************************/

#include "search.h"
    /*****************内部方法********************************/
    static RBtreeNode root;//红黑树根节点
    static RBtreeNode NewNode(Key key , Value val , int N , bool color)//新建节点
    {
        RBtreeNode x;
        x = (RBtreeNode)malloc( sizeof( struct RBtreenode ) );
        x->key = key;
        x->val = val;
        x->N = N;
        x->color = color;
        return x;
    }
    
    static bool IsRed(RBtreeNode h)//判断节点颜色
    {
        if(h == NULL)
            return BLACK;
        return (h->color == RED);
    }
    static RBtreeNode RotateLeft(RBtreeNode h)//左旋转
    {
        RBtreeNode x = h->right;//暂存h左节点
        h->right = x->left;
        x->left = h;
        x->color = h->color;//保存h颜色
        h->color = RED;//h成为红色
        return x;
    }
    static RBtreeNode RotateRight(RBtreeNode h)//右旋转
    {
        RBtreeNode x = h->left;//暂存h左节点
        h->left = x->right;
        x->right = h;
        x->color = h->color;//保存h颜色
        h->color = RED;//h成为红色
        return x;//返回，子树根节点，便于递归动态修改树结构
    }
    static void FlipColors(RBtreeNode h)//颜色反转
    {
        h->color = RED;
        h->left->color = BLACK;
        h->right->color = BLACK;
    }
    static int Size(RBtreeNode x)
    {
        if(x == NULL)
            return 0;
        return x->N;
    }
    static Value Get(RBtreeNode x , Key key)//以x为根节点的子树中查找，命中返回值，未命中返回NULL
    {
        if(x == NULL)
            return 0;//未命中,返回0
        int cmp = key - x->key;
        if(cmp < 0)//比x键小，向坐子树查找
            return Get(x->left , key);
        else if(cmp > 0)//比x键大，向右子树查找
            return Get(x->right , key);
        else
            return x->val;//命中
    }
    static RBtreeNode Put( RBtreeNode h , Key key , Value val)
    {
        if(h == NULL)
            return NewNode(key , val , 1 , RED);//未命中，则插入
        int cmp = key - h->key;
        if(cmp < 0)//比x键小，向坐子树查找
            h->left = Put(h->left , key , val);
        else if(cmp > 0)//比x键大，向右子树查找
            h->right = Put(h->right , key , val);
        else
            h->val = val;//命中更新数值
    
        if(IsRed(h->right) && !IsRed(h->left))//递归对每个节点进行平衡操作
            h = RotateLeft(h);
        if(IsRed(h->left) && IsRed(h->left->left))
            h = RotateRight(h);
        if(IsRed(h->left) && IsRed(h->right))
            FlipColors(h);
    
        h->N = Size(h->left) + Size(h->right) + 1;
        return h;
    }
    /*************************************************/
    int RBtree_Size()
    {
        return Size(root);
    }
    void RBtree_Put(Key key , Value val)
    {
        root = Put(root , key , val);//
        root->color = BLACK;
    }
    Value RBtree_Get(Key key)
    {
        return Get(root , key);
    }
    
    /**********树的测试********************************/
    /* * 前序遍历伪代码 */
    static void preorder(RBtreeNode tree)
    {
         if(tree != NULL)
         {
             printf("%c ", tree->key);
             preorder(tree->left);
             preorder(tree->right);
         }
    }
    /* * 中序遍历伪代码 */
    static void inorder(RBtreeNode tree)
    {
        if(tree != NULL)
        {
            inorder(tree->left);
            printf("%c ", tree->key);
            inorder(tree->right);
        }
    }
    /* * 后序遍历伪代码 */
    static void postorder(RBtreeNode tree)
    {
        if(tree != NULL)
        {
            postorder(tree->left);
            postorder(tree->right);
            printf("%c ", tree->key);
        }
    }
    void RBtree_preorder()
    {
        printf("preorder:");
        preorder(root);
        printf("\n");
    }
    void RBtree_inorder()
    {
        printf("inorder:");
        inorder(root);
        printf("\n");
    }
    void RBtree_postorder()
    {
        printf("postorder:");
        postorder(root);
        printf("\n");
    }
    /*************************************************/

int main(void)
    {
        int i = 0;
        for(i = 0 ; i < 12 ; i++){
            BST_Put(keys1[i] , vals1[i]);
            RBtree_Put(keys1[i] , vals1[i]);
        }
        BST_preorder();
        RBtree_preorder();
    //    RBtree_inorder();
    //    RBtree_postorder();
        printf("S = %d \n" , RBtree_Get('S') );
        printf("R = %d \n" , RBtree_Get('R') );
        printf("A = %d \n" , RBtree_Get('A') );
        printf("\n");

![这里写图片描述][SouthEast 24]

# 基于散列表查找 #

## 简介 ##

**散列表简介**

> 散列表（哈希表）就是把Key通过一个固定的算法函数（哈希/散列函数）转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的索引下标，将value存储在以该数字为下标的数组里。这样查询和插入速度非常的快，只需要将Key通过散列函数找到数组索引，进行查询和插入操作，几乎是常数的时间复杂度。hash的本质就是找到一种数据内容和数据存放地址之间的映射关系。  
> 如果没有内存限制，可以直接将键作为数组的索引，那么查找操作访问一次内存即可，这就是直接寻址表，但是当键很多时，需要内存太大了。散列表是在时间和空间上作出了权衡，采用散列函数缩小了需要处理的下标范围。  
> **散列表查找操作：**  
> 1、通过散列函数将键转化成数组索引，理想情况下不同键转化为不同索引值，但是这是理想情况，通过可能出现多个键转化成同一索引的情况，所以需要第二步。  
> 2、处理第一步的问题，叫做碰撞处理，主要方法有拉链法和线性探测法。

## 散列函数 ##

> 如果有一个可以容纳M个项的表，则需要将键转换成\[0,M-1\]范围内的整数。  
> 散列函数尤为重要，设计散列函数的目标是很容易计算并且尽量每一个键对应一个数组索引。不同数据类型对应不同散列函数。以下介绍一些常用的散列函数。
> 
> **1、除留余数法（模哈希法）**  
> 对于正整数，选择大小为素数（散列值分布会更好，冲突较少）的数组M，直接h(k) = k mod M即可。  
> **2、浮点数散列化**  
> 如果键是0-1之间的实数，直接将其乘以M并四舍五入即可得到一个0到M-1的索引值。  
> **3、字符串散列化**  
> ![这里写图片描述][SouthEast 25]

## 基于拉链法散列表 ##

线性分离方法  
![这里写图片描述][SouthEast 26]

#include "search.h"
    
    /***********************hash公共方法***********************/
    /* *使用霍纳算法+除留余数法hash字符串，返回0-M之间 * 基数是素数，很牛逼的做法。 */
    static int hashstring(char *v , int M)//以素数127 hash字符串
    {
        int hash = 0;
        int a = 127;//素数hash
        for( ; *v != '\0' ; v++){
       //霍纳算法
            hash = (a*hash + *v)%M;
        }
        return hash;
    }
    /* *使用霍纳算法+除留余数法hash字符串，返回0-M之间 * 基数是伪随机序列，很牛逼的做法。 */
    static int hashUniversal(char *v , int M)//通用hash，以伪随机素数 hash字符串
    {
        int hash = 0;
        int a = 31415;//通过a是伪随机序列 hash
        int b = 27168;
        for( ; *v != '\0' ; v++  ){
            hash = (a*hash + *v)%M;
            a = a * b % (M-1);
        }
        return hash;
    }
    /***********************hash公共方法***********************/
    
    /*******************拉链法实现散列表方法************************/
    static SCHashNode* heads;//M矩阵,动态分配指针数组
    int SCHCount = 0;//符号表大小
    SCHashNode NewNode(SCHashNode head , Key * key , Value val)
    {
        SCHashNode x = (SCHashNode)malloc(sizeof(struct SCHashnode) );//分配结构体
        x->next = head;
        x->key = key;
        x->val = val;
        return x;//将x插入链表头
    }
    void SeparateChainingHashST_Init()//初始化数组M
    {
        int i;
        heads = (SCHashNode *)malloc(MCount * sizeof(SCHashNode));//分配指针数组，指针的指针。
        for(i = 0 ; i < MCount ; i++)//初始化为空
            heads[i] = NULL;
    }
    void SeparateChainingHashST_Put(Key * key , Value val)
    {
        SCHashNode x;
        int hash;
        hash = hashstring(key , MCount);
    #ifdef BEBUG
        printf("%s hash is %d\n",key , hash);
    #endif
        for(x = heads[hash] ; x != NULL ; x = x->next){
       //遍历命中则更新
            if(strcmp(x->key , key) == 0){
                x->val = val;
                return ;
            }
        }
        heads[hash] = NewNode(heads[hash] , key , val);//未命中插入链表前面
        SCHCount++;
    }
    Value SeparateChainingHashST_Get(Key * key )
    {
        SCHashNode x;
        int hash;
        hash = hashstring(key , MCount);
        for(x = heads[hash] ; x != NULL ; x = x->next){
            if(strcmp(x->key , key) == 0){
                return x->val;//命中
            }
        }
        return 0;//未命中
    }
    int SeparateChainingHashST_Size()
    {
        return SCHCount;
    }
    /************************************************************/

![这里写图片描述][SouthEast 27]

## 基于线性探测法的列表线 ##

![这里写图片描述][SouthEast 28]  
线性探测插入和查找动画：  
![这里写图片描述][SouthEast 29]

![这里写图片描述][SouthEast 30]

/**************************线性探测散列表************************************/
    typedef struct LPHashnode* LPHashNode;//定义指针变量
    struct LPHashnode{
        Key * key;      //键,是一个字符串
        Value val;      //值，是一个数字
    };
    void LinearProbingHashST_Init();//初始化
    void LinearProbingHashST_Put(Key * key , Value val);//插入
    Value LinearProbingHashST_Get(Key * key );//查找
    void LinearProbingHashST_Delete(Key* key );//删除
    int LinearProbingHashST_Size();//获取元素个数
    /**************************************************************************/

/*******************线性探测实现散列表方法******************************************/
    static  int UserSetM = 2;//用户设定存储数组大小，故意设定很小，为了测试动态哈希。
    static int LPHM = UserSetM;//实际存储数组大小，这个数值会变化，使得散列表的使用率永远都不会查过1/2,减少探测次数。
    static int LPHCount = 0;//符号表中元素个数
    static LPHashNode LPH_heads;//用于动态分配数组
    
    static void ReSize_LPHM(int M)//重新调整数组大小,代价很大，重新分配，重新插入
    {
        LPHashNode x;
        int i;
        x = LPH_heads;//保持原始数组地址
        LPH_heads = (LPHashNode)malloc(M * sizeof(struct LPHashnode));//重新分配LPHM对应的数组空间
        for(i = 0 ; i < LPHM ; i++)//初始化为空
            LPH_heads[i].key = NULL;
        LPHCount = 0;//因为需要重新插入新数组空间，所以将元素个数清0。
        for(i = 0 ; i < M ; i++){
       //将原始数组有键的位置，重新插入。
            if(x[i].key != NULL)
                LinearProbingHashST_Put(x[i].key , x[i].val);
        }
        free(x);//释放原始数组位置。
    }
    void LinearProbingHashST_Init()
    {
        int i;
        LPH_heads = (LPHashNode)malloc(LPHM * sizeof(struct LPHashnode));//分配LPHM对应的数组空间
        for(i = 0 ; i < LPHM ; i++)//初始化为空
            LPH_heads[i].key = NULL;
    }
    void LinearProbingHashST_Put(Key* key , Value val)
    {
        int i;
        if(LPHCount > LPHM / 2){
       //保证使用率不大于1/2.
            LPHM = 2*LPHM;//扩大两倍
            ReSize_LPHM(LPHM);//重新调整
        }
        i = hashstring(key , LPHM);//hash
    
        for( ; LPH_heads[i].key != NULL ; i = (i + 1)%LPHM)//循环查找
            if(strcmp(LPH_heads[i].key , key) == 0){
       //遍历命中则更新
                LPH_heads[i].val = val;
                return ;
            }
        LPH_heads[i].key = key;//未命中，则插入空白位置
        LPH_heads[i].val = val;
        LPHCount++;//元素加1
    }
    Value LinearProbingHashST_Get(Key* key )
    {
        int i = hashstring(key , LPHM);
        for( ; LPH_heads[i].key != NULL ; i = (i + 1)%LPHM)//循环查找
        if(strcmp(LPH_heads[i].key , key) == 0){
       //遍历命中则返回
            return LPH_heads[i].val;
        }
        return 0;//遇到空未命中，返回空
    }
    void LinearProbingHashST_Delete(Key* key )
    {
        int i;
        struct LPHashnode temp;
        if(key == NULL)//key为空，直接返回
            return ;
        i = hashstring(key , LPHM);
        while(LPH_heads[i].key != NULL){
       //查找键直到遇到空为止（如果遇到空，那么肯定键不在表中）
            if(strcmp(LPH_heads[i].key , key) == 0)
                break;
            else 
                i = (i+1)%LPHM;
        }
        if(LPH_heads[i].key == NULL)//遇到空，证明不在表中
            return ;
        LPH_heads[i].key = NULL;//命中，则键清空
        LPH_heads[i].val = 0;
    
        i = (i+1)%LPHM;//索引键簇下一个元素
        while(LPH_heads[i].key != NULL){
       //将键重新插入表
            temp = LPH_heads[i];//缓存键值
            LPH_heads[i].key = NULL;//将键清空
            LPH_heads[i].val = 0;
            LPHCount--;
            LinearProbingHashST_Put(temp.key , temp.val);//并重新插入
            i = (i+1)%LPHM;
        }
        LPHCount--;//总体元素个数减1
    
        if(LPHCount > 0&&LPHCount == LPHM / 8){
       //如果总体元素太少，为了节约空间，缩小LPHM
            LPHM = LPHM/2;
            ReSize_LPHM(LPHM);//消耗时间
        }
    }
    int LinearProbingHashST_Size()
    {
        return LPHCount;
    }
    /************************************************************/

#include "search.h"
    Key*  keys2[] = {
       "universal" , "split" , "warmup" , "glue" , "internal" , "tricky" , "concise" , "disjoint" , "symmetric" , "symmetric" , "universal" , "split" };
    Value vals2[] = {
       0 , 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ,11};
    int main(void)
    {
        int i = 0;
        LinearProbingHashST_Init();
        for(i = 0 ; i < 12 ; i++){
            LinearProbingHashST_Put(keys2[i] , vals2[i]);
        }
        printf("\n%d\n" , LinearProbingHashST_Size());
        LinearProbingHashST_Delete(keys2[0]);
        LinearProbingHashST_Delete(keys2[2]);
        LinearProbingHashST_Delete(keys2[3]);
        LinearProbingHashST_Delete(keys2[5]);
        printf("\n%d\n" , LinearProbingHashST_Size());
        printf("%s val is %d\n", keys2[0] , LinearProbingHashST_Get(keys2[0]));
        printf("%s val is %d\n", keys2[1] , LinearProbingHashST_Get(keys2[1]));
        printf("%s val is %d\n", keys2[2] , LinearProbingHashST_Get(keys2[2]));
        printf("%s val is %d\n", keys2[3] , LinearProbingHashST_Get(keys2[3]));
        printf("%s val is %d\n", keys2[4] , LinearProbingHashST_Get(keys2[4]));
        printf("%s val is %d\n", keys2[5] , LinearProbingHashST_Get(keys2[5]));
        printf("%s val is %d\n", keys2[6] , LinearProbingHashST_Get(keys2[6]));
        printf("%s val is %d\n", keys2[7] , LinearProbingHashST_Get(keys2[7]));
    }

![这里写图片描述][SouthEast 31]  
测试了动态调整数组，插入，删除以及查找代码，结果如上图所示，正确。将初始化数组维度定义为2，是为了测试数组动态调整效果。清楚思路，然后写起来就没有那么复杂了。

## 性能 ##

## 实际用途 ##

# 查找常见习题 #

## 查找一个整数数组中第二大的数 ##

思路：从头到尾遍历数组，通过两个变量，一个变量记录已经遍历的最大数，一个变量记录已经遍历的第二大数。

## 二分查找集合 ##

适用于事先已经排好序的顺序表。首先将给定值K与表中间位置的关键字比较，若相等，则查找成功，返回该元素存储位置；如不等，则按照所需在前半部分或者后半部分查找。

[SouthEast]: /images/20220606/dd6add5a29f64d1d992798f5f0e8ccb8.png
[SouthEast 1]: /images/20220606/d943bf02deb146b4a41e331060c80440.png
[SouthEast 2]: /images/20220606/2e6f51804a354d728a6da9bc4b8b1cf4.png
[SouthEast 3]: /images/20220606/520eced22f274169994bb704e4adf1ad.png
[SouthEast 4]: /images/20220606/b2a076b2565948b086cf796d66f763e9.png
[SouthEast 5]: /images/20220606/dbf6726a4df94c6ebc6e3fcf510253f2.png
[SouthEast 6]: /images/20220606/fa3415fb175e4e07be9255b47b25aadb.png
[SouthEast 7]: /images/20220606/4752795bf3df4a03a2b9a802af70d1ea.png
[SouthEast 8]: /images/20220606/eaea6834135c46728a3b532a69f1fc78.png
[SouthEast 9]: /images/20220606/bbdea2290c48475dab7a534107b6467b.png
[SouthEast 10]: /images/20220606/3c827461da80476d8b1a44e2edd0dd8a.png
[SouthEast 11]: /images/20220606/a00a2b11138846eb8871c5d697212188.png
[SouthEast 12]: /images/20220606/d5067c43d94046878f90e3a6e05bda7b.png
[SouthEast 13]: /images/20220606/55c3a47c799746858da8ce48f391093e.png
[SouthEast 14]: /images/20220606/35058c39781a42f88f8b29a934ba2412.png
[SouthEast 15]: /images/20220606/a4defc1a3072486093fff5729ee90915.png
[SouthEast 16]: /images/20220606/3edfd0eb5a684d63a7e9e0728d40a51e.png
[SouthEast 17]: /images/20220606/2a2191894f11432bb5aa30fd03cf1a10.png
[SouthEast 18]: /images/20220606/709b09849846424ebf942e2709b0ea42.png
[SouthEast 19]: /images/20220606/d31c7683be2240cdb9f0f34cf1de11ec.png
[SouthEast 20]: /images/20220606/9376520ea89b4af69f540940fc1c74ae.png
[SouthEast 21]: /images/20220606/8fe2f67d436841a4b3e99f8f8b77e992.png
[SouthEast 22]: /images/20220606/f5fc74d0dd1e47279f78588e23e3573e.png
[SouthEast 23]: /images/20220606/9aae4a6241414bbb9d4d6126498df943.png
[SouthEast 24]: /images/20220606/05389166618a4afc84394769e31227b7.png
[SouthEast 25]: /images/20220606/60e5d6afaeb74c478915014038738e1d.png
[SouthEast 26]: /images/20220606/604de40ab3ff4cca9bebdfcd8b18036c.png
[SouthEast 27]: /images/20220606/bff9775b97b64920b8c59701f2a94a86.png
[SouthEast 28]: /images/20220606/0bdec609a62b423f91714e3e47e9b5bb.png
[SouthEast 29]: /images/20220606/c6de320940114981a84ce5a1db6b5c98.png
[SouthEast 30]: /images/20220606/c03b6f40fa064c7faa3b15f38e8431da.png
[SouthEast 31]: /images/20220606/0e0feaf86b76417094ec400743322be7.png