C语言静态查找表：顺序查找、二分查找、分块查找

柔情只为你懂 2022-04-25 05:00 509阅读 0赞

**目录**

1 静态查找表

2 静态查找的三种方法

2.1 顺序查找

2.1.1 概念

2.1.2 分类

2.1.3 源代码示例

2.1.4 性能分析

2.2 二分查找

2.2.1 实现算法前提

2.2.2 实现思路（以升序为例）

2.2.3 源代码示例

2.2.4 性能分析

2.3 分块查找

2.3.1 概念

2.3.2 实现思路

2.3.3 特点

2.3.4 源代码示例

2.3.5 性能分析

3 三种算法性能比较

--------------------

# 1 静态查找表 #

概念：静态查找表是数据元素的线性表，可以是基于数组的顺序存储或以线性链表存储。

# 2 静态查找的三种方法 #

## 2.1 顺序查找 ##

### 2.1.1 概念 ###

顺序查找又称静态查找，是最基本的查找方法之一。

### 2.1.2 分类 ###

1.无监视哨：从表中一端开始，向另一端逐个将其关键码与待查找元素比较。若相等，则查找成功，返回给定值在表中存储位置；否则查找失败。

2.有监视哨：表中 0 位置存储待查找元素。从表尾向表头查找，若搜索到 0 位置，说明查找失败；否则查找成功。优点：查找过程中省略了每次查找的检测过程，直接返回元素下标，当 L.length >= 1000 时，与方法（1）相比进行一次查找所需平均时间几乎减少一半。

ps：监视哨也可设置在高下标处

### 2.1.3 源代码示例 ###

![20190501201213725.jpg][]

### 2.1.4 性能分析 ###

设表中有 n 个元素，给定值 x 与表中第 i 个元素相等，则定位元素 x 时，共查找 n - i + 1 次，即 Ci = n - i + 1。因此查找成功时，平均查找长度（Average search length）为：

![ASL=\\sum^n\_\{i=1\}p\_i(n-i+1)][ASL_sum_n_i_1_p_i_n-i_1]

设每个元素的查找概率相等，即 ![p\_i=\\frac\{1\}\{n\}][p_i_frac_1_n]

将 ![\\large p\_\{i\}][large p_i] 代入可得：![ASL=\\frac\{n+1\}\{2\}][ASL_frac_n_1_2]

## 2.2 二分查找 ##

### 2.2.1 实现算法前提 ###

要实现表的二分查找，必须使表有序（升序 / 降序）

### 2.2.2 实现思路（以升序为例） ###

取有序表中间元素为比较对象：

（1）若待查找元素 = 中间元素，则返回中间元素下标；

（2）若待查找元素 < 中间元素，则在表左半部分查找；

（3）若待查找元素 > 中间元素，则在表右半部分查找

### 2.2.3 源代码示例 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE 100   // 表中最大元素个数
    typedef int ElemType; // 设置表中元素类型为整型
    typedef struct {
        ElemType data[MAXSIZE + 1]; // 下标0处存放监视哨，数组元素存储1~n单元
        int length;
    } SqList;
    
    void CreateSqList(SqList *L);           // 创建表
    void ASCSort(SqList *L);                // 对表进行升序排序
    int BinarySearch(SqList L, ElemType x); // 二分查找非递归算法
    int BinarySearch_Recursive(SqList L, int low, int high, ElemType x);
    // 二分查找递归算法
    
    int main(void)
    {
        SqList L;
        int index;
    
        CreateSqList(&L);
        printf("元素总数为：%d\n", L.length);
        ASCSort(&L);
    
        index = BinarySearch(L, 3);
        if (index == 0)
            printf("查找失败！\n");
        else
            printf("查找成功，下标为：%d\n", index);
    
        index = BinarySearch_Recursive(L, 1, L.length, 8);
        if (index == 0)
            printf("查找失败！\n");
        else
            printf("查找成功，下标为：%d\n", index);
    
        return 0;
    }
    
    void CreateSqList(SqList *L) // 创建表
    {
        int i, n;
    
        printf("请输入元素个数：");
        scanf("%d", &n);
        while (n > MAXSIZE || n < 1) {
            printf("个数超出范围，重新输入：");
            scanf("%d", &n);
        }
        L->length = n;
    
        printf("请依次输入元素值：\n");
        for (i = 1; i <= L->length; i++)
            scanf("%d", &(L->data[i]));
    }
    void ASCSort(SqList *L) // 对表进行升序排序
    {
        int i, j, temp;
    
        for (i = 1; i <= L->length - 1; i++)
            for (j = i; j <= L->length; j++)
                if (L->data[i] > L->data[j]) {
                    temp = L->data[i];
                    L->data[i] = L->data[j];
                    L->data[j] = temp;
                }
    
        printf("升序排序后：");
        for (i = 1; i <= L->length; i++)
            printf("%d, ", L->data[i]);
        printf("\n");
    }
    int BinarySearch(SqList L, ElemType x) // 二分查找非递归算法
    {
        int low, mid, high;
    
        low = 1;
        high = L.length;
        while (low <= high) {
            mid = (high + low) / 2;
    
            if (x == L.data[mid])
                return mid;
            else if (x < L.data[mid])
                high = mid - 1;
            else // (x > L.data[mid])
                low = mid + 1;
        }
    
        return 0;
    }
    int BinarySearch_Recursive(SqList L, int low, int high, ElemType x)
    {
        int mid;
    
        if (low > high)
            return 0;
        else {
            mid = (high + low) / 2;
    
            if (x == L.data[mid])
                return mid;
            else if (x < L.data[mid])
                return BinarySearch_Recursive(L, low, mid - 1, x);
            else // (x > L.data[mid])
                return BinarySearch_Recursive(L, mid + 1, high, x);
        }
    }

