数据结构: 数组在算法中的应用

       数组是计算机科学中的一种基础数据结构，它在算法中有着广泛的应用，其关键要素是索引与索引对应的值。

       请注意，这些代码示例需要适当的辅助函数（如 swap ）和主函数来运行。此外，一些算法（如KMP算法）需要额外的辅助函数来计算最长公共前缀数组（LPS）。

       以下是数组在算法中的一些常见应用:

1 排序

1.1 冒泡排序

       通过重复交换相邻元素来排序数组。

void bubbleSort(int arr[], int n) {

    for (int i = 0; i < n-1; i++)     

        for (int j = 0; j < n-i-1; j++)

            if (arr[j] > arr[j+1])

                swap(&arr[j], &arr[j+1]);

}

1.2 选择排序

       每次从未排序的部分选择最小（或最大）的元素放到已排序序列的末尾。

void selectionSort(int arr[], int n) {

    int i, j, min_idx;

    for (i = 0; i < n-1; i++) {

        min_idx = i;

        for (j = i + 1; j < n; j++) {

            if (arr[j] < arr[min_idx]) {

                min_idx = j;

            }

        }

        if (min_idx != i) {

            int temp = arr[i];

            arr[i] = arr[min_idx];

            arr[min_idx] = temp;

        }

    }

}

1.3 插入排序

       构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

void insertionSort(int arr[], int n) {

    int i, key, j;

    // 从第二个元素开始遍历数组

    for (i = 1; i < n; i++) {

        key = arr[i]; // 选择未排序部分的第一个元素

        j = i - 1;

        // 将选中的元素与已排序部分的元素比较，并将已排序元素向后移动

        while (j >= 0 && arr[j] > key) {

            arr[j + 1] = arr[j];

            j = j - 1;

        }

        // 将选中的元素插入到正确的位置

        arr[j + 1] = key;

    }

}

1.4 快速排序

       选择一个“基准”元素，将数组分为两部分，一部分比基准小，另一部分比基准大，然后递归排序这两部分。

void quickSort(int arr[], int low, int high) {

    if (low < high) {

        int pi = partition(arr, low, high);

        quickSort(arr, low, pi - 1); // Before pi

        quickSort(arr, pi + 1, high); // After pi

    }

}

int partition(int arr[], int low, int high) {

    int pivot = arr[high]; // pivot

    int i = (low - 1); // Index of smaller element

    for (int j = low; j <= high - 1; j++) {

        // If current element is smaller than or equal to pivot

        if (arr[j] <= pivot) {

            i++; // increment index of smaller element

            swap(&arr[i], &arr[j]);

        }

    }

    swap(&arr[i + 1], &arr[high]);

    return (i + 1);

}

void swap(int* a, int* b) {

    int t = *a;

    *a = *b;

    *b = t;

}

2 搜索

2.1 线性搜索

       遍历数组，直到找到目标元素。

int linearSearch(int arr[], int n, int x) {

    for (int i = 0; i < n; i++) {

        if (arr[i] == x) {

            return i; // 找到元素，返回索引

        }

    }

    return -1; // 未找到元素，在返回-1

}

2.2 二分搜索

       在已排序的数组中，通过比较中间元素与目标值来减少搜索范围。

int binarySearch(int arr[], int l, int r, int x) {

    if (r >= l) {

        int mid = l + (r - l) / 2;

        if (arr[mid] == x)

            return mid;

        if (arr[mid] > x)

            return binarySearch(arr, l, mid - 1, x);

        return binarySearch(arr, mid + 1, r, x);

    }

    return -1;

}

3 动态规划

       动态规划（Dynamic Programming，简称DP）是一种在数学、管理科学、计算机科学和经济学中使用的，通过把原问题分解为相对简单的子问题的方式求解复杂问题的方法。

        用于解决具有重叠子问题和最优子结构特性的问题，如斐波那契数列、最长公共子序列、背包问题等。

3.1 斐波那契

int fib(int n) {

    int f[n+2]; // 1 extra to handle case, n = 0

    f[0] = 0;

    f[1] = 1;

    for (int i = 2; i <= n; i++) {

        f[i] = f[i-1] + f[i-2];

    }

    return f[n];

}

