1.线性表线性表是n个具有相同特性的数据元素的有限序列是⼀种在实际中⼴泛使⽤的数据结构常⻅的线性表顺序表、链表、栈、队列、字符串...线性表在逻辑上是连续的但在物理结构上不一定是连续的线性表在物理上存储时通常以数组和链式结构的形式存储2.顺序表2.1顺序表的概念和结构概念顺序表是⽤⼀段物理地址连续的存储单元依次存储数据元素的线性结构⼀般情况下采⽤数组存储不管在逻辑结构还是物理结构上都是线性的顺序表和数组的区别顺序表的底层结构是数组是用数组来实现的对数组的封装实现了常⽤的增删改查等接口2.2顺序表的分类顺序表分为两类静态顺序表和动态顺序表2.2.1静态顺序表概念使⽤定⻓数组存储元素底层是一个固定长度的数组在编译期间就已经确定好了缺陷空间给小了不够用给多了就造成了空间浪费typedef int SLDataType; #define N typedef struct SeqList { SLDataType a[N];//定长数组 int size; //有效数据个数 }SL; //此处起别名也可去掉SL另加一行写上typedef struct SeqList SL;取别名是为了方便我们后续修改以这段代码为例下面的代码再用int可以直接使用SLTDataType这是为了防止一键修改时将其他不相关数据误改了2.2.2动态顺序表动态顺序表底层数组空间在不断的变化可增容相对比于静态顺序表可在一定程度上降低空间浪费typedef struct SeqList { SLDataType a; int size;//有效数据个数 int capacity;//空间容量 }SL;2.3动态顺序表的实现要学习动态顺序表我们要先了解动态内存的开辟malloc申请固定大小的内存不初始化内存里是随机垃圾值calloc申请固定大小的内存初始化自动清零realloc调整已分配内存的大小扩大或缩小既然要增容该如何增加呢增容一般成倍数增加一般二倍三倍推荐二倍增容此处成倍数增加是为了防止频繁增容由于每次增容都会发生重新找打的空间拷贝旧数据释放旧等操作空间频繁增容可能会导致程序运行效率低下2.3.1顺序表的初始化//seqlist.c #includeseqlist.h void SLInit(SL* ps)//形参 { ps-a NULL; ps-size ps-capacity 0; }//test.c #includeseqlist.h void test01() { SL sl; SLInit(sl);//实参 } int main() { test01(); }注意此处形参和实参之间要传地址2.3.2顺序表的插入操作1申请空间SLCheckCapacity(SL*ps) { //判断空间是否足够 if (ps-size ps-capacity) { int tmp; //考虑capacity一开始是0的情况 int newCapacity ps-capacity 0 ? 4 : 2 * ps-capacity; //增容 //realloc的第二个参数单位是字节 SLDataType* tmp (SLDataType*)realloc(ps-arr, newCapacity * sizeof(SLDataType)); //realloc函数会自动释放空间无需手动释放 if (tmp NULL) { perror(realloc fail); exit(1); } ps-arr tmp; ps-capacity newCapacity; } }2尾插此处我们应用realloc函数增加容量思路直接在顺序表末尾空位心如新元素同步更新有效长度//尾插 void SLPushBack(SL* ps, SLDataType x) { assert(ps); SLCheckCapacity(ps); //空间足够的情况下直接插入 ps-arr[ps-size]x; }时间复杂度O(1)注意1此处要考虑空间不够的情况需要手动开辟内存空间2要考虑capacity一开始是0的情况3考虑插入不成功的情况4保证插入元素不为空3头插思路所有原有元素从后往前集合体后移一位在最前面空位放入新数据若头插数据 x4我们需要将数组中所有的数据都往后挪动一位,此时为整体挪动//头插 void SLPushFront(SL* ps, SLDataType x) { //考虑头插的数据为空 assert(ps); SLCheckCapacity(ps); //空间足够的情况 //将顺序表中所有数据向后挪动一位 for (int i ps-size;i 0;i--) { ps-arr[i] ps-arr[i - 1]; } ps-arr[0]x; ps-size; }时间复杂度ON2.3.3顺序表的删除操作1打印顺序表//打印顺序表 void SLPrint(SL* ps) { for (int i 0;i ps-size;i) { printf(%d,ps-arr[i]); } printf(\n); }2尾删思路直接把顺序表有效长度减一无视末尾旧数据瞬间完成删除//尾删 void SLPopBack(SL* ps) { //ps限制参数不能为NULL //ps-size顺序表不能为空 assert(psps-size); --ps-size; }时间复杂度O1测试代码SLPopBack(sl); SLPrint(sl); SLPopBack(sl); SLPrint(sl); SLPopBack(sl); SLPrint(sl); SLPopBack(sl);注意1既要保证顺序表不为空又要保证ps不为空这是两种不同的情况3头删思路把后面的元素挨个往前挪一格覆盖掉第一个元素再把顺序表长度减一//头删 void SLPopFront(SL* ps) { assert(ps ps-size); for (int i 0;i ps-size - 1;i) { ps-arr[i] ps-arr[i 1]; } --ps-size; }时间复杂度ON总结操作要不要挪元素效率核心逻辑尾删❌ 完全不用极快 O(1)只改长度size尾插❌ 完全不用极快 O(1)末尾空位直接放头删✅ 全部往前挪很慢 O(n)后面元素覆盖第一个头插✅ 全部往后挪很慢 O(n)所有人后退腾位置4在指定位置之前插入数据思路将原顺序表pos及之后的数据整体向后挪动一位,再将要插入的数据插入到空出的空间里顺序表的总长度1//在指定位置之前插入数据 void SLInsert(SL* ps, int pos, SLDataType x) { SLCheckCapacity(ps); assert(ps); assert(pos0posps-size); //pos及之后的数据整体向后挪动一位 for (int i ps-size;i pos;i--) { ps-arr[i] ps-arr[i - 1]; } ps-arr[pos] x; ps-size; }时间复杂度O(N)5删除pos位置的数据思路将pos之后的数据整体向前移动一位将pos覆盖掉并把顺序表总长度减一//删除pos位置的数据 void SLErase(SL* ps, int pos) { assert(ps); assert(pos 0ps-size); //把pos之后的数据整体向前挪动一位 for (int i pos;i ps-size - 1;i--) { ps-arr[i] ps- arr[i1]; } --ps-size; }时间复杂度ON2.3.4查找功能思路:遍历顺序表找到返回正值找不到返回负值//查找数据功能 int SLFind(SL* ps, SLDataType x) { for (int i 0;i ps-size;i) { if (ps-arr[i] x) { //找到了 return 1; } } return -1; }//test.c int find SLFind(sl,3); if (find0) { printf(找到了); } else { printf(未找到); }2.3.5销毁功能//销毁 void SLDestory(SL* ps) { if (ps-arr) { free(ps-arr); } ps-arr NULL; ps-size ps-capacity 0; }3.顺序表相关算法题3.1移除元素思路1查找val值对应的下标pos执行删除pos位置数的操作此实现方法遍历顺序表查找时需要循环一次删除pos时又要循环一次因此时间复杂度O(N^2)思路2创建一个新的tmp数组空间大小与元u你数组一致遍历原数组将非value的值打印到tmp数组里再将tmp数组拷贝回原数组中用空间换时间时间复杂度ON 空间复杂度ON思路3双指针法(src在前面探路找非value值dst在后面站岗保存val值)创建了两个变量dst以及src在src不越界的情况下:1nums[src]val,src2nums[src]!val,将src赋值给dstdst,src3最后返回dst即为有效值个数注意此处我们只在意前k个数即可后面的数不重要代码实现int removeElement(int* nums, int numsSize, int val) { //定义两个变量 int dst0,src0; while(srcnumsSize) { //src值和val比较 ifnums[src]!val { nums[dst]nums[src]; src; dst } src; } return dst; }3.2删除有序数组中的重复项思路双指针法创建两个变量分别指向起始位置和下一个位置由于这是个有序数组相同的数据一定会挨着1nums[src]nums[dst],src2nums[src]!nums[dst],dst,将src赋值给dstsrc3最后返回数量dst1int removeDuplicates(int* nums, int numsSize) { //创建两个变量 int dst0,dst0; while(srcnumsSize) { //判断src和dst的值 ifnums[src]nums[dst]dst!src { dst; nums[dst]nums[src]; } src; } return dst1; }3.3合并两个有序数组思路1先合并再排序冒泡排序ON^2思路2创建一个新数组空间大小和原数组一样遍历两个原数组数据比较大小并放到tmp中空间换时间时间复杂度和空间复杂度均为ON思路3从前往后比较大小找小的小的往前放会导致数据被覆盖从后往前比较大小找大的void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) { int l1m-1; int l2n-1; intl3mn-1; while(l10l20) { //比较大小——找大 ifnums1[l1]nums2[l2] { nums1[l3]nums[l2--]; } else { nums1[l3--]nums2[l2--]; } } //要么l1先越界要么l2先越界 whilel20 { nums1[l3--]nums2[l2--]; } }注意l1和l2不会同时越界原因如下第一个循环的条件是l10l20循环结束的瞬间必然至少要有一个已经越界因此l1和l2不可能同时大于等于零也不可能同时给小于零