数据结构初阶：详解线性表之顺序表 | 极客日志

C算法

数据结构初阶：详解线性表之顺序表

顺序表是线性表的顺序存储结构，底层依赖连续内存空间。本文梳理了静态与动态顺序表的区别，重点通过 C 语言完整实现了顺序表的初始化、扩容机制、头尾及指定位置的插入与删除、查找修改及销毁功能。内容涵盖指针操作细节、内存分配策略及边界条件处理，适合初学者构建扎实的数据结构基础。

王者发布于 2026/3/300 浏览

数据结构初阶：详解线性表之顺序表

线性表与顺序表概述

在深入具体实现前，先明确线性表的概念。线性表是由 n 个具有相同特性的数据元素组成的有限序列。生活中常见的线性表包括顺序表、链表、栈、队列和字符串等。从逻辑上看，线性表是连续的；但在物理存储上，它不一定连续，通常以数组或链表结构进行存储。

顺序表的概念

顺序表使用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组进行存储。简单来说，顺序表的底层就是数组。

既然底层是数组，为什么还要封装成顺序表？直接用数组不行吗？这是因为顺序表对数组进行了封装，实现了增删查改等常用功能，使得数据操作更加高效和规范。

顺序表的分类

顺序表主要分为两类：静态顺序表和动态顺序表。

静态顺序表

静态顺序表的长度相对固定，使用定长数组存储元素。其结构体定义如下：

typedef int Elemtype;
#define N 10
typedef struct Sqlist {
    Elemtype arr[N]; // 定长数组
    int length;      // 当前有效数据个数
} Sqlist;

静态顺序表开发维护成本低，但存在致命缺陷：预分配的空间 N 若过小则不够用，过大则浪费内存，无法灵活满足'按需分配'的需求。因此，实际开发中更常使用动态顺序表。

动态顺序表

动态顺序表支持内存的动态伸缩，能够根据需求调整容量。其基本结构如下：

typedef int Elemtype;
typedef struct Sqlist {
    Elemtype* data; // 指向动态分配的数组首地址
    int length;     // 当前有效元素个数
    int size;       // 当前顺序表的总容量
} Sqlist;

顺序表的实现

在开始编码之前，准备好必要的头文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h> // 用于 malloc、realloc
#include <assert.h> // 用于断言检查




  Elemtype;

void Init_Sqlist(Sqlist* pSqlist) {
    assert(pSqlist);
    // 申请初始空间
    pSqlist->data = (Elemtype*)malloc(INIT_SIZE * sizeof(Elemtype));
    if (pSqlist->data == NULL) {
        printf("空间申请失败\n");
        return;
    }
    pSqlist->length = 0;
    pSqlist->size = INIT_SIZE;
}

void Push_Front(Sqlist* pSqlist, Elemtype num) {
    assert(pSqlist);
    // 空间不足时扩容
    if (pSqlist->length >= pSqlist->size) {
        Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, 
            (pSqlist->size + INSERT_SIZE) * sizeof(Elemtype));
        if (newbase == NULL) {
            printf("新空间申请失败\n");
            return;
        }
        pSqlist->data = newbase;
        pSqlist->size += INSERT_SIZE;
    }
    // 从后向前移动元素
    for (int i = pSqlist->length - 1; i >= 0; i--) {
        pSqlist->data[i + 1] = pSqlist->data[i];
    }
    pSqlist->data[0] = num;
    pSqlist->length++;
}

void Push_Back(Sqlist* pSqlist, Elemtype num) {
    assert(pSqlist);
    if (pSqlist->length >= pSqlist->size) {
        Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, 
            (pSqlist->size + INSERT_SIZE) * sizeof(Elemtype));
        if (newbase == NULL) {
            printf("空间申请失败\n");
            return;
        }
        pSqlist->data = newbase;
        pSqlist->size += INSERT_SIZE;
    }
    pSqlist->data[pSqlist->length] = num;
    pSqlist->length++;
}

void Push_Pos(Sqlist* pSqlist, Elemtype num, int pos) {
    assert(pSqlist);
    if (pos < 0 || pos > pSqlist->length) {
        printf("pos 值不合法\n");
        return;
    }
    if (pSqlist->length >= pSqlist->size) {
        Elemtype* newbase = (Elemtype*)realloc(pSqlist->data, 
            (pSqlist->size + INSERT_SIZE) * sizeof(Elemtype));
        if (newbase == NULL) {
            printf("申请空间失败\n");
            return;
        }
        pSqlist->data = newbase;
        pSqlist->size += INSERT_SIZE;
    }
    // 从后向前移动
    for (int i = pSqlist->length - 1; i >= pos; i--) {
        pSqlist->data[i + 1] = pSqlist->data[i];
    }
    pSqlist->data[pos] = num;
    pSqlist->length++;
}

void Pop_Front(Sqlist* pSqlist) {
    assert(pSqlist);
    if (pSqlist->length == 0) return;
    // 向前移动元素，注意循环条件
    for (int i = 0; i < pSqlist->length - 1; i++) {
        pSqlist->data[i] = pSqlist->data[i + 1];
    }
    pSqlist->length--;
}

void Pop_Back(Sqlist* pSqlist) {
    assert(pSqlist);
    if (pSqlist->length > 0) {
        pSqlist->length--;
    }
}

void Pop_Pos(Sqlist* pSqlist, int pos) {
    assert(pSqlist);
    if (pos < 0 || pos >= pSqlist->length) {
        printf("pos 值不合法\n");
        return;
    }
    // 向前移动元素
    for (int i = pos; i < pSqlist->length - 1; i++) {
        pSqlist->data[i] = pSqlist->data[i + 1];
    }
    pSqlist->length--;
}

// 查找元素
void Search_Elem(Sqlist* pSqlist, Elemtype num) {
    for (int i = 0; i < pSqlist->length; i++) {
        if (pSqlist->data[i] == num) {
            printf("找到了，下标：%d\n", i);
            return;
        }
    }
    printf("找不到\n");
}

// 修改元素
void Change_Num(Sqlist* pSqlist, Elemtype num, int pos) {
    assert(pSqlist);
    if (pos < 0 || pos >= pSqlist->length) {
        printf("pos 不合法\n");
        return;
    }
    pSqlist->data[pos] = num;
    printf("修改成功\n");
}

void Print_Sqlist(Sqlist* pSqlist) {
    assert(pSqlist);
    for (int i = 0; i < pSqlist->length; i++) {
        printf("%d ", pSqlist->data[i]);
    }
    printf("\n");
}

void Destory_Sqlist(Sqlist* pSqlist) {
    assert(pSqlist);
    free(pSqlist->data);
    pSqlist->data = NULL;
    pSqlist->length = 0;
    pSqlist->size = 0;
}