3.2 最长公共子序列

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 动态规划求解最长公共子序列的长度
int lcs_length(char *X, char *Y, int m, int n) {
    int L[m+1][n+1];
    int i, j;

    // 构建L[m+1][n+1]表
    for (i = 0; i <= m; i++) {
        for (j = 0; j <= n; j++) {
            if (i == 0 || j == 0)
                L[i][j] = 0;
            else if (X[i-1] == Y[j-1])
                L[i][j] = L[i-1][j-1] + 1;
            else
                L[i][j] = (L[i-1][j] > L[i][j-1]) ? L[i-1][j] : L[i][j-1];
        }
    }

    // L[m][n]包含了X[0..m-1]和Y[0..n-1]的LCS的长度
    return L[m][n];
}

3.3 背包问题

        背包问题是一种组合优化的问题。在典型的背包问题中，你给定一组物品，每个物品都有自己的重量和价值，并且存在一个限定的总重量。目标是确定在不超过总重量的前提下，哪些物品应该被选中，以使得总价值最大化。

       这里提供的是0-1背包问题的动态规划解决方案的C语言实现。0-1背包问题是指每个物品只有两种选择：要么完全拿走，要么完全不要。

#include <stdio.h>

// 动态规划求解0-1背包问题

int knapSack(int W, int wt[], int val[], int n) {

    int i, w;

    int K[n+1][W+1];

    // 构建dp表

    for (i = 0; i <= n; i++) {

        for (w = 0; w <= W; w++) {

            if (i == 0 || w == 0)

                K[i][w] = 0;

            else if (wt[i - 1] <= w)

                K[i][w] = (val[i - 1] + K[i - 1][w - wt[i - 1]]) > K[i - 1][w] ? (val[i - 1] + K[i - 1][w - wt[i - 1]]) : K[i - 1][w];

            else

                K[i][w] = K[i - 1][w];

        }

    }

    // 返回最大价值

    return K[n][W];

}

4 图算法

4.1 邻接矩阵

        表示图中顶点间连接关系的二维数组。

#define V 5 // 5 vertices

void addEdge(int graph[V][V], int src, int dest) {

    graph[src][dest] = 1;

    graph[dest][src] = 1; // For undirected graph

}

void printGraph(int graph[V][V]) {

    for (int i = 0; i < V; i++) {

        for (int j = 0; j < V; j++) {

            printf("%d ", graph[i][j]);

        }

        printf("\n");

    }

}

4.2 最短路径问题

（如Dijkstra算法、Bellman-Ford算法）。

4.2.1 Dijkstra算法

       最短路径问题是图论中的一个经典问题，其中Dijkstra算法是求解单源最短路径问题的一种非常著名的算法。

#include <stdio.h>

#include <limits.h>

// 用于找到最短路径集合中具有最小距离的顶点

int minDistance(int dist[], int sptSet[], int n) {

    int min = INT_MAX, min_index;

    for (int v = 0; v < n; v++)

        if (sptSet[v] == 0 && dist[v] <= min)

            min = dist[v], min_index = v;

    return min_index;

}

// 实现Dijkstra算法

void dijkstra(int graph[V][V], int src, int n) {

    int dist[V]; // dist[i]表示源点到i的最短距离

    int sptSet[V]; // sptSet[i]为真，如果i在最短路径集合中

    // 初始化所有距离为无穷大，sptSet[]为假

    for (int i = 0; i < n; i++)

        dist[i] = INT_MAX, sptSet[i] = 0;

    // 源点到自己的距离总是为0

    dist[src] = 0;

    // 找到所有顶点的最短路径

    for (int count = 0; count < n - 1; count++) {

        // 选择最短距离顶点的最小值

        int u = minDistance(dist, sptSet, n);

        // 标记这个顶点已经处理

        sptSet[u] = 1;

        // 更新相邻顶点的距离值

        for (int v = 0; v < n; v++)

            if (!sptSet[v] && graph[u][v] && dist[u] != INT_MAX &&

                dist[u] + graph[u][v] < dist[v])

                dist[v] = dist[u] + graph[u][v];

    }

    // 打印构建的距离数组

    for (int i = 0; i < n; i++)

        printf("顶点 %d 到源点的最短距离是: %d\n", i, dist[i]);

}