![20190501211535808.jpg][]

### 2.2.4性能分析 ###

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70][]

查找图中任一元素的过程，即是从根节点到该元素的路径，比较次数 k 为该元素节点在树中的层次数。所以：![K=\\lfloor log\_2n+1 \\rfloor][K_lfloor log_2n_1 _rfloor]

设每个元素的查找概率相等，即

![p\_i=\\frac\{1\}\{n\}][p_i_frac_1_n]，

![ASL=\\sum^n\_\{i=1\}p\_iC\_i=p\_ik \\approx log\_2(n+1)-1][ASL_sum_n_i_1_p_iC_i_p_ik _approx log_2_n_1_-1]

## 2.3分块查找 ##

### 2.3.1概念 ###

分块查找又称索引顺序查找，是对顺序查找的一种改进。

### 2.3.2实现思路 ###

将数据表分成若干块，然后为每块建立一个索引，将所有块组织起来建立一个索引表

（1）数据表：存储所有数据元素

（2）索引表(index\_table)：表中每个索引有两个部分，关键码字段、指针字段

关键码字段：存储对应块中的最大元素

指针字段：存储对应块中起始元素位置

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1][]

### 2.3.3特点 ###

表中数据是分块有序的。即索引表中数据是有序的，数据表中数据不要求有序。

查找元素时，先根据索引表确定元素所在块数，然后再从数据表对应块中查找该元素。

### 2.3.4源代码示例 ###

