数据结构----串、数组和广义表_／∥／，，：必y；，广义丨丨1jly\串

栈和队列是操作受限的线性表，串、数组和广义表是内容受限的线性表，严格来说不是线性表。

一、串

1，串的定义

串：零个或多个字符组成的有限数列

字串位置从1~n编号，不是0开始。

所有空串是相等的。（类似于集合）

2，串的类型定义和存储结构

重点：找子串的位置（串的匹配）
线性表不强调元素类型，串的元素只能是字符型。
串的顺序存储结构

串的链式存储结构：操作方便，但存储密度低。为了提高存储密度，将多个字符放在一个结点中，地址占四个字节，一个字符占一个字节

顺序存储结构用的更多，因为实际上做匹配和查找更多，插入删除不多。

3，BF算法

模式匹配算法：确定主串中所含子串第一次出现的位置。bf算法：简单但时间效率差。kmp算法速度更快。重点掌握BF算法。
BF算法：采用穷举法的思路。从主串中每一个字符依次比较，每次匹配失败主串指针i退回到i-j+2处，子串指针j退回到1，匹配成功后，i-t.length为子串在主串起始位置。

从主串的pos处开始匹配

4，KMP算法

主串指针i不必回溯，且子串指针回溯不一定从头开始。

匹配到next[j]时，回溯的位置：从next[1]开始的前k-1个字符和next[j]前面的k-1个字符进行匹配，相同则回溯到第k个字符，否则回溯到第1个字符。
算法直接在BF算法基础上将i，j回溯部分的代码改成BMP算法回溯方式即可。

时间效率为O（n+m）
next函数改进：引入改进后的nextval函数，计算方法：根据j位置的next值为a，则找到模式串中的第a个字符，看第a个字符跟第j个字符是否一致，如果一致则根据第a个字符的next值为b，将第b个字符跟第j个字符进行比较，相同则依次类推，不同则直接将a位置的next等于nextval；如果第a个字符跟第j个字符不一致，直接将j位置的next等于nextval。（很绕口，意思就是next只根据j前面的k个字符相等来确定新的j，但是改进过的nextval多考虑一层，根据next和当前j位置的元素来确定新的j，更加科学）

二、数组

1，数组的定义和特点

数组定义：按一定格式排列的具有相同类型的数据元素的集合。
一维逻辑结构：一维数组是线性结构，定长的线性表。
二维数组：每一行作为一个元素，获得一个线性表，且该表中每一个元素都是线性表；按列同理。但是按照二维来看，其中的元素上下左右都有元素，也就是不止一个前驱或者不止一个后继，所以为非线性结构。声明时，int num[m][n]，m行×n列；或者先定义一个n列的一维数组，再对这个一维数组的每个元素定义为m行，也可以获得。

2，数组的抽象数据类型定义

j_i为第i维的下标，D中是数组的任意一个元素。

3，数组的顺序存储

数组结构固定（维数和和维届不变）且一般不做插入删除，故采用顺序结构。注意数组多维映射到数据一维的关系。

对于m行n列的数组，查找第i行第j列的元素：i×n+j+1（i，j从0开始），则前面有i×n+j个元素。每个元素需要L个存储单元，则a[i][j]的存储位置为：LOC(i,j)=LOC(0,0)+(i×n+j)×L。
三维数组按照页/行/列/存储。

4，对称矩阵压缩存储

常规矩阵：随机存取，运算简单，密度为1；
**压缩存储：**对于多个数据元素值相同时，只分配一个空间，对零元素不分配空间。
非零元素少于5%，成为稀疏矩阵。
对称矩阵只存储上（下）三角以及主对角线，占用空间n（n+1）/2。就是前n个自然数的和。
对于三角矩阵，a[i][j]前面有元素个数：k（k-1）/2+q-1；（k为i，j中较大数，q为较小数，而且i，j从1开始；a[i][j]对应数组下标为和元素个数相同。

5，三角矩阵、对角矩阵压缩存储

三角矩阵对角线以上或以下的元素都为一个常数c。

**对角矩阵：（带状矩阵）**除了主对角为中心的带状区域，都为0。用二维数组来存储对角矩阵。

6，稀疏矩阵压缩存储

由三元组顺序表（行，列，元素）来唯一确定稀疏矩阵的一个非零元，矩阵由若干三元组+矩阵维数+非零元素总个数来确定。三元组称为有序的双下标法。

十字链表：灵活插入新的非零元素

需要m维行指针和n维列指针分别指向对应行列的元素.

三、广义表

广义表拓宽了元素的范围，可以递归定义自己。大写字母表示广义表，小写字母表示原子。除表头以外的元素组成的子表就是表尾；首元素是表头，表头可以是原子或子表。

1，广义表的性质

2，广义表和线性表的区别

广义表的基本运算：求表头+求表尾。
广义表中元素不是同样大小，因此不能用数组来存储，通常用链表存储。