5 字符串处理

5.1 字符串匹配

        如KMP算法、Boyer-Moore算法等，使用数组来存储字符串的部分匹配信息。

5.1.1 KMP算法

       KMP算法的核心思想是，当在文本字符串中从左到右进行模式匹配时，如果某个字符不匹配，那么我们可以利用之前已经匹配的部分信息，跳过一些不必要的比较，从而提高匹配效率。

void KMPSearch(char *pat, char *txt) {

    int M = strlen(pat);

    int N = strlen(txt);

    int lps[M];

    computeLPSArray(pat, M, lps);

    int i = 0; // index for txt

    int j = 0; // index for pat

    while (i < N) {

        if (pat[j] == txt[i]) {

            i++;

            j++;

        }

        if (j == M) {

            printf("Found pattern at index %d\n", i - j);

            j = lps[j-1];

        } else if (i < N && pat[j] != txt[i]) {

            if (j != 0)

                j = lps[j-1];

            else

                i = i+1;

        }

    }

}

5.1.2 Boyer-Moore算法

       Boyer-Moore算法是一种高效的字符串搜索算法，它通过两个关键的预处理函数来优化搜索过程：坏字符规则（Bad Character Heuristic）和好后缀规则（Good Suffix Heuristic）。以下是C语言实现Boyer-Moore算法的关键函数：

1. 坏字符规则的预处理函数：

#define NO_OF_CHARS 256

void badCharHeuristic(char* str, int size, int badchar[NO_OF_CHARS]) {

    int i;

    for (i = 0; i < NO_OF_CHARS; i++)

        badchar[i] = -1;

    for (i = 0; i < size; i++)

        badchar[(int)str[i]] = i;

}

2. 搜索函数：

void search(char* txt, char* pat) {

    int m = strlen(pat);

    int n = strlen(txt);

    int badchar[NO_OF_CHARS];

    badCharHeuristic(pat, m, badchar);

    int s = 0; // s is shift of the pattern with respect to text

    while (s <= (n - m)) {

        int j = m - 1;

        while (j >= 0 && pat[j] == txt[s + j])

            j--;

        if (j < 0) {

            printf("\n pattern occurs at shift = %d", s);

            s += (s + m < n) ? m - badchar[txt[s + m]] : 1;

        } else {

            s += max(1, j - badchar[txt[s + j]]);

        }

    }

}

       在这段代码中， badCharHeuristic 函数用于构建坏字符规则表，它记录了模式字符串中每个字符的最后出现位置。 search 函数则是Boyer-Moore算法的核心，它使用坏字符规则来决定模式字符串应该向右移动的距离。

       要使用这些函数，你需要在主函数中调用 search 函数，并传入文本字符串和模式字符串。这样就会打印出模式字符串在文本字符串中出现的所有位置。

       在Boyer-Moore算法中，"好后缀"（Good Suffix）是指在模式字符串中，当发生匹配失败时，已经成功匹配的模式字符串的后缀中最长的相同前缀和后缀的子串。这个概念用于在发生不匹配时，决定模式字符串应该向右移动的距离。

       例如，假设我们有模式字符串  "ABABC" ，并且我们正在尝试在文本字符串中匹配它。如果我们在某个位置尝试匹配时， "B"  和  "C"  都匹配成功了，但下一个字符不匹配，那么  "BC"  就是一个好后缀。因为  "BC"  是模式字符串的后缀，并且它也是模式字符串的前缀。

       在Boyer-Moore算法中，当发生不匹配时，算法会查找这个好后缀在模式字符串中的下一个出现位置。然后，模式字符串会移动到文本字符串中的下一个位置，使得这个好后缀与模式字符串的开始位置对齐。

       例如，考虑模式字符串  "ABCDABD" ，如果我们在文本字符串中匹配时在位置  5  处发生了不匹配（即  "D"  不匹配），那么  "ABD"  就是已经匹配的子串，其中  "BD"  是一个好后缀。在模式字符串中， "BD"  也出现在开头，所以模式字符串应该移动到文本字符串中下一个  "B"  的位置，以便  "BD"  能够与模式字符串的开始位置对齐。

       以下是构建好后缀规则表的C语言函数：