#include <stdio.h>
    #include <stdlib.h>
    
    #define MAXSIZE  100  // 表中最大元素个数
    #define BLOCKNUM 5    // 索引表中最大块数
    typedef int KeyType;  // 设置索引表元素类型为整型
    typedef int DataType; // 设置记录的其他项为整型
    typedef struct        // 数据表结构体
    {
        KeyType key;       // 节点元素
        DataType data;     // 节点的其他项
    } SqList[MAXSIZE + 1]; // 数据表0位置存储数据表的长度
    
    typedef struct // 索引表结构体
    {
        KeyType key;            // 块的最大关键字
        int addr;               // 块的起始地址
    } IndexTable[BLOCKNUM + 1]; // 索引表0位置存储数据表的长度
    
    void CreateSqList(SqList L, IndexTable id);   // 创建表
    void TraverseSqList(SqList L, IndexTable id); // 遍历表
    int BlockSearch(SqList L, IndexTable id, KeyType x); // 查找块中元素值为x的元素
    
    int main(void)
    {
        SqList L;
        IndexTable id;
        int index;
    
        CreateSqList(L, id);
        TraverseSqList(L, id);
    
        index = BlockSearch(L, id, -7);
        if (index == 0)
            printf("表中无此元素！\n");
        else
            printf("查找成功，元素下标为：%d\n", index);
    
        index = BlockSearch(L, id, 17);
        if (index == 0)
            printf("表中无此元素！\n");
        else
            printf("查找成功，元素下标为：%d\n", index);
    
        index = BlockSearch(L, id, 100);
        if (index == 0)
            printf("表中无此元素！\n");
        else
            printf("查找成功，元素下标为：%d\n", index);
    
        return 0;
    }
    
    void CreateSqList(SqList L, IndexTable id) // 创建表
    {
        int i, j, k, m, n;
        int elemnum, bnum; // 总元素个数；总块数
        int max = INT_MIN; // 块中最大元素
    
        printf("请输入元素个数( < 100)、块数( < 5 )：");
        scanf("%d%d", &elemnum, &bnum);
        while (elemnum < 1 || elemnum > MAXSIZE || bnum < 1 || bnum > BLOCKNUM ||
               bnum > elemnum) {
            printf("输入有误，重新输入：");
            scanf("%d%d", &elemnum, &bnum);
        }
    
        L[0].key = elemnum; // 数据表0位置存储数据表的长度
        id[0].key = bnum;   // 索引表0位置存储索引表的长度
    
        n = elemnum / bnum;             // 平均每块元素个数
        for (i = 1; i <= bnum - 1; i++) // 构造前 bnum - 1 块中的元素
        {
            printf("请输入块 %d 的 %d 个元素（最小元素不能小于 %d ）：", i, n, max);
    
            k = (i - 1) * n; // 第 i 块元素起始下标
            for (j = 1; j <= n; j++) {
                scanf("%d", &(L[k + j].key));
                if (max < L[k + j].key) // 获取第 i 块中最大元素
                    max = L[k + j].key;
            }
            id[i].key = max;
            id[i].addr = k + 1;
        }
    
        k = (bnum - 1) * n;
        m = elemnum - k; // 最后一块元素个数
        printf("请输入块 %d 的 %d 个元素（最小元素不能小于 %d ）：", bnum, m, max);
        for (j = 1; j <= m; j++) // 构造最后一块中的元素
        {
            scanf("%d", &(L[k + j].key));
            if (max < L[k + j].key) // 获取最后一块中最大元素
                max = L[k + j].key;
        }
        id[i].key = max;
        id[i].addr = k + 1;
    }
    void TraverseSqList(SqList L, IndexTable id) // 遍历表
    {
        int i;
    
        printf("---------数据表信息---------\n");
        for (i = 1; i <= L[0].key; i++) // 遍历并输出表中元素
            printf("%d, ", L[i].key);
        printf("\n---------索引表信息---------");
        for (i = 1; i <= id[0].key; i++) // 遍历并输出索引表信息
            printf("\n%d, %d", id[i].key, id[i].addr);
        printf("\n----------------------------\n");
    }
    int BlockSearch(SqList L, IndexTable id, KeyType x) // 查找块中元素值为x的元素
    {
        int low1, high1, low2, high2, mid, i;
    
        low1 = 1;
        high1 = id[0].key;    // 设置索引表二分查找上下区间
        while (low1 <= high1) // 查找元素所在块数
        {
            mid = (low1 + high1) / 2;
            if (x <= id[mid].key)
                high1 = mid - 1;
            else
                low1 = mid + 1;
        }
    
        if (low1 <= id[0].key) // 若low1 > id[0].key，则关键子大于数据表中所有元素
        {
            low2 = id[low1].addr; // 元素所在块的最小下标
            if (low1 == id[0].key)
                high2 = L[0].key; // 元素所在块的最大下标
            else
                high2 = id[low1 + 1].addr - 1;
    
            for (i = low2; i <= high2; i++) // 在指定块中查找元素并返回下标
                if (L[i].key == x)
                    return i;
        }
    
        return 0; // 查找失败返回0
    }

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2][]

### 2.3.5性能分析 ###

设 n 个数据元素的表分为 m 个子表，则子表(sub\_table)元素个数为 t = n / m ；

则

![ASL=ASL\_\{(index\\\_table)\}+ASL\_\{(sub\\\_table)\}=\\frac\{1\}\{2\} \\times (m+1) +\\frac\{1\}\{2\} \\times (\\frac\{n\}\{m\}+1)=\\frac\{1\}\{2\} \\times (m+\\frac\{n\}\{m\})+1][ASL_ASL_index_table_ASL_sub_table_frac_1_2_ _times _m_1_ _frac_1_2_ _times _frac_n_m_1_frac_1_2_ _times _m_frac_n_m_1]

