嵌入式 - 数据结构与算法：（1-1）数据结构 - 顺序表（Sequential List）

线性表包括：顺序表、链表

顺序表（Sequential List）

顺序表的本质就是一个可以动态增长的数组。

存储方式是：连续内存（底层是数组），元素紧挨着存放，支持随机访问。

在 C 中，数组一旦定义，大小通常是固定的。但实际使用中，我们不知道要存多少个元素，所以需要动态分配内存，并在不够用时扩容。

这就引出了顺序表的设计目标：模拟一个“长度可变”的数组，同时记录当前用了多少空间、总共能用多少空间。

1）核心结构

我们需要三个信息：① 指向数据的指针（代替固定数组）、② 当前有多少个有效元素（比如插入了 5 个数）、③ 当前最多能存多少个元素（避免越界）。

那么结构体就是一个很好的容器，例如：

/* 定义顺序表 */typedefstruct{int*data;// 指向一块连续内存的首地址（相当于动态数组）intlength;// 当前已经存了多少个元素（从 0 开始计数），后续如果要遍历顺序表的话，是遍历此变量，这个变量很重要！！！！！intcapacity;// 这块内存总共能存多少个元素}SeqList;

一个顺序表的完整内存空间应包含 数据区+其他变量 。

2）关键操作（封装成函数）

2.1）初始化

• 用malloc申请一块初始内存（比如能存 10 个整数）
• 设置length = 0（还没放任何数据）
• capacity = 10

例如：

/* 初始化顺序表 */boolInitSeqList(SeqList*list){list->data=(int*)malloc(INIT_CAPACITY*sizeof(int));if(!list->data)returnfalse;list->length=0;list->capacity=INIT_CAPACITY;returntrue;}

2.2）插入元素（重点理解）

顺序表插入新元素只能在当前已有/有效元素的末尾之后、或已有元素之间的合法位置插入，不能乱插的原因在下面第三小点阐述。

① 在尾部插入元素

尾部插入其实就是“在length位置插入”，所以尾部就是index = length。

例如：

/* 尾部插入元素 elem（独立实现） */boolPushBack(SeqList*list,intelem){// 如果满了，先扩容if(list->length>=list->capacity){if(!Resize(list)){printf("Error: Failed to resize in PushBack!\n");returnfalse;}}// 直接放到末尾list->data[list->length]=elem;list->length++;returntrue;}

如果想简化代码的，可以使用Insert函数：

// 尾部插入元素 elemboolPushBack(SeqList*list,intelem){returnInsert(list,list->length,elem);}

② 在第 i 个位置插入，可以是表首

• 先检查i是否合法（0 ≤ i ≤ length）
• 如果length == capacity，说明满了，需要用realloc扩容（比如增加 5 个空间）
• 把从第i位开始的所有元素往后挪一位
• 把新元素放进第i位
• length++
• ⚠️ 注意：因为内存是连续的，插入中间必须“腾地方”，所以效率低。

例如：

/* 在 index 位置插入元素 elem */boolInsert(SeqList*list,intindex,intelem){if(index<0||index>list->length){printf("Error: Insert index out of range!\n");returnfalse;}// 如果满了，扩容if(list->length>=list->capacity){if(!Resize(list)){printf("Error: Failed to resize!\n");returnfalse;}}// 后移元素, 这里 --i和i--等同，后续也是for(inti=list->length;i>index;--i){list->data[i]=list->data[i-1];}list->data[index]=elem;list->length++;returntrue;}

③ 为什么不能在最大容量内的任意地址插入？

首先在技术上，是能直接在最大容量内的任意地址写入的，内存是我们自己申请的，可以随便在哪读写。

根本原因是：

由于顺序表在定义的时候，就定义length表示有效数据个数，一旦你绕过length直接写入非连续位置，就破坏了顺序表“逻辑连续”的契约，导致所有基于length的操作（遍历、查找、插入、删除）都无法正确感知或管理你写入的数据，从而造成逻辑混乱或数据丢失。

展开来说就是：

顺序表在研究出来的时候，就规定了一个顺序表的结构体包含三个信息：① 指向一篇连续内存（存放数据）的指针、② 当前有多少个有效元素length、③ 当前最多能存多少个元素（申请的内存大小限制），它的很多操作都是基于length的。它对外承诺的行为包括：

1. 元素是连续存储的（逻辑上）
2. 长度 = 有效元素个数
3. 遍历时只遍历前length个元素
4. 插入/删除保持连续性

一旦跳过length随意插入，那么：

• 后果 1：遍历会漏掉你的数据
• 后果 2：后续插入会覆盖或错乱
• 后果 3：查找、删除等操作全部失效

你可以在申请的内存中的任意地址插入数据，只要你记得，但是这样的话，你就要始终记得那个位置有数据，并且要承担因为后续插入数据引起的数据移动、数据存储混乱问题。而且违背了顺序表设计的初衷。后面想解决这个问题，就可以使用链表。

2.3）删除元素

• 检查位置是否合法
• 记下要删的值
• 把它后面的所有有效元素往前挪一位
• length--
• ⚠️ 注意：所有元素往前挪一位的本质是覆盖前一位，全部移完之后，原来的最后一位并没有数据覆盖，但一般都不管，length-1之后，那位数据就已经不包含在有效数据之内的，下次插入数据会被覆盖掉。

例如：

/* 删除 index 位置的元素，并通过 *elem 返回被删元素 */boolDelete(SeqList*list,intindex,int*elem){if(index<0||index>=list->length){printf("Error: Delete index out of range!\n");returnfalse;}*elem=list->data[index];// 前移元素for(inti=index;i<list->length-1;++i){list->data[i]=list->data[i+1];}list->length--;returntrue;}

2.4）随机访问

• 直接list.data[i]就能拿到第 i 个元素（O(1) 时间）

2.5）遍历/打印顺序表

顺序表的有效数据长度为length，所有只需要遍历前length个元素即可。

例如：

/* 打印顺序表 */voidPrintSeqList(constSeqList*list){printf("SeqList: [");for(inti=0;i<list->length;++i){printf("%d",list->data[i]);if(i<list->length-1)printf(", ");}printf("] (length=%d, capacity=%d)\n",list->length,list->capacity);}

2.6）查找（某个元素第一次出现的位置）

/* 查找 elem 第一次出现的位置，未找到返回 -1 */intFind(constSeqList*list,intelem){for(inti=0;i<list->length;++i){if(list->data[i]==elem){returni;// return i+1 也行，看用途}}return-1;}

3）完整代码示例

C 语言手撕顺序表完整代码（初始化、销毁、插入元素、删除元素等操作）：

#include<stdio.h>#include<stdlib.h>#include<stdbool.h>#defineINIT_CAPACITY10// 初始容量#defineINCREMENT5// 扩容增量// 顺序表结构体typedefstruct{int*data;// 指向数据区的指针intlength;// 当前元素个数intcapacity;// 当前最大容量}SeqList;// 初始化顺序表boolInitSeqList(SeqList*list){list->data=(int*)malloc(INIT_CAPACITY*sizeof(int));if(!list->data)returnfalse;list->length=0;list->capacity=INIT_CAPACITY;returntrue;}// 销毁顺序表voidDestroySeqList(SeqList*list){free(list->data);list->data=NULL;list->length=0;list->capacity=0;}// 打印顺序表voidPrintSeqList(constSeqList*list){printf("SeqList: [");for(inti=0;i<list->length;++i){printf("%d",list->data[i]);if(i<list->length-1)printf(", ");}printf("] (length=%d, capacity=%d)\n",list->length,list->capacity);}// 获取当前长度intGetLength(constSeqList*list){returnlist->length;}// 扩容函数（内部使用）staticboolResize(SeqList*list){intnew_capacity=list->capacity+INCREMENT;int*new_data=(int*)realloc(list->data,new_capacity*sizeof(int));if(!new_data)returnfalse;list->data=new_data;list->capacity=new_capacity;returntrue;}// 在 index 位置插入元素 elemboolInsert(SeqList*list,intindex,intelem){if(index<0||index>list->length){printf("Error: Insert index out of range!\n");returnfalse;}// 如果满了，扩容if(list->length>=list->capacity){if(!Resize(list)){printf("Error: Failed to resize!\n");returnfalse;}}// 后移元素for(inti=list->length;i>index;--i){list->data[i]=list->data[i-1];}list->data[index]=elem;list->length++;returntrue;}// 删除 index 位置的元素，并通过 *elem 返回被删元素boolDelete(SeqList*list,intindex,int*elem){if(index<0||index>=list->length){printf("Error: Delete index out of range!\n");returnfalse;}*elem=list->data[index];// 前移元素for(inti=index;i<list->length-1;++i){list->data[i]=list->data[i+1];}list->length--;returntrue;}// 查找 elem 第一次出现的位置，未找到返回 -1intFind(constSeqList*list,intelem){for(inti=0;i<list->length;++i){if(list->data[i]==elem){returni;}}return-1;}// 获取 index 位置的元素，通过 *elem 返回boolGetElem(constSeqList*list,intindex,int*elem){if(index<0||index>=list->length){returnfalse;}*elem=list->data[index];returntrue;}// 测试主函数intmain(){SeqList list;/* SeqList *list = (SeqList*) malloc (sizeof (SeqList)); // 也可以用动态内存分配方法定义这个顺序表结构体 */if(!InitSeqList(&list)){printf("Failed to initialize list!\n");return-1;}// 插入测试Insert(&list,0,10);Insert(&list,1,20);Insert(&list,1,15);// 插入到中间PrintSeqList(&list);// [10, 15, 20]// 查找intpos=Find(&list,15);printf("Find 15 at index: %d\n",pos);// 删除intdeleted;if(Delete(&list,1,&deleted)){printf("Deleted element: %d\n",deleted);PrintSeqList(&list);// [10, 20]}// 获取元素intval;if(GetElem(&list,1,&val)){printf("Element at index 1: %d\n",val);}DestroySeqList(&list);return0;}

运行结果如下：

SeqList:[10,15,20](length=3,capacity=10)Find15at index:1Deleted element:15SeqList:[10,20](length=2,capacity=10)Element at index1:20