一、核心概念：什么是顺序表？

想象一下电影院里的一排座位，每个座位都有一个连续的编号（1号、2号、3号……）。如果你有 5 号座位的票，你可以立即找到它，因为你知道它就在 4 号之后，6 号之前。

顺序表 (Sequential List) 就是这样的结构。它是指在内存中用一块地址连续的空间来存储数据的线性表。

它有两个关键特征：

• 地址连续：所有元素都紧挨着存放，就像排好的座位。

• 随机访问：因为地址连续，只要知道第一个元素的位置和想访问元素的“编号”（索引），就可以通过简单的数学计算（基地址 + 索引 * 单个元素大小）立即定位到任何一个元素。这使得查找特定位置的元素非常快。

在 C 语言中，最能体现这个概念的就是数组。

二、静态顺序表：用数组直接实现

这是最基本的形式，在程序编译时就确定了大小，之后不能再改变。

1、示例：管理一个班级的学生成绩

假设我们要记录一个最多容纳 50 名学生的班级的成绩。

#include <stdio.h>

#define MAX_SIZE 50 // 定义顺序表的最大容量

int main() {
    // 1. 定义一个静态顺序表（数组）来存储成绩
    int scores[MAX_SIZE]; 
    
    // 2. `length` 变量记录当前实际存储了多少个元素
    int length = 0;

    // --- 插入操作 ---
    // 假设我们录入5个学生的成绩
    printf("--- 插入数据 ---\n");
    scores[0] = 88;
    scores[1] = 92;
    scores[2] = 76;
    scores[3] = 95;
    scores[4] = 85;
    length = 5; // 更新当前长度
    printf("成功录入5名学生的成绩。\n\n");

    // --- 遍历（访问）操作 ---
    printf("--- 遍历数据 ---\n");
    printf("当前班级所有成绩如下：\n");
    for (int i = 0; i < length; i++) {
        printf("学生 %d: %d 分\n", i + 1, scores[i]);
    }
    printf("\n");

    // --- 在指定位置插入一个新成绩 ---
    // 比如，想在第3个位置（索引为2）插入一个新成绩 80
    printf("--- 在指定位置插入数据 ---\n");
    int new_score = 80;
    int insert_position = 2; // 索引为2的位置

    // 为了腾出位置，需要将从 `insert_position` 开始的所有元素向后移动一位
    for (int i = length - 1; i >= insert_position; i--) {
        scores[i + 1] = scores[i];
    }
    scores[insert_position] = new_score; // 放入新元素
    length++; // 长度加1
    printf("在第 %d 个位置插入新成绩 80 分成功。\n\n", insert_position + 1);

    // 再次遍历查看结果
    printf("--- 插入后遍历 ---\n");
    for (int i = 0; i < length; i++) {
        printf("学生 %d: %d 分\n", i + 1, scores[i]);
    }
    printf("\n");

    // --- 删除一个元素 ---
    // 比如，删除第4个位置（索引为3）的成绩
    printf("--- 删除数据 ---\n");
    int delete_position = 3; // 索引为3的位置

    // 从被删除元素的下一个位置开始，所有元素向前移动一位
    for (int i = delete_position; i < length - 1; i++) {
        scores[i] = scores[i + 1];
    }
    length--; // 长度减1
    printf("删除第 %d 个位置的成绩成功。\n\n", delete_position + 1);

    // 再次遍历查看结果
    printf("--- 删除后遍历 ---\n");
    for (int i = 0; i < length; i++) {
        printf("学生 %d: %d 分\n", i + 1, scores[i]);
    }
    printf("\n");

    return 0;
}

静态顺序表的缺点：

• 容量固定：如果班级来了第 51 个学生怎么办？程序就出错了（数组越界）。

• 空间浪费：如果班级只有 5 个学生，我们却分配了 50 个位置，剩下的 45 个位置就浪费了。

为了解决这个问题，我们引入了更强大的动态顺序表。

三、动态顺序表：更灵活的实现

动态顺序表在程序运行时才分配内存，并且当空间不足时可以动态扩容。这通常通过 C 语言的 malloc, realloc 和 free 函数，结合 struct（结构体）来实现。

示例：用结构体封装一个动态顺序表

我们将创建一个结构体来表示我们的顺序表，它包含三个核心部分：

• 一个指向数据存储区的指针 (data)。

• 记录当前元素数量的大小 (size)。

• 记录当前已分配空间总容量的容量 (capacity)。

#include <stdio.h>
#include <stdlib.h> // 需要用到 malloc, realloc, free

// 1. 定义动态顺序表的结构体
typedef struct {
    int* data;      // 指向动态分配的内存
    int size;       // 当前存储的元素个数
    int capacity;   // 当前的总容量
} SeqList;

// 2. 初始化一个顺序表
SeqList* createList(int initialCapacity) {
    SeqList* list = (SeqList*)malloc(sizeof(SeqList));
    if (!list) return NULL; // 内存分配失败
    
    list->data = (int*)malloc(sizeof(int) * initialCapacity);
    if (!list->data) {
        free(list);
        return NULL; // 内存分配失败
    }
    
    list->size = 0;
    list->capacity = initialCapacity;
    printf("顺序表创建成功，初始容量为 %d。\n", initialCapacity);
    return list;
}

// 3. 在末尾添加元素（带自动扩容）
void add(SeqList* list, int value) {
    // 检查是否需要扩容
    if (list->size == list->capacity) {
        int newCapacity = list->capacity * 2; // 容量翻倍
        int* newData = (int*)realloc(list->data, sizeof(int) * newCapacity);
        if (!newData) {
            printf("错误：扩容失败！\n");
            return;
        }
        list->data = newData;
        list->capacity = newCapacity;
        printf("空间不足，已自动扩容至 %d。\n", newCapacity);
    }
    
    // 在末尾添加元素
    //list->data[list->size] 等价于 *(list->data + list->size)
    list->data[list->size] = value;
    list->size++;
}

// 4. 打印顺序表的所有元素
void printList(SeqList* list) {
    printf("当前列表内容 (大小: %d, 容量: %d): [ ", list->size, list->capacity);
    for (int i = 0; i < list->size; i++) {
        printf("%d ", list->data[i]);
    }
    printf("]\n");
}

// 5. 销毁顺序表，释放内存
void destroyList(SeqList* list) {
    if (list) {
        free(list->data); // 先释放数据区
        free(list);       // 再释放结构体本身
        printf("顺序表已销毁，内存已释放。\n");
    }
}


// --- 主函数：使用我们的动态顺序表 ---
int main() {
    // 创建一个初始容量为 4 的顺序表
    SeqList* myList = createList(4);

    // 添加一些元素
    printf("\n--- 添加元素 ---\n");
    add(myList, 10);
    printList(myList);
    add(myList, 20);
    printList(myList);
    add(myList, 30);
    printList(myList);
    add(myList, 40);
    printList(myList);

    // 此时 size == capacity，再添加一个元素将触发自动扩容
    printf("\n--- 测试自动扩容 ---\n");
    add(myList, 50);
    printList(myList);
    
    // 销毁列表，防止内存泄漏
    destroyList(myList);

    return 0;
}

这个动态版本的代码更加健壮和实用。它封装了操作细节，实现了自动扩容，是实际开发中更常用的方式。