数据结构入门：详解顺序表的实现与操作

2.2.2 动态顺序表

定义与特点

• 可变容量：支持运行时动态调整容量（扩展或收缩），通过重新分配内存实现。
• 内存分配：通常在堆上动态分配，由程序逻辑管理（如 malloc 或 new）。
• 高级操作：封装了插入、删除、扩容等复杂逻辑，用户无需手动处理内存。

// 定义顺序表存储的元素类型为 int
// 使用宏定义方便后续修改元素类型（例如改为 float 或自定义结构体）
#define SLDataType int
// 动态顺序表结构体定义
typedef struct Seqlist {
    SLDataType* arr; // 指向动态分配数组的指针（存储元素）
    int size; // 当前顺序表中有效元素的数量
    int capacity; // 当前顺序表的总容量
} SL;

将静态顺序表和动态数据表做一个对比：

经过比对，我们发现 静态顺序表简单但僵化，适合确定性的小规模数据。动态顺序表复杂但强大，是现代编程语言中动态数组的基础实现。

本文将以实现动态顺序表为主，详细讲述动态顺序表的扩容，头插，尾插，删除等操作。

3. 动态顺序表的实现

3.1 SeqList.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
typedef int SLDataType;
// 动态顺序表 -- 按需申请
typedef struct SeqList {
    SLDataType* arr;
    int size; // 有效数据个数
    int capacity; // 空间容量
}SL;
//初始化和销毁
void SLInit(SL* ps);
void SLDestroy(SL* ps);
void SLPrint(SL* ps);
//扩容
void SLCheckCapacity(SL* ps);
//头部插入删除 / 尾部插入删除
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushFront(SL* ps, SLDataType x);
void SLPopFront(SL* ps);
//指定位置之前插入/删除数据
void SLInsert(SL* ps, int pos, SLDataType x);
void SLErase(SL* ps, int pos);
int SLFind(SL * ps, SLDataType x);

一个动态顺序表至少应该能够实现以上功能，下面我们来逐一实现。

3.2 SeqList.c

3.2.1 初始化

void SLInit(SL* ps) {
    ps->arr = NULL;
    ps->capacity = 0;
    ps->size = 0;
}

3.2.2 销毁

void SLDestroy(SL* ps) {
    if (ps->arr) {
        free(ps->arr);
    }
    ps->arr = NULL;
    ps->capacity = 0;
    ps->size = 0;
}

注意：这里释放空间需要判断指针是否为空，如果是空指针直接释放会报错，同时我们要检查的是 ps->arr，并不是 ps，需要额外注意，不要释放 ps 的空间和将 ps 置空指针

3.2.3 打印