void goodSuffixHeuristic(char* pat, int m, int goodSuffix[NO_OF_CHARS]) {

    int i, j;

    for (i = 0; i < m; i++) {

        goodSuffix[i] = -1;

    }

    for (i = 0; i < m - 1; i++) {

        int len = 0;

        // Check for the longest prefix which is also suffix

        for (j = m - 1; j >= 0; j--) {

            if (pat[j] == pat[len]) {

                len++;

                goodSuffix[j] = len;

            } else {

                break;

            }

        }

    }

    for (i = 0; i < m; i++) {

        // If the value is not set then it means it is a bad character

        if (goodSuffix[i] == -1)

            goodSuffix[i] = m;

    }

}

       这个函数会填充一个数组，该数组用于存储每个字符在模式字符串中对应的好后缀长度。如果在模式字符串中没有找到相同的前缀和后缀，则该位置的值将保持为  -1 。在搜索函数中，这个数组将与坏字符规则表一起使用，以确定在发生不匹配时模式字符串应该移动的最大距离。

       请注意，这个函数是一个简化的版本，它只考虑了模式字符串的前缀和后缀相等的情况。在实际应用中，可能需要更复杂的逻辑来处理不同的情况。

6 矩阵操作

6.1 矩阵乘法

       计算两个矩阵的乘积。

#include <stdio.h>

#define MAX_ROWS 100

#define MAX_COLS 100

// 矩阵乘法函数

void matrixMultiply(int A[][MAX_COLS], int B[][MAX_COLS], int C[][MAX_COLS], int Arows, int Acols, int Brows, int Bcols) {

    for (int i = 0; i < Arows; i++) {

        for (int j = 0; j < Bcols; j++) {

            C[i][j] = 0; // 初始化结果矩阵的元素为0

            for (int k = 0; k < Acols; k++) {

                C[i][j] += A[i][k] * B[k][j];

            }

        }

    }

}

6.2 矩阵链乘

       矩阵链乘问题是动态规划的经典应用之一。给定一系列矩阵，找出一种乘法顺序，使得计算所有矩阵的乘积所需的标量乘法次数最少。

       假设有 A_1, A_2, ..., A_n 个矩阵需要相乘，矩阵 A_i 的维度为 p_{i-1} \times p_i。矩阵链乘问题就是要找到一种乘法顺序，使得总的标量乘法次数最小。

       以下是矩阵链乘问题的关键函数，使用动态规划求解：

#include <stdio.h>

#include <limits.h>

// 动态规划解决矩阵链乘问题

void matrixChainOrder(int p[], int n, int **m, int **s) {

    // 初始化m和s

    for (int i = 1; i < n; i++) {

        m[i][i] = 0;

    }

    for (int l = 2; l < n; l++) { // l是链的长度

        for (int i = 1; i < n - l + 1; i++) {

            int j = i + l - 1;

            m[i][j] = INT_MAX;

            for (int k = i; k < j; k++) {

                // q = cost/scalar multiplications

                int q = m[i][k] + m[k+1][j] + p[i-1] * p[k] * p[j];

                if (q < m[i][j]) {

                    m[i][j] = q;

                    s[i][j] = k; // s[i][j]是分割点

                }

            }

        }

    }

}

// 打印最优乘法顺序

void printOptimalParens(int i, int j, int **s) {

    if (i == j) {

        printf("A%d", i);

    } else {

        printf("(");

        printOptimalParens(i, s[i][j], s);

        printOptimalParens(s[i][j] + 1, j, s);

        printf(")");

    }

}

// 主函数

