【数据结构】 顺序表

1 线性表

线性表（linear list）是n个具有相同特性的数据元素的有限序列。线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串…

线性表在逻辑上是线性结构，也就是说是连续的一条直线。但是在物理结构上不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式存储。

2 顺序表

那么今天我们首先来学习顺序表，然后再学习链表，有一个循序渐进的效果

2.1 概念及结构

顺序表是用一段物理地址连续的存储单元依次存储数据元素的线性结构，一般情况下采用数组存储。在数组上完成数据的增删查改。
顺序表一般可以分为：

1. 静态顺序表：使用定长数组存储元素。
   
   这种顺序表空间固定，那么存储到一定数量时就不能存储，不太方便

2. 动态顺序表：使用动态开辟的数组存储
   
   动态开辟就很好解决了空间不够的问题。

2.2 接口实现

静态顺序表只适用于确定知道需要存多少数据的场景。
静态顺序表的定长数组导致N定大了，空间开多了浪费，开少了不够用。
所以现实中基本都是使用动态顺序表，根据需要动态的分配空间大小，所以下面我们实现动态顺序表。

//那么我们先来实现接口函数#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<string.h>
typedef int SLDataType;
#define INIT_CAPACITY 4typedef struct SeqList//顺序表的创建
{SLDataType* s;//作为动态数组来初始化int size;//元素个数应该为正数int capacity;//初始容量大小
}SL;
//写接口函数时，要想我们对顺序表有什么操作？void SLInit(SL* ps);//顺序表的初始化
void SLDestroy(SL* ps);//顺序表的销毁
void SLPrint(SL* ps);//打印顺序表
void SLCheckCapacity(SL* ps);//检查容量是否充足
void SLPushBack(SL* ps, SLDataType x);//在尾部插入数据
void SLPopBack(SL* ps);//在尾部删除数据
void SLPushFront(SL* ps, SLDataType x);//在首部插入数据
void SLPopFront(SL* ps);//在首部删除数据
void SLInsert(SL* ps, int pos, SLDataType x);//在中间插入某个数据
void SLErase(SL* ps, int pos);//删除中间某个数据
int SLSearch(SL* ps, SLDataType x);//寻找某个元素并且返回下标

写完接口函数时，就要实现函数了
注意：在写代码时，最好写完一个接口函数就要进行调试，这样找错误就很方便。

//首先是对顺序表的初始化
void SLInit(SL* ps)
{assert(ps);//进行断言，ps指向的对象不为空ps->s = (SLDataType*)malloc(sizeof(SLDataType) * INIT_CAPACITY);//malloc开辟空间时，后面要考虑开辟失败的情况，要进行检查if (ps->s == NULL){perror("malloc fail");return;}ps->size = 0;//初始化没有元素ps->capacity = INIT_CAPACITY;//进行初始化
}

//打印顺序表
void SLPrint(SL* ps)
{assert(ps);//如果是空的顺序表就不能打印int i = 0;for (i = 0; i < ps->size; i++){printf("%d ", ps->s[i]);}printf("\n");//打印完换行
}

//进行容量检查
void SLCheckCapacity(SL* ps)
{assert(ps);//判断为不为空顺序表if (ps->size == ps->capacity)//在进行尾部插入数据时要先判断空间够不够，不够要进行扩容{SLDataType* ptr =(SLDataType*)realloc(ps->s, sizeof(SLDataType) * ps->capacity * 2);//这里使用新的指针是因为如果开辟失败返回空指针，就不会影响到原来开辟的内存空间if (ptr == NULL){perror("realloc fail");return;}ps->s = ptr;//开辟成功将新开辟空间的指针赋给原来的指针ps->capacity *= 2;//因为空间扩大了两倍，那么容量也要扩大两倍}
}

//进行尾部插入数据
void SLPushBack(SL* ps, SLDataType x)
{assert(ps);//断言可以找到问题SLCheckCapacity(ps);//尾部插入要判断最后一个元素有没有空间，没有则开辟ps->s[ps->size] = x;//将数据赋给最后一个元素ps->size++;//同时将元素个数加一//SLInsert(ps, ps->size, x);//这个函数先不用管，后面会讲
}

//进行头部插入数据
void SLPushFront(SL* ps, SLDataType x)
{assert(ps);//判断为不为空SLCheckCapacity(ps);//判断容量够不够for (int i = ps->size - 1; i >= 0; i--){ps->s[i + 1] = ps->s[i];//将所有的数往后移一位}ps->size++;//元素要加一ps->s[0] = x;//进行赋值//SLInsert(ps, 0, x);//后面会讲
}

//进行尾部删除
void SLPopBack(SL* ps)
{assert(ps);//判断不为空assert(ps->size > 0);//判断顺序表中有没有元素ps->size--;//直接删除一个元素
}

