C语言实现线性表顺序存储结构详解

何川

发布时间：2026-10-14| 5人浏览过

原创

线性表作为最基础的数据结构，其顺序存储在计算机内存中以连续数组形式保存。本文将深入探讨顺序表的存储原理、地址计算公式以及基于C语言的完整实现方案，包括结构体定义、动态内存管理和核心操作函数的编写。

线性表的顺序存储原理

顺序表是在计算机内存中以数组形式保存的线性表，它使用一组地址连续的存储单元依次存储数据元素。这种结构的物理特性决定了逻辑上相邻的数据元素在内存中也必须相邻。

假设线性表的每个元素占用 len 个内存单元，用 location(ki) 表示第 i 个元素所占空间的第一个单元地址，则存在以下关系：

location(k1) = location(k1) + (i-1)*len
location(ki+1) = location(ki) + len

只要确定了起始位置（基址），表中任意元素的地址均可通过上述公式快速计算得出，这正是顺序表支持随机访问的优势所在。

动态分配顺序表结构定义

为了适应不同规模的存储需求，通常采用动态分配方式。主要包含三个部分：基址指针、当前长度和当前分配的存储容量。

/* c2-1.h 线性表的动态分配顺序存储结构 */
#define LIST_INIT_SIZE 10 /* 初始分配量 */
#define LISTINCREMENT 2   /* 增量 */

typedef struct {
    ElemType *elem;        /* 存储空间基址 */
    int length;            /* 当前长度 */
    int listsize;          /* 当前分配的存储容量 */
} SqList;

其中，LISTINITSIZE 指定初始空间大小，LISTINCREMENT 指定扩容时的增量单位。这种设计允许在空间不足时自动扩展内存。

基本操作的实现细节

第一步：初始化与销毁

初始化是创建空表的基础操作。通过 malloc 分配初始内存，并重置长度和容量字段。若分配失败需处理溢出错误。销毁时则释放内存并将指针置空，防止内存泄漏。

Status InitList(SqList *L) {
    (*L).elem = (ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
    if(!(*L).elem) exit(OVERFLOW);
    (*L).length = 0;
    (*L).listsize = LIST_INIT_SIZE;
    return OK;
}

第二步：获取与查找元素

GetElem 负责根据索引 i 返回对应元素值，需验证索引合法性。而 LocateElem 则是遍历列表寻找满足特定比较关系的第一个元素位置，适用于模糊匹配或重复检测场景。

Status GetElem(SqList L, int i, ElemType *e) {
    if(i < 1 || i > L.length) exit(ERROR);
    *e = *(L.elem + i - 1);
    return OK;
}

第三步：插入与删除操作

这是顺序表操作中最复杂的两个步骤，均涉及大量数据移动。插入时，若发现 length >= listsize，需先调用 realloc 扩容。随后将从插入位置开始的后续元素整体右移一位。删除操作逻辑相反，需将目标位置后的元素左移以填补空缺。

Status ListInsert(SqList *L, int i, ElemType e) {
    // ... 合法性检查与扩容逻辑 ...
    q = (*L).elem + i - 1; // 插入位置
    for(p = (*L).elem + (*L).length - 1; p >= q; --p)
        *(p + 1) = *p;     // 元素右移
    *q = e;
    ++(*L).length;
    return OK;
}