void SLPrint(SL* ps) {
    for (int i = 0; i < ps->size; i++) {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}

3.2.4 顺序表扩容

void SLCheckCapacity(SL* ps) {
    // 检查是否需要扩容（当前元素数 == 当前容量）
    if (ps->capacity == ps->size) {
        // 计算新容量：如果当前容量为 0（初始状态）则设为 4，否则扩容 2 倍
        int new_capacity = ps->capacity == 0 ? 4 : 2 * (ps->capacity);
        // 尝试重新分配内存
        SLDataType* tem = realloc(ps->arr, new_capacity * sizeof(SLDataType));
        // 处理内存分配失败的情况
        if (tem == NULL) {
            perror("realloc"); // 打印错误信息
            exit(EXIT_FAILURE); // 终止程序（EXIT_FAILURE 是标准错误退出码）
        }
        // 更新顺序表结构
        ps->arr = tem; // 指向新分配的内存
        ps->capacity = new_capacity; // 更新容量值
    }
}

关键点说明：扩容时机：当 size == capacity 时触发扩容，这是为了防止下一次插入操作导致溢出。扩容策略：初始容量设为 4（常见设计，避免初期频繁扩容）之后每次按 2 倍扩容（标准库常用策略，均摊时间复杂度为 O(1)）。内存管理：使用 realloc 而不是 malloc，可以保留原有数据必须检查返回值是否为 NULL（内存分配可能失败）。错误处理：使用 perror 输出错误信息（会显示系统级的错误原因）。EXIT_FAILURE 是标准库定义的错误退出码（通常值为 1）。安全性：先将 realloc 结果赋给临时变量 tem，确认成功后再赋给 ps->arr 避免直接 ps->arr = realloc(...) 导致内存泄漏

3.2.5 尾部插入及尾部删除

/**
 * @brief 在顺序表尾部插入一个元素
 * @param ps 指向顺序表结构的指针（必须非空）
 * @param x 要插入的元素值
 */
void SLPushBack(SL* ps, SLDataType x) {
    assert(ps); // 确保顺序表指针有效（若 ps 为 NULL 则终止程序）
    SLCheckCapacity(ps); // 检查并扩容（若容量不足）
    ps->arr[ps->size++] = x; // 在尾部插入元素，并更新 size
}

/**
 * @brief 删除顺序表尾部元素（逻辑删除）
 * @param ps 指向顺序表结构的指针（必须非空且 arr 有效）
 */
void SLPopBack(SL* ps) {
    assert(ps && ps->arr); // 确保顺序表指针和内部数组指针均有效
    ps->size--; // 减少 size，忽略最后一个元素（逻辑删除）
}

3.2.6 头部插入及头部删除

/**
 * @brief 在顺序表头部插入一个元素
 * @param ps 指向顺序表结构的指针（必须非空且内部数组已初始化）
 * @param x 要插入的元素值
 * @note 时间复杂度 O(n)，需要移动所有元素
 */
void SLPushFront(SL* ps, SLDataType x) {
    // 1. 参数校验
    assert(ps && ps->arr); // 确保顺序表指针和内部数组指针有效
    // 2. 容量检查（必要时扩容）
    SLCheckCapacity(ps); // 检查并处理容量不足的情况
    // 3. 移动元素：从后往前逐个后移
    for (int i = ps->size; i > 0; i--) {
        ps->arr[i] = ps->arr[i - 1]; // 将元素向后移动一位
    }
    // 4. 插入新元素到头部
    ps->arr[0] = x; // 在数组头部放入新元素
    // 5. 更新元素计数
    ps->size++; // 顺序表长度 +1
}

/**
 * @brief 删除顺序表头部元素
 * @param ps 指向顺序表结构的指针（必须非空且顺序表不为空）
 * @note 时间复杂度 O(n)，需要移动剩余所有元素
 */
void SLPopFront(SL* ps) {
    // 1. 参数校验
    assert(ps && ps->size > 0); // 确保顺序表有效且不为空
    // 2. 移动元素：从前往后逐个前移
    for (int i = 0; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1]; // 将元素向前移动一位
    }
    // 3. 更新元素计数
    ps->size--; // 顺序表长度 -1
    /* 可选：清零最后一个元素位置的值
       ps->arr[ps->size] = 0; // 防止脏数据
    */
}

3.2.7 特定位置插入及删除

/**
 * @brief 在顺序表指定位置前插入元素
 * @param ps 指向顺序表结构的指针（必须非空）
 * @param pos 要插入的位置索引（0 ≤ pos ≤ ps->size）
 * @param x 要插入的元素值
 * @note 时间复杂度 O(n)，需要移动元素
 * @note 边界情况：
 * - pos=0：相当于头部插入
 * - pos=size：相当于尾部追加
 */
void SLInsert1(SL* ps, int pos, SLDataType x) {
    assert(ps); // 确保顺序表指针有效
    assert(pos >= 0 && pos <= ps->size); // 检查位置合法性
    SLCheckCapacity(ps); // 检查并扩容（若容量不足）
    // 从后往前移动元素，腾出 pos 位置
    for (int i = ps->size; i > pos; i--) {
        ps->arr[i] = ps->arr[i - 1]; // 元素后移
    }
    ps->arr[pos] = x; // 在 pos 位置插入新元素
    ps->size++; // 更新元素数量
}

/**
 * @brief 在顺序表指定位置后插入元素
 * @param ps 指向顺序表结构的指针（必须非空）
 * @param pos 参考位置索引（0 ≤ pos < ps->size）
 * @param x 要插入的元素值
 * @note 时间复杂度 O(n)，需要移动元素
 * @note 边界情况：
 * - pos=0：在第一个元素后插入
 * - pos=size-1：相当于尾部追加
 */
void SLInsert2(SL* ps, int pos, SLDataType x) {
    assert(ps); // 确保顺序表指针有效
    assert(pos >= 0 && pos < ps->size); // 检查位置合法性
    SLCheckCapacity(ps); // 检查并扩容
    // 从后往前移动元素，腾出 pos+1 位置
    for (int i = ps->size; i > pos + 1; i--) {
        ps->arr[i] = ps->arr[i - 1]; // 元素后移
    }
    ps->arr[pos + 1] = x; // 在 pos+1 位置插入新元素
    ps->size++; // 更新元素数量
}

