第一篇：如何在数组中操作数据【数据结构入门】

记录以下自己重温数据结构的笔记，附带自己实现的C代码，
其中部分Python代码是网上教程里的，顺手粘贴过来，做一对比/
（Python确实简洁，但是C更好理解不是吗哈哈哈）

数组的定义

数组：线性表数据结构，利用一段连续的内存空间，存储相同类型的数据
数组中的每个元素有唯一的下标索引
两个角度理解数组：线性表结构，连续的内存空间，本质：采用顺序存储结构的线性表

随机访问数据元素

数组最显著的特点：支持随机访问，就是通过下标直接定位并访问任意一个元素
本质：第一个元素地址为首地址，每个元素都有唯一的下标和对应的内存地址，访问数组元素时，利用下标通过寻址公式快速计算出目标元素的内存地址，实现高效访问
寻址公式：下标 i 的元素地址 = 首地址 + i × 单个元素占用的字节数

多维数组

一般由m行n列的数据元素组成，本质上可理解为数组的数组，每个元素本身也是一个数组。
第一维表示行，第二维表示列。内存中，二维数组通常采用行优先或列优先的存储方式。
二维数组常被视为矩阵，可用于处理如矩阵转置、矩阵加法、矩阵乘法等问题。

数组在不同编程语言中的实现

不同编程语言中的数据实现存在一定差异。
C/C++中的数组最贴合其定义：他们使用一块连续的内存空间来存储相同类型的数据元素。
无论是基本数据类型，还是结构体、对象，在数组中都以连续方式排列。

int arr[3][4] = {{0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11}};

Java中的数组类似于C，但在多维数组的情况下，其允许创建不规则数组，即每个嵌套数组的长度可以不同。

int[][] arr = new int[3][];
arr[0] = new int[]{1, 2, 3};
arr[1] = new int[]{4, 5};
arr[2] = new int[]{6, 7, 8, 9};

Python使用“列表”这种容器类型，类似于Java中的ArrayList，通常将其作为数组使用，与传统数组不同的是，Python不仅可以存储不同类型的数据元素，长度也可以动态变化，并且支持丰富的内置方法。

arr = ['python', 'java', ['asp', 'php'], 'c']

数组的几种基本操作

基本上，数组的操作主要涉及“增删改查”四类，掌握这个就可以说掌握了数组的具体应用

访问元素

假设我们要访问数组中第 i 个元素：

1. 首先检查下标 i 是否在合法范围内，即 0 ≤ i ≤ len（nums）-1，超出该范围属于非法访问
2. 如果下标合法，则可直接通过下标获取对应元素的值
3. 如果下标不合法，则抛出异常或返回特殊值
4. 访问数组元素不依赖于数组元素个数，因此其时间复杂度为O(1)
5. C语言不会在访问时检查数组下标是否越界，因此编程者必须自己确保索引在有效范围内

int arr[10] = {1, 2, 3, 4, 56, 7, 89, 999};

int main() {

    printf("the first number is %d\n", arr[3]);
    arr[3] = 8;
    printf("the second number is %d\n", arr[3]);

    return 0;
}

// 从数组 nums 中读取下标为 i 的数据元素值
def get_element(nums: list[int], index: int):
    """获取数组中指定下标的元素值"""
    if 0 <= index < len(nums):
        return nums[index]
    else:
        raise IndexError(f"数组下标 {index} 超出范围 [0, {len(nums)-1}]")

//示例用法
arr = [0, 5, 2, 3, 7, 1, 6]
print(get_element(arr, 3))  # 输出: 3

查找元素

查找数组中元素值为 val 的位置

1. 遍历数组，将目标值与每个元素进行比较
2. 找到匹配元素时返回其下标
3. 遍历完未找到时返回特殊值
4. 当数组无序时，查找元素只能通过将 val 与数组中的每个元素依次比较，这种方式称为线性查找。由于需要遍历整个数组，线性查找的时间复杂度为O(n)

int arrfind(int nums[], int size, int val) {
    for (int i = 0; i < size; i++) {
        if(nums[i] == val){
            return i;
        }
    }
    return -1;
}

