第二部分 线性结构
4、线性表
4.1线性表
线性表：零个或多个数据元素的有限序列。（概念：空表、直接前驱、直接后继）（操作：插入、删除）
线性表的顺序存储结构：指在一段地址连续的存储单元依次存储线性表的数据元素。（用数组来实现这一结构）
时间复杂度：
存储读取：O(1)
插入删除：O(n)
顺序存储结构的优缺点
线性表的链式存储结构：用任意一种存储单元存储数据元素，存储单元可以是连续的也可以是不连续的。
头结点与头指针异同
4.2单链表:
线性表的链式存储结构，即单链表
单链表时间复杂度：查找O(n)、插入O(n)[头插法，尾插法]、删除O(n)
单链表结构和顺序存储结构对比：
a、频繁查找很少删除和插入适用线性表的顺序存储结构（游戏中人物信息[顺序]，人物装备[链式]）；
b、线性表长度不确定情况下[链式]
4.3静态链表：
用数组描述的链表。不移动数据元素，只修改下标。
4.4循环链表：
将单链表尾部指针指向头，使整个单链表形成一个环，这种首尾相接的单链表就是单循环链表，简称循环链表。
指针指向尾部查找头结点和尾结点比较方便
4.5双向链表
在循环链表的基础上每个结点增加一个指向前驱的指针域。（redis 中list类型，头）
4.6总结:
4.6.1JAVA语言数据结构的实现
List
| List实现 | | |
| 数组形式访问List链式集合数据，元素可重复， 访问元素较快 | |
| 数组形式访问List链式集合数据，元素可重复， 访问元素较快，线程安全 | |
| 链表方式的List链式集合，元素可重复，元素 的插入删除较快 | |
Set
| Set实现 | | |
| | |
| | |
| 保持元素大小次序的集合，元素需要实现Comparable接口 | |
Map
| Map实现 | | |
| | |
| 是一个可以记录插入顺序和访问 顺序的HashMap | 存储方式是哈希散列表，但是维护 了头尾指针用来记录顺序 |
| | |
| | |
5、栈与队列
5.1栈（线性表）
栈（Stack、LIFO）限定在表的一端进行插入和删除操作的线性表。（操作：进栈、出栈）
（栈顶、栈底）
栈的应用
a、斐波那契数列实现
兔子例子：
递归和迭代区别：迭代使用循环结构，递归使用选择结构；
b、四则运算表达式求值：后缀表达式求值（逆波兰）
一种不需要括号的后缀表示法，称为逆波兰。
后缀表示法表示为
5.2队列
队列（queue、FIFO）限定在表一端进行删除，而在另一段进行插入的线性表。（队头、队尾）
循环队列：把队列头尾相接的顺序存储结构称为循环队列。（为解决假溢出问题）
队列存储结构
队列顺序存储结构：
队列链式存储结构：（其实就是单链表，只是在头出，尾部插入）
队列应用如（Spark资源调度机制、消息队列kafka、生活排队买票等等）
总结
6、串（线性表）
串是由零个或多个字符组成的有限序列。
s是串的名称，用双引号括住序列式字符串的值。空串、子串、主串。
ASCII(128-256)、Unicode（65万）；其中unicode前256位与ASCII相同。
与线性表区别：线性表主要是对单个数据元素操作，而串是对子串应用操作（查找，替换等），本质上串也是线性表的一种扩充。
顺序存储结构：
在高级语言中存储空间是动态分配的，如：C语言的 malloc()和free()管理。
链式存储结构：
一个结点存储一个或多个数据元素，无数据元素则用#代替。性能不如顺序存储结构。
朴素模式匹配算法：（普通的匹配算法）
串的定位操作称为模式匹配
如：s="goodgoogle" t="google"
平均时间复杂度O(n+m)；
最坏情况下O((n-m+1)*m);
效率低；
KMP模式匹配算法：
为避免大量重复匹配，所以提出了克努特-莫里斯-普拉特算法（KMP算法）。
最坏情况是O(m+n);
http://baike.baidu.com/link?url=r2SB_2hU3KPYmMPuOe8LBojLIqWruheWvyvNjrUoG7i1JmedJcYUJw8genvRHCGT2nQIYiBhFQjvGl0Ow8lBWg83VfMCoc4-6BfmkQTqep3
收藏
淘帖
踩
优秀
到位
