数据结构基础：顺序表原理与动态实现详解

2.2.2 动态顺序表

定义与特点

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

// 定义顺序表存储的元素类型为 int
#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（内存分配可能失败）。
• 安全性：先将 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 头部插入及头部删除

头部操作涉及元素移动，时间复杂度为 O(n)。

/**
 * @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++;
}

/**
 * @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--;
    /* 可选：清零最后一个元素位置的值
    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;
    ps->size++;
}

/**
 * @brief 在顺序表指定位置后插入元素
 * @param ps 指向顺序表结构的指针（必须非空）
 * @param pos 参考位置索引（0 ≤ pos < ps->size）
 * @param x 要插入的元素值
 * @note 时间复杂度 O(n)，需要移动元素
 */
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;
    ps->size++;
}

/**
 * @brief 删除顺序表指定位置的元素
 * @param ps 指向顺序表结构的指针（必须非空且顺序表非空）
 * @param pos 要删除的位置索引（0 ≤ pos < ps->size）
 * @note 时间复杂度 O(n)，需要移动元素
 */
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 元素的存储位置。

算法步骤

1. 初始化 src 和 dst 为 0。
2. 遍历数组：如果 nums[src] == val，跳过该元素（src++）。
3. 如果 nums[src] != val，将其复制到 nums[dst]，然后 src++ 和 dst++。
4. 最终 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 不同的元素。

算法步骤

1. 初始化 dst = 0（第一个元素必定唯一），src = 1。
2. 遍历数组：如果 nums[dst] == nums[src]，跳过重复元素（src++）。
3. 如果 nums[dst] != nums[src]，将 nums[src] 复制到 nums[++dst]，然后 src++。
4. 最终 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 中的未处理元素。

算法步骤

1. 初始化指针：l1 = m - 1（指向 nums1 最后一个有效元素），l2 = n - 1（指向 nums2 最后一个元素），l3 = m + n - 1（指向 nums1 末尾）。
2. 逆向遍历合并：比较 nums1[l1] 和 nums2[l2]，将较大的值放入 nums1[l3]，并移动对应指针。
3. 处理剩余元素：如果 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--;
    }
}