int arr[] = {1, 2, 3, 4, 56, 7, 89, 999};

int main() {

    // 查找数组元素
    int arr_size = sizeof(arr);// sizeof(arr[0]);

    // 在arr数组中寻找元素3
    int i1 = arrfind(arr,arr_size,3);
    printf("num 5 index is: %d\n",i1);

    // 在arr数组中寻找元素15
    int i2 = arrfind(arr,arr_size,15);
    printf("num 15 index is: %d\n",i2);

    return 0;
}

def find_element(nums: list[int], val: int):
    """查找数组中元素值为 val 的位置"""
    for i in range(len(nums)):
        if nums[i] == val:
            return i
    return -1

示例用法
arr = [0, 5, 2, 3, 7, 1, 6]
print(find_element(arr, 5))  # 输出: 1
print(find_element(arr, 9))  # 输出: -1 (未找到)

插入元素

在数组的第 i 个位置插入值 val

1. 检查 i 是否在数组范围之内
2. 拓展数组长度，为新元素腾出空间
3. 将 i 及其之后的元素整体向后移动一位
4. 在 i 位置插入 val

bool insert_element(int arr[], int *currentSize, int maxSize, int index, int val) {
    // 检查索引是否有效：必须在 0 到 currentSize 之间（含）
    // 注意：可以在末尾插入，即 index == *currentSize
    if (index < 0 || index > *currentSize) {
        printf("错误：插入索引 %d 越界！有效范围是 [0, %d]\n", index, *currentSize);
        return false;
    }

    // 检查数组是否已满
    if (*currentSize >= maxSize) {
        printf("错误：数组已满，无法插入新元素！\n");
        return false;
    }

    // 【关键步骤】 从最后一个元素开始，逐个向后移动，为新元素腾出空间
    for (int i = *currentSize - 1; i >= index; i--) {
        arr[i + 1] = arr[i];
    }

    // 在指定位置插入新值
    arr[index] = val;

    // 更新数组的实际大小
    (*currentSize)++;

    return true;
}

改变元素

将数组中的第 i 个元素改为 val

1. 检查 i 是否在数组长度之内
2. 将第 i 个元素值赋值为 val

// 改变数组指定的元素值
bool change_array(int arr[], int size, int index, int val)
{
    if (index < 0 || index >= size) {
        printf("错误：赋值索引 %d 越界！有效范围是 [0, %d]\n", index, size);
        return false;
    }

    arr[index] = val;

    return true;
}

删除元素

删除数组中指定 i 位置的元素

1. 检查下标 i 是否在合法的范围内
2. 将 i + 1 位置及其之后的元素整体向前移动一位
3. 删除最后一个元素（或更新数组长度）
4. 删除元素需要移动后续元素，移动次数与数组长度有关，因此时间复杂度为O(n)

/**
 * 删除数组中指定索引位置的元素
 * @param arr: 目标数组
 * @param currentSize: 指向当前数组元素个数的指针（函数会修改它）
 * @param index: 要删除的元素索引
 * @return: 成功返回 true，失败（索引越界）返回 false
 */
bool delete_element(int arr[], int *currentSize, int index) {
    // 检查索引是否有效：必须在 [0, currentSize - 1] 范围内
    if (index < 0 || index >= *currentSize) {
        printf("错误：删除索引 %d 越界！有效范围是 [0, %d)\n", index, *currentSize);
        return false;
    }

    // 从 index + 1 开始，将每个元素向前移动一位
    for (int i = index; i < *currentSize - 1; i++) {
        arr[i] = arr[i + 1];
    }

    // 逻辑上减少数组大小
    (*currentSize)--;

    return true;
}

总结

数组采用连续的内存空间来存储相同类型的数据，其优势在于支持随机访问，可以通过下标高效定位和访问任意元素
数组的访问和修改操作时间复杂度为时间复杂度为O(1)，而插入和删除操作需要移动元素，时间复杂度为O(n)
这部分内容需要掌握的是逻辑（其实概括一下都是先校验索引范围，再操作数据，最后打印出来展示，三步走），具体的实现比较简单，实际应用中更应关注函数、指针等细节方面