一.线性表概念引入线性表定义具有n个相同特性数据元素的有限序列线性表是统称如水果顺序表、链表是具体类型如苹果、梨。二.顺序表详解1. 顺序表定义与底层结构线性表定义一类具有相同特性的数据结构的集合。例如顺序表、链表、栈、队列。两大特性逻辑结构人为想象出来的结构。线性表的逻辑结构一定是线性的即数据元素之间是“一对一”的连续关系。例如排队时我们将其抽象成一条直线但现实中队伍并非直线这条直线是人为想象的逻辑结构。数组也是如此我们想象它是一个连续的矩形框但在物理内存中并非如此。物理结构数据在计算机内存中的实际存储方式。线性表的物理结构不一定是线性的。顺序表定义线性表的一种用一组地址连续的存储单元依次存储线性表中的数据元素。其底层实现是数组。【重点】掌握要求理解​ |考试频率高频​ |408考法常考顺序表与链表的对比以及顺序表各种操作的时间复杂度分析。逻辑结构与物理结构分析逻辑结构线性。物理结构线性因为底层数组在内存中是连续存储的。2. 顺序表与数组的区别数组基础存储结构需手动实现增删查改如“苍蝇馆子的炒西兰花”原料是基础食材。顺序表数组的“封装”如“米其林餐厅的绿野仙踪”原料是数组但提供了增删查改的现成方法。易错点误将顺序表等同于数组顺序表是带操作接口的数组3. 顺序表的分类1静态顺序表定义编译时确定数组大小如#define N 100数组int a[N]。特点结构简单但空间固定空间小则存不下空间大则浪费。【重点】静态顺序表的局限性2动态顺序表定义运行时动态申请空间用malloc/realloc调整数组大小。优势空间按需分配避免浪费或不足比如抖音用户注册静态顺序表会因空间固定流失用户动态顺序表可动态扩容。3初始化调用方式SLInit(sl);取实参sl的地址传给ps。涉及知识点函数传值调用vs传址调用忘记用传址调用修改结构体变量形参的改变要影响实参必须传地址4.增删改查1尾插时间复杂度O(1)均摊时间复杂度二倍扩容下每次插入的均摊成本为O(1) 。空间复杂度O(1)仅用常数级临时变量。易错点realloc第二个参数未乘sizeof(SLDataType)realloc申请的是字节数需计算元素总字节数。capacity0时直接二倍扩容0×20需特殊处理为初始容量4。未检查realloc的返回值失败返回NULL会丢失原数组地址测试结果如下说明已经正确处理尾插2头插复杂度时间复杂度O(n)空间复杂度O(1)测试结果如下说明正确处理了头插3尾删检查合法性assert(ps-size 0);确保顺序表不为空。删除数据逻辑删除只需将size--即可。不需要物理清除数据如赋值为0或-1也不需要释放空间。因为size决定了有效数据的范围后续插入操作会覆盖这些“垃圾数据”。易错点认为需要物理删除数据或释放空间。复杂度时间复杂度O(1)空间复杂度O(1)测试结果:4头删检查合法性assert(ps-size 0);。移动数据将所有数据从前往后依次向前移动一位。必须从前往后移动否则会覆盖数据。更新sizesize--复杂度时间复杂度O(n)空间复杂度O(1)5查找检查合法性assert(ps);遍历查找遍历数组若找到则返回当前下标。未找到处理遍历结束后仍未找到返回一个无效下标通常为-1。复杂度时间复杂度O(n)空间复杂度O(1)6插入任意位置检查合法性assert(ps);assert(pos 0 pos ps-size);pos可以是size即在末尾插入等同于尾插检查空间调用SLCheckCapacity。移动数据将从pos到size-1的所有数据从后往前依次向后移动一位。插入数据在array[pos]位置插入x。更新sizesize。复杂度;时间复杂度O(n)空间复杂度O(1)(7) 删除任意位置判断pos合法性使用assert。将pos之后的所有数据整体向前挪动一位从pos1移到pos依次类推。有效数据个数size减 1。时间复杂度O(n)空间复杂度O(1)8顺序表的销毁释放顺序表底层动态申请的数组空间并将结构体成员还原为初始状态。思路检查array指针是否不为空若不为空则调用free释放空间。将array置为NULL。将size和capacity置为 0。三.顺序表的应用1.移除元素思路1申请新数组辅助空间法算法思路申请与原数组大小相同的新数组temp。遍历原数组将值不为val的元素依次放入temp。将temp中的元素导回原数组。返回ktemp中有效元素个数。注意要对边界有所判定最上面如果数组大小为0的时候根本没必要再循环了对于数组的返回赋值也是要循环不能直接nums*temp时间和空间复杂度都是O(N)思路2双指针法重点算法思路定义两个变量抽象指针src和dst初始均指向数组起始位置。src负责探路遍历数组寻找不等于val的元素。dst负责接收当src找到非val值时将其赋值给dst位置然后dst和src都向后移动若src遇到val则只有src向后移动dst不动。当src越界时循环结束dst的值即为非val元素的个数k。此时时间O(N),空间O(1)而且是更高阶的思路应该作为以后的首选原地修改2.去重复元素前提数组已按非递减顺序排列也就是递增排列原地去重核心思路双指针法src探路dst存唯一值。指针初始化dst指向数组起始位置下标0。src指向数组第二个位置下标1。算法思路比较src与dst指向的值。若相等src跳过重复值。若不等先dst再将src的值赋给dst最后src。当src越界时结束返回dst 1有效元素个数。3. 合并两个有序数组题目将非递减数组nums2合并到nums1中使结果仍为非递减。nums1空间大小等于m n。核心思路从后往前遍历谁大谁先放避免元素覆盖。指针定义l1指向nums1有效元素的末尾下标m-1。l2指向nums2有效元素的末尾下标n-1。l3指向nums1最终存放位置的末尾下标mn-1。算法思路当l1 0且l2 0时比较nums1[l1]和nums2[l2]。将较大值放入nums1[l3]并将对应指针和l3均向前移动一位--。若l2先越界l2 0说明nums2已合并完毕nums1剩余元素已在正确位置结束。若l1先越界l1 0说明nums2尚有剩余元素需将其全部拷贝到nums1前部。void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n) {int l1 m - 1, l2 n - 1, l3 m n - 1;while (l1 0 l2 0) {if (nums1[l1] nums2[l2]) {nums1[l3--] nums1[l1--];} else {nums1[l3--] nums2[l2--];}}// 若l2仍有剩余拷贝到nums1开头while (l2 0) {nums1[l3--] nums2[l2--];}}复杂度分析时间复杂度O(mn)。空间复杂度O(1)。易错点与重点必须从后往前合并从前往后会覆盖nums1原有数据。循环结束后只需处理l2剩余的情况l1剩余无需处理。两个指针不可能同时越界每次循环必有一个指针移动四.顺序表总结与问题顺序表特性回顾头部/中部插入删除时间复杂度O(n)需移动大量元素。尾部插入删除时间复杂度O(1)。扩容机制realloc申请新空间、拷贝数据、释放旧空间有性能开销。空间浪费通常采用2倍扩容可能导致较多预留空间闲置。引出链表为解决顺序表头部操作慢、扩容开销大、空间浪费的问题引入链表这一物理结构非连续的数据结构。