/**
 * @brief 删除顺序表指定位置的元素
 * @param ps 指向顺序表结构的指针（必须非空且顺序表非空）
 * @param pos 要删除的位置索引（0 ≤ pos < ps->size）
 * @note 时间复杂度 O(n)，需要移动元素
 * @note 边界情况：
 * - pos=0：删除头部元素
 * - pos=size-1：删除尾部元素
 */
void SLErase(SL* ps, SLDataType pos) {
    assert(ps && ps->size > 0); // 确保顺序表有效且非空
    assert(pos >= 0 && pos < ps->size); // 检查位置合法性
    // 从 pos 位置开始，用后续元素覆盖当前元素
    for (int i = pos; i < ps->size - 1; i++) {
        ps->arr[i] = ps->arr[i + 1]; // 元素前移
    }
    ps->size--; // 更新元素数量
    /* 可选：清除残留数据（防止脏数据）
       ps->arr[ps->size] = 0;
    */
}

3.2.8 查找元素，返回下标

/**
 * @brief 在顺序表中查找指定元素的位置
 * @param ps 指向顺序表结构的指针（必须非空）
 * @param x 要查找的元素值
 * @return 如果找到，返回元素的索引（0 ≤ index < size）；
 * 如果未找到，返回 -1
 * @note 时间复杂度 O(n)，需要遍历数组
 */
int SLFind(SL* ps, SLDataType x) {
    assert(ps); // 确保顺序表指针有效
    // 遍历顺序表查找元素
    for (int i = 0; i < ps->size; i++) {
        if (ps->arr[i] == x) {
            return i; // 找到元素，返回索引
        }
    }
    return -1; // 未找到元素
}

4. 顺序表算法题

1. 力扣：移除元素

核心思想 使用 双指针技巧：src（源指针）：遍历原始数组，检查每个元素。dst（目标指针）：记录非 val 元素的存储位置。 算法步骤 初始化 src 和 dst 为 0。 遍历数组：如果 nums[src] == val：跳过该元素（src++）。 如果 nums[src] != val：将其复制到 nums[dst]，然后 src++ 和 dst++。 最终 dst 的值即为新数组的长度。

代码：

int removeElement(int* nums, int numsSize, int val) {
    int src = 0, dst = 0;
    while(src < numsSize) {
        if(nums[src] == val) src++;
        else {
            nums[dst] = nums[src];
            dst++;
            src++;
        }
    }
    return dst;
}

2. 力扣：删除有序数组的重复项

核心思想 使用 双指针技巧：dst（目标指针）：记录唯一元素的存储位置。src（源指针）：遍历数组，寻找与 dst 不同的元素。 算法步骤 初始化 dst = 0（第一个元素必定唯一），src = 1。 遍历数组：如果 nums[dst] == nums[src]：跳过重复元素（src++）。 如果 nums[dst] != nums[src]：将 nums[src] 复制到 nums[++dst]，然后 src++。 最终 dst + 1 即为新数组的长度（因为索引从 0 开始）。

代码：

int removeDuplicates(int* nums, int numsSize) {
    int dst = 0, src = 1;
    while(src < numsSize) {
        if(nums[dst] == nums[src]) {
            src++;
        } else {
            nums[++dst] = nums[src++];
        }
    }
    return dst + 1;
}

3. 力扣：合并两个有序数组

核心思想 使用 逆向双指针法 从后向前合并，避免覆盖 nums1 中的未处理元素。 算法步骤 初始化指针：l1 = m - 1：指向 nums1 的最后一个有效元素。 l2 = n - 1：指向 nums2 的最后一个元素。 l3 = m + n - 1：指向 nums1 的末尾（合并后的位置）。 逆向遍历合并：比较 nums1[l1] 和 nums2[l2]，将较大的值放入 nums1[l3]，并移动对应指针。重复直到 nums1 或 nums2 遍历完毕。 处理剩余元素：如果 nums2 有剩余元素（l2 >= 0），直接复制到 nums1 的前端。

代码：

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {
    int l1 = m - 1, l2 = n - 1, l3 = m + n - 1;
    while(l1 >= 0 && l2 >= 0) {
        if(nums1[l1] > nums2[l2]) {
            nums1[l3] = nums1[l1];
            l3--;
            l1--;
        } else {
            nums1[l3] = nums2[l2];
            l2--;
            l3--;
        }
    }
    while(l2 >= 0) {
        nums1[l3] = nums2[l2];
        l2--;
        l3--;
    }
}