关键词：
线性表
线性表是n个具有相同特性的数据元素的有限序列。线性表是一种在现实中应用广泛的数据结构，常见的线性表有顺序表，链表，栈，队列，字符串等。
线性表元素具有相同的特性：唯一的开始结点和终端结点，唯一的前驱和后继。线性表在逻辑上是线性结构，可以想象成一条直线。但在物理上不一定是连续的，线性表的物理存储通常以数组和链式结果的形式存储。如图：
1 顺序表
1.1 顺序表的定义及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，即数组的形式存储。顺序表必须从头向后依次存储，在数组上完成数据的增删查改的操作，当然顺序表一般分为动态顺序表和静态顺序表。
顺序表结构体定义
//1. 静态顺序表
#define NUM 1000//元素容量
typedef int SLDataType;//顺序表元素类型
typedef struct SeqList
SLDataType data[NUM];//顺序表数组
int size;//元素个数
SL;//顺序表结构体名
//2. 动态顺序表
typedef int SLDataType;
typedef struct SeqList
SLDataType* data;//元素数组
int size;
int capacity;
SL;
- 结构体的用途就是描述一个复杂对象。存放数据的数组和记录元素个数和容量的变量都是为了描述顺序表这一个整体对象的不可缺少的成员变量，所以将其都放在一个名为顺序表的结构体中。
- 静态顺序表定义相对简单，但元素容量固定，变量
size用于记录有效数组元素个数。动态顺序表使用动态开辟数组，故增加一个变量capacity用于记录数组容量。 - 使用
#define定义元素容量，对结构体类型和元素类型的重命名，同样也是方便后期更改，达到“一改俱改”的效果。
1.2 动态顺序表的接口实现
静态顺序表是定长数组，只适用于数据存量确定的场景。而动顺序表是动态开辟的数组，可以灵活的增容，所以现实中基本上都是用动态顺序表。下列是基本的增删查改操作的接口函数。
//顺序表初始化
void SeqListInit(SeqList* psl, size_t capacity);
//检查空间
void CheckCapacity(SeqList* psl);
//顺序表尾插
void SeqListPushBack(SeqList* psl, SLDataType x);
//顺序表尾删
void SeqListPopBack(SeqList* psl);
//顺序表头插
void SeqListPushFront(SeqList* psl, SLDataType x);
//顺序表头删
void SeqListPopFront(SeqList* psl);
//顺序表查找
int SeqListFind(SeqList* psl, SLDataType x);
//顺序表任意位置插入
void SeqListInsert(SeqList* psl, size_t pos, SLDataType x);
//顺序表任意位置删除
void SeqListErase(SeqList* psl, size_t pos);
//顺序表销毁
void SeqListDestory(SeqList* psl);
//顺序表打印
void SeqListPrint(SeqList* psl);
顺序表尾插尾删
尾插有三种情况：顺序表没有空间或空间已满需扩容，空间未满直接插入。
尾删也要考虑到有效元素个数为0的情况。
void SeqListPushBack(SL* ps, SLDataType x)
CheckCapacity(ps);
ps->data[ps->size] = x;
ps->size++;
void SeqListPopBack(SL* ps)
assert(ps->size > 0)
ps->size--;
考虑到特殊情况后，尾插尾删就很简单了。
顺序表头插头删
void SeqListPushFront(SL* ps, SLDataType x)
CheckCapacity(ps);
int end = ps->size - 1;
//移动数据
while (end >= 0)
ps->data[end + 1] = ps->data[end];
end--;
//插入
ps->data[0] = x;
ps->size++;
void SeqListPopFront(SL* ps)
assert(ps->size > 0);
int begin = 1;
//移动数据并覆盖
while (begin < ps->size)
ps->data[begin - 1] = ps->data[begin];
begin++;
ps->size--;
头插首先将整体也就是下标从0到size-1的元素后移一个位置。为防止内容覆盖，则必须从后向前移，方法是定义“尾指针”，每次减一从后向前遍历，最后增加一个元素即可。
头删则是将下标为1到size-1的元素前移一个位置，定义“头指针”指向第二个元素从前向后遍历，正好将第一个元素覆盖。
任意位置插入删除
void SeqListInsert(SL* ps, int pos, SLDataType x)
assert(pos >= 0 && pos <= ps->size);
CheckCapacity(ps);
int end = ps->size - 1;
while (end >= pos)
ps->data[end + 1] = ps->data[end];
end--;
ps->data[pos] = x;
ps->size++;
void SeqListErase(SL* ps, int pos)
assert(pos >= 0 && pos < ps->size && ps->size > 0);
int begin = pos + 1;
while (begin < ps->size)
ps->data[begin - 1] = ps->data[begin];
begin++;
ps->size--;
指定位置的插入和删除其实就是分别把头插头删的最终位置和起始位置换成指定下标pos。当然头插头删也可以用指定位置插入删除的方法实现。
其他基本接口
void SeqListInit(SL* ps)
ps->data = NULL;
ps->size = 0;
ps->capacity = 0;
void SeqListDestroy(SL* ps)
free(ps->data);
ps->data = NULL;
ps->size = 0;
ps->capacity = 0;
结构体成员数组使用的是动态开辟的空间所以记得初始化和销毁内存。因为代码执行过程中越界编译器可能不会即使检测出来，销毁内存同时还有帮助检测数组越界的功能。
void CheckCapacity(SL* ps)
if (ps->size == ps->capacity)
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* ptr = (SLDataType*)realloc(ps->data, newcapacity * sizeof(SLDataType));
if (ptr == NULL)
perror("mallocfail");
exit(-1);
ps->data = ptr;
ps->capacity = newcapacity;
不管是尾插，头插还是任意位置插入都要考虑需扩容的情况。同样，不管是尾删，头删还是任意位置删除都要考虑有效元素个数为0的情况。故可将检测顺序表容量的代码封装成函数，以便调用。
动态开辟内存是有内存消耗的，异地扩复制内容也会增加时间消耗，所以尽量每次开辟大一点以减少开辟次数。
realloc开辟内存分为“原地扩”和“异地扩”，如果原空间后面有足够大的空间就原地扩，反之则重新开辟一段空间将原空间的内容复制过去并释放原空间返回新空间地址，称为异地扩。
int SeqListFind(SL* ps, SLDataType x)
for (int i = 0; i < ps->size; i++)
if (ps->data[i] == x)
return i;
return -1;
void SeqListPrint(SL* ps)
for (int i = 0; i < ps->size; i++)
printf("%d ", ps->data[i]);
printf("\\n");
1.3 数组面试题
竞赛面试普遍采用OJ(Online Judge)的方式，OJ题型分为IO型和接口型。
- IO型，就是输入输出函数都由被试者实现，系统进行输入输出操作，并检查程序结果是否实现。
- 接口型，被试者仅需利用系统提供的接口写出功能函数，由系统自主调用，检查测试用例是否正确。
Example 1 移除元素
移除数组 nums中所有数值等于 val 的元素，并返回移除后数组的新长度。
思路 1
时间复杂度为 O ( N 2 ) O(N^2) O(N2)，空间复杂度为 O ( 1 ) O(1) O(1)
int removeElement(int* nums, int numsSize, int val)
int number = numsSize;
int* pnums = nums;
while (pnums < nums + number)
if (*pnums == val)
int begin = pnums - nums;
//begin是该元素的下标，numsSize-begin是该元素之后的元素个数
while (begin < numsSize - 1)
nums[begin] = nums[begin + 1];
begin++;
number--;
else
pnums++;
return number;
思路 2
时间复杂度为 O ( N ) O(N) O(N)，空间复杂度为 O ( N ) O(N) O(N)
int removeElement(int* nums, int numsSize, int val)
int tmp[200] = 0 ;
int j = 0;
//转移不是val的元素
for (int i = 0; i < numsSize; i++)
if(nums[i] != val)
tmp[j] = nums[i];
j++;
//赋值给nums
for(int i = 0; i < j; i++)
nums[i] = tmp[i];
return j;
思路 3
快慢指针，通过指针分别指向。可以用指针也可以用下标的方式。
时间复杂度为 O ( N ) O(N) O(N)，空间复杂度为 O ( 1 ) O(1) O(1)
int removeElement(int* nums, int numsSize, int val)
int* src = nums;
int* dst = nums;
//1. 指针版
while (src - nums < numsSize)
if (*src != val)
*dst = *src;
dst++;
src++;
//是与不是，src都要++；只有赋值后dst才++
return dst - nums;
//2. 下标版
int src = 0, dst = 0;
while(src < numsSize)
if(nums[src] != val)
nums[dst] = nums[src];
dst++;
src++;
return dst;
Example 2 数组去重
删除有序数组 nums 中重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。
找到一段相同数字的区间，只留一个。
int removeDuplicates(int* nums, int numsSize)
int begin = 0, end = 1;
int dst = 1;
if(numsSize == 0)
return 0;
while (end < numsSize)
if(nums[begin] == nums[end])
end++;
else
begin = end;
nums[dst] = nums[begin];
end++;
dst++;
return dst;
Example 3 合并数组
两个按非递减顺序排列的整数数组nums1和nums2，合并nums2到nums1中，使合并后的数组同样按非递减顺序排列。
思路 1
开辟新数组，将两数组的元素相比取其小值放入新数组中。
时间复杂度为 O ( M + N ) O(M+N) O(M+N)，空间复杂度为 O ( M + N ) O(M+N) O(M+N)
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
int i = 0, j = 0, dst = 0;
int nums3[200] = 0 ;
while (i < m && j < n)
if (nums1[i] <= nums2[j])
nums3[dst] = nums1[i];
dst++, i++;
else
nums3[dst] = nums2[j];
dst++, j++;
//剩余元素
while (i < m)
nums3[dst] = nums1[i];
dst++, i++;
while (j < n)
nums3[dst] = nums2[j];
dst++, j++;
for(int i = 0; i < m + n; i++)
nums1[i] = nums3[i];
思路 2
无需开辟新数组，从大到小比较和移动元素。
时间复杂度为 O ( m i n m , n ) O(min\\lbrace m,n \\rbrace) O(minm,n)，空间复杂度为 O ( 1 ) O(1) O(1)
void merge(int* nums1, int nums1Size, int m,
int* nums2, int nums2Size, int n)
int i = m - 1, j = n - 1;
int dst = m + n - 1;
while (i >= 0 && j >= 0)
if (nums2[j] >= nums1[i])
nums1[dst] = nums2[j];
dst--, j--;
else
nums1[dst] = nums1[i];
dst--, i--;
while (j >= 0)
nums1初阶数据结构——线性表——链表——带头双向循环链表(代码片段)
🎉🎉想快速入门数据结构，推荐订阅作者的初阶数据结构专栏！此专栏预计更新：顺序表，链表，栈，队列，二叉树，排序算法等等🎉🎉初阶数据结构我们通过c语言实现，所... 查看详情
初阶数据结构——线性表——链表——不带头单向链表(代码片段)
🎉🎉想快速入门数据结构，推荐订阅作者的初阶数据结构专栏！此专栏预计更新：顺序表，链表，栈，队列，二叉树，排序算法等等🎉🎉初阶数据结构我们通过c语言实现，所... 查看详情
初阶数据结构二c语言实现顺序表(代码片段)
从本篇开始，我们进入数据结构的真正重点内容，话不多说，我们开始吧！文章目录一、线性表二、顺序表1、概念及结构2、顺序表接口的实现2.1顺序表的创建2.2顺序表的初始化SeqListInit2.3顺序表的尾插SeqListPushBack... 查看详情
数据结构初阶栈(代码片段)
栈：一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一端称为栈顶，另一端称为栈底。栈中的数据元素遵守后进先出LIFO（LastInFirstOut）的原则。顺序存储还是... 查看详情
c语言实现顺序表(初阶数据结构)(代码片段)
...语SeqList.h文件内容test7_29_.c文件内容前言这是小编第一篇数据结构的文章，从今天开始更新数据结构相关的博客，希望大家多 查看详情
数据结构初阶第四篇——双链表（实现+图解）(代码片段)
这篇博客，我要给大家分享双链表的知识，上一篇博客，我给大家分享了有关单链表的知识，单链表相比双链表而言结构比较简单，但事实上，双链表的实现比单链表要方便很多，下面我就来给大家聊... 查看详情
数据结构初阶第三篇——单链表（实现+动图演示）[建议收藏](代码片段)
上一篇博客我已经分享了顺序表的相关内容，这一篇博客，我又要来介绍一下单链表有关内容。本篇博客代码链接：https://gitee.com/byte-binxin/data-structure/tree/master/SList_2目录链表的概念链表的实现链表的单个节点的定义... 查看详情
数据结构初阶图解链表双向带头循环链表(代码片段)
单链表在之前的博客里已经详细讲解过了（指路导航无哨兵位单向非循环链表），接下来讲解的是双向带头循环链表。源码地址链接注意：要转图请提前打招呼一级指针还是二级指针？首先我们要确定的问题... 查看详情
数据结构初阶第二篇——顺序表（实现+动图演示）[建议收藏](代码片段)
本篇博客我要给大家分享一下顺序表，这个存储数据元素的结构我在之前通讯录的文章也提到过，今天我来带大家再深入了解一下~博主本片篇博客代码码云链接：https://gitee.com/byte-binxin/data-structure/tree/master/SeqList_2ÿ... 查看详情
数据结构初阶：动态顺序表的功能实现（用c语言实现，附图分析）(代码片段)
文章目录一、动态版本顺序表二、动态顺序表的实现思路三、动态顺序表内存布局图四、初始化顺序表和内存释放五、顺序表接口实现：1.尾部插入数据2.头部插入数据3.尾部删除数据4.头部删除数据5.显示数据6.查找数据7.在... 查看详情
数据结构链表(代码片段)
🚀writeinfront🚀📜所属专栏：初阶数据结构🛰️博客主页：睿睿的博客主页🛰️代码仓库：🎉VS2022_C语言仓库🎡您的点赞、关注、收藏、评论，是对我最大的激励和支持！！... 查看详情
数据结构初阶第四节.链表详讲(代码片段)
...;今天我们将学习有关单链表的有关知识；单链表也是数据结构中的一大重点；今天就让我们来学习它吧！！！！！！！！！！一、单链表的概念链表是一种物理存储结构上非连续、... 查看详情
数据结构初阶链表详解无哨兵位单向非循环链表(代码片段)
链表概念及结构概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链式结构在逻辑上是连续的，但是在物理上不一定连续现实中的结点一般都是... 查看详情
初阶数据结构——栈(代码片段)
🎉🎉想快速入门数据结构，推荐订阅作者的初阶数据结构专栏！此专栏预计更新：顺序表，链表，栈，队列，二叉树，排序算法等等🎉🎉初阶数据结构我们通过c语言实现，所... 查看详情
初阶数据结构——队列(代码片段)
🎉🎉想快速入门数据结构，推荐订阅作者的初阶数据结构专栏！此专栏预计更新：顺序表，链表，栈，队列，二叉树，排序算法等等🎉🎉初阶数据结构我们通过c语言实现，所... 查看详情
初阶数据结构——二叉树(代码片段)
🎉🎉想快速入门数据结构，推荐订阅作者的初阶数据结构专栏！此专栏预计更新：顺序表，链表，栈，队列，二叉树，排序算法等等🎉🎉初阶数据结构我们通过c语言实现，所... 查看详情
数据结构-线性表(代码片段)
线性表是最基本的数据结构。基本概念线性表(LinearList)：由同类型数据元素构成有序序列的线性结构。表中元素个数称为线性表的长度线性表没有元素时称为空表表起始位置为表头，表结束位置为表尾抽象数据类型描述类型名称... 查看详情
11201771010119穷吉(代码片段)
理论知识：一般将数据结构分为两大类：线性数据结构和非线性数据结构线性数据结构：线性表、栈、队列、串、数组和文件非线性数据结构：树和图。线性表：1.所有数据元素在同一个线性表中必须是相同的数据类型。2.线性... 查看详情