什么是数组

数组是一种数据结构，用于存储相同数据类型的元素的集合。这些元素在内存中是连续存储的。数组的每个元素都可以通过其索引来访问，索引从 0 开始，到数组长度减 1。这种连续存储的方式使得数组在访问和处理大量数据时非常高效。
在编程中，数组被广泛用于各种场景，例如存储和处理一系列数字、字符串、对象等。它们可以是一维的（线性数组），也可以是多维的（如二维数组、三维数组等）。多维数组通常用于表示更复杂的数据结构，如矩阵、表格等。请注意，虽然数组的元素必须是相同的数据类型，但这个数据类型可以是基本数据类型（如整数、浮点数、字符等），也可以是复杂的数据类型（如对象、结构体等）。这使得数组在编程中非常灵活和有用。

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

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

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

C语言提供了指针和动态内存分配函数（如 malloc 和 free），使我们能够创建动态数组或链表等数据结构，这些结构可以根据需要动态地扩展和缩小。通过使用指针和动态内存分配，我们可以在运行时根据需要分配和释放内存，从而灵活地处理数组和其他数据结构的大小。
需要注意的是，动态内存分配需要谨慎处理，以避免内存泄漏或其他与内存管理相关的问题。因此，在使用动态内存分配时，我们需要确保正确地分配和释放内存，以避免潜在的错误和资源浪费。

无序数组操作

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

搜索

#include <bits/stdc++.h>
  using namespace std;

// Function to implement search operation
int 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

删除

#include <iostream>
 using namespace std;

// Function to delete an element
int 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 deletion
10 50 30 40 20 

Array after deletion
10 50 40 20

数组优缺点

• 按照索引查询元素速度快。
• 能存储大量数据。
• 按照索引遍历数组方便。
• 数组定义简单，而且访问很方便。
• 可以随机访问其中的元素。

• 根据内容查找元素速度慢。
• 数组的大小一经确定不能改变，不适合动态存储。
• 数组只能存储一种类型的数据。
• 增加、删除元素效率慢。
• 未封装任何方法，所有操作都需要用户自己定义。
• 数组的空间必须是连续的，这就造成数组在内存中分配空间时必须找到一块连续的内存空间。所以数组不可能定义的太大，因为内存中不可能有那么多大的连续的内存空间，而解决这个问题的方法就是使用链表。