数据结构–数组（详细分析）

大家好，欢迎来到IT知识分享网。

目录

🍉引言

🍉数组

🍈数组的特性

🍈数组的优缺点

🍍优点：

🍍缺点：

🍈数组的声明与初始化

🍈数组的常见操作

🍍 插入操作

🍍删除操作

🍍查找操作

🍅线性查找：

🍅二分查找：

🍈数组的常见问题实现

🍍反转数组

🍍数组中的最大和最小元素

🍈演示

🍍插入操作

🍍删除操作

🍍反转数组

🍉总结

🍉引言

• 数据结构是计算机科学的基石，它们为数据的组织、管理和存储提供了不同的方法和策略。在众多数据结构中，数组和字符串是最基本且常用的两种。本教学文章将详细分析数组与字符串的特性，展示两者的示例操作与问题实现，并通过图示演示实现问题的过程。

🍉数组

🍈数组的特性

数组是一种线性数据结构，它使用连续的内存空间存储相同类型的元素。数组的主要特点如下：

1. 固定大小：数组在声明时必须指定大小，并且在大多数编程语言中，数组的大小在其生命周期内不可改变。
2. 随机访问：数组支持通过索引进行快速随机访问，这使得数组在查找操作中的效率很高。
3. 相同数据类型：数组中所有元素必须是相同的数据类型，这保证了数组的内存布局的紧凑性和一致性。
4. 低级别存储：由于数组使用连续的内存空间存储数据，它们在内存管理和访问速度方面具有优势。

🍈数组的分类

🍍基本定义

• 数组的空间复杂度通常为 O(n)，其中 n 是数组的元素个数。具体来说，如果每个元素占用的空间是固定的（比如在C语言中的 int 类型占用4个字节），那么整个数组的空间复杂度就是元素个数乘以每个元素占用的空间。

🍍静态数组 vs 动态数组

🍅静态数组

• 静态数组在编译时确定大小，一旦分配就不能改变大小。其空间复杂度为：O(n)其中 n 是数组的长度。

🍅动态数组

• 动态数组（如C++中的 std::vector，Java中的 ArrayList）在运行时可以调整大小。当需要扩展时，通常会以一定比例（如2倍）增加大小。因此，动态数组的空间复杂度稍微复杂一些，考虑到了扩展时的额外开销。
• 动态数组的平均空间复杂度仍然是 O(n)，但在最坏情况下，当数组需要扩展时，空间复杂度会瞬间增加到 O(2n)，即需要额外的空间来存储新的元素数组。

🍍内存分配的细节

🍅连续内存分配

• 数组元素在内存中是连续存储的，这种方式的优点是访问速度快，但缺点是需要一次性分配大块连续的内存。在内存紧张或碎片化严重的情况下，可能会导致分配失败。

🍅空间浪费

• 由于数组在创建时必须确定大小，如果预估不准确，可能会出现空间浪费或空间不足的情况。预分配过多会导致内存浪费，预分配过少则需要重新分配更大的数组，这样不仅增加了额外的内存开销，还可能影响性能。

🍍实际示例分析

假设我们有一个包含 1000 个整数的数组 int arr[1000];：

• 每个整数占用 4 个字节。
• 数组总共占用的空间为 1000×4=×4=4000 字节，即 4 KB。

🍍 动态数组的扩展分析

假设一个动态数组在初始分配时大小为 4，存储了4个元素后需要扩展到 8：

1. 初始状态：大小为 4，占用 4×4=164×4=16 字节。
2. 扩展到 8：需要分配新的内存块，占用 8×4=328×4=32 字节。

在扩展过程中，原有的4个元素需要复制到新的内存块，导致在扩展的瞬间，数组占用的空间为 16+32=4816+32=48 字节。

🍍总结

• 静态数组：空间复杂度为 O(n)，其中 n 是数组长度。
• 动态数组：平均空间复杂度为 O(n)，但由于扩展过程可能导致瞬时空间复杂度达到 O(2n)。

🍈数组的优缺点

🍍优点：

• 快速访问：
  • 数组提供了快速访问元素的能力。由于数组元素在内存中是连续存储的，可以通过索引直接访问任意元素，时间复杂度为 �(1)O(1)。
• 易于遍历：
  • 数组的线性结构使得遍历非常方便，可以使用简单的循环结构（如for循环）访问所有元素。
• 内存管理：
  • 数组在内存中是连续分配的，这可以提高缓存命中率，从而加快访问速度。
• 简单性：
  • 数组的数据结构和操作（如插入、删除、访问）相对简单，容易理解和实现。

🍍缺点：

• 固定大小：
  • 在大多数编程语言中，数组的大小在创建时必须确定，不能动态调整。如果预估不准确，要么浪费内存，要么导致空间不足。
• 插入和删除效率低：
  • 由于数组的元素是连续存储的，在中间位置插入或删除元素需要移动大量元素，时间复杂度为 �(�)O(n)，这对性能有负面影响。
• 内存浪费：
  • 如果数组大小预估过大，会浪费内存；如果预估过小，又可能导致数组溢出，需重新分配更大的数组，增加了复杂性和时间开销。
