一、线性表的基本概念线性表的定义线性表(linear list)是相同类型的n(n0)个数据元素的有限序列。一般表示为 L (a1 , a2 , ..., ai, ai1 , ..., an)n是表的长度当 n0时称为空表。a1 是表头元素 an 是表尾元素。表头元素没有前驱其余的任意元素都有唯一的前驱元素表尾元素没有后继其余的任意元素都有唯一的后继元素。线性表的定义就是数据的逻辑结构(第一章2.2)数据运算的定义针对逻辑结构的运算的实现要针对线性表选择的存储结构选择顺序存储来实现线性表就是顺序表选择链式存储实现线性表就是链表。二、线性表的两种实现方式用顺序存储的方式实现线性表就是顺序表用链式存储的方式实现线性表就是链表。1.顺序存储顺序表把逻辑上相邻的数据元素存放在一段连续物理存储单元中数据元素之间的逻辑关系可以由物理存储关系体现。2.链式存储链表逻辑上相邻的数据元素存储在任意的一组物理存储单元中数据元素之间的逻辑关系用指针来表示。线性表L (张三, 李四, 王五,赵六)分别用顺序存储和链式存储展示如下3.举例贪吃蛇移动本质是数据的头部插入数据尾部删除数据。踩到点后的本质是头部插入数据尾部不删除数据。顺序表是在创建的时候创建好空间贪吃蛇执行时需要移动数据。时间复杂度O(N);链表可以任意位置申请空间再指向表头即可。O(1);三、C引用补充1.引用的定义类型 引用别名 引用变量;引用时必须初始化2.引用的特性引用在定义时必须初始化一个变量可以有多个引用引用一旦引用一个实体再不能引用其他实体3引用的做参数函数调用传值传参将实参的值复制一份给形参函数内对形参的修改不会影响实参。函数调用指针传参传递实参的地址指针通过指针间接访问和修改实参。指针传参和引用传参除了通过形参修改实参的作用对于大对象传参还有减少拷贝提高效率的作用。指针和传参和引用传参在功能上是重叠的一些场景用引用程序要简化方便一些。四、顺序表1.1静态顺序表静态顺序表就是用固定大小的静态数组来存储数据。优点是实现简单缺点是适用场景局限只适用于确定知道自己最多存放多少数据的场景否则空间申请少了不够用申请多了浪费。1.2动态顺序表动态顺序表就是用⼀个堆上动态申请的数组来存储数据如果空间不够了可以做扩容处理。优点适用场景多不确定自己要存放多少数据的场景也很适合缺点是实现相对复杂一些。后续我们主要实现动态顺序表因为动态顺序表可以掌握静态顺序表就是手拿把掐。代码在SqList · Epiphany_ran/opencode - 码云 - 开源中国2.1初始化顺序表的结构体变量创建好后系统会以随机值对其进行填充所以在使用前须先进行初始化步骤如下a. 使用malloc申请一个默认大小动态数组空间比如默认大小为4这个空间一般不要太大因为太大了用不了就浪费了反正如果不够后续可以扩容。b. 申请成功后将有效元素个数初始化为0因为初始化阶段顺序表中还未存放任何有效元素。c. 将capacity设置为所申请空间的实际大小。2.2销毁由于顺序表中的空间是用malloc从堆上动态申请的使用完后必须释放否则会内存泄漏。具体步骤如下a. 检测顺序表 s 的空间是否被销毁。b. 如果未销毁使用 free 将其释放掉并将 arr 设置 NULLsize 和 capacity 设置为0。c. 其次要注意的free本质并不是真的把空间销毁掉free的本质是把这段空间的使用权还给操作系统操作系统后续还可以把这段空间分配给别人。2.3插入顺序表经过初始化之后才可以进行元素插入操作。插入函数原型为void SqListInsert(SqList* ps, int i, SqDataType x) , 即在顺序表的第i个位置之前插入新元素x如果 i 的位置非法则不进行插入插入具体步骤如下a. 参数检测。主要检测位序i是否满族 0 i s.size 满足则着插入否则无法插入。b. 检测是否需要扩容如果顺序表中存满了则需要先扩容之后才能插入。c. 插入元素x。将 i 及其之后的所有元素整体往后移动一个位置然后将 x 填充到待插入位置。d. 插入成功后给有效元素个数加1我们这里扩容使用C的库函数 void* realloc (void* ptr, size_t size) 实现ptr是旧空间的指针size是需要的新空间的字节数realloc函数有以下几种情况a. 原地扩容如果当前数组后面有足够的空间没有分配给别人realloc则会将后面空间分配给我们返回的地址跟ptr一样。b. 异地扩容如果当前数组后面没有足够的空间(这些空间已经分配给别人了)realloc则会尝试找一块 size 大小的新空间如果没有找到则代表扩容失败了返回NULL找到了则会把ptr空间的数据拷贝到新空间然后释放ptr指向的旧空间然后返回新空间的地址。2.4 删除删除函数原型 SqDataType SqListDelete(SqList* ps, int i)删除函数的功能是删除顺序表中第 i 个位置上的元素删除的元素通过返回值带出注意i必须在0 ≤ i s.size 否则无法删除。具体操作如下a. 参数检测主要检测位序i是否满足 0 i s.size 满足则删除否则无法删除。b. 将 i 位置之后所有元素整体往前搬移一个位置。c. 删除成功将有效元素个数减1。2.5查找顺序表有两种查找操作位序查找和按值查找。位序查找函数原型 SqDataType GetElem(SqList* ps, int i) 第i个位置元素随机访问在i满足 0 i s.size 时(不满足则报错)直接返回顺序表第i个元素即可。按值查找函数原型 int LocateElem(SqList* ps, SqDataType x) 从前往后逐个查找找到第一个相等的就返回其下标否则返回-1。2.6复杂度分析插入的时间复杂度a. 最好情况位序 i n 1 在表尾插入插入时无需扩容无需移动元素时间复杂度为 O(1)b. 最坏情况位序 i 1在表头插入此时需要将所有元素整体往后移动1步即移动语句需要执行n次再叠加需要扩容异地扩容的最大的消耗是要拷贝n个元素那么时间复杂度为O(n)c. 平均情况假设在任意位置前插入元素的概率Pi相等则Pi 1 / n1则在长度为 n 的线性表中插入一个元素时所需移动元素的平均次数为那么时间复杂度为 O(n)。删除的时间复杂度a. 最好情况位序 i n 在表尾删除删除时无需移动元素时间复杂度为 O(1)b. 最坏情况位序 i 1 在表头删除此时需要将i位置后面的元素依次往前挪动覆盖即挪动n-1个数据时间复杂度为O(n)c. 平均情况假设在任意位置删除元素的概率 相等则 Pi 1 / n 则在长度为 n 的线性表中删除个一元素时所需移动元素的平均次数为那么时间复杂度为 O(n)。下标查找的时间复杂度因为顺序表中的数组物理存储上是连续的通过首地址常数次就是可以算出任意i位置的地址所以时间复杂度均是 O(1)。按值查找的时间复杂度a. 最好情况查找的元素就在表头此时比较 1 次即可找到时间复杂度为 O(1)b. 最坏情况查找的元素在表尾或不存在时则需要比较 n 次时间复杂度为 O(n)c. 平均情况假设查找任意位置元素的概率Pi相等则 Pi 1 / n则在长度为n的线性表中查找一个值的比较平均比较次数为那么时间复杂度为O(n)。