四、完整代码
1、SeqLIst.h
#pragma once //防止头文件重复包含 //头文件的包含 #include <stdio.h> #include <stdlib.h> #include <assert.h> //符号与结构的定义 #define DEF_SIZE 5 //初始容量 #define CRE_SIZE 2 //一次扩容的倍数 typedef int SLDataType; //将数据类型重命名为SLDataType typedef struct SeqList { SLDataType* data; //对应数据类型的指针，用来指向动态开辟的空间 size_t size; //记录当前有效数据的个数 size_t capacity; //记录当前容量，不够就增容 }SL; //函数的声明 //初始化顺序表 void SeqListInit(SL* psl); //在尾部插入数据 void SeqListPushBack(SL* psl, SLDataType x); //在头部插入数据 void SeqListPushFront(SL* psl, SLDataType x); //在尾部删除数据 void SeqListPopBack(SL* psl); //在头部删除数据 void SeqListPopFront(SL* psl); //在指定下标处插入数据 void SeqListInsert(SL* psl, size_t pos, SLDataType x); //在指定下标处删除数据 void SeqListErase(SL* psl, size_t pos); //查找数据 int SeqListFind(const SL* psl, SLDataType x); //修改指定位置数据 void SeqListModify(SL* psl, size_t pos, SLDataType x); //打印顺序表中的数据 void SeqListPrint(const SL* psl); //检查容量(增容) void CheckCapacity(SL* psl); //销毁顺序表 void SeqListDestory(SL* psl);
2、SeqList.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" //初始化顺序表 void SeqListInit(SL* psl) { assert(psl); //断言：防止psl为空 psl->data = (SLDataType*)calloc(DEF_SIZE, sizeof(SLDataType)); //开辟默认大小的空间并初始化 if (psl == NULL) //判空 { perror("calloc fail"); //打印错误信息 return; } psl->size = 0; psl->capacity = DEF_SIZE; } //销毁顺序表 void SeqListDestory(SL* psl) { assert(psl); //断言：防止psl为空 free(psl->data); //释放（避免内存泄漏） psl->data = NULL; //置空（避免野指针） psl->size = 0; psl->capacity = 0; } //检查容量（增容） void CheckCapacity(SL* psl) { assert(psl); //断言：防止psl为空 if (psl->size == psl->capacity) //当数据个数和容量相等时扩容 { //将realloc的返回值交由一个临时变量保存，防止扩容失败丢失原来空间的地址 SLDataType* ptr = (SLDataType*)realloc(psl->data, psl->capacity * CRE_SIZE * sizeof(SLDataType)); if (ptr == NULL) //判空 { perror("realloc fail"); return; } psl->data = ptr; psl->capacity *= CRE_SIZE; //增加容量 } } //在尾部插入数据 void SeqListPushBack(SL* psl, SLDataType x) { assert(psl); SeqListInsert(psl, psl->size, x); //直接调用insert函数 //assert(psl); //判空 //CheckCapacity(psl); //检查容量 //psl->data[psl->size] = x; //插入数据 //psl->size++; } //在头部插入数据 void SeqListPushFront(SL* psl, SLDataType x) { assert(psl); SeqListInsert(psl, 0, x); //直接调用insert函数 //assert(psl); //判空 //CheckCapacity(psl); //检查容量 //int i = 0; //for (i = psl->size - 1; i >= 0; i--) //{ // psl->data[i + 1] = psl->data[i]; //将数据整体向后移 //} //psl->data[0] = x; //插入数据 //psl->size++; } //打印顺序表中的数据 void SeqListPrint(const SL* psl) { assert(psl); //判空 size_t i = 0; for (i = 0; i < psl->size; i++) { printf("%d ", psl->data[i]); } printf("\n"); } //在尾部删除数据 void SeqListPopBack(SL* psl) { assert(psl); SeqListErase(psl, psl->size - 1); //直接调用Erase函数 //assert(psl); //assert(psl->size); //psl->size--; //如果尾部有数据，直接让size--即可 } //在头部删除数据 void SeqListPopFront(SL* psl) { assert(psl); SeqListErase(psl, 0); //直接调用Erase函数 //assert(psl); //assert(psl->size); //size_t i = 0; //for (i = 0; i < psl->size - 1; i++) //{ // psl->data[i] = psl->data[i + 1]; //让表中的数据依次往前移 //} //psl->size--; } //查找数据 int SeqListFind(const SL* psl, SLDataType x) { assert(psl); int i = 0; for (i = 0; i < (int)psl->size; i++) { if (psl->data[i] == x) return i; //找到元素所在返回下标 } return -1; //找不到返回-1（一个无效下标） } //修改指定位置的数据 void SeqListModify(SL* psl, size_t pos, SLDataType x) { assert(psl); assert(pos < psl->size); //断言 psl->data[pos] = x; //修改数据 } //在指定下标处插入数据 void SeqListInsert(SL* psl, size_t pos, SLDataType x) { assert(psl); assert(pos <= psl->size); //断言 因为可能会在尾部插入数据，所以pos可以等于size CheckCapacity(psl); //检查容量 size_t end = psl->size; while (end > pos) //把pos及以后的数据向后挪动一位 { psl->data[end] = psl->data[end - 1]; --end; } psl->data[pos] = x; //插入数据 ++psl->size; } //在指定下标处删除数据 void SeqListErase(SL* psl, size_t pos) { assert(psl); assert(pos < psl->size); size_t i = 0; for (i = pos; i < psl->size - 1; i++) { psl->data[i] = psl->data[i + 1]; } psl->size--; }
3、test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "SeqList.h" void test1() //测试插入 { //初始化 SL sl; SeqListInit(&sl); //尾插 SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); SeqListPrint(&sl); //头插 SeqListPushFront(&sl, 8); SeqListPushFront(&sl, 9); SeqListPushFront(&sl, 10); SeqListPrint(&sl); //在指定位置插入 SeqListInsert(&sl, 3, 6); SeqListInsert(&sl, 0, 6); SeqListInsert(&sl, 9, 6); SeqListPrint(&sl); //销毁 SeqListDestory(&sl); } void test2() //测试删除 { //初始化 SL sl; SeqListInit(&sl); //尾插 SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); SeqListPrint(&sl); 尾删 //SeqListPopBack(&sl); //SeqListPopBack(&sl); //SeqListPopBack(&sl); //SeqListPrint(&sl); 头删 //SeqListPopFront(&sl); //SeqListPopFront(&sl); //SeqListPopFront(&sl); //SeqListPrint(&sl); //删除指定位置元素 SeqListErase(&sl, 3); SeqListPrint(&sl); SeqListErase(&sl, 1); SeqListPrint(&sl); SeqListErase(&sl, 0); SeqListPrint(&sl); //销毁 SeqListDestory(&sl); } void test3() //测试查和改 { //初始化 SL sl; SeqListInit(&sl); //尾插 SeqListPushBack(&sl, 1); SeqListPushBack(&sl, 2); SeqListPushBack(&sl, 3); SeqListPushBack(&sl, 4); SeqListPrint(&sl); //查找并修改 int find = 0; int modify = 0; do { scanf("%d", &find); //要查找的元素 scanf("%d", &modify); //要修改的值 int pos = SeqListFind(&sl, find); //查找该元素是否存在 if (pos != -1) { SeqListModify(&sl, pos, modify); //存在就修改 } SeqListPrint(&sl); } while (find != EOF); //销毁 SeqListDestory(&sl); } //测试函数 int main() { //test1(); //测试插入 //test2(); //测试删除 test3(); //测试查和改 return 0; }
大家也可以去我的 Gitee 仓库中获取完整代码：SeqList/SeqList · 野猪佩奇/日常学习 - 码云 - 开源中国 (gitee.com)
五、顺序表的缺陷
顺序表存在如下缺陷：
在头部/中间的插入与删除需要挪动数据，时间复杂度为O(N)，效率低；
增容需要申请新空间，可能会拷贝数据，释放旧空间，会有不小的消耗；
增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到 200，如果我们再继续插入了5个数据，后面没有数据插入了，那么会浪费95个数据空间；
针对顺序表存在的这些缺陷，我们设计出了链表。
六、顺序表力扣OJ题
1、移除元素
题目链接
题目描述
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
思路分析
思路1 – 循环遍历，挪动覆盖数据：遍历这个数组，每当遇见等于val的元素时，就将数组后面的元素整体向前挪动一位。
时间复杂度：O(N^2) 空间复杂度：O(1)。
思路2 – 遍历数组，挪动元素到新空间：开辟一个新的数组，然后遍历原来的数组，将不等于val的元素放入新开辟的数组中，将等于val的元素丢弃；最后让新开辟的数组覆盖掉原数组。
时间复杂度：O(N) 空间复杂度：O(N)。
思路3 -- 遍历数组，挪动覆盖数据（双指针解法）：定义两个指针src 和 dst，最开始都指向数组第一个元素，然后开始遍历数组；如果arr[src] != val，那么让arr[dst] = arr[src]，然后 src++，dst++；如果 arr[src]==val，则 src++，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++]; } else { src++; } } return dst; }
2、删除有序数组中的重复项
题目链接
26. 删除有序数组中的重复项 - 力扣（LeetCode）
题目描述
给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
思路分析
这道题的解题思路和上面的移除元素十分相似，都是使用双指针；让 src 和 dst 都指向数组第一个元素，然后判断 arr[src] 和 arr[dst] 是否相等，如果相等，说明是重复元素，则让 src++，dst 不动；如果不相等，就让dst++，然后将 arr[src] 赋给 arr[dst]，再让 src++；然后一直往后遍历数组，直到将数组遍历完。
时间复杂度：O(N) 空间复杂度：O(1)
代码实现
int removeDuplicates(int* nums, int numsSize){ int src = 0; int dst = 0; while(src < numsSize) { if(nums[src] != nums[dst]) { nums[++dst] = nums[src++]; //注意：dst是前置++ } else { src++; } } return dst+1; //由于dst是前置++，所以返回值需要+1 （数组下标从0开始） }
3、合并两个有序数组
题目链接
题目描述
给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。
注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。
思路分析
思路1：开辟新数组，并排序：我们可以将两个数组中的元素存放到一个新数组中，然后对数组中的元素进行排序，最后用新数组的数据覆盖掉原数组的数据。
时间复杂度：O((M+N)*log(M+N)) (使用qsort进行排序) 空间复杂度：O(1)。
思路2：开辟新数组，把数据有序的放入数组中（双指针法）：因为两个原数组都是有序的，所以我们可以用两个指针 src1 和 src2 分别指向两个数组，如果src1 指向的元素小于 src2，就把src1的数据放入新数组中然后通过比较大小的方式把数据依次放入新数组中，最后新数组的数据覆盖掉原数组的数据。
思路1代码实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int src1 = 0; int src2 = 0; int dst = 0; int* ret = (int*)calloc(m+n, sizeof(int)); while(src1<m && src2<n) //当达到其中一个数组末尾时停下 { if(nums1[src1] > nums2[src2]) //如果数组1中的元素大 { ret[dst++] = nums2[src2++]; //将2中的元素赋给新数组 } else { ret[dst++] = nums1[src1++]; //否则，将1中的元素赋给新数组 } } if(src1 < m) //如果1中的元素有剩余 { while(src1 < m) { ret[dst++] = nums1[src1++]; } } if(src2 < n) //如果2中的元素有剩余 { while(src2 < n) { ret[dst++] = nums2[src2++]; } } memcpy(nums1, ret, (m+n)*sizeof(int)); //将1数组中的数据覆盖 free(ret); ret = NULL; }
思路2代码实现
void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){ int end1 = m - 1; //指向数组1最后一个有效数据 int end2 = n - 1; //指向数组2末尾 int end = m+n-1; //指向数组1末尾 while(end1 >=0 && end2 >= 0) //当其中一个数组遍历完成后循环结束 { if(nums1[end1] < nums2[end2]) //从后往前，需要找大的 { nums1[end--] = nums2[end2--]; } else { nums1[end--] = nums1[end1--]; } } //如果数组1中还有元素则不用管，因为它本来就是有序的； if(end2 >= 0) //如果数组2还有元素 { while(end2 >= 0) { nums1[end--] = nums2[end2--]; } } }
