【10月更文挑战第22天】
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是⼀种在实际中⼴泛使 ⽤的数据结构，常⻅的线性表：顺序表、链表、栈、队列、字符串...
线性表在逻辑上是线性结构，也就说是连续的⼀条直线。但是在物理结构上并不⼀定是连续的， 线性表在物理上存储时，通常以数组和链式结构的形式存储。
具有一类相同特性的数据结构的集合
水果：苹果、香蕉、梨
蔬菜：青菜、黄瓜、冬瓜、丝瓜
线性表：顺序表、链表
具有一类相同特性的数据结构的集合
想用特征指的是两个方面：逻辑结构、物理结构
那么物理结构指的是数据在内存上的存储形式
逻辑结构：人为想象出来的数据的组织形式
线性表中的成员在逻辑结构上都是线性的
对于一个数组1 2 3 4 5 6
下标i进行++操作依次访问，这个可以看得出数组在物理结构上是线性的
因为这个数组的排列顺序我们能知道数组在逻辑结构上面的话是线性的
而对于顺序表来说，逻辑结构是线性的，但是物理结构是不是线性的呢
所以顺序表在逻辑结构上一定是线性表，但是在物理结构上我们不知道是不是线性的
我们需要对顺序表的底层结构进行探究
顺序表的基础概念
顺序表的概念:顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构，⼀般情况下采⽤数组存储
所以顺序表的底层结构就是数组
我们在上一章节说道：顺序表在逻辑结构上一定是线性表，但是在物理结构上我们不知道是不是线性的
但是这里我们知道顺序表的底层结构是数组，因为数组在物理结构上是线性的，那么顺序表在物理结构上也是线性的
那么数组和顺序表的区别是什么呢？
将数组进封装一下，提供一些对数据管理的操作，比如说增加删除修改查找
那么数组就变成了顺序表，所以说顺序表的底层结构是数组
顺序表
顺序表是对数组进行封装：结构体
顺序表的定义
定义之前已经知道数组大小的数组
int arr[3]={1,2,3}
定义之前不知道数组大小的数组---动态内存管理
int *arr---定义一个指针
sequence:流畅的 List:表
那么对顺序表的定义
静态顺序表的定义
1.已知顺序表的大小:
静态顺序表：
struct SeqList
{
int arr[1000];
int size;//顺序表中有效数据的个数
}；
如果我们一开始不知道顺序表的大小的话，在后面代码生成的时候申请了大小，这就是动态顺序表
对于顺序表，我们不一定是整型数组，可能是字符数组，那么这个时候我们就要用到typedef了，将数据类型重命名，因为这样会很方便的，如果一个个改的话就很麻烦
我们在不确定用什么类型的数据的时候，我们将数据类型重命名就行了，到时候我们要进行更改的时候仅仅只需要更改这里的数据类型，没必要一个个进行更改
那么上面的顺序表就改成这个样子了
typedef int SLDataType
define N 7 我们在这里将数组的大小进行宏定义，随时可以进行修改的
struct SeqList
{
SLDataType arr[N];
int size;//顺序表中有效数据的个数
}；
以后不想使用整型的数据就将一开始的重命名进行修改就行了
动态顺序表的定义
对于动态的顺序表的话，我们不知道数组的大小
struct SeqList
{
int *arr; 我们在这里创建一个指针，后期我们为这块指针指向的空间申请空间
int capacity； 顺序表空间大小，我们需要一个变量来保存我们的空间大小
int size;//顺序表中有效数据的个数
int size;//保存当前顺序表有效数据的个数
}；
静态顺序表和动态顺序表的对比以及优缺点
那么我们到这里就知道了顺序表分为动态和静态的，但是哪个好呢？
对于静态顺序表，我们必须知道顺序表的大小，我们要给定一个大小‘
对于这个数组大小我们是不好定义的
假设我们一开始给的大小是100，但是后期我们要插入10000，那么很明显空间不够用，那么会造成空间数据丢失，会有很严重的后果的
如果我们给的顺序表大小很大，但是利用率很低，就会造成空间的浪费了
那么我们总结一下静态顺序表的缺点：
空间给小了不够用，给大了造成空间浪费
对于动态顺序表来说的话，我们一开始用malloc开辟一块空间，如果后期所需的空间不够的话，我们是可以用reallocJ进行空间大小扩增的，我们再次申请一块空间了，即是这个动态顺序表在开辟空间是造成了浪费，那么这个浪费也是可控的，浪费程度比较小
对比了两种顺序表，明显是动态顺序表更加好些，那么我们接下来实现动态顺序表
动态顺序表的实现
我们在实现顺序表的时候我们需要三个文件个文件 SeqList.c和SeqList.h和test.c文件
我们在SeqList.c中具体实现各种操作
我们在SeqList.h中定义顺序表结构，声明要提供的操作
我们在test.c文件中主要是对我们我们写的顺序表进行测试，看看写的对不对，测试函数
.h文件就起到了目录的作用，主要放的是函数的名称
.c文件就起到了对函数的具体操作
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
void SLtest01()
{
SL s;//创建顺序表变量
SLInit(&s);//我们这里初始化应该传的是地址，而不是值,//如果传的是值，那么sl的改变会影响s的改变
//尾插数据
SLPushBack(&s, 1);
SLPushBack(&s, 2);
SLPushBack(&s, 3);
SLPushBack(&s, 4);
SLPrint(&s);
/*SLPushFront(&s, 1);
SLPushFront(&s, 2);
SLPushFront(&s, 3);
SLPushFront(&s, 4);
SLPrint(&s);
SLInsert(&s, 12, s.size-1);
SLPopBack(&s);*/
//删除指定位置数据
/*SLErase(&s, s.size-1);
SLPrint(&s);*/
int ret=SLFind(&s, 2);
printf("%d", ret);
SLDestory(&s);
}
int main()
{
SLtest01();
return 0;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include "SeqList.h"
//顺序表的初始化
void SLInit(SL *ps)
{
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
//顺序表的销毁
void SLDestory(SL *ps)
{
if (ps->arr )//相当于ps!=NULL
{
free(ps->arr);//将申请的空间进行释放
}
//让变量回到最初始的状态
ps->arr = NULL;
ps->size = ps->capacity = 0;
}
/*对于插入数据，有两种情况：空间充足和空间不足
空间充足：顺序表的容量为capacity，有效数据为size个，
那么我们只需要在顺序表的下标为size的位置进行插入数据，然后进行size++，插入其他的数据
空间不足：先增容，再插入。一但capacity=size时，就说明我们的顺序表满了，那么我们就进行增容操作
所以我们在插入数据的时候要先判断空间是否充足*/
/*增容的讲究
* 增容一般是成倍数的增加，比如2 3倍
*
为什么不能一次增容到位呢？
因为增容的操作本身就有一定的程序性能的消耗，若频繁的增容会
导致程序效率低下
*/
/*增容分两种情况
* 1.连续空间足够，直接扩容
* 2.连续空间不够
（1）要重新找一块满足条件的地址，分配足够的内存
* （2）拷贝原有的数据到新的地址
* （3）销毁地址
增量和插入数据的个数是正相关的，所以我们每次采用二倍进行增容
*/
//判断空间是否充足
void SLCheckCapacity(SL*ps)
{
//判断空间是否充足
if (ps->size == ps->capacity)//空间不足，我们要进行增容操作
{//有效数据等于实际容量，就是说明当前内存已经满了
//增容
//我们要将realloc返回的地址强转为SLDatatype*
//因为顺序表中数据类型都是SLDatatype
//为了防止申请失败的话，返回的是NULL，原有的数据都消失了
//我们创建一个临时变量，在进行判断是否申请成功了，我们再为原先的地址进行付赋值
//我们要对capacity进行判断，如果capacity一开始是0的话，那么增容的结果还是0
//所以我们在增容之前要对capacity进行判断
//若capacity为.，给个默认值，否则x2倍
int newCapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
/*解释下这个三目操作符
* 如果ps->capacity == 0的话，那么我们就给一个默认值4
* 如果ps->capacity ！= 0的话，那么我们直接给容量乘个2倍
之所以乘以二，我们将这个乘以二的值直接放到增容的参数里面，
原先的参数就是二倍的capacity
但是现在的参数newCapacity同样也是2倍的
*/
SLDatatype* tmp = (SLDatatype*)realloc(ps->arr, newCapacity * sizeof(SLDatatype));//2倍的增加
//判断是否申请成功 我们的容量还要乘以每个元素的字节大小就是我们要申请的空间大小
if (tmp == NULL) //如果这里是整型的话，那么我们就要申请4个整型大小的空间，每个整型4个字节
{
perror("realloc fail!");
exit(1);//都申请失败了，我们直接退出
}
//增容成功
ps->arr = tmp;
ps->capacity = newCapacity;
}
}
//时间复杂度为O(1)
//尾部插入数据
void SLPushBack(SL* ps, SLDatatype x)//往哪里插入数据，插入的数据是什么
{
//判断传过来的地址是不是空地址
/*if (ps == NULL)
{
return;
}*/
//粗暴的解决方法
assert(ps);//等价于assrert(pa!=NULL)
//如果ps为空指针那么就会报错
//判断空间是否充足
SLCheckCapacity(ps);
//插入数据
//我们直接在下标为size的位置进行插入数据
//插入完数据之后我们进行size++操作，进行下个数据的插入
ps->arr[ps -> size++] = x;
//换另一个位置进行插入数据
}
/*对于头插操作
* 我们需要将一个数字插到第一个
* 在之前我们需要将原本的数字往后面挪动一位
* 从后往前进行挪动
* 如果从前往后会导致数据被覆盖的
* 挪动完成之后我们再为第一个数进行赋值
*/
//时间复杂度为O(N)
//头部插入数据
void SLPushFront(SL* ps, SLDatatype x)
{
//防止传过来的顺序表为空
assert(ps);
//判断空间是否充足
SLCheckCapacity(ps);
//插入操作
//数据整体后移一位
for (int i = ps->size; i > 0;i--)//从后往前挪动，那么我们就将最后一位挪到下标为size的位置上
{
ps->arr[i] = ps->arr[i - 1];
}
//下标为0的位置空出来了
ps->arr[0] = x;
ps->size++;//插入了数据，那么size就要增加
}
//顺序表的打印操作
void SLPrint(SL* ps)
{
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->arr[i]);
}
printf("\n");
}
//尾部删除
void SLPopBack(SL* ps)
{
assert(ps);
assert(ps->size);//这里的size不能为0，如果有效数据为0的话，那么就不能进行删除操作了
//ps->arr[ps->size - 1] = -1;
/*上面这句话多余了
假设顺序表里面有1 2 3 4
现在我们要进行尾删除数据
我们进入代码直接指向了size--操作，那么现在的size就指向了4的位置
那么此时size就是3，有效的数据是3个
那么有效的数据是前三个数据1 2 3
假如我们要进行增加数据也是不会影响的
size--之后，我们在打印的时候都是以0到size-1这个范围进行操作的
变相的删除这个尾部的数据了
利用了size的变化
*/
ps->size--;//有效数据减一
}
/*
从前往后挪动
1 2 3
2先将1覆盖，然后3挪动到2之前的位置，那么我们就起到了头部删除
*/
//头部删除
void SLPopFront(SL* ps)
{
assert(ps);//顺序表不能为空
assert(ps->size);//有效数据不能为空
//数据整体向前挪动一位
for (int i=0;i<ps->size-1; i++)
{
ps->arr[i] = ps->arr[i + 1];//将后面的数据覆盖到前面的数据
}
ps->size--;
}
//在指定位置之前插入数据(空间足够才能直接插入)
void SLInsert(SL* ps, SLDatatype x, int pos)
{
assert(ps);
assert(pos>=0&&pos<=ps->size);//对pos的位置进行限制
//判断空间是否充足
SLCheckCapacity(ps);
//将pos下标指向的数以及后面的数都往后挪动一位
for (int i=ps->size;i>pos; i--)
{
ps->arr[i] = ps->arr[i - 1];//前一个位置的值给到后面的位置，从后往前挪动
//最后一次就是将pos指向的位置上的数向后挪动到pos+1上面
//就是用pos上的数为pos+1位置上的数进行赋值
}
//我们将pos位置上以及后面的数据往后挪了一步，那么现在的pos上就是空的
//我们现在为pos位置上进行数据的插入
ps->arr[pos] = x;
ps->size++;
}
//删除指定位置的数据
void SLErase(SL* ps, int pos)
{
assert(ps);
assert(pos >= 0 && pos < ps->size);//不能等于，因为size指向的是最后一共额有效数据的下一个位置
//删除数据思路：
/*我们将pos指向的数字删除了，那么pos指向的数字后面的数字都要往前挪动一位
size也要--操作
在挪动的时候我们是从前往后挪
*/
//pos之后的数据整体向前挪动一位
for (int i=pos;i<ps->size-1 ;i++)
{
ps->arr[i] = ps->arr[i + 1];
//最后一次挪动的时候，我们要将size-1的值赋值到size-2上面
}
ps->size--;
}
//查找数据
int SLFind(SL* ps, SLDatatype x)
{
assert(ps);
for (int i=0 ; i < ps->size; i++)
{
if (ps->arr[i] == x)
{
return i;
}
}
//说明没有找到：返回一个无效的下标
return -1;
}
#pragma once
#include<stdio.h>
#include<stdlib.h>//动态申请函数的头文件
#include<assert.h>
//定义动态顺序表结构
typedef int SLDatatype;
typedef struct SeqList
{
SLDatatype* arr;//定义一个指针
int capacity;//顺序表空间大小
int size;//记录顺序表中有效数据个数
}SL;
//typedef struct SeqList SL;//为顺序表的类型名字进行重命名
//另一种重命名的方法就是在我们创建顺序表结构体的时候我们直接进行
//重命名，新名字直接写在下括号的后面，分号的前面
//顺序表的初始化
void SLInit(SL *ps);
//销毁
void SLDestory(SL *ps);
//打印顺序表
void SLPrint(SL* ps);
//尾部插入数据
void SLPushBack(SL* ps, SLDatatype x);//往哪里插入数据，插入的数据是什么
//头部插入数据
void SLPushFront(SL* ps, SLDatatype x);
//尾部删除
void SLPopBack(SL* ps);
//头部删除
void SLPopFront(SL* ps);
//在指定位置之前删除数据
void SLInsert(SL* ps, SLDatatype x, int pos);
//删除指定位置的数据
void SLErase(SL* ps, int pos);
//查找数据
int SLFind(SL* ps, SLDatatype x);
//查找成功的话，返回顺序表对应下标的位置
顺序表算法题
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
/*
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：
更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。
用户评测：
评测机将使用以下代码测试您的解决方案：
int[] nums = [...]; // 输入数组
int val = ...; // 要移除的值
int[] expectedNums = [...]; // 长度正确的预期答案。
// 它以不等于 val 的值排序。
int k = removeElement(nums, val); // 调用你的实现
assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
如果所有的断言都通过，你的解决方案将会 通过。
示例 1：
输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]
解释：你的函数函数应该返回 k = 2, 并且 nums 中的前两个元素均为 2。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
示例 2：
输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]
解释：你的函数应该返回 k = 5，并且 nums 中的前五个元素为 0,0,1,3,4。
注意这五个元素可以任意顺序返回。
你在返回的 k 个元素之外留下了什么并不重要（因此它们并不计入评测）。
提示：
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100
*/
//遍历数组，将数组中等于val的数据删除
//返回数组中与val不同元素的数量
/*
第一步：遍历数组，找val 一层循环
val之后的数据整体向前挪动一位 两层循环
那么时间复杂度就是O(N^2)
*/
/*
新思路：时间复杂度降到O(N)
空间复杂度是O(1),不需要额外的开辟空间+
定义两个变量指向数组第一个位置，判断nuns[src]是否等于val
相等的话那么src++
不相等的话，我们将src这个位置的数据给到nums[dst] ,然后src++和dst++
*/
int removeElement(int* nums, int numsSize, int val)
{
int src = 0, dst = 0;
while (src < numsSize)
{
if (nums[src] == val)//如果src指向的是我们要找的数字我们就将src++
{
src++;
}
else//src指向的数字不是我们找的数字，我们就将src指向的数字赋值给dst指向的位置上的数字
{
nums[dst] = nums[src];
dst++;
src++;
}
}
//此时det指向的位置就是要返回的有效个数
return dst;
}
/*
再次说明一下这个代码
假设我们的数组里面是2 2 3 4 6
我们要找到3，并返回非3的元素的个数
一开始我们的src和dst都指向的第一个元素
因为一开始src指向的数字不是我们要找的数字，那么我们 就进行src++ dst++操作
并将src指向的数字赋值给dst指向的位置上，因为都是指向的2，所以不变
然后src就指向了第二个元素的位置，dst也是指向了第二个元素的位置
因为src现在指向的数字还不是val，所以我们继续进行src++ dst++操作
并将src指向的数字赋值给dst指向的位置上，因为都是指向的2，所以不变
那么src指向了3，dst也是指向了3
因为此时的src找到我们要找的val，所以我们进行src++操作
那么src现在指向了4，dst仍然指向了3
那么因为现在的src指向的不是val，所以我们将src所指的数字赋值给dst指向的位置
那么现在dst位置上的就是4了
赋值完成之后src++和dst++
dst指向了第4个位置，src指向了第五个位置就是6
因为src指向的不是val，那么我们将src指向的6赋值给dst所指的位置
通过这种方法我们变相将val删除了，并且最后的dst的值就是非val有效个数
那么我们直接返回dst就行了
*/
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
/*
给你一个 非严格递增排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。
考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：
更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
返回 k 。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。
示例 1：
输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
示例 2：
输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
提示：
1 <= nums.length <= 3 * 104
-104 <= nums[i] <= 104
nums 已按 非严格递增 排列
*/
/*题目简介：
* 删除数组中的重复元素，返回删除后数组的新长度
返回数组中唯一元素的个数
我们还要将数组进行改变
*/
/*思路：
* 定义两个指针，dst指向的第一个位置，sr指向的下个位置
* 判断src和dst位置的数字是否相等
* 相等的话就说明这两个数字重复了，那么src++，找到不相等的值
* 找到不相等的值我们就将dst++，
* 然后我们将nums[src]赋值给dest位置上
* 赋值后src++
*/
/*简单版本的思路：
* （1）相等：src++
* （2）不相等：dst++,nums[dst]=nums[src],src++
*/
/* 1 2 2 2 2 3
一开始我们的dst指向的是第一个元素，src指向的是第二个元素，因为两个元素不相等，
dst++,指向了第二个元素，然后将src指向的数字赋值给dst指向的数字，因为指向的位置是一样的，那么数据就不变了
然后src++,src指向了第三个元素，判断是否相等，那么src++,那么src就指向了第三个元素
，再次判断相等，相等，那么src++,src就指向了第四个元素
再次判断相等，相等，那么src++,src就指向了第五个元素
再次判断相等，相等，那么src++,src就指向了第6个元素3
不相等了，那么dst++，此时dst指向二档是第三个数据
那么我们将srx指向的3赋值给dst，然后src++，src就跳出数组了
那么此时dst的值是2，但是有效数据是3
所以我们在返回值的时候返回的是dst+1
*/
int removeDuplicates(int* nums, int numsSize)
{
int dst = 0, src = 0;
while (src < numsSize)
{
//判断nums[dst]和nums[src]数据是否相同
//相同就是重复了src++
//不相等：dst++, nums[dst] = nums[src], src++
//if (nums[dst] == nums[src])
//{
// src++;
//}
//else//不相同
//{
// dst++;
// nums[dst] = nums[src];
// src++;
//}
//反正都是要src++的
if (nums[dst] != nums[src]&&++dst!=src)
{
//我们还在条件判断中写出了dst不等于src的条件我们就=不进行赋值了
/*dst++;我们直接在判断src和dst是否相等的时候进行后置++
先++，再判断dst和src是否相等*/
//这种写法可以避免无效的赋值
nums[dst] = nums[src];
}
src++;
}
return dst + 1;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
/*
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。
请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。
示例 3：
输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
提示：
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109
进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？*/
//注意：一开始题目就说了nums1的大小是m+n
//我们不需要额外申请空间，nums1里面的空间是足够的
/*场景一：l2先跳出循环
合并nums2到nums1中
nums1的初始长度是m+n,但是有效数据是m个
假设nums1: 1 2 6 _ _ _
nums2: 3 4 5
创建三个指针，第一个指针l1指向的是nums1的有效数据最后一个位置
第二个指针l2，指向的是nums2的有效数据最后一个位置
第三个指针l3，指向的是nums1的实际容量的最后一个位置
第一次比较l1指向的数字大于l2指向的数字，那么将l2的数字赋值到l3的位置
赋值过后，l1-- l3-- 注意l2不动，因为l2指向的数字还没有放到nums1里面
现在l2指向的是5，l1指向的是2，因为l2>l1所以将l2的5赋值到l3的位置
那么l2-- l3-- l2指向的是4 l1指向的是2，因为l2>l1,所以将l2的值赋值到l3的位置
赋值后l2-- l3-- 此时l2指向的是3，l3指向的是6 l1指向的是2
l1<l2 那么将l2指向的3赋值到l3指向的位置 l2-- l3--
那么l1和l3就重合了 l2就跳出循环了
*/
/*场景2 l1先跳出循环
nums1 3 4 5 _ _ _
nums2 1 2 6
l1指向了5 l2指向了6 l3指向的是nums1最后的位置
第一次l2>l1，那么将6赋值到l3的位置
放完后 l2-- l3--
l2指向的是2 l1指向的是5，l2<l1,所以将l1的值赋值到l3的位置，
那么l1-- l3-- l1指向的是4 ，l2指向的是2
因为 l1>l2，所以将l1指向的4赋值到l3的位置，那么l1-- l3--
那么l1 指向的是3 l2指向的是2
l1>l2 所以将l1指向的3赋值到l3 的位置 l1-- l3--
此时的l1已经跳出循环了
此时l2还有两个数据
那么我们就对这两个数据进行处理
l2指向的2赋值到l3的位置 l2-- l3--
最后一个数字赋值到l3的位置
*/
/*总结分析：
对于两种场景来说，结束条件要么是l1<0,要么是l2<0
对于l1<0，此时l2里面的数据还没有完全放到l1里面去，此时我们还要处理l2剩下的数据，循环放到l1中
对于l2<0的话，就说明l2里面的数据已经完全放到l1里面了，我们就不需要进行额外的处理了
*/
/*
简易思路：
创建三个指针，分别指向nums1最后一个数据位置，nums2最后一个数据位置，nums1最后一个容量位置
比较l1和l2位置的数据，谁大谁往l3位置放数据
*/
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int l1 = m - 1;//nums1中最后一个有效数据的下标
int l2 = n - 1;//nums2中最后一个有效数据的下标
int l3 = m + n - 1;//nums1中容量的最后位置的下标
//进行l1和l2数据的比较
while (l1>=0&&l2>=0)
{
if (nums1[l1] > nums2[l2])
{
nums1[l3--] = nums1[l1--];//一定不能忘了l1--和l3--
}
else
{
//l1==l2 要么l2>l1
nums1[l3--] = nums2[l2--];//将l2位置的数据放到l3位置处
}
}
//跳出while循环有两种情况，要么l1<0 要么l2<0
//不存在第三种情况吗？：l1<0 l2<0 同时跳出循环
while (l2 >= 0)//将l2剩下的数字循环放到l1中
{
nums1[l3--] = nums2[l2--];
}
}
/*
l1先<0的话需要处理
l2先<0的话不需要处理
*/
顺序表问题与思考
• 中间/头部的插⼊删除，时间复杂度为O(N) ,尾部的插入为O(1)
• 增容需要申请新空间，拷⻉数据，释放旧空间。会有不⼩的消耗。
• 增容⼀般是呈2倍的增⻓，势必会有⼀定的空间浪费。例如当前容量为100，满了以后增容到200，我们再继续插⼊了5个数据，后⾯没有数据插⼊了，那么就浪费了95个数据空间。
思考：如何解决以上问题呢?
• 头部、中间位置的插入删除，时间复杂度变成O(1)
• 减少或者避免增容带来的性能消耗
• 避免空间浪费，要几个空间就给几个空间
那么接下来就是进行链表的学习了
