前引：上一篇我们复习了复杂度，今天我们来通过实践回忆我们的线性表知识点，下面将讲解什么是线性表，顺序结构又是什么，知识点简洁精髓，无废话可言，小编会从每个细节讲起，包含头文件的使用，分析每句代码的位置，这篇文章可作为你的绝佳复习资料哦，欢迎在评论区进行点评
目录
知识点速览
线性表： n 个具有相同特性的数据元素的有限序列。在逻辑上来说是线性结构，也就是说它存起来的数据像一条线一样（物理上并不一定是连续的），通常以数组、链表结构来存储（常见的线性表：顺序表、链表、栈、队列、字符串......）
顺序表：用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般采用数组存储，在数组上完成数据的增删查找（顺序表可以分类为：静态顺序表（定长数组存储）、动态顺序表（动态开辟的数组存储））
代码实现与讲解
上面我们知道顺序表有两种实现方式，一种是定长数组，另一种是动态开辟数组，下面小编将分别作讲解，内容详细，分析到位，不仅是小编的复习整理，也是学习记录！
定义结构体
静态数组来存储数据，咱们需要一个结构体，因为涉及到多个变量，比如当前存储的数据个数、最大空间、存储空间，结构体可以参考下面这样设计：
struct List
{
//定长数组
int arr[10];
//当前数据个数
int size;
//最大存储量
int max;
};这样我们就定义了一个结构体，它的类型是 struct List ，类比 int 、char 一样属于数据类型。下面我们来创造结构体变量，有以下两种方式：直接创造 类型+名称这样创造。如下参考：
这里我们有几点可以优化 及 注意的地方：
（1）使用typedef 来重新定义变量，例如这个结构体被typedef重新定义之后，它的类型就可以 简写为 List
typedef struct List
{
//定长数组
int arr[10];
//当前数据个数
int size;
//最大存储量
int max;
}List;（2）同样我们可以用 typedef 来定义变量类型、用宏定义常量，可以方便以后进行代码维护
//定义变量类型
typedef int Plastic;
//宏定义常量
#define MAX 10
typedef struct List
{
//定长数组
Plastic arr[MAX];
//当前数据个数
Plastic size;
//最大存储量
Plastic max;
}List;（3）注意下面这两种写法，小编通过画图来进行注释
静态顺序表
我们已经定义完了结构体，下面我们来简单看看静态顺序表，这里因为静态顺序表与动态顺序表除了开辟类型不一样，其它大致相同，我们以动态顺序表为主要的讲述对象
初始化
这里需要注意，我们改变的是结构体的成员，需要取地址，因为实参是形参的一份临时拷贝，取地址的话，函数就拿到的是结构体的地址，否则就是对结构体的一份拷贝，不会真正改变，例如：
//初始化
Preliminary(&Static);在初始化空间的时候，我们可以采用函数 memset ，这样可以避免使用几条代码的循环
void Preliminary(List* Static)
{
//初始化当前数据个数
Static->size = 0;
//初始化最大存储个数
Static->max = MAX;
//初始化空间
memset(Static->arr, 0, sizeof(Plastic) * MAX);
}初始化完成之后，再按照数组那样取存储数据就好了，下面我们来重点讲解动态顺序表！
动态顺序表
初始化
跟之前的初始化其实大差不差，只是我们结构体里面存的数组变成了指针，需要初始化时开辟空间
typedef struct List
{
//动态空间指针
Plastic* arr;
//当前数据个数
Plastic size;
//最大存储量
Plastic max;
}List;下面我们来初始化结构体里面的变量 ，下面我们再通过调试来看初始化的结果
void Preliminary(List* Static)
{
//初始化当前数据个数
Static->size = 0;
//初始化最大存储个数
Static->max = MAX;
//开辟数组空间
Static->arr = (int*)malloc(sizeof(Plastic) * MAX);
//判断空间有效性
if (Static->arr == NULL)
{
printf("开辟空间失败\n");
return;
}
}
存储元素
下面我们来将元素存储进动态空间，按照逻辑，我们应该考虑当前是否是满空间，否则就要扩容了，为了以后方便维护，和提高代码的可读性，我们先来实现扩容函数！下面的代码有几点注意！
（1）扩容空间的指针最好不要用原空间指针，因为扩容可能不是在原空间后面开辟
（2）如果扩容成功，需要将原空间指针与新空间指针连接起来
//扩容
void Extend(List* Static)
{
int* pc = (int*)realloc(Static->arr, sizeof(Plastic) * (Static->max) * 2);
//判断扩容是否成功
if (pc == NULL)
{
printf("扩容失败\n");
return;
}
else
{
//更新空间
Static->arr = pc;
Static->max *= 2;
printf("扩容成功\n");
}
}
下面我们来存储数据（注意更新元素个数），并且通过调试来观察存储结果
void Storage(List* Static, int data)
{
//如果空间已满，就进行扩容
if (Static->size == Static->max)
{
Extend(Static);
}
//存储元素
Static->size++;
Static->arr[Static->size - 1] = data;
}
头插
头插前有两个操作需要注意：
（1）注意空间是否存在，否则无法头插
（2）头插需要判断空间是否充裕，通常是判断size+1的元素空间是否越界
然后经过这两个判断之后，进行头插，为了使代码效率高，我们选择从后往前进行挪动之前的数据，然后再进行插入，思维演示如下：
头插之前
头插之后
//头插
void Head(List* Static, int data)
{
//如果空间不存在则无法头插
if (Static->arr == NULL)
{
printf("空间不存在无法头插\n");
return;
}
//判断空间是否充足
if (Static->size + 1 == Static->max)
{
Extend(Static);
}
int end = Static->size - 1;
//移动元素
while (end >= 0)
{
Static->arr[end + 1] = Static->arr[end];
end--;
}
//插入元素
Static->arr[0] = data;
Static->size++;
}尾插
我们刚才设置的结构体里面有一个成员是记录当前元素个数的，咱们尾插的步骤就是：先找尾、再插入。这里刚好就是size下标的地方（注意判断空间是否充裕），由于过程简单，我们直接上代码
void Tail(List* Static, int data)
{
//判断空间是否充裕
if (Static->size + 1 == Static->max)
{
Extend(Static);
}
//插入
Static->arr[Static->size] = data;
Static->size++;
}头删
删除第一个元素，我们这里不需要判断空间是否支持删除，只需要判断删除的这个元素空间是否存在就行了（不存在就退出）。判断之后，这里最方便的方式是将元素向前挪动，需要控制下标不能越界
头删之前
头删之后
void Head_Omit(List* Static)
{
//判断是否有元素可以删除
if (Static->size == 0)
{
printf("删除失败\n");
return;
}
//从第一个元素开始将后面的元素往前挪动
int end = 0;
while (end < Static->size-1)// 注意控制下标不能越界
{
Static->arr[end] = Static->arr[end + 1];
end++;
}
//元素个数减一
Static->size--;
尾删
尾插就不多说了，先判断空间是否支持删除（size > 0），然后size--即可
尾删之前
尾删之后
void Tail_Omit(List* Static)
{
//判断能否删除
if (Static->size == 0)
{
printf("删除失败\n");
return;
}
//删除
Static->size--;
}随机删除
随机删除小编就以提供下标为列，将对应下标的元素删除，需要考虑空间元素数量是否支持删除情况。小编提供的思路：先找到那个下标的元素，然后将后面的元素前移
删除之前
删除之后
//随机删除（下标位置删除）
Random_Omit(List* Static, int under)
{
//找对应下标的元素
int end = 0;
while (end < Static->size && Static->arr[end] != Static->arr[under])
{
end++;
}
//如果没有找到
if (end == Static->size)
{
printf("该元素不存在\n");
return;
}
//将后面的元素向前挪动
while (end < Static->size - 1)
{
Static->arr[end] = Static->arr[end + 1];
end++;
}
//元素个数减一
Static->size--;
}随机插入
这里小编还是根据下标来找到插入的位置，先判断该下标是否支持插入，然后该下标原来的元素全部后移，再插入即可
插入之前
插入之后
//随机插入（下标位置插入）
void Random_Insert(List* Static, int under, int data)
{
//先判断该下标是否支持插入
int end = 0;
while (end < Static->size && end != under)
{
end++;
}
//如果没有找到
if (Static->size == end)
{
printf("该位置无法插入\n");
return;
}
//该下标位置及后面的元素后移
end = Static->size-1;
while (end != under)
{
Static->arr[end] = Static->arr[end-1];
end--;
}
//插入
Static->arr[under] = data;
Static->size++;
}练习题一
小编来大概解读一下这个题目：给你一个值，将一个数组中与这个值相等的元素移除，其余元素 按顺序前移
思维方法：
（1）这一种是最简单的一种：就是创建另外一个数组空间，将这些符合规定的值全部存到这个新数组里面，然后返回不等于这个值的元素个数，这是最普通的写法，小编就不演示了啊！
（2）算法解法思想：我们可以采用双指针的方法，通过指针的快慢移动，来处理等于val的值，如果在力扣上不方便调试，大家可以放在自己的编译器上去观察数据变化，重点是学会，不是求速通
例题详解：
首先我们设置2个下标（a，b），a就负责找不同于val的值，找到之后b所在的下标元素就等于a所在下标的值，然后a、b都向前移动一位，就这样循环就行了，注意a不能越界，下面我画图演示
我用数组【0、1、2、2、3、0、4、2】，val=2做例子，大家对着图配上代码梳理一遍思路！
int removeElement(int* nums, int numsSize, int val)
{
int a = 0;
int b = 0;
int k = 0;
while (a < numsSize)
{
//a找不同
while (a < numsSize && nums[a] == val)
{
a++;
}
if (a >= numsSize)
{
break;
}
//填埋、后移
nums[b] = nums[a];
a++;
b++;
k++;
}
return k;
}练习题二
思维方法：
（1）此题我们还是可以通过双指针的思想来做，两个指针分别指向两个数组的起始位置，通过建立第三个数组空间，来根据双指针元素的大小进行顺序填充即可，但是此方法比较复杂（不推荐）
（2）找较大的元素，从后往前进行填充，这样也可以不用开辟新数组，详细解答过程如下
例题详解：
如果是 n1 先走完：
首先我们定义三个下标，例如num指向nums1的末尾，m1指向nums1初始数据末尾，n1指向nums2初始数据末尾，如下图：
然后我们通过找较大的值来从后向前填充。例如此时nums1【m1】>=nums2【n1】，num的位置就填充nums1【m1】，然后m1--，num--，例如：
接着通过循环来进行上面的操作：找两个数组中较大的值，填入num的位置，直到某个数组当前下标越界为止。【中间循环过程跳过】
此时我们按照上面的循环结束条件，两个数组的情况应该是下面这样的，nums1剩余的元素都是比nums2小的，自然也就不用管，直接达到了排序效果
如果是 m1 先走完：
我们再来看下面这种情况，如果是m1先走完，说明nums2中的剩余元素都是比nums1小的，m1走完也就结束了循环，存在nums2中有元素剩余，如图：
此时我们看到nums2的元素还没有走完，但是已经出循环了，这种情况就需要将nums2剩余的未排完的元素拷贝到nums1中去
if (m1 < 0)
{
memcpy(nums1, nums2, sizeof(int) * (n1 + 1));
}下面是总的代码，此题很有整理的必要，希望小编的讲解大家可以弄清楚！还是408真题哦！
void merge(int* nums1, int m, int* nums2, int n)
{
int m1 = m - n - 1;
int n1 = n - 1;
int num = m - 1;
while (n1 >= 0 && m1 >= 0)
{
if (nums2[n1] >= nums1[m1] && n1 >= 0 && m1 >= 0)
{
nums1[num] = nums2[n1];
n1--;
num--;
}
if (nums1[m1] >= nums2[n1] && n1 >= 0 && m1 >= 0)
{
nums1[num] = nums1[m1];
m1--;
num--;
}
}
//如果nums2中有元素剩余，就拷贝到nums1
if (m1 < 0)
{
memcpy(nums1, nums2, sizeof(int) * (n1 + 1));
}
}
