【数据结构初阶】顺序表的实现
一、线性表
线性表（linear list）是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。 我们的顺序表和链表就分别是以数组和链式结构进行存储的
下面的两张图片就分别是我们的顺序表和链表的存储形式（逻辑结构并不是物理结构）
二、顺序表
2.1 顺序表的概念及结构
顺序表是用一段物理地址连续的存储单元依次存储数据元素的一种线性结构，一般情况下，我们采用数组进行存储，在数组上面完成数据的增删查改
值得注意的点有两个： 一个是按照顺序存储，怎么说呢？就像是我们排队在超市结账的那个队伍一样，顺序表就有点像那个，因为我们得按照顺序来站队嘛！这就有点类似于顺序表 另一个是存储单元，其实这个就是一个结构体，我们自己来定义这个结构体里面到底应该有什么，他就是为满足我们的需要所生的，比如我们上面所说的那个排队的例子，一个队伍，他究竟是由什么组成的呢？他又有什么特性呢？我们不妨来分析一下，队伍中每个人其实就是一个元素，这个元素的个数是有限个的，有限也就意味着有个最大值。那么我们把他抽象成顺序表，其实顺序表中的存储单元无非就是这个队伍，我们需要那么一个结构体，能包含我想要的类型。
那么我们这个结构体应该拥有什么呢？ 其实就是data，size，这些东西而已
2.2 顺序表类型
我们的顺序表有两种类型，一种是静态顺序表，一种是动态顺序表。 分别利用定长数组和动态开辟这两部分知识来实现
其实我们稍微比较一下就知道这两种顺序表的优劣了： 静态顺序表，他存储元素的个数，需要我们开辟一个非常僵硬的定长数组来存放，而且这个数组的大小随着我们存储元素的增加和减少，它又需要不断地进行改变，那数组大小什么时候就是一个标准呢？答案是：没有标准。数组空间开大了，那就浪费了，开小了又不够用，一旦数据溢出，我们又得手动改变这个数组的大小，始终没有一个头，我们需要不停的改啊改，改啊改，改到你要疯了为止。 友友们看到这里就感觉有点无语了，这个静态顺序表这么没用，博主你还讲什么呀？当然是为了衬托我们的动态顺序表啦，也就能用上我们的指针部分的内容了，指针多方便啊，看起来也高级嘛，之前C语言不是说指针比较重要么，就体现在数据结构这里的应用了。
但我们的动态顺序表也其实有一些缺陷，因为他也不能每次精确的将自己开辟空间的个数与实际数据的个数完美对应起来。这也就为我们后面的链表引出，进行了铺垫。
#define N 10//开小了不够用，开大了浪费，所以不实用
typedef int SLDataType;
typedef struct SeqList
{
SLDataType a[N];//定长数组
SLDataType size;//记录存储多少个有效数据
}SL;
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* array;//指向动态开辟的数组
size_t size;//有效数据个数
size_t capacity;//容量空间大小
}SL;2.3 顺序表中结构体定义和链表中结构体定义的对比
为什么要给大家讲解一下这里呢？因为我觉得，函数接口的功能实现，我们不会可以慢慢走读代码，慢慢去理解，可是他们中结构体为什么这么定义？我觉得这是一个比较重要的问题。
typedef int SLDataType;
typedef struct SeqList
{
SLDataType* array;//指向动态开辟的数组
size_t size;//有效数据个数
size_t capacity;//容量空间大小
}SL;
在C语言中我们学到的结构体，其实就是为了数据结构的学习做铺垫的。 那顺序表的结构都需要有什么呢？我们在脑海里不妨想象一下顺序表它应该是一个什么样子的？他就是一条长长的数组，里面存储了很多重要的数据，所以我们就可以考虑，我们的结构体该如何定义啊？是不是需要一个数组呢？但这个数组我们用的是指针来维护，也就是利用动态内存开辟的方式给这些数据开辟一个居住的空间，所以我们所定义的结构体中就应该包含一个指针类型，一个size变量表示有多少个数据，还应有一个基，这个基用来表示我们的最大空间，如果空间满了，那我们就进行开辟基的2倍的空间大小，这样的话，就可以稍微解决一下我们合理开辟空间大小的问题了
与链表所不同的是，我们所定义的结构体不需要这么多花里胡哨的东西，我链表就很纯粹嘛，我就需要个数据和地址，就能存储很多很多的数据了，那还需要什么数组大小，数组空间的最大值呀这些东西来修饰我的数组，我的链表就需要指针和数据，其他什么都不需要。
正因为这样我们在定义结构体时，链表和顺序表就发生了差异，如下所示，非常的干净和纯粹，哪里用那么多东西来修饰我的空间，我只需要指针就够了。这也从另一方面体现出我们指针的好处
typedef struct SListNode//单链表结点
{
SLTDateType data;
struct SListNode* next;
}SLTNode;2.4 顺序表各个接口的实现
2.4.1 顺序表的初始化，销毁和打印
void SLPrint(SL* ps)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
printf("%d ", ps->array[i]);
}
printf("\n");
}
void SLInit(SL*ps)
{
assert(ps);
ps->array = NULL;
ps->size = 0;
ps->capacity = 0;
}
void SLDestroy(SL* ps)
{
assert(ps);
if (ps->array)
{
free(ps->array);
ps->array = NULL;
ps->size = ps->capacity = 0;
}
}1.初始化：我们先将顺序表中维护元素所处空间的指针int*array,为了方便后面的讲解，我们将结构体类型重定义为SL。我们刚开始初始化，把指针置为空指针，size和capacity都置为0就好了，后面我们会在空间大小检查的模块对这些进行改变 2.打印：由于我们的数据元素都是些整型，而且这还是个顺序表，所以我们只需要一个for循环将顺序表中的每个数据打印出来就好了，这个接口也是很好实现的。不过多赘述 3.销毁：这里的销毁也是很简单的，因为我们的数据都被存储在一个连续的物理空间当中，尽管这个空间是动态开辟的，但也没有什么影响，所以我们只需要free指向这块儿动态开辟空间的指针就可以了，将这块儿空间还给操作系统就完成我们的销毁接口了
2.4.2 顺序表空间大小的检查
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
//如果capacity！=0我们对newcapacity扩大2倍，后续的开辟空间也就扩大二倍了
//如果capacity==0我们给newcapacity赋值为初值4，后续开辟空间直接开辟4个大小的空间
SLDataType* tmp = (SLDataType*)realloc(ps->array, newcapacity * sizeof(SLDataType));
//回顾知识，realloc扩容的方式有两种，一种是原地扩容，一种是异地扩容（原来空间会自动realloc被销毁）
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);//直接终止程序，-1代表异常终止，0代表正常终止
}
//如果realloc接收的指针是null，那么相当于malloc一个空间这个空间大小是newcapacity，类型是SLDataType
ps->array = tmp;
ps->capacity = newcapacity;
}
}我们可以直到当size==capacity时，也就意味着我们空间满了，我们要重新开辟空间了，以满足更多数据的存储。这里我们也用到了一个三木表达式，刚好解决了，我们初始化后容量为0的问题，然后我们用relloc开辟空间大小正好利用了，realloc的一个特点，就是如果，你传给realloc的指针是一个空指针的话，那么realloc的行为和malloc相似，会开辟一块儿新的空间，并且返回这块儿空间的地址。
下面是realloc的介绍
The realloc function changes the size of an allocated memory block. The memblock argument points to the beginning of the memory block. If memblock is NULL, realloc behaves the same way as malloc and allocates a new block of size bytes. If memblock is not NULL, it should be a pointer returned by a previous call to calloc, malloc, or realloc.
另外，这里要补充一点，我们的realloc是有可能开辟空间失败的，如果我的内存块儿不够你要求开辟的大小的话，realloc是会返回一个空指针NULL的，，所以我们加了一个分支语句的判断，如果开辟成功，我们就继续使用结构体中那些指针和capacity的名字，方便我们写后面的代码，因为命名没有换嘛，所以你会感觉舒服一下。
别看上面的代码有点多，其实就是注释多而已，总结一下其实就是，每次空间满了我们的capacity*2，然后realloc空间的大小，让这个空间按变为2倍。 另一个部分就是判断我们开辟空间是否成功，开辟成功，我们将命名重新回到结构体中的命名
所以就是两部分，1.开辟空间 2.判断空间是否开辟成功
void SLCheckCapacity(SL* ps)
{
if (ps->size == ps->capacity)
{
int newcapacity = ps->capacity == 0 ? 4 : ps->capacity * 2;
SLDataType* tmp = (SLDataType*)realloc(ps->array, newcapacity * sizeof(SLDataType));
if (tmp == NULL)
{
perror("realloc fail");
exit(-1);//直接终止程序，-1代表异常终止，0代表正常终止
}
else
{
ps->array = tmp;
ps->capacity = newcapacity;
}
}
}2.4.3 顺序表的尾插，尾删
void SLPushBack(SL* ps, SLDataType x);
void SLPopBack(SL* ps);
void SLPushBack(SL* ps, SLDataType x)
{
assert(ps);
SLCheckCapacity(ps);//检查是否需要扩容
ps->array[ps->size] = x;
ps->size++;
//SLInsert(ps, ps->size, x);//我们的SLInsert里面就有判断是否扩容的函数，所以直接调用SLInsert就可以了
}
void SLPopBack(SL*ps)
{
//温柔的检查
/*if (ps->size == 0)
{
return;
}*/
//暴力的检查
assert(ps->size > 0);//必须数组中有数据，我们才可以删除数据
//我们在程序运行的时候，会直接报错，将你的问题在debug版本下直接暴露出来，方便你解决处理问题
ps->size--;//将长度--，打印的时候就不会打印释放掉的元素了，循环次数-1
SLErase(ps, ps->size - 1);
}1.尾插：我们在插入数据之前，肯定要进行空间大小的检查，如果空间不够了，我们要进行扩容。因为这里是尾插，所以在数组下表为size的位置插入我们的数据x就可以了。这个接口也不难 2.尾删：尾删更简单，我们只要将访问的空间量-1就可以了，这样我们访问这块空间时，就会把最后一个元素忽略掉，不会去访问它，所以就是一句代码ps->size–; 这样就可以完成我们的尾删接口了，哈哈哈，感觉好简单啊，🤣🤣🤣，自己有点尴尬了都。
2.4.4 顺序表的头插，头删
void SLPushFront(SL* ps, SLDataType x)
//这里我们头插时，需要挪动数组，因为从前往后挪动会覆盖掉我们后面的元素，所以我们从后往前一个一个向后挪动数组元素，
//给头部留出位置
{
assert(ps);
SLCheckCapacity(ps);//检查是否需要扩容
//挪动数据
int end = ps->size - 1;
while (end >= 0)
{
ps->array[end+1] = ps->array[end];
end--;
}
ps->array[0] = x;
ps->size++;
//SLInsert(ps, 0, x);
}
void SLPopFront(SL* ps)
{
//道理相同，如果我们从后往前挪动数据的话，必然后一个数据会覆盖掉前一个数据的，所以我们这里采用从前往后挪动的方法
//直接用第一个数据后面的数据将第一个覆盖掉，这样正好就使得数组的第一个元素无效了，我们也就无法访问到这一元素了，正好
//满足了我们的需求,我们也需要一个begin指向下标
assert(ps->size > 0);//必须数组中有数据，我们才可以删除数据
int begin = 1;//从第二个元素开始往前挪动元素
while (begin<ps->size)
{
ps->array[begin - 1] = ps->array[begin];
begin++;
}
ps->size--;
//SLErase(ps, 0);
}1.头插：我们要在数组头部插入一个数据的话，其实是需要挪动整个数组中的数据内容的，我们需要将每一个数据的位置向后挪动一个下标。但是我们怎么挪动呢，从前向后挪动？这样的话，后面的元素不久被覆盖掉了？所以这样是不行的，我们要从后往前遍历，这样就很好避免了挪动数据时后面元素丢失的问题了。有了思路后，怎么实现呢？也很简单。我们做一个while循环就好了，定义一个end下标，将这个end从后往前遍历，依次将数组元素向后挪动即可。
要注意我们增加元素的第一步是要想到，空间是否满了，没满就插入数据，满了我们就扩容。也就是对空间大小进行检查。
2.头删：头删需要注意的一个问题是，我么又要挪动整个顺序表里面的元素，将所有元素的下标都-1，向前挪动一位。这回就是从前往后遍历了，因为从后往前挪动的话，前面的数据又会被覆盖掉，所以我们又定义了一个下标为begin的变量，从下标为1，也就是第二个元素，将每个元素都往前挪动一位，这样也就完成了我们的PopFront接口的实现
2.4.5 顺序表的查找
int SLFind(SL* ps, SLDataType x)
{
assert(ps);
for (int i = 0; i < ps->size; i++)
{
if (ps->array[i] == x)
{
return i;
}
}
return -1;
}查找：这个接口的实现也是比较简单的，我们只需要将整个顺序表遍历一遍，遇到我们要找的元素我们就返回此时顺序表中这个元素的下标，如果遍历之后发现没有我要找的元素，就返回-1
2.4.6 对任意位置进行删除和插入数据
void SLInsert(SL* ps, int pos, SLDataType x)
{
assert(pos >= 0 && pos <= ps->size);
SLCheckCapacity(ps);
int end = ps->size - 1;
//进行挪动数据
while (end >= pos)
{
ps->array[end + 1] = ps->array[end];
end--;
}
//插入我们的数据
ps->array[pos] = x;
ps->size++;
}
void SLErase(SL* ps, int pos)
{
assert(pos >= 0 && pos < ps->size);
int begin = pos + 1;
while (begin < ps->size)
{
ps->array[begin - 1] = ps->array[begin];
begin++;
}
ps->size--;
}其实无论是删除还是插入数据，我们都需要面临一个问题，就是数据的挪动，因为不管是插入还是删除，我们都改变了这个顺序表原来的有序结构，改变了结构之后，我们又想恢复它这种有序的特性，那只能进行数据的挪动了，如果插入的位置靠后，我们挪动的数据个数也就会偏少，如果插入的位置越靠前，我们挪动的数据个数就越多，付出的代价也越大。
1.插入：这里用到的思想和之前的头插思想，没有什么两样，一个是将所有的数据进行了挪动，一个就是将部分的数据进行挪动。我们只需要加一个控制条件就好了，这样就可以控制我们挪动数据的个数了。
具体的实现也是定义了一个end下边的变量，让这个下标在遇到pos位置时就停下来挪动，这样就可以完成我们的任意位置插入的接口了
2.删除：删除的思想和插入的思想是比较类似的，我们只要从pos位置开始，将后面的元素都往前挪动一位，这样也就实现了我们的任意位置删除的接口了。
具体的代码实现也是定义了一个begin的变量，让他从pos+1的位置开始，将后面的元素都往前挪动就完事了，注意好下标之间的关系，这个接口也就顺利实现了。
三、三道力扣题
3.1 leetcode1. 移除元素
我们其实可以利用双指针的思想来解决这道题，就是找那么一个先驱指针往前遍历，不是value的话，我们就将这个值给到我们的dst位置，如果恰好是value，我们就让这个先驱指针src++，注意找到不是value的元素将src赋值到dst之后，src和dst都要++，其目的就是要保证dst之前的所有元素都是非value的，然后我们返回dst的值，这样数组里面的value就都会被我们过滤掉了。dst之前的所有元素都是非value的了。 下面就是我们的代码实现
int removeElement(int* nums, int numsSize, int val)
{
int src = 0;
int dst = 0;
while (src < numsSize)
{
if (nums[src] != val)
{
nums[dst] = nums[src];
src++;
dst++;
}
else
src++;
}
return dst;
}3.2 leetcode2删除有序数组中的重复项
方法一：双指针
int removeDuplicates(int* nums, int numsSize)
{
if (numsSize <= 1)
return numsSize;
int src = 1;
int dst = 0;
while (src < numsSize)
{
while (nums[dst] == nums[src])
{
src++;
if (src >= numsSize)
//判断是否越界，如果在while循环里面越界，只能说明这个数组全是相同元素
{
return dst + 1;
}
}
dst++;
nums[dst] = nums[src];
src++;
}
return dst + 1;
}双指针的核心思想还是没有变，我们还是用一个先驱指针，去向前遍历我们的数组，遇到和dst相等的元素，我们就向后遍历，其思想保证的标准还是dst之前的元素中是没有重复项的，然后我们返回正确的没有重复项的有序数组的长度，这样系统后端进行用例测试时，for循环输出，输出次数为我们的返回值，他就可以输出一个完美的没有重复项的数组。
值得注意的是，在我们循环去找没有重复项的元素时，是有可能出现越界访问的情况的，所以我们要判断一下，如果在我们的while循环里边src遍历数组出现越界情况时，我们就知道后面的dst到src之内的元素都是重复项，那么我们直接返回dst+1就可以了。
方法三：三指针
int removeDuplicates(int* nums, int numsSize)
{
int begin = 0;
//这个算法就是用begin和end去遍历一段相同的数，直到两者不相等，然后把begin给到dst，dst+1，需要额外判断的情况就是
//当end越界之后，我们有最后一步操作就是，把begin的值给到dst
int end = 1;
int dst = 0;
if (numsSize <= 1)
return numsSize;
while (end < numsSize)
{
if (nums[begin] == nums[end])
{
end++;
}
else
{
nums[dst] = nums[begin];
begin = end;
dst++;
end++;
}
}
//end越界之后，我们还需要，将begin中的数据在赋值给下标是dst的数据当中，这是最后一步
nums[dst] = nums[begin];
dst++;
return dst;
}这个算法与第一个算法在思想上其实是差别不大的，第一个算法是将dst作为要返回的值，让src作为一个先驱指针去进行遍历数组，而第二个算法就是用begin去寻找重复段，过了这个重复段，我们就将begin下标的值给到我们要返回的dst。
其实我个人觉得，还是双指针好用一些，这个三指针有点难想，不过这种思想还是很不错的，应该以欣赏的眼光去看待。
3.3 leetcode3合并两个有序数组
题目的意思是什么呢？他其实就是想把两个升序的有序数组的内容进行合并，合并为一个升序的数组，如果有相同的元素，我们就依次往后排就可以了。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n)
{
int end1 = m - 1, end2 = n - 1;
int end = m + n - 1;
while (end1 >= 0 && end2 >= 0)
{
if (nums1[end1] > nums2[end2])
{
nums1[end--] = nums1[end1--];
// end1--;
// end--;
}
else
{
nums1[end--] = nums2[end2--];
// end--;
// end2--;
}
}
while (end2 >= 0)//如果end2遍历完我们什么也不用干，因为end1中放的就是他自己
{
nums1[end--] = nums2[end2--];
// end2--;
}
}这个代码的思想是什么呢？其实还是和我们顺序表的实现非常相似，如果你对顺序表的实现掌握的非常熟练的话，这些题目其实就是实现顺序表中思想的一种变形，所以我们还是要好好写代码，认真的自己去实现代码，要不然真就是个纯纯码农了，哈哈哈！
回到正题上来，咳咳！有点跑题了。
我们还是利用的避免覆盖数组中元素的这样一种思想，就是我们乳沟从前往后去比较这两个数组中的而元素，然后进行较小元素的赋值的话，还是会出老毛病，就是我们后面的元素会被前面的元素覆盖掉，所以我们换一种策略，从后往前去遍历我们这两个数组，将较大元素挑出来放到nums1中，要记住我们放也是从nums1中后面的位置开始放。
这样的话，假设我们的nums2数组遍历全都遍历完了，此时说明nums2中的任一元素都大于nums1中的元素，所以跳出循环后我们什么也不用干。 但如果nums1遍历完了的话，我们就再多做一个循环就好，将nums2中的元素放到nums1中就可以了。
四、顺序表总结，单链表起头。
今天的学习就到这里了，我们总结一下顺序表吧那就😎
顺序表我们其实可以将他理解为一个连续数组，其中存放了我们的数据，值得注意的是，顺序表的一大特点就是他是按照顺序连续存放的，并且也是存放在一块儿连续的物理空间当中，当然我们可以看出来顺序表存在不少的问题，比如插入个数据还得挪动其他数据等等，这都会造成很大的代价，所以下一篇博客我们来来聊聊针对顺序表缺陷，设计出来的单链表吧，单链表相对于顺序表还是要高级不少的，不过我们还是要先把顺序表的基础打好，然后再去学链表，这样更加好理解一些。