当 ![m= \\sqrt\{n\}][m_ _sqrt_n] 时，  ![ASL=\\sqrt\{n\}+1][ASL_sqrt_n_1] 达到最小值。

# 3.三种算法性能比较 #

顺序查找时间复杂度：![T(n)=O(n)][T_n_O_n]

二分查找时间复杂度：![T(n)=O(log\_2n)][T_n_O_log_2n]

分块查找时间复杂度：![T(n)=O(\\sqrt\{n\})\\\\][T_n_O_sqrt_n]

![O(n) > O(\\sqrt\{n\})>O(log\_2n)][O_n_ _ O_sqrt_n_O_log_2n]

## ##

[20190501201213725.jpg]: /images/20220210/dd440b9af1bc4e1c9b1762c53e821095.png
[ASL_sum_n_i_1_p_i_n-i_1]: https://latex.codecogs.com/gif.latex?ASL%3D%5Csum%5En_%7Bi%3D1%7Dp_i%28n-i&plus;1%29
[p_i_frac_1_n]: https://latex.codecogs.com/gif.latex?p_i%3D%5Cfrac%7B1%7D%7Bn%7D
[large p_i]: https://private.codecogs.com/gif.latex?%5Cbg_white%20%5Clarge%20p_%7Bi%7D
[ASL_frac_n_1_2]: https://latex.codecogs.com/gif.latex?ASL%3D%5Cfrac%7Bn&plus;1%7D%7B2%7D
[20190501211535808.jpg]: /images/20220210/3e67a889c3414b5f8b67724fdc2b250a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70]: /images/20220210/c360635afcc54a77b9e9ad346c7edb97.png
[K_lfloor log_2n_1 _rfloor]: https://latex.codecogs.com/gif.latex?K%3D%5Clfloor%20log_2n&plus;1%20%5Crfloor
[ASL_sum_n_i_1_p_iC_i_p_ik _approx log_2_n_1_-1]: https://latex.codecogs.com/gif.latex?ASL%3D%5Csum%5En_%7Bi%3D1%7Dp_iC_i%3Dp_ik%20%5Capprox%20log_2%28n&plus;1%29-1
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 1]: /images/20220210/504225a5d07542e689d276f39dc45b65.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjI1MDMwMg_size_16_color_FFFFFF_t_70 2]: /images/20220210/83e545284c464a68b443134d51754055.png
[ASL_ASL_index_table_ASL_sub_table_frac_1_2_ _times _m_1_ _frac_1_2_ _times _frac_n_m_1_frac_1_2_ _times _m_frac_n_m_1]: https://latex.codecogs.com/gif.latex?ASL%3DASL_%7B%28index%5C_table%29%7D&plus;ASL_%7B%28sub%5C_table%29%7D%3D%5Cfrac%7B1%7D%7B2%7D%20%5Ctimes%20%28m&plus;1%29%20&plus;%5Cfrac%7B1%7D%7B2%7D%20%5Ctimes%20%28%5Cfrac%7Bn%7D%7Bm%7D&plus;1%29%3D%5Cfrac%7B1%7D%7B2%7D%20%5Ctimes%20%28m&plus;%5Cfrac%7Bn%7D%7Bm%7D%29&plus;1
[m_ _sqrt_n]: https://latex.codecogs.com/gif.latex?m%3D%20%5Csqrt%7Bn%7D
[ASL_sqrt_n_1]: https://latex.codecogs.com/gif.latex?ASL%3D%5Csqrt%7Bn%7D&plus;1
[T_n_O_n]: https://latex.codecogs.com/gif.latex?T%28n%29%3DO%28n%29
[T_n_O_log_2n]: https://latex.codecogs.com/gif.latex?T%28n%29%3DO%28log_2n%29
[T_n_O_sqrt_n]: https://latex.codecogs.com/gif.latex?T%28n%29%3DO%28%5Csqrt%7Bn%7D%29%5C%5C
[O_n_ _ O_sqrt_n_O_log_2n]: https://latex.codecogs.com/gif.latex?O%28n%29%20%3E%20O%28%5Csqrt%7Bn%7D%29%3EO%28log_2n%29