数组算法
Array是一个容器，可以容纳固定数量的项目，这些项目应该是相同的类型。大多数数据结构都使用数组来实现其算法。以下是理解Array概念的重要术语。
- 元素 - 存储在数组中的每个项称为元素。
- 索引 - 数组中元素的每个位置都有一个数字索引，用于标识元素。
1.数组表示
可以使用不同语言以各种方式声明数组。为了说明，我们采取C数组声明。
可以使用不同语言以各种方式声明数组。为了说明，我们采取C数组声明。
根据以上说明，以下是要考虑的重点。
- 索引从0开始。
- 数组长度为10，这意味着它可以存储10个元素。
- 可以通过索引访问每个元素。例如，我们可以将索引6处的元素提取为9。
2.基本操作
以下是数组支持的基本操作。
- 遍历 - 逐个打印所有数组元素。
- 插入 - 在给定索引处添加元素。
- 删除 - 删除给定索引处的元素。
- 搜索 - 使用给定索引或值搜索元素。
- 更新 - 更新给定索引处的元素。
在C中，当使用size初始化数组时，它会按以下顺序为其元素分配默认值。
| 数据类型 | 默认值 |
| 布尔 | 假 |
| 烧焦 | 0 |
| INT | 0 |
| 浮动 | 0.0 |
| 双 | 0.0F |
| 空虚 | |
| wchar_t的 | 0 |
3.插入操作
插入操作是将一个或多个数据元素插入到数组中。根据需求，可以在开头，结尾或任何给定的数组索引处添加新元素。
在这里，我们看到插入操作的实际实现，我们在数组的末尾添加数据 -
算法
令 Array 为 MAX 元素的线性无序数组。
实例1
结果
让 LA 是一个线性阵列(无序的)与 Ñ 元件和 ķ 是一个正整数，使得 ķ <= N。以下是将ITEM插入洛杉矶第 K 个位置的算法-
1. Start 2. Set J = N 3. Set N = N+1 4. Repeat steps 5 and 6 while J >= K 5. Set LA[J+1] = LA[J] 6. Set J = J-1 7. Set LA[K] = ITEM 8. Stop
实例2
以下是上述算法的实现 -
#include <stdio.h> main() { int LA[] = {1,3,5,7,8}; int item = 10, k = 3, n = 5; int i = 0, j = n; printf("The original array elements are :\n"); for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); } n = n + 1; while( j >= k) { LA[j+1] = LA[j]; j = j - 1; } LA[k] = item; printf("The array elements after insertion :\n"); for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); } }
当我们编译并执行上述程序时，它会产生以下结果 -
输出
The original array elements are : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8 The array elements after insertion : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 10 LA[4] = 7 LA[5] = 8
3.删除操作
删除是指从数组中删除现有元素并重新组织数组的所有元素。
算法
考虑 LA 是一个线性阵列 Ñ 元件和 ķ 是一个正整数，使得 ķ <= N。以下是删除在LA的第 K 个位置可用的元素的算法。
1. Start 2. Set J = K 3. Repeat steps 4 and 5 while J < N 4. Set LA[J] = LA[J + 1] 5. Set J = J+1 6. Set N = N-1 7. Stop
实例1
以下是上述算法的实现
#include <stdio.h> void main() { int LA[] = {1,3,5,7,8}; int k = 3, n = 5; int i, j; printf("The original array elements are :\n"); for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); } j = k; while( j < n) { LA[j-1] = LA[j]; j = j + 1; } n = n -1; printf("The array elements after deletion :\n"); for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); } }
当我们编译并执行上述程序时，它会产生以下结果 -
输出
The original array elements are : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8 The array elements after deletion : LA[0] = 1 LA[1] = 3 LA[2] = 7 LA[3] = 8
4.搜索操作
您可以根据数组元素的值或索引搜索数组元素。
算法
考虑 LA 是一个线性阵列 Ñ 元件和 ķ 是一个正整数，使得 ķ <= N。以下是使用顺序搜索查找具有ITEM值的元素的算法。
1. Start 2. Set J = 0 3. Repeat steps 4 and 5 while J < N 4. IF LA[J] is equal ITEM THEN GOTO STEP 6 5. Set J = J +1 6. PRINT J, ITEM 7. Stop
实例2
以下是上述算法的实现
#include <stdio.h> void main() { int LA[] = {1,3,5,7,8}; int item = 5, n = 5; int i = 0, j = 0; printf("The original array elements are :\n"); for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); } while( j < n){ if( LA[j] == item ) { break; } j = j + 1; } printf("Found element %d at position %d\n", item, j+1); }
当我们编译并执行上述程序时，它会产生以下结果 -
输出
The original array elements are : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8 Found element 5 at position 3
5.更新操作
更新操作是指在给定索引处更新阵列中的现有元素。
算法
考虑 LA 是一个线性阵列 Ñ 元件和 ķ 是一个正整数，使得 ķ <= N。以下是更新在LA的第 K 个位置可用的元素的算法。
1. Start 2. Set LA[K-1] = ITEM 3. Stop
实3例
以下是上述算法的实现 -
#include <stdio.h> void main() { int LA[] = {1,3,5,7,8}; int k = 3, n = 5, item = 10; int i, j; printf("The original array elements are :\n"); for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); } LA[k-1] = item; printf("The array elements after updation :\n"); for(i = 0; i<n; i++) { printf("LA[%d] = %d \n", i, LA[i]); } }
当我们编译并执行上述程序时，它会产生以下结果 -
输出
The original array elements are : LA[0] = 1 LA[1] = 3 LA[2] = 5 LA[3] = 7 LA[4] = 8 The array elements after updation : LA[0] = 1 LA[1] = 3 LA[2] = 10 LA[3] = 7 LA[4] = 8
2.动态规划
动态编程方法类似于将问题分解为更小但更小的子问题的分而治之。但不同的是，分而治之，这些子问题并没有独立解决。相反，记住这些较小子问题的结果并用于类似或重叠的子问题。
动态编程用于我们遇到问题的地方，可以将其划分为类似的子问题，以便可以重复使用它们的结果。大多数情况下，这些算法用于优化。在解决现有子问题之前，动态算法将尝试检查先前解决的子问题的结果。结合子问题的解决方案以实现最佳解决方案。
所以我们可以说 -
- 该问题应该能够分成较小的重叠子问题。
- 通过使用较小子问题的最佳解决方案可以实现最佳解决方案。
- 动态算法使用Memoization。
对照
与解决局部优化的贪婪算法相反，动态算法被激励用于问题的整体优化。
与分而治之的算法相比，其中解决方案被组合以实现整体解决方案，动态算法使用较小子问题的输出，然后尝试优化更大的子问题。动态算法使用Memoization来记住已经解决的子问题的输出。
实例1
使用动态编程方法可以解决以下计算机问题 -
- 斐波纳契数系列
- 背包问题
- 河内塔
- 由Floyd-Warshall完成的所有最短路径
- Dijkstra的最短路径
- 项目安排
动态编程可以自上而下和自下而上的方式使用。当然，大多数情况下，参考之前的解决方案输出比CPU周期重新计算更便宜。
