预习篇之串、数组和广义表

串

（笔试重点 ：笔试选择题：好像有算子串的个数吧，方正不多；编程题笔试偏多偏简单，算送分题多，就是那种一版会编程的读了题就能做的，eg：字符串局部位旋转，单词颠倒等 ）

串（字符串）：是零个或多个字符组成的有限序列，一般记为S=‘a1a2…..an’，属于取值受限的线性表”为任意串的子串。

主串：包含子串的串相应地称为主串

位置：字符在串中的序号称为该字符在串中的位置。

串相等：只有两个串的长度相等，且每个对应的字符都相等时才相等。

空格串：由一个或多个空格组成的串，非空串。

存储：

定长顺序串：存储分配是在编译时完成的，用一组地址连续的存储单元存储串的字符序列。（开始下标：0,；结束标志字“\0”）

堆分配存储（堆串），用称为“堆”的自由存储空间，并可用malloc()和free()函数完成动态存储管理。

串的块链存储表示（链表）:

串的模糊匹配算法：朴素模式匹配算法（Brute-Force算法，简单匹配算法）、KMP算法

数组和广义表

（见过相关的选择题，出的不多，了解概念就好）

数组

定义：n(n>1)个相同类型数据元素a0,a1,…,an-1构成的有限序列，且该有限序列存储在一块地址连续的内存单元中。是线性表在元素上的扩展。

矩阵的压缩存储：特殊存储（对称矩阵、三角矩阵、对角矩阵）

广义表

定义：是线性表的推广，是由零个或多个单元素或子元素所组成的有限序列

广义表的长度：表中所含元素的个数n

广义表的深度：广义表展开后所含的括号的最大层数

表头：非空时，称第一个元素a1为广义表的表头，可能是原子，也可能是广义表；

表位：其余元素组成的表（a2,a3…….an）称为广义表的表尾，一定是广义表。

存储：头尾链表存储表示、扩展线性存储表示、