//进行头部删除
void SLPopFront(SL* ps)
{assert(ps);//判读为不为空assert(ps->size > 0);//当这个数组是空的，size就为负数了//那么头部删除就可以进行覆盖，可以用memmove函数；也可以进行一个一个覆盖int begin = 0;for (begin = 1; begin <= ps->size - 1; begin++){ps->s[begin - 1] = ps->s[begin];//后一个将前一个进行覆盖}ps->size--;//让元素减一
}

//进行插入数据
void SLInsert(SL* ps, int pos, SLDataType x)//这个插入包括了头插和尾插，所以可以进行复用
{assert(ps);//判断为不为空assert(pos >= 0 && pos <= ps->size);//判断指定下标要合法，等于0就是要头插，等于ps->size就是要尾插SLCheckCapacity(ps);//检查容量是否充足int end = ps->size - 1;while (end >= pos){ps->s[end + 1] = ps->s[end];end--;//往后一个一个赋值}ps->s[pos] = x;//最后在pos位置赋值为xps->size++;//元素个数加一
}

//进行删除元素
void SLErase(SL* ps, int pos)
{assert(ps);//判断为不为空assert(pos >= 0 && pos < ps->size);//判断位置要合法int begin = pos + 1;while (begin < ps->size){ps->s[begin - 1] = ps->s[begin];++begin;//一个一个往前覆盖}ps->size--;//元素要减一
}

//进行元素的查找，找到了则返回下标，没找到则返回-1
int SLSearch(SL* ps, SLDataType x)//返回元素下标，要有返回值
{assert(ps);//判断为不为空for (int i = 0; i < ps->size; i++){if (ps->s[i] == x)return i;//进行循环查找，找到了就返回下标}return -1;//循环结束代表没找到，返回-1表示没找到
}

//最后进行顺序的销毁
void SLDestroy(SL* ps)//销毁顺序表时，要释放内存，并且将指针设为空
{assert(ps);//判断为不为空free(ps->s);//释放指针所指向的内存空间ps->s = NULL;//同时将指针置为空ps->size = ps->capacity = 0;//元素和容量置为0
}

注意：在进行传参数时，如果要改变所指向的内容，就要传地址过去，不要传值过去，切记！！！

2.3 数组相关面试题

顺序表的内容完成后，那么接下来就要写写题目来巩固能力了

1. 原地移除数组中所有的元素val，要求时间复杂度为O(N),空间复杂度O(1)。
   https://leetcode.cn/problems/remove-element/

//首先我们可以将元素覆盖的方式去写。
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];//如果不等于元素不相等，那么将dst加一，src也加一}src++;//如果相等，只有src加一，dst不加一，等下个元素进行覆盖}return dst;//最后返回数组的新长度
}//也可以这样写
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哪种情况都要加一}else{src++;}}return dst;
}
//![动图描述](https://img-blog.csdnimg.cn/8c7e4339443448fc9930d677b4f59539.gif#pic_center)

2. 删除排序数组中的重复项。
   https://leetcode.cn/problems/remove-duplicates-from-sorted-array/

//这道题目和上一个思路差不多，每个数字之只能出现一次，返回数组的新长度
//我们使用快慢指针
int removeDuplicates(int* nums, int numsSize){int src = 1;//让src为1int dst = 0;while (src < numsSize){if (nums[dst] == nums[src]){src++;//两个数相等就src加1}else{nums[++dst] = nums[src++];//不相等就进行赋值}}return dst + 1;//最后返回dst+1
}//结合图片进行理解
//![动态理解](https://img-blog.csdnimg.cn/0d82014700df493184df034d7e3de84d.gif#pic_center)

3. 合并两个有序数组
   https://leetcode.cn/problems/merge-sorted-array/

//这里的非递减是可能递增也可能相等
//这里我们可以从头一个一个比较，小的放前面，大的放后面，但这样比较实在麻烦。换个角度，如果从后面开始放就会方便很多。
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){int end1 = m - 1;//作为最后一个元素比较int end2 = n - 1;int dst = m + n - 1;while (end1 >= 0 && end2 >= 0){if (nums2[end2] > nums1[end1]){nums1[dst--] = nums2[end2--];//如果大，那么num2放元素}else{nums1[dst--] = nums1[end1--];//如果小，那么num1放元素}}while (end2 >= 0)//这里判断end2，如果还有元素，依次放上去//不判断end1的原因是num1的元素就在num1中，不用进行移植{nums1[dst--] = nums2[end2--];}
}
//结合动态理解!(https://img-blog.csdnimg.cn/7a9667b48f7d40e48155cfb77ec0dd45.gif#pic_center)

以上题目希望可以加深和理解顺序表

2.4 顺序表的问题与思考

问题：

1. 中间/头部的插入删除，时间复杂度为O(n)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到200，我们在再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。

如何解决以上问题呢？那就要使用链表了！！！

这次我们学习了顺序表，下次学习链表，希望各位学习永无止境！！！o_O

晚风庭院落梅初。淡云来往越疏疏。–李清照