数据结构和算法（Data Structure And Algorithms）
线性表（linear_list）
线性表是最基本和最常用的一类数据结构，它表示的是线性结构。
在线性结构中，数据元素之间存在着一对一的关系，其特点是数据元素之间按某种规定存在一个顺序关系。
# 基本内容
- 1.线性表基本概念
- 2.线性表的两种存储结构：顺序和链式存储结构
- 3.线性表的简单应用
- 4.线性表的扩展
1. 线性表的定义
线性表：n个同类型数据元素的有限序列，记为：
L = (a1，a2，...，ai，... ，an)
其中
- L为表名；
- i为数据元素a
i在线性表中的位序； - n为线性表的表长，n为0时称为空表；
- 数据元素之间的关系是：
- a
i-1领先于ai，ai领先于ai+1； - 称a
i-1是ai的直接前驱，称ai+1是ai的直接后继； - 除第一个元素外，均有唯一前驱；
- 除最后一个元素外，均有唯一后继；
- a
线性表特点
- 元素a
i的数据类型相同； - 位序i从1开始；
- 前驱和后继
2. 线性表的抽象数据类型
合并线性表
合并线性表算法分析
最好情形分析：B为A的前面部分元素：1+2+...+n = n*(n+1)/2
最坏情形分析：B和A交集为空：m+(m+1)+...+(m+n-1) = n*m + (n-1)*n/2
如上，n值越小，整体的性能越好，所以一般把长度较小的一个线性表作为B。
合并2个有序表
时间复杂度T(N) = O(m+n) =O(N)，之后的归并排序就是利用这个原理
3.线性表的顺序存储结构
用一组地址连续的存储单元依次存放线性表中的数据元素，其中线性表的起始位置s称作线性表的基地址。
==优势：可以随机存取数据==
空间分配方式
- 静态：数组（空间大小固定不可变）
- 动态：指针（用新的大的空间指针，释放旧的空间）
三元素
- ElemType *elem : 一大块连续存储空间的首地址指针
- length : 线性表的长度（初始值应该为0）
- list_size : 线性表空间的大小
顺序结构基本操作实现
初始化--创建线性表
查找
按位置查找---O(1)
按值查找--O(n)
插入元素操作--O(n)
- 检查插入位置是否合法，如果合法则继续，否则退出；
- 判断表是否已占满，由于是事先分配空间，可能存在所分配存储空间全部被占用的情况，此时也是不能实现插入的；
- 若检查通过，则数据元素依次向后移动一个位置，为了避免覆盖原数据，应该从最后一个元素开始依次向前处理；
- 新数据元素放到指定位置；
- 表长加一；
插入算法的时间性能分析：
删除元素操作
- 检查删除的位置是否合法并且当前线性表不为空表；
- 若检查通过，数据元素依次向前移动一个位置；
- 表长减1；
时间复杂性分析
4. 线性表的链式存储结构
- 顺序存储结构可以存储线性表的数据，支撑线性表的基本和复杂操作的实现
- 同样的，问题也和突出
- 我们无法知道到底预先分配多大的空间才合适
- 插入删除的开销很大
- 解决方案：一个数据一个空间，数据之间不连续，避免一次性大空间分配失败或者使用过程中空间不足的问题
单链表
用一组地址任意的存储单元存放线性表中的数据元素。
结点
- 数据域（数据元素）
- 指针域（指示直接后继元素存储位置）
以==结点的序列==表示线性表，称为“链表”
以线性表中第一个数据元素a1的存储地址作为线性表的地址，称作线性表的头指针。
有时为了操作方便，在第一个结点之前虚加一个“头结点”，并用链表的头指针指向头结点，称为带头结点的单链表。
- 不带头结点
- 链表指针存放链表第一个数据元素结点的地址
- 空链表时该指针域为null
- 带头结点的单链表
- 一个专门的结点，称为头结点
- 该头结点永远存在
- 该头结点指针域存放第一个数据元素结点的地址
- 空链表时，L.next = null
单链表的C语言实现
单链表基本操作实现
按位置查找--O(pos)=O(n)
链表的操作只能通过头指针出发，顺着链域next逐个结点比较，直到搜索到指定位置的结点为止
按值查找--O(n)
- 初始化：P指针指向线性表第一个结点；位置i=1；操作状态s为错误
- 只要线性表不为空，循环做下面操作
- 如果待查找数据==当前结点数据，则退出循环；
- 否则p指针指向下一个结点；位置计数器i自增；
- 循环外面判断p!=null，则找到数据，将位置i赋值给pos参数；修改操作状态s为成功！
- 返回操作状态。
插入操作-O(pos+k)=O(n)
删除操作-O(pos+k)=O(n)
- 首先求得第i-1个结点的指针p；
- 修改第i-1个结点的后继域为第i+1个结点的地址；
- 再通过delete或free释放第pos个结点所占的存储空间
创建单链表--O(n)
- 建立一个空表
- 输入数据元素a
n，建立结点并插入到单链表； - 输入数据元素a
n-1，建立结点并插入到单链表； - 依次类推，直到输入a
1为止。
单链表的变形
1. 循环单链表
最后一个结点的指针域的指针又指回第一个结点的链表
和单链表的差别仅在于判别链表中最后一个节点的条件不再是后继是否为空，而是后继是否为头结点。
2. 带尾指针的循环单链表
应用情形一：将两个循环单链表合并
上图中，p是头结点，La和Lb分别是两个循环链表的尾指针，顾名思义，尾指针指向的就是单链表的最后一个数据元素
应用情形2：经常需要在最后一个元素后面或者第一个元素前面添加新的元素
3. 双向链表
-
单链表找后继很方便，但是找前驱很复杂
-
增加另一个空间(指针域)存放前驱的指针
- 双向循环链表
- 操作特点
- 查询和单链表相同
- 插入和删除时需要同时修改两个方向上的指针
双向链表插入操作
双向链表的删除操作
4. 静态链表
- 某些语言中不提供指针，如java和Visual BASIC等，只能通过其他方式来模拟指针；
- 采用数组模拟链表的指针，用以表示数据元素后继所存放位置
- 数据元素的存储空间像顺序表一样事先静态分配的
- 数据元素之间的关系像链表一样显示的
5. 顺序与链式存储结构的比较
合并线性表的场景
==虽然都是n，但是链式存储的时间复杂度消耗在定位上，而顺序存储是消耗在交换数据元素上，所以真实的实际开销，顺序结构要大一些，最佳性能选择是链式存储结构，但由于数量级同级，且实际案例中分配空间大小可预估，考虑到编程难度我们采用顺序存储也是可行的。==
合并有序表
6. 线性表的扩展
回顾线性表：n个相同元素的有限序列
DS = （D,L,O,S）
- 线性表的逻辑结构L：一对一（前驱、后继）
- 线性表的基本操作O：创建、查找元素、插入、删除等
- 线性表的存储结构S：顺序、链式（单链表、双向链表、循环链表、双向循环链表）
操作受限的线性表--栈和队列
栈和队列是限定插入和删除只能在表的“端点”进行的线性表
栈
栈是限定在表的同一端进行插入或者删除操作的线性表。进行插入或删除操作的一端称为栈顶，另一端称为栈底，没有数据元素的栈称为空栈，插入数据元素的操作称为入栈，删除数据元素的操作称为出栈。
栈的抽象数据类型
顺序栈
类型定义
约定top用于存放栈顶元素的位置，top=-1表示空栈，top=stack_size-1表示栈满，入栈时top加一，出栈时top减一
溢出
- 顺序栈的数据元素空间大小是预先分配的
- 当空间全部占满后再入栈产生的溢出称为“上溢”；
- 当栈为空时再出栈也将产生的溢出称为“下溢”；
顺序栈入栈操作
顺序栈出栈操作
顺序表取栈顶元素的操作
多个顺序栈空间共享
链栈
栈的链式存储结构
- 单链表（头部做插入删除操作是比较方便的，时间复杂度为O(k)，反之，时间复杂度为O(n)）
- 双向链表
- 循环链表
链栈入栈操作
链栈出栈操作
链栈取栈顶元素操作
队列
队列是限定是能在表的一端进行插入，在表的另一端进行删除的线性表
- 队尾（rear）：允许插入的一端
- 队头（front）：允许删除的一端
队列特点：先进先出（FIFO）
队列的抽象数据类型
顺序队列
假溢出解决-视为循环顺序队列
- 方法一：用计数器记录队列中的元素个数
- 初始化队列时c=0；
- 入队时，计数器加一；
- 出队时，计数器减一；
- 当计数器=maxqsize时，队满
- 当计数器=0时，队空
- 方法二：设一个标志位来区别队列空还是满
- 初始化队列时：sq->front = sq->rear,标志位为false；
- 入队后，sq->front = sq->rear时，则设置标志位为true；
- 出队后，sq->front = sq->rear时，则设置标志位为false；
- 所以若sq->front = sq->rear，标志位为true时，队满；false时，队空；
- 方法三：牺牲一个元素空间，来区别队空或队满
- 入队前，先判断sq->rear+1是否等于sq->front，若是则为队满；
- 而当sq->front = sq->rear时，为队空。
==方法三没有其他新增的东西，建议第三种==
京公网安备 11010502036488号