• 类型限制：
  • 数组通常只能存储相同类型的数据，这限制了数组的灵活性。如果需要存储不同类型的数据，需要使用其他数据结构（如对象或元组）。

🍈数组的声明与初始化

在C语言中，可以通过以下方式声明和初始化数组：

#include <stdio.h> int main() { // 声明一个大小为5的整数数组 int arr[5]; // 初始化数组 int arr2[5] = {1, 2, 3, 4, 5}; // 打印数组元素 for(int i = 0; i < 5; i++) { printf("%d ", arr2[i]); } return 0; } 

🍈数组的常见操作

🍍 插入操作

在数组中插入元素需要将插入位置之后的所有元素向后移动一位，以腾出位置：

#include <stdio.h> void insert(int arr[], int n, int pos, int value) { for(int i = n; i > pos; i--) { arr[i] = arr[i - 1]; } arr[pos] = value; } int main() { int arr[6] = {1, 2, 3, 4, 5}; int n = 5; // 当前数组元素数量 int pos = 2; // 插入位置 int value = 99; // 插入值 insert(arr, n, pos, value); for(int i = 0; i <= n; i++) { printf("%d ", arr[i]); } return 0; } 

🍍删除操作

删除数组中的元素需要将删除位置之后的所有元素向前移动一位：

#include <stdio.h> void delete(int arr[], int n, int pos) { for(int i = pos; i < n - 1; i++) { arr[i] = arr[i + 1]; } } int main() { int arr[5] = {1, 2, 3, 4, 5}; int n = 5; // 当前数组元素数量 int pos = 2; // 删除位置 delete(arr, n, pos); for(int i = 0; i < n - 1; i++) { printf("%d ", arr[i]); } return 0; } 

🍍查找操作

在数组中查找元素可以通过线性查找或二分查找（如果数组有序）来实现：

🍅线性查找：

#include <stdio.h> int linearSearch(int arr[], int n, int value) { for(int i = 0; i < n; i++) { if(arr[i] == value) { return i; } } return -1; } int main() { int arr[5] = {1, 2, 3, 4, 5}; int value = 3; // 查找值 int index = linearSearch(arr, 5, value); if(index != -1) { printf("Element found at index %d\n", index); } else { printf("Element not found\n"); } return 0; } 

🍅二分查找：

#include <stdio.h> int binarySearch(int arr[], int left, int right, int value) { while(left <= right) { int mid = left + (right - left) / 2; if(arr[mid] == value) { return mid; } if(arr[mid] < value) { left = mid + 1; } else { right = mid - 1; } } return -1; } int main() { int arr[5] = {1, 2, 3, 4, 5}; int value = 3; // 查找值 int index = binarySearch(arr, 0, 4, value); if(index != -1) { printf("Element found at index %d\n", index); } else { printf("Element not found\n"); } return 0; } 

🍈数组的常见问题实现

🍍反转数组

反转数组意味着将数组中的元素顺序颠倒：

#include <stdio.h> void reverseArray(int arr[], int n) { int start = 0; int end = n - 1; while(start < end) { int temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } int main() { int arr[5] = {1, 2, 3, 4, 5}; reverseArray(arr, 5); for(int i = 0; i < 5; i++) { printf("%d ", arr[i]); } return 0; } 

运行结果：

🍍数组中的最大和最小元素

查找数组中的最大和最小元素：

#include <stdio.h> void findMaxMin(int arr[], int n, int *max, int *min) { *max = arr[0]; *min = arr[0]; for(int i = 1; i < n; i++) { if(arr[i] > *max) { *max = arr[i]; } if(arr[i] < *min) { *min = arr[i]; } } } int main() { int arr[5] = {1, 2, 3, 4, 5}; int max, min; findMaxMin(arr, 5, &max, &min); printf("Max: %d, Min: %d\n", max, min); return 0; } 

运行结果：

🍈演示

🍍插入操作

在数组 arr = [1, 2, 3, 4, 5] 中插入值 99 到位置 2：

初始数组: [1, 2, 3, 4, 5] 插入值99到位置2: 向后移动: [1, 2, 3, 3, 4, 5] 向后移动: [1, 2, 2, 3, 4, 5] 插入完成: [1, 99, 2, 3, 4, 5] 

🍍删除操作

在数组 arr = [1, 2, 3, 4, 5] 中删除位置 2 的元素：

初始数组: [1, 2, 3, 4, 5] 删除位置2的元素: 向前移动: [1, 2, 4, 4, 5] 向前移动: [1, 2, 4, 5, 5] 删除完成: [1, 2, 4, 5] 

🍍反转数组

将数组 arr = [1, 2, 3, 4, 5] 反转：

初始数组: [1, 2, 3, 4, 5] 反转过程: 交换位置0和4: [5, 2, 3, 4, 1] 交换位置1和3: [5, 4, 3, 2, 1] 反转完成: [5, 4, 3, 2, 1] 

🍉总结

• 数组作为一种固定大小且内存连续的线性数据结构，提供了高效的随机访问能力

希望这些能对刚学习数据结构的同学们提供些帮助哦！！！