int main() {

    int arr[] = {30, 35, 15, 5, 10, 20, 25}; // 矩阵的维度

    int size = sizeof(arr) / sizeof(arr[0]);

    int **m = (int **)malloc(size * sizeof(int *));

    int **s = (int **)malloc(size * sizeof(int *));

    for (int i = 0; i < size; i++) {

        m[i] = (int *)malloc(size * sizeof(int));

        s[i] = (int *)malloc(size * sizeof(int));

    }

    matrixChainOrder(arr, size, m, s);

    printf("最少的标量乘法次数是: %d\n", m[1][size - 1]);

    printf("最优乘法顺序是: ");

    printOptimalParens(1, size - 1, s);

    printf("\n");

    // 释放内存

    for (int i = 0; i < size; i++) {

        free(m[i]);

        free(s[i]);

    }

    free(m);

    free(s);

    return 0;

}

       在这个代码中， matrixChainOrder  函数计算了计算所有矩阵乘积的最小标量乘法次数，并存储在二维数组  m  中。数组  s  用于重建最优乘法顺序。

        printOptimalParens  函数递归地打印出最优的乘法顺序。

       在  main  函数中，我们初始化了矩阵的维度数组  arr ，分配了内存给动态数组  m  和  s ，并调用了  matrixChainOrder  函数来填充这些数组。然后，我们打印出最小的标量乘法次数和最优乘法顺序。

       请注意，这段代码假设所有的矩阵都是长方形的，并且它们的相邻矩阵的维度是匹配的，即除了第一个矩阵，每个矩阵的第一个维度都应该与前一个矩阵的第二个维度相同。

7 滑动窗口

       滑动窗口是一种常见的解决数组问题的方法，特别是在处理固定长度的子数组或子串时。以下是一个C语言实现的滑动窗口的关键函数示例，用于查找一个数组中最长的无重复字符的子串的长度：

#include <stdio.h>

#include <string.h>

// 函数返回最长无重复字符的子串的长度

int lengthOfLongestSubstring(char* s) {

    int n = strlen(s);

    int maxLength = 0;

    int start = 0; // 滑动窗口的起始位置

    // 用于存储字符最后出现的位置

    int lastIndex[256] = {0};

    for (int end = 0; end < n; end++) {

        // 如果字符已经出现过，且其最后出现的位置在当前滑动窗口内

        if (lastIndex[s[end]] >= start) {

            start = lastIndex[s[end]] + 1;

        }

        // 更新字符的最后出现位置

        lastIndex[s[end]] = end;

        // 计算当前滑动窗口的长度，并更新最长长度

        maxLength = maxLength > (end - start + 1) ? maxLength : (end - start + 1);

    }

    return maxLength;

}

// 主函数

int main() {

    char s[] = "abcabcbb";

    printf("最长无重复字符的子串的长度是: %d\n", lengthOfLongestSubstring(s));

    return 0;

}

       lengthOfLongestSubstring  函数用于计算字符串 s 中最长的无重复字符的子串的长度。它使用一个滑动窗口，通过 start 和 end 指针表示窗口的起始和结束位置。 lastIndex 数组用于存储每个字符最后出现的位置。

       当遇到重复字符时，将窗口的起始位置 start 移动到重复字符的下一个位置。每次迭代都更新最长长度 maxLength 。

       在 main 函数中，我们调用 lengthOfLongestSubstring 函数并打印出结果。

       这个函数适用于查找字符串中最长的无重复字符的子串，但它可以修改用于解决其他类型的滑动窗口问题。

8 计数问题

8.1 桶排序

       桶排序（Bucket Sort）是一种分布式排序算法，它将数组分为多个桶，每个桶内使用其他排序算法（如插入排序）进行排序，然后合并各个桶中的数据。桶排序的关键在于如何合理地分配桶以及如何合并桶中的数据。

       以下是一个C语言实现的桶排序的关键函数示例：

#include <stdio.h>

#include <stdlib.h>

#include <math.h>

// 函数声明

void bucketSort(float arr[], int n);

// 桶排序的关键函数

void bucketSort(float arr[], int n) {

    // 创建桶

    float *buckets[n]; // 桶数组

    for (int i = 0; i < n; i++) {

        buckets[i] = (float *)malloc(n * sizeof(float)); // 为每个桶分配内存

        buckets[i][0] = 0; // 初始化桶的计数为0

    }

    // 将数组元素分配到各个桶中

    for (int i = 0; i < n; i++) {

        int idx = (int)(n * arr[i]); // 计算元素应该放入哪个桶

        buckets[idx][++buckets[idx][0]] = arr[i]; // 将元素放入桶中，并更新桶的计数

    }

    // 对每个桶进行排序，这里使用插入排序

    for (int i = 0; i < n; i++) {

        int size = buckets[i][0];

        for (int j = 1; j < size; j++) {

            for (int k = j; k > 0 && buckets[i][k] < buckets[i][k - 1]; k--) {

                float temp = buckets[i][k];

                buckets[i][k] = buckets[i][k - 1];

                buckets[i][k - 1] = temp;

            }

        }

    }

    // 合并桶中的数据

    int idx = 0;

    for (int i = 0; i < n; i++) {

        for (int j = 0; j < buckets[i][0]; j++) {

            arr[idx++] = buckets[i][j];

        }

    }

    // 释放桶的内存

    for (int i = 0; i < n; i++) {

        free(buckets[i]);

    }

}

