数据结构与算法03 顺序表+链表
注意点：
- 函数的定义中建议增加断言：结构体指针不能为NULL！（空指针不能接引用！）
- 控制台退出后显示的代码只要不为0，就不是正常退出！
- Vs中编辑 -> 高级 -> 查看空白 可以查看是空格还是TAB！
- assert(0 <= pos <= ps->size)不允许这样子写！
- assert(pos >= 0 && pos <= ps-> size)
- 缩容指的是释放部分内存，这种方法不行！内存只能整块申请，整块一起释放！
复杂度比较：
- 头插 / 头删 N个数据的时间复杂度为：O(N^2)
- 尾插 / 头删 N个数据的时间复杂度为：O(N)
有了中间插入（中间删除）之后，那么头插和尾插（头删和尾删）也就是中间插的另一种形式！
- 头插法也就是insert在ps->0位置处插入数据；
- 尾插法也就是insert在ps->size位置处插入数据；
- 头删法也就是insert在ps->0位置处删除数据；
- 尾删法也就是insert在ps->size位置处删除数据；
realloc分为两种：原地扩容和异地扩容！
原地扩容：后面的空间没有分配给其他位置！（原地扩容效率非常高！）
异地扩容：找一块空间更大的满足条件的内存空间，将内容拷贝进去，再将原来的空间释放掉！
int main()
{void* ps1 = malloc(10);printf("%p\n", ps1);void* ps2 = realloc(ps1,20);printf("%p\n", ps2);return 0;
}
地址相同！这时即为原地扩容！
int main()
{void* ps1 = malloc(10);printf("%p\n", ps1);void* ps2 = realloc(ps1,200);printf("%p\n", ps2);return 0;
}
此时为异地扩容！
如果realloc申请的空间比malloc申请的小！（官网解释说一般会移动至一个新的空间），但是此时编译器的地址往往不变！
void* ps1 = malloc(10);printf("%p\n", ps1);void* ps2 = realloc(ps1,200);printf("%p\n", ps2);void* ps3 = realloc(ps2, 5);printf("%p\n", ps3);
可以通过访问空间来验证：
当i = 5的时候，访问会报错，说明申请的空间从20 - 5的时候，虽然地址不变，但是使用权从20个变成5个！
释放时只能全部释放：如果只能释放一部分，那么后面的空间有可能被其他程序使用，此时扩容只能异地扩容 --- >>> 效率降低！
注意点：如果需要写菜单，需要保证之前写的函数的验证没有错误！（在菜单界面中不容易验证函数代码）
练习一：移除数据
. - 力扣（LeetCode）
要求时间复杂度为O(N);
空间复杂度为O(1);
解法一：双指针(在原数组上进行修改)
解法：
int removeElement(int* nums, int numsSize, int val) {int src = 0;int dst = 0;while(src <= numsSize-1){if (nums[src] != val)nums[dst++] = nums[src++];elsesrc ++;}return dst;
}练习二：去重
删除有序数组中的重复项，保留一个1
. - 力扣（LeetCode）
代码如下：
int removeDuplicates(int* nums, int numsSize) {int src = 1;int dst = 0;while(src < numsSize){if (nums[dst] == nums[src]){src ++;}else{nums[++dst] = nums[src++];}}return (dst+1);
}练习三、合并两个有序数组
. - 力扣（LeetCode）
解法一：逆向双指针
合并后的元素一共有m+n个，因此dst的坐标为(m+n-1) !
出循环后说明end1和end2比然后一个结束！但是如果是end2结束，那么num1前面的数字不需要进行修改！因此只需要多考虑end2还没有结束的情况！
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; // 合并后的数组共有m+n-1个有效数字while(end1 >=0 && end2 >=0) // 两种情况只要有一种即可{if (nums1[end1] < nums2[end2]){nums1[dst--] = nums2[end2--];}else{nums1[dst--] = nums1[end1--];}}while (end2 >= 0){nums1[dst--] = nums2[end2--];}}顺序表总结：
1、中间头部插入删除数据，效率低下；
2、空间不够，需要扩容，但是扩容会有一点的时间消耗，且在空间上可能造成一定的空间浪费！