线性表

顺序存储结构（数组） 一段地址连续的存储的单元依次存储线性表的数据元素

数组： 数组的长度是存放线性表的存储空间的长度，存储分配后这个量一般不变 线性表的长度是线性表中存储元素的个数，这个数小于等于数组长度

线性表中元素地址值： 后一个元素的地址值 = 前一个位置 + 前一个元素占据的存储单元

存取时间复杂度： 由上面的公式可知，数组的存取时间性能为o（1）

插入与删除： 插入： 1. 插入位置不合理，抛出异常（插入位置 < 1 个位置或大于数组长度+1） 2. 线性表长度 >= 数组长度，抛出异常或动态增加容量 3. 从最后一个位置开始遍历到第 i 个位置，全部向后移动一个位置，将元素插到第 i 个位 置 4. 线性表长度加一

删除： 1. 删除位置不合理，抛出异常（删除位置 < 1 个位置或大于数组长度+1） 2. 线性表为空，抛出异常 3. 取出要删除的元素 4. 从删除位置遍历到最后一个位置，将他们向前移动一个位置 5. 线性表长度减一

数组的优缺点 优点： ● 无需为元素之间的逻辑关系增加额外的存储空间 ● 可以快速存取表中任意位置的位置的元素 缺点： ● 插入删除需要移动大量元素 ● 线性表长度变化较大时难以确定存储空间 ● 造成存储空间的碎片

链式存储结构 链表除了存储数据信息外，还存有后继元素的储存地址 每一个元素称为结点，节点分为两部分，前一部分存储数据，称为数据域，后一部分存储后继元素 的地址值，称为指针域 每个节点中只包含一个指针域，叫做单链表 链表第一个节点的存储位置较头指针，最后一个节点指针为空

链表的第一个节点前可以设一个头结点，数据域可以不存东西也可以存链表的长度，指针域指向第一个结点 若链表有头结点，头指针指向头结点，无论链表是否为空，头指针都不为空。此时头结点的指针域为空

单链表的读取 ● 获取第 i 个元素 ● 声明一个指针指向第一个结点，初始化一个 j 从 1 开始向 p 向后移动， j 累加 1 ● 若到了链表尾P为空，说明 i 不存在 ● 反之存在，返回 p

时间复杂度： 最坏的情况为 o（n）

单链表的插入和删除 插入（在位置 i 插入 s） ● 声明指针p , s。p指向链头，初始化 j 从 1开始 ● 当 j < i 时，让 p向后移动，不断指向下一个结点 ● 若到链表尾p为空，说明第 i 个结点不存在 ● 若查找成功，在系统中用指针 s 生成一个空节点 s ● 将元素e赋值给s的数据域 ● 单链表插入语句 将p的指针域赋值给s的指针域，将 s 的位置赋值给p的指针域 删除（删除位置 i 的结点） ● 声明指针p，q。p指向链头，初始化 j 从 1开始 ● 当 j < i 时，让 p向后移动，不断指向下一个结点 ● 若到链表尾p为空，说明第 i 个结点不存在 ● 否则将欲删除的元素的位置 p -> next 赋值给q ● 将q个位置 赋值给p ● 返回q的数据域的值，并释放q 单链表查找的时间复杂度为o（n），插入和删除的时间复杂度为o（n），但是在这个位置之后的 插入和删除只是简单的通过赋值移动指针，时间复杂度为o（1）。对于插入和删除越频繁的操作，单 链表的效率高

单链表的整表创建: 头插法: ● 声明一个指针 p ● 声明一个空链表 L，生成一个头结点，指针指向null ● 循环 ● 生成新结点赋值给p ● 给p的数据域赋值 ● 将头结点的指针域赋值给p的指针域 ● 将p的位置赋值给头结点的指针域 尾插法： ● 声明两个指针p , r ● 声明一个空链表 L，生成一个头结点，将r赋值为指向尾部的结点 ● 循环 ● 生成新节点p ● 给新结点的数据域赋值 ● 将p的位置赋值给r的指针域 ● 循环完毕，将r的指针域指向null 单链表的整表删除 ● 声明两个指针 p， q ● p指向链表的第一个结点 ● 循环，当p不为空时 ● 将p的指针域赋值给q ● 释放p ● 将q赋值给p ● 循环完毕，链表头指针指向null

单链表结构和顺序存储结构（数组）的优缺点

存储分配方式： 顺序结构用一段连续存储单元依次存储线性表的数据元素 单链表采用链式存储结构，用一组任意的存储单元存放线性表的元素 时间性能 查找： 顺序结构 ： o（1） 单链表 ： o（n） 插入删除： 顺序结构 ： o（n） 单链表 ： 查出某个位置的指针后，插入和删除时间为o（1） 空间性能： 顺序结构需要预先分配空间，分大了浪费，分小了溢出 单链表不需要分配存储空间，只要有就可以分配，元素个数也不受限制

总结： 线性表需要频繁进行插入和删除操作时，采用链表；需要大量查找时，宜采用顺序存储结 构 一开始不知道元素个数时，宜采用链表；事先知道，采用顺序存储结构

循环链表 将单链表的尾指针指向头结点，使整个单链表形成一个环

与单链表的差异： 单链表： p -> next = null ？ 到了尾部 ： 没到尾部 循环链表： p -> next = 头结点 ？ 循环结束 ： 循环未结束

循环链表查找第一个结点花费o（1），找最后一个花费o（n），对循环链表进行改造，不用头指针，改用指向尾部的尾指针rear，这样查找尾部结点的时间为o(1)，查找头结点为rear -> next ->next(头结点的存在)，时间复杂度也为o(1)

对于将两个循环链表合成一个循环链表的处理方法（a链表尾结点为rearA，b链表尾结点为rearB） ● 声明指针p, q ● p = rearA -> next ● q = rearB -> next ● rearA -> next = rearB -> next -> next ● rearB -> next = p ● free(q) 双向链表 单链表查找下一个的时间复杂度为o（1），但是查找上一个的复杂度为o（n），为了解决这一问题，引入双向链表 双向链表是在单链表的每个结点中，再设置一个前驱结点指针

在双向链表中插入元素： 将 s 插入 p 和 p -> next之间 ● s -> PRior = p ● s - > next= p - > next ● p - > next-> prior = s ● p - > next = s 在双向链表中删除元素： 删除p： 将p - > next 赋值给 p -> prior 的后继 将p - > prior赋值给 p - ＞next 的前驱 free（p）