第四章：串、数组与广义表
OVERVIEW
- 串：内容受限的线性表
- 数组&广义表：线性结构的推广
一、String串
1.String定义：
2.StringADT：
3.String存储结构：
串中元素逻辑关系与线性表相同，串可以采用与线性表相同的存储结构：
（1）顺序串：
（2）链串：
块链结构对普通的链串进行优化，提高存储密度：
注意：在实际中相较于链串，顺序串使用更多（对字符串的插入、删除运算较少，顺序结构更利于匹配、查找操作）
4.String模式匹配算法：
（1）BF算法：
注：BF算法时间复杂度最好情况为
O(m)，最差为O(n-m)*m + m，平均情况为O(n*m)
（2）KMP算法：
next函数的改进：
5.String串应用：
二、数组
1.数组定义：
注意：数组特点是结构固定——定义后维数与维界不再改变，通常的操作只有取元素or 修改元素的值。
2.数组ADT：
3.数组存储结构：
注意：由于数组特点——结构固定、维数&界数基本不变，且一般不作插入删除操作，所以很少采用链式存储结构
（1）一维数组：
（2）二维数组：
（3）三维数组：
（4）n维数组：
4.特殊矩阵的压缩存储
（1）对称矩阵：
（2）三角矩阵：
（3）对角矩阵（带状矩阵）：
（4）稀疏矩阵存储★：
顺序存储结构：三元组存储
三元组顺序表又称为有序的双下标法。
- 三元组顺序表的优点：非零元素在表中按行序有序存储，因此便于进行按行顺序处理的矩阵运算。
- 三元组顺序表的缺点：不能随机存储。若按行号存取某一行中的非零元素，则需要从头开始进行查找。
链式存储结构：十字链表
三、lists广义表
1.list定义
2.lists与linear_list的区别
广义表可以看成是线性表的推广，线性表是广义表的特例。
