什么是数组

数组是一种数据结构，用于存储相同数据类型的元素的集合。这些元素在内存中是连续存储的。数组的每个元素都可以通过其索引来访问，索引从 0 开始，到数组长度减 1。这种连续存储的方式使得数组在访问和处理大量数据时非常高效。

在编程中，数组被广泛用于各种场景，例如存储和处理一系列数字、字符串、对象等。它们可以是一维的（线性数组），也可以是多维的（如二维数组、三维数组等）。多维数组通常用于表示更复杂的数据结构，如矩阵、表格等。请注意，虽然数组的元素必须是相同的数据类型，但这个数据类型可以是基本数据类型（如整数、浮点数、字符等），也可以是复杂的数据类型（如对象、结构体等）。这使得数组在编程中非常灵活和有用。

数组

数组中偏移量（offset）是一个重要的概念。它表示从数组的起始位置（通常为 0）到特定元素位置的距离。通过增加一个偏移量到数组的起始位置，我们可以轻松地计算出每个元素在数组中的位置。例如，如果我们有一个名为 “friends” 的数组，并且我们知道第一个朋友在第 10 个阶梯上，那么当我们想要找到第 2 个朋友时，我们可以将偏移量设置为1（第 2 个朋友在第 11 个阶梯上），然后添加这个偏移量到基础值（10）来得到新的位置。

数组的每个元素都存储在连续的内存地址中。数组的每个元素占用的内存大小取决于其数据类型。例如，如果数组的数据类型是整数，那么每个元素通常占用4个字节（这可能会根据编程语言和计算机架构的不同而有所不同）。同样，如果数据类型是浮点数，每个元素可能占用更多的字节，如4或8个字节。因此，如果我们知道一个特定索引的位置，以及数组中元素的数据类型，我们就可以计算出下一个索引的位置。

索引与内存

在 C 语言中，数组的大小在声明时就已经确定，并且之后不能更改。这是因为 C 语言中的数组是在栈上分配的静态内存，这意味着在编译时就已经为数组分配了固定大小的内存空间。确实，数组的这种特性使得我们无法动态地扩展或缩小数组的大小。如果尝试扩展数组，我们无法保证下一个内存位置是空闲的，因此可能无法获得所需的额外空间。同样地，如果尝试缩小数组，由于内存是静态分配的，编译器是唯一能够销毁并释放该内存的实体，因此缩小操作也无法实现。

C语言提供了指针和动态内存分配函数（如 malloc 和 free），使我们能够创建动态数组或链表等数据结构，这些结构可以根据需要动态地扩展和缩小。通过使用指针和动态内存分配，我们可以在运行时根据需要分配和释放内存，从而灵活地处理数组和其他数据结构的大小。

需要注意的是，动态内存分配需要谨慎处理，以避免内存泄漏或其他与内存管理相关的问题。因此，在使用动态内存分配时，我们需要确保正确地分配和释放内存，以避免潜在的错误和资源浪费。

无序数组操作

在未排序的数组中进行搜索、插入和删除操作通常需要 O(n) 的时间复杂度，其中 n 是数组的元素数量。这是因为在最坏的情况下，我们需要遍历整个数组来找到特定的元素或进行插入或删除操作。以下是在未排序的数组中进行搜索、插入和删除操作的算法示例。

搜索

遍历数组，检查每个元素是否与要搜索的元素匹配。如果找到匹配的元素，返回其索引。如果遍历完数组仍未找到匹配的元素，返回-1（表示未找到）。

#include <bits/stdc++.h>  using namespace std;// Function to implement search operationint findElement(int arr[], int n, int key){    int i;    for (i = 0; i < n; i++)        if (arr[i] == key)            return i;    // If the key is not found    return -1;}int main(){    int arr[] = { 12, 34, 10, 6, 40 };    int n = sizeof(arr) / sizeof(arr[0]);    // Using a last element as search element    int key = 40;    // Function call    int position = findElement(arr, n, key);    if (position == -1)        cout << "Element not found";    else        cout << "Element Found at Position: "            << position + 1;    return 0;}

时间复杂度：O(n)。

空间复杂度：O(1)。

插入

遍历数组，找到要插入元素的位置。将要插入的元素插入到该位置。调整后续元素的索引以适应新元素。

#include <iostream> using namespace std;void insertElement (int arr[], int n, int x, int pos){  // shift elements to the right  // which are on the right side of pos  for (int i = n - 1; i >= pos; i--)    arr[i + 1] = arr[i];  arr[pos] = x;}int main (){  int arr[15] = { 2, 6, 1, 9, 15 };  int n = 5;  cout << "Before insertion : ";  for (int i = 0; i < n; i++)    cout << arr[i] << " ";  cout << endl;  int x = 11, pos = 2;  // Function call  insertElement (arr, n, x, pos);  n++;  cout << "After insertion : ";  for (int i = 0; i < n; i++)    cout << arr[i] << " ";  return 0;}

输出

Before insertion : 2 6 1 9 15 After insertion : 2 6 11 1 9 15

时间复杂度：O(n)。

删除

遍历数组，找到要删除的元素。删除该元素（可能需要调整后续元素的索引以适应删除的元素）。

#include <iostream> using namespace std;// Function to delete an elementint deleteElement (int arr[], int n, int key){  // Find position of element to be deleted  int pos = -1;  for (int i = 0; i < n; i++)    {      if (arr[i] == key)        {          pos = i;          break;        }    }  if (pos == -1)    {      cout << "Element not found";      return n;    }  // Deleting element  for (int i = pos; i < n - 1; i++)    arr[i] = arr[i + 1];  return n - 1;}int main (){  int arr[] = { 10, 50, 30, 40, 20 };  int n = sizeof (arr) / sizeof (arr[0]);  int key = 30;  cout << "Array before deletion\n";  for (int i = 0; i < n; i++)    cout << arr[i] << " ";  // Function call  n = deleteElement (arr, n, key);  cout << "\n\nArray after deletion\n";  for (int i = 0; i < n; i++)    cout << arr[i] << " ";  return 0;}

输出：

Array before deletion10 50 30 40 20 Array after deletion10 50 40 20

时间复杂度：O(n)。数组优缺点优点:按照索引查询元素速度快。能存储大量数据。按照索引遍历数组方便。数组定义简单，而且访问很方便。可以随机访问其中的元素。缺点:根据内容查找元素速度慢。数组的大小一经确定不能改变，不适合动态存储。数组只能存储一种类型的数据。增加、删除元素效率慢。未封装任何方法，所有操作都需要用户自己定义。数组的空间必须是连续的，这就造成数组在内存中分配空间时必须找到一块连续的内存空间。所以数组不可能定义的太大，因为内存中不可能有那么多大的连续的内存空间，而解决这个问题的方法就是使用链表。