// 主函数

int main() {

    float arr[] = {0.78, 0.17, 0.39, 0.26, 0.72, 0.94, 0.21, 0.12, 0.23, 0.68};

    int n = sizeof(arr) / sizeof(arr[0]);

    bucketSort(arr, n);

    printf("排序后的数组: \n");

    for (int i = 0; i < n; i++) {

        printf("%0.2f ", arr[i]);

    }

    printf("\n");

    return 0;

}

       在这个示例中， bucketSort  函数接受一个浮点数数组 arr 和数组的长度 n 作为参数。它首先创建一个桶数组，并将数组元素分配到各个桶中。然后，对每个桶内的数据使用插入排序算法进行排序。最后，将所有桶中的数据合并回原数组。

      在 main 函数中，我们定义了一个浮点数数组 arr ，调用 bucketSort 函数对其进行排序，并打印排序后的数组。

      请注意，这个桶排序的实现假设数组的元素在 [0, 1) 区间内。如果数组的元素范围不同，可能需要调整桶的分配策略。此外，为了简化实现，每个桶的大小与原数组相同，这不是最优化的内存使用方式，但可以确保有足够的空间存储每个桶中的元素。

8.2 计数排序

       对整数数组进行排序，基于元素出现的次数。

void countSort(int arr[], int n) {

    int max = 0;

    for (int i = 0; i < n; i++) {

        if < n; i++) {

        ifarrarr[i] > max) max = arr[i];

    }

    int count[max+1];

    for (int i = 0; i <= max; i++) {

        count[i] = 0;

    }

    for (int i = 0; i < n; i++) {

        count[arr[i]]++;

    }

    int index = 0;

    for (int i = 0; i <= max; i++) {

        while (count[i] > 0) {

            arr[index++] = i;

            count[i]--;

        }

    }

}

9 前缀和

       用于快速计算数组的子数组和，常用于解决区间查询问题。

void prefixSum(int arr[], int n) {

    int prefix[n];

    prefix[0] = arr[0];

    for (int i = 1; i < n; i++) {

        prefix[i] = prefix[i-1] + arr[i];

    }

    // prefix[i] now contains sum of arr[0...i]

}

10 堆

10.1 优先队列

       使用数组实现的堆结构，可以快速获取最大或最小元素。

最大堆调整

void maxHeapify(int arr[], int n, int i) {
    int largest = i;
    int l = 2*i + 1;
    int r = 2*i + 2;

    if (l < n && arr[l] > arr[largest])
        largest = l;

    if (r < n && arr[r] > arr[largest])
        largest = r;

    if (largest != i) {
        swap(&arr[i], &arr[largest]);
        maxHeapify(arr, n, largest);
    }
}

11 并查集

       用于处理一些不交集的合并及查询问题。

int find(int i, int parent[]) {

    if (parent[i] == -1)

        return i;

    return find(parent[i], parent);

}

void Union(int x, int y, int parent[]) {

    int xset = find(x, parent);

    int yset = find(y, parent);

    if(xset != yset){

        parent[xset] = yset;

    }

}

12 双指针

       用于解决数组中的问题，如“反转字符串”、“判断回文链表”。

12.1 反转字符串

void reverseString(char* s) {

    int i = 0, j = strlen(s) - 1;

    while (i < j) {

        char temp = s[i];

        s[i] = s[j];

        s[j] = temp;

        i++;

        j--;

    }

}

       数组的应用非常广泛，不同的算法根据问题的特性选择不同的数据结构和方法。数组由于其简单性和高效的随机访问特性，在算法设计中扮演着重要角色。