数据结构：顺序表

文章目录

• • 前言
  • 一、线性表
  • 二、顺序表
  • • 2.1 概念和结构
    • • 顺序表和数组的关系：
    • 2.2 分类
    • 2.3 动态数据表的实现：
    • • 2.3.1 初始化
      • 2.3.2 增容
      • 2.3.3 尾插
      • 2.3.4 头插
      • 2.3.5 尾删
      • 2.3.6 头删
      • 2.3.7 指定位置之前插入数据
      • 2.3.8 删除pos位置的数据
      • 2.3.9 查找
      • 2.3.10 销毁
  • 三， 顺序表的问题和思考

前言

本篇我们学习顺序表相关知识。 学习顺序表之前我们要先了解一下线性表。 SeqList—顺序表—sequence list

一、线性表

逻辑结构是线性的，物理结构不一定是线性的 定义： 线性表：由n（n≥0）个同类型数据元素组成的有限有序序列

核心特征（线性结构通用特点）：

常见线性表应用： 数组、链表、栈、队列、字符串、普通集合序列等，本质都属于线性表范畴。

逻辑结构： ————描述数据元素之间的抽象逻辑关系，和内存、存储无关，只看元素间的前后 / 从属关系。

• 线性表、栈、队列、串 → 线性逻辑结构（一对一）
• 树 → 树形结构（一对多）
• 图 → 图形结构（多对多）
• 线性表，首先是逻辑层面的定义。

物理结构（存储结构）： —————描述逻辑结构如何落地到计算机内存，也就是「内存存储方式」。 一共就四类标准存储结构：

散列（哈希）存储 两大存储结构（核心分类）： 线性表根据内存存储方式（物理结构) 分为两大类：

• 顺序存储（顺序表）
• 链式存储（链表）

二、顺序表

逻辑结构是线性的，物理结构也是线性的

2.1 概念和结构

存储原理： 把线性表的元素连续存放在一块内存空间中，逻辑相邻的元素，物理内存也相邻。 类比：一排连号座位，人按顺序坐下。

底层实现： 编程语言中数组就是顺序表的典型实现。

• 地址连续、下标直接映射元素位置
• 依靠数组下标访问元素

顺序表和数组的关系：

从属 & 实现关系 顺序表唯一实现方式就是数组

• 顺序表 ≠ 单纯数组 数组只是顺序表用来存放元素的底层空间。
• 绝大多数场景：顺序表 = 数组 + 配套管理变量 + 操作函数

2.2 分类

（1）静态顺序表 数组长度固定不可变，由静态数组实现，初始化就划定最大容量，容易出现溢出。

#define MAXSIZE 100
typedef struct {
int arr[MAXSIZE]; // 静态数组（定长数组）
int size; // 有效数据个数
} SeqList;

适用：数据量已知、不会大幅变化的场景。 （2）动态顺序表 用动态数组（堆上开辟的数组）实现，支持动态扩容

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

// 元素类型，可按需修改
typedef int ElemType;
// 初始容量
#define INIT_CAPACITY 4
// 扩容倍数
#define EXPAND_RATIO 2

// 动态顺序表结构
typedef struct {
ElemType* data; // 指向动态数组（堆内存）
int size; // 当前元素个数
int capacity; // 当前最大容量
} SeqList;

基于动态内存（堆区）实现，可动态扩容，现代程序主流用法。

• 取别名是为了一键修改顺序表中数据的类型

2.3 动态数据表的实现：

我们创建三个文件来实现：

2.3.1 初始化

这里使用：传址调用 只要看不到取地址操作符，就是传值调用 在SeqList.h 文件中：

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

//定义动态顺序表的结构
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* arr;
int size; //有效数据个数
int capacity; //空间容量
}SL;//给顺序表取别名

//typedef struct SeqList SL; 第二种取别名方法

//初始化
void SLInit(SL* ps);

在SeqList.c中：

#include"SeqList.h"

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

在 test.c 文件中

#include"SeqList.h"

void test01()
{
SL sl;
SLInit(&sl);
}

int main()
{
test01();
return 0;
}

