【编织时空一：探究顺序表与链表的数据之旅】（上）：https://developer.aliyun.com/article/1424867
顺序表查找：int SeqListFind(SeqList* s, SLDataType x);
顺序表有顺序存取的功能，因此按位查找元素可以直接通过数组下标定位取得。
// 顺序表查找 int SeqListFind(SeqList* s, SLDataType x) { for (int i = 0; i < s->size; i++) { if (s->a[i] == x) return i; } return -1; }
顺序表在pos位置插入x：void SeqListInsert(SeqList* s, size_t pos, SLDataType x);
顺序表的元素插入和插队是一个意思的。想象一下，有一个人要插队，他要插到第3个位置去，那么他前面的两个人不用动，而他后面的人都得动。具体步骤是：最后面的那个人后退一个位置，倒数第二个人后退到原来最后一个人的位置，这样子后面的每个人依次后退，最后就空出来了一个位置，这个人就插队进去了。顺序表也是这么插入的。在插入操作完成后表长+1（多了一个人）。
元素插入有一些要求：
- 元素下标是否越界（有没有插队到奇怪的位置）
- 顺序表存储空间是否满了（有没有位置让你插队）
// 顺序表在pos位置插入x void SeqListInsert(SeqList* s, size_t pos, SLDataType x) { //检查pos是否合法 assert(pos >= 0 && pos <= s->size); //检查是否需要扩容 CheckCapacity(s); int end = s->size - 1; while (end >= pos) { s->a[end + 1] = s->a[end]; end--; } s->a[pos] = x; s->size++; }
顺序表删除pos位置的值：void SeqListErase(SeqList* s, size_t pos);
删除和插入的操作类型，这里借用插队的例子说明。一群人在排队，有一个人有事临时走了，那么这个人的位置就空出来了，后面的人就一个个往前一步，补上这个空位。在删除操作完成后表长-1（少了一个人）。
元素删除有一些要求：
- 元素下标是否越界（走的人是不是这个排队里面的人）
- 顺序表存储空间是否为空（有没有人可以走）
// 顺序表删除pos位置的值 void SeqListErase(SeqList* s, size_t pos) { //检查pos是否合法 assert(pos >= 0 && pos < s->size); int begin = pos; while (begin < s->size - 1) { s->a[begin] = s->a[begin + 1]; begin++; } s->size--; }
顺序表销毁：void SeqListDestory(SeqList* s);
顺序表初始化的时候是用malloc函数向系统申请的空间，malloc函数申请的空间是在内存的堆区，堆区的空间不会被系统自动回收，还需要用free函数释放空间。与malloc一样，要引头文件#include<stdlib.h>。
// 顺序表销毁 void SeqListDestory(SeqList* s) { free(s->a);//释放开辟的空间 s->a = NULL; s->size = 0; s->capicity = 0; }
顺序表打印：void SeqListPrint(SeqList* s);
// 顺序表打印 void SeqListPrint(SeqList* s) { for (int i = 0; i < s->size; i++) { printf("%d ", s->a[i]); } printf("\n"); }
修改顺序表pos位置的值
// 修改顺序表pos位置的值 void SeqListModify(SeqList* s, size_t pos, SLDataType x) { assert(pos >= 0 && pos < s->size); //修改pos位置的值 s->a[pos] = x; }
3.顺序表OJ题
1. 原地移除数组中所有的元素val，OJ链接：https://leetcode.cn/problems/remove-element/
思路一：暴力解法
这个题目暴力的解法就是两层for循环，一个for循环遍历数组元素 ，第二个for循环更新数组。
删除过程如下：
int removeElement(int* nums, int numsSize, int val) { int size = numsSize; for (int i = 0; i < size; i++) { if (nums[i] == val) { // 发现需要移除的元素，就将数组集体向前移动一位 for (int j = i + 1; j < size; j++) { nums[j - 1] = nums[j]; } i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位 size--; // 此时数组的大小-1 } } return size; }
- 时间复杂度：O(n^2)
- 空间复杂度：O(1)
思路二：双指针法（快慢指针法）： 通过一个快指针和慢指针在一个whiler循环下完成工作。
定义快慢指针
- 快指针：寻找新数组的元素 ，新数组就是不含有目标元素的数组
- 慢指针：指向更新 新数组下标的位置
删除过程如下：
int removeElement(int* nums, int numsSize, int val) { int fastindex = 0; int slowindex = 0; while (fastindex < numsSize) { if (nums[fastindex] != val) { nums[slowindex++] = nums[fastindex++];//赋值 } else { fastindex++;//发现需要移除的元素，就将指针向后移动一位 } } return slowindex; }
- 时间复杂度：O(n)
- 空间复杂度：O(1)
2. 删除排序数组中的重复项，OJ链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
int removeDuplicates(int* nums, int numsSize) { int src = 1; int dest = 0; while(src< numsSize) { if (nums[src] == nums[dest]) { src++; } else { dest++; nums[dest] = nums[src]; src++; } } return dest + 1; }
3. 合并两个有序数组，OJ链接：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 end = m + n- 1; while (end1 >= 0 && end2 >= 0) { if (nums1[end1] < nums2[end2]) nums1[end--] = nums2[end2--]; else nums1[end--] = nums1[end1--]; } while (end2 >= 0) nums1[end--] = nums2[end2--]; }
