赣州网站建设效果,wordpress插件安装教程,电商培训心得体会总结简短,制作ppt用什么软件好数组是计算机科学中的一种基础数据结构#xff0c;它在算法中有着广泛的应用#xff0c;其关键要素是索引与索引对应的值。 请注意#xff0c;这些代码示例需要适当的辅助函数#xff08;如 swap #xff09;和主函数来运行。此外#xff0c;一些算法#xff08;如KMP算… 数组是计算机科学中的一种基础数据结构它在算法中有着广泛的应用其关键要素是索引与索引对应的值。 请注意这些代码示例需要适当的辅助函数如 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[j1]) swap(arr[j], arr[j1]);
}
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[n2]; // 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[m1][n1]; int i, j; // 构建L[m1][n1]表 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[n1][W1]; // 构建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 i1; } }
}
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[k1][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[max1]; 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--; }
} 数组的应用非常广泛不同的算法根据问题的特性选择不同的数据结构和方法。数组由于其简单性和高效的随机访问特性在算法设计中扮演着重要角色。