这里我们需要使用传址调用：

如果使用传值调用： 修改不到原变量

2.3.2 增容

所有插入操作前都要判断是否满容 所以我们先学习如何增容

typedef struct {
ElemType* arr;
int size; // 当前有效元素个数
int capacity; // 当前最大容量
} SeqList;

条件： 当 size == capacity 触发扩容 代表空间已满，再插入元素就会越界，必须开辟更大内存。

//判断空间是否足够
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//增容
//realloc第二个参数，单位是字节
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity*sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}

执行扩容：

• 原内存后方有连续空闲空间→ 原地向后拓展，指针地址不变，无需拷贝数据（效率高）
• 原内存后方无足够连续空间→ 系统重新找一块更大的连续堆内存，自动把旧数据拷贝过去，再自动 free 旧内存，返回新地址

• 内存分配可能失败（系统内存不足），必须判空
• 不能直接写 ps->arr = realloc(…)：一旦分配失败返回 NULL，会把原数据指针直接置空 → 内存泄漏 + 数据丢失
• 所以先用临时指针 tmp 接收结果，校验成功再赋值给 ps->arr

• 如果原内存后面有空：tmp == ps->arr（地址一样），只是容量变大，原地追加。
• 如果原后面没空：tmp 是全新地址，旧内存被自动释放，换到新空间。

如果每次只增加一个空间，会存在频繁扩容的问题：

所以我们要根据业务预估数据量，从源头减少扩容次数。

2.3.3 尾插

时间复杂度为O(1)

//尾插
void SLPushBack(SL* ps, SLDataType x)
{
//判断空间是否足够
if (ps->size == ps->capacity)
{
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
//增容
//realloc第二个参数，单位是字节
SLDataType* tmp = (SLDataType*)realloc(ps->arr, newCapacity*sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail!");
exit(1);
}
ps->arr = tmp;
ps->capacity = newCapacity;
}
//空间足够的情况下
ps->arr[ps->size++] = x;
}

2.3.4 头插

时间复杂度为O(n)

// 头插函数
void SLPushFront(SL* ps, SLDataType x)
{
//温柔的处理方式
//if (ps == NULL)
//{
//return;
//}
// 断言：防止传入空指针，比if判断更适合调试
assert(ps != NULL);

// 检查容量，不够则扩容
SLCheckCapacity(ps);

// 元素整体后移：从最后一位开始挪，避免数据覆盖
for (int i = ps->size; i > 0; i—)
{
ps->arr[i] = ps->arr[i – 1];
}

// 头部放入新元素
ps->arr[0] = x;
++ps->size;
}

逻辑：

2.3.5 尾删

时间复杂度为O(1)

//尾删
void SLPopBack(SL* ps)
{
//ps：限制参数不能直接给NULL
//ps->size：顺序表为空
assert(ps && ps->size);
—ps->size;
}

void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\\n");
}

断言 assert(ps && ps->size)

• ps：防止传入空指针；
• ps->size：防止对空顺序表执行尾删（空表无元素可删）；
• 调试模式下触发断言直接报错，定位问题。

尾删核心逻辑

• 动态顺序表尾删不需要移动元素，只需把有效元素个数 size 减 1。
• 原数组末尾数据仍存在内存中，但遍历 / 访问只会读到 size 范围内元素，等价于删除。

2.3.6 头删

时间复杂度为O(n)

//头删
void SLPopFront(SL* ps)
{
assert(ps && ps->size);

// 从前往后，后一个元素覆盖前一个，整体左移一位
for (int i = 0; i < ps->size–1; i++)
{
ps->arr[i] = ps->arr[i + 1];
}

// 有效元素个数减一
—ps->size;
}

循环逻辑说明：

• 有效下标范围：0 ~ size-1
• 删除头部元素，需要把 [1, size-1] 所有元素整体左移一位
• 循环条件 i < ps->size – 1：刚好遍历到倒数第二个元素，用 i+1 取最后一个元素，不会越界。

移动方向： 必须从前向后移动，和头插的移动方向相反。

2.3.7 指定位置之前插入数据

