第四章 串、数组和广义表
4.1 串的词定义
串（或字符串）是由零个或多个字符组成的有限序列。
串是内容受限制的线性表，它限定了表中元素为字符
串中字符的数目称为串的长度。
零个字符的串称为空串，其长度为零。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。
通常成字符在序列中的序号为该字符的在串中的位置。子串在主串中的位置以子串的第一个字符在主串中的位置来表示。
称两个串是相等的，当且仅当这两个串的值相等。即两个串的长度，对应各个对应位置的自负都相等。
空格常常是串的字符集合中的一个元素，可以出现在其他字符中间。由一个或多个空格组成的串。
4.4 数组
4.4.1 数组的类型定义
多位数组可以看成是线性表的推广，其特点是结构中的数据元素本身可以具有某种结构的数据，但属于统一数据类型。
一个n维数组实质上是n个线性表的组合，其每一维都是一个线性表。
4.4.2 数组的顺序储存
4.4.3 特殊矩阵的压缩储存
压缩储存即为多个值相同的元只分配一个储存空间，对零元不分配空间。
1.对称矩阵
2.三角矩阵
4.2案例引入
案例1：病毒感染监测
4.5 广义表
4.5.1 广义表的定义
广义表是线性表的推广，也称列表。表中的元素可以是称为原子的单个元素，也可以是一个字表，所以线性表可以看做广义表的特例
4.5.2 广义表的储存结构
广义表中的数据元素可以有不同的结构（或是原子，或是列表），因此难以用顺序存储结构表示，通常采用链式村树结构。
1头尾链表的存储结构
2.拓展线性链表的存储结构
4.6 案例分析和实现
案例1 病毒感染案例
4.3 串的类型定义、存储结构及其运算
4.3.1 串的抽象类型定义
4.3.2 串的储存结构
1. 串的顺序存储
用一组地址连续的储存单元存储串值的字符序列。按照定义大小，为每个定义的串变量分配一个固定长度的储存区。
2. 串的链式存储
占用存储量大且操作复杂
4.3.3 串的模式匹配算法
子串的定位运算通常称为串的模式匹配或串匹配。
1.BF算法
实现简单，但存在回溯，效率低，时间复杂度为O（m*m）。
2. KMP算法
对BF算法进行改进，消除回溯，提高了效率，时间复杂度为O（m+n）