🔵

串的逻辑结构与线性表相似，区别仅在于串的数据对象限定为字符集

串是一种特殊的线性表

串通常以整体作为操作的对象，线性表通常以单个元素作为操作对象

串或字符串：是由零个或多个字符组成的有序序列

字串：串中任意个连续的字符组成的子序列

空串：零个字符的串

🔴空格串：由空格组成的串

串有两种基本存储结构：顺序存储，链式存储

顺序存储

用一组地址连续的存储单元存储串值的字符序列

串的存储可以用定长一维数组来表示

⚫️ ::顺序存储的字符串都是从下标为1的数组分量开始存储，下标为0的分量闲置不用

堆式顺序存储：在堆区上动态分配和释放字符数组空间

链式存储

为了方便串的操作，设头指针和尾指针分别指向第一个节点和最后一个节点

🔴当字符无法完全将串的节点占满，用#来补满剩下的空间

块链存储：每个节点可以存放一个或多个字符，称每一个节点为块，称整个链表为块链结构

字串的定位运算一般称串的模式匹配或串匹配

著名的两种算法BF ,KMP

用指针i，j指示主串S和子串T中当前待比较的字符位置，i的初值为pos，j的初值为1

如果两个串均未达到串尾，则循环执行以下操作

分别比较指针i，j所指的字符，若相等则指针i，j同时向后移动一位，继续比较

若字符值不相等，则指针退后重新开始匹配，变成i=i-j+2，j=1，然后重新匹配

（指针i，j最开始指向下标为1的数组元素，每次回溯时，指针i向后移动一位，指针j回到原点）

🔴模式匹配不一定从主串的第一个位置开始，可以从指定的主串中查找的起始位置pos

只移动子串，让模式串向右移动，不需要回溯主串指针

让模式串向右滑动，将前缀的字符串直接移动到后缀字符串的位置，然后让子串的n号位

在与主串当前位置进行比较

🔴（n=公共前后缀长度+1）

这是因为： 如果字符匹配时，模式串上的比较箭头会向后移动一位

而当遇到字符不匹配时，模式串需要向右移动，主串保持不动，而指向模式串的比较箭头仍留在原地，

所以下一次再比较时，该比较箭头指向的位置n会发生改变

数组是由类型相同的数据元素构成的有序集合，每个元素称为数组元素

数组可以看成线性表的推广，其特点是结构中的元素本身可以具有某种结构的数据，但属于同一数据类型

对于数组，一旦规定了其维度和各维的长度，便可以为它分配空间，

而只要给出一组下标则可以求相应的数组元素的存储位置

如

🔴下标存放从1开始

所谓压缩存储，是指为多个值相同的元只分配一个储存空间，对零元不分配空间

广义表是线性表的推广，也称为列表

对于线性表而言，存储的数据元素只能是单个元素，而在广义表中，数据元素可以是单个元素，称为原子，也可以是一个广义表，称为子表

🔴:广义表的定义是一个递归的定义

两种重要的运算取表头 取表尾

取表头

取出的表头为非空广义表的第一个元素，它可以是单原子，也可以是一个子表

取表尾

取出的表尾为除去表头以外的全部元素构成的表

表尾一定是一个广义表

由于广义表中的数据元素可能为原子或者广义表，因此需要两种结构的结点

一种是表结点，用于表示广义表

另一种是原子结点，用于表示原子

🔴一对确定的表头和表尾可唯一确定广义表

表结点：由标志域，指示表头的指针域，指示表尾的指针域组成

原子结点：由标志域和值域组成

标志域：tag，tag=1表示结点为子表，tag=0表示结点为原子

🔵:广义表的长度和深度

广义表长度：广义表中第一层的元素个数（第一个括号里面的元素个数）

广义表深度：广义表的最大的嵌套次数