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

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

线性表是 n 个具有相同特性的数据元素的有限序列，逻辑上呈线性结构。常见的线性表包括顺序表、链表、栈、队列等。在物理存储上，线性表通常采用顺序结构或链式结构。

一、什么是顺序表？

定义： 顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，底层通常基于数组实现。

注意： 顺序表不等于数组。数组只是底层存储介质，顺序表是对数组的封装，提供了增删查改等接口。

二、顺序表的分类

1. 静态顺序表

使用定长数组存储元素。缺点是空间固定，可能不够用或造成浪费。

2. 动态顺序表

空间按需申请，灵活性更高。

三、动态顺序表的实现

为了模块化开发，我们通常将头文件、源文件和测试文件分开。

SeqList.h

#pragma once
#include <stdio.h>
#include <stdlib.h>

// 定义数据类型，方便后续修改
typedef int SLTDataType;

// 定义顺序表结构
typedef struct SeqList {
    SLTDataType* arr;  // 存储数据的指针
    int size;          // 有效数据个数
    int capacity;      // 当前容量
} SL;

// 初始化函数声明
void SLInit(SL* ps);

SeqList.c

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

// 初始化顺序表
void SLInit(SL* ps) {
    if (ps == NULL) return;
    ps->arr = NULL;
    ps->size = 0;
    ps->capacity = 0;
}

// 打印顺序表
void SLPrint(SL* ps) {
    if (ps == NULL || ps->arr == NULL) {
        printf("Empty List\n");
        return;
    }
    for (int i = 0; i < ps->size; i++) {
        printf("%d ", ps->arr[i]);
    }
    printf("\n");
}

// 检查容量并增容
void SLCheckCapacity(SL* ps) {
    if (ps->size == ps->capacity) {
        int newCapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
        SLTDataType* tmp = (SLTDataType*)realloc(ps->arr, newCapacity * sizeof(SLTDataType));
        if (tmp == NULL) {
            perror("realloc fail!");
            exit(1);
        }
        ps->arr = tmp;
        ps->capacity = newCapacity;
    }
}

// 尾插
void SLPushBack(SL* ps, SLTDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    ps->arr[ps->size++] = x;
}

// 头插
void SLPushFront(SL* ps, SLTDataType x) {
    assert(ps);
    SLCheckCapacity(ps);
    // 整体向后移动
    for (int i = ps->size; i > 0; i--) {
        ps->arr[i] = ps->arr[i - 1];
    }
    ps->arr[0] = x;
    ps->size++;
}

test.c（测试文件）

#define _CRT_SECURE_NO_WARNINGS
#include "SeqList.h"

void test_basic() {
    SL s1;
    SLInit(&s1);
    SLPushBack(&s1, 1);
    SLPushBack(&s1, 2);
    SLPushBack(&s1, 3);
    SLPrint(&s1);
}

void test_head_insert() {
    SL s2;
    SLInit(&s2);
    SLPushFront(&s2, 1);
    SLPushFront(&s2, 2);
    SLPushFront(&s2, 3);
    SLPrint(&s2);
}

int main() {
    test_basic();
    test_head_insert();
    return 0;
}

调试建议： 编写代码时，养成断点调试的习惯。运行到函数内部时，观察变量 size 和 capacity 的变化，能帮助你更好地理解内存分配过程。

四、关键操作解析

1. 尾插与增容

当 size 等于 capacity 时，需要扩容。通常采用 2 倍扩容策略。虽然会有一定空间浪费，但能显著减少 realloc 调用次数，摊还时间复杂度更优。

2. 头插与移位

头插需要在头部腾出位置，因此需要将现有数据整体后移。这会导致 O(N) 的时间复杂度，但在顺序表中这是不可避免的代价。

五、总结

顺序表通过连续的物理空间实现了高效的随机访问，插入和删除操作则涉及数据移动。理解其底层机制（如增容策略、传址调用）对于掌握数据结构至关重要。在实际开发中，根据数据量是否变化选择静态或动态顺序表，能有效平衡性能与资源。