时间复杂度为O(n)

//指定位置pos之前插⼊数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
// 校验顺序表指针合法
assert(ps);
// 限制插入位置范围：0 ≤ pos ≤ size
// pos=0 等价头插，pos=size 等价尾插
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;
}

核心关键点

• pos >= 0 && pos <= ps->size 是标准合法区间：
• pos = 0：在表头插入（等价 SLPushFront）
• pos = size：在表尾插入（等价尾插） 中间值：在对应下标前插入

• 必须从后往前挪，和头插逻辑一致，避免数据被覆盖。
• 循环 i = size; i > pos：刚好把 pos 及后面所有元素后移一格，腾出 pos 位置。

• 最好在表尾插入，不需要移动元素，时间复杂度为O(1),最坏在表头插入，需移动全部元素，复杂度 O(n),平均复杂度为O(n).

2.3.8 删除pos位置的数据

时间复杂度为O(n)

// 删除POS位置的数据
void SLErase(SL* ps, int pos)
{
// 校验顺序表指针有效
assert(ps);
// 合法位置：0 ≤ pos < size，不能删不存在的下标
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;
}

核心要点

• pos = 0：等价头删
• pos = size-1：等价尾删

2.3.9 查找

遍历数组

//查找
int SLFind(SL* ps, SLDataType x)
{
for (int i = 0; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
//找到了
return i;
}
}
//未找到
return –1;
}

2.3.10 销毁

//销毁
void SLDestroy(SL* ps)
{
assert(ps); // 校验顺序表结构体指针不为空
if (ps->arr) // 避免对空指针 free（安全冗余判断）
free(ps->arr);
ps->arr = NULL; // 置空野指针
ps->size = ps->capacity = 0; // 清空有效数据与容量
}

关键点说明

三， 顺序表的问题和思考

一、问题回顾与解读

二、核心问题的解决方案

1. 如何解决「中间 / 头部插入删除效率低」的问题？ 根本方案：改用链式存储结构，即链表。

• 链表的元素不要求物理连续，插入 / 删除操作只需要修改相邻结点的指针，无需移动数据，时间复杂度为 O (1)（前提是已经找到目标结点）。
• 但链表也有短板：不支持随机访问，按下标查找需要从头遍历，时间复杂度为 O (N)。 折中优化（顺序表内部）：
• 如果业务场景能接受，尽量把操作集中在尾部（比如用栈、队列），这样可以规避中间 / 头部操作的 O (N) 开销。
• 或者使用无锁数组、分段数组等更复杂的结构，但实现成本较高。

2. 如何缓解「扩容开销大」的问题？

• 预分配（预估初始容量） 提前根据业务预估数据量，给顺序表设置一个合理的初始容量，避免频繁触发扩容。 例如：已知数据量不会超过 1000，就直接设置 INIT_CAPACITY = 1024。
• 优化扩容策略 降低扩容倍数：比如从 2 倍改为 1.5 倍，减少单次扩容的拷贝数据量。 固定增量扩容：每次只增加固定大小（如 100），适合数据量波动小的场景，避免一次性拷贝过多数据。
• 延迟释放旧空间 扩容时不立即释放旧空间，而是缓存起来，等下次扩容或销毁时再统一释放，减少系统调用次数。

3. 如何解决「空间浪费」的问题？

• 缩容（Shrink to fit）机制 当元素数量远小于容量时，主动缩小容量，释放闲置空间。 典型触发条件：当 size < capacity / 4 时，将容量缩小为原来的 1/2。 注意：缩容不能太频繁，否则会导致反复扩容 – 缩容的性能抖动。
• 调整扩容倍数 改用更小的扩容倍数（如 1.5 倍），减少单次扩容后闲置空间的比例。 例如：容量 100 扩容到 150，再插入 5 个元素，仅浪费 45 个单元，比 2 倍扩容的浪费少很多。
• 业务侧主动释放 提供接口让用户在数据写入完成后主动调用 shrink_to_fit() 函数，手动释放多余空间，如 C++ 的 vector::shrink_to_fit()。