线性表

线性表的概念

• 线性表的定义

顺序表

• 把线性表的节点按逻辑顺序一次存储在一连串地址连续的存储单元里

• 第i个元素和第i+1个元素的存储位置Loc满足关系式 , 每个元素需占用个存储单元

• 特点：
• 逻辑顺序与物理顺序一致。
• 可以提前计算地址，因此可以乱序随机访问。
• 优点：
• 节省存储空间。由于结点之间的相邻逻辑关系可以用物理位置上的相邻关系表示，因此不需增加额外的存储空间来表示此关系。
• 存取速度快。
• 缺点：插入、删除等操作时需要移动大量数据。

• 静态存储与动态存储

• 顺序表（SeqList）的类定义
代码

• 顺序表查找数据
• 显然，最好考虑的是顺序查找，从头开始找直到最后。
• 考虑查找第i个元素，假设查找概率均等，则我们考虑ACN(average competing number)的计算。

• 循序表插入数据
• 如果要在i位置插入数据，显然要把从第i个开始的所有数据往后移动。移动的时候，考虑从最后一个往后移动，那么理论上需要次移动，因此整个算法的时间复杂度为。
• 更精确地来说，考虑插入概率均等，我们计算AMN(average moving number)。

• 顺序表删除元素
• 删除元素，作出如下考虑：将原i为元素保存，随后从第i+1位开始往前移动一位，最后将现存元素数量n减1。
• 类似的，时间复杂度也是。

• 顺序表实现两个集合的并
• 显然，对于两个集合，我们要对A集合中的每个元素，在B集合中我们要进行查找。
• 如果，那么显然成立。

• 顺序表实现两个集合的交
• 显然类似的，时间复杂度应当为。

单链表

• 多个类表达一个概念(单链表)。
• 链表结点(ListNode)类
• 链表(List)类

• 特点
• 优点：善于插入删除等操作。实现单链表的插入和删除算法，不需要移动元素，只需修改结点指针，比顺序表方便。
• 缺点：
• 由于物理关系不确定，需要额外的指针空间。
• 情况复杂，要专门讨论空表和在表头插入的特殊情形。
• 寻找插入或删除位置只能沿着链顺序检测。

• 单链表类定义
代码

📌

有没有办法缩短查询的时间？跳表！

时间复杂度变为

• 带附加头结点（表头结点）的单链表
• 表头结点位于表的最前端，本身不带数据，仅标志表头。
• 设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现。
• 用类模版的定义
代码
• 两种创建链表方法：前插法和后插法
代码

循环链表

• 循环链表是一种头尾相接的链表。

• 循环链表最后一个结点的 link 指针不为0（NULL），而是指向了表头结点。

• 只要知道表中某一结点的地址，就可搜寻到所有其他结点的地址。

• 为了使空表和非空表的处理一致，循环链表中也可设置一个头结点。

双向链表

• 通常采用带头节点的双向循环链表表示

• 前驱结点和后继结点

单链表的应用：多项式

静态链表的结构与存储

• 为数组中每一个元素附加一个链接指针，就形成静态链表结构。

• 静态链表每个结点由两个数据成员构成：data域存储数据，link域存放链接指针

• 处理时中可以不改变各元素的物理位置，只要重新链接就能改变这些元素的逻辑顺序。

• 它是利用数组定义的，在整个运算过程中存储空间的大小不会变化。

• 区别：静态链表和动态链表是线性表链式存储结构的两种不同的表示方式。
• 静态链表是用类似于数组方法实现的，是顺序的存储结构，在物理地址上是连续的，而且需要预先分配地址空间大小。所以静态链表的初始长度一般是固定的，在做插入和删除操作时不需要移动元素，仅需修改指针。
• 动态链表是用内存申请函数（new）动态申请内存的，所以在链表的长度上没有限制。动态链表因为是动态申请内存的，所以每个节点的物理地址不连续，要通过指针来顺序访问。