串、数组和广义表
知识大纲•
- 串、数组和广义表
- 串
- 串的顺序存储
- 串的链式存储
- 模式匹配算法
- BF算法
- KMP算法
- 数组
- 特殊矩阵的压缩存储
- 广义表
- 串
串•
串的定义•
串的逻辑结构与线性表相似，区别仅在与串的数据对象限定为字符集
串是一种特殊的线性表
串通常以整体作为操作的对象，线性表通常以单个元素作为操作对象
串或字符串：是由零个或多个字符组成的有序序列
串值：双引号括起来的字符序列
子串：一个串中任意个连续的字符组成的子序列（含空串）
真子串：指不包含自身的所有子串
主串：包含子串的串相应地称为主串
子串位置：子串第一个字符在主串中的位置
空串：零个字符的串
空格串：由空格组成的串
串相等：当且仅当两个串的长度相等并且各个对应位置上的字符都相等
串的存储结构•
顺序存储
- 用一组连续的存储单元存储串值的字符序列
- 串的存储可以用定长一维数组来表示
- 顺序存储的字符串都是从下标为1的数组分量开始存储，下标为0的分量闲置不用
- 堆式顺序存储：在堆区上动态分配和释放字符数组空间
链式存储
- 使用链式存储结构
- 数据域为单个字符
- 块链存储：每个结点可以存放一个或多个字符，称每一个结点为块，称整个链表为块链结构
串的模式匹配算法•
子串的定位运算一般称为模式匹配或串匹配
著名的两种算法由BF和KMP
BF算法
- 用指针i，j指示主串S和子串T中当前待比较的字符位置，i的初值为pos，j的初值为1
- 如果两个串均未达到串尾，则循环执行以下操作
- 分别比较指针i，j所指的字符，若相等则指针i，j同时向后移动一位，继续比较
- 若字符值不相等，则指针后退重新开始匹配，变成i=i-j+2，j=1，然后重新匹配（指针i，j最开始指向下标为1的数组元素，每次回溯时，指针i向后移动一位，指针j回到原点）
模式匹配不一定从主串的第一个位置开始，可以从指定的主串中查找的起始位置pos
KMP算法
- 当第一个位置就出现字符不匹配，子串移动到主串的第二位进行比较
- 当其他位置出现字符不匹配，寻找公共前后缀
- 当字符匹配时，子串的比较箭头后移动一位继续比较
让模式串（子串）向右滑动，将前缀的字符串之间移动到后缀字符串的位置，然后让子串的n号位在与主串当前位置进行比较
n=公共前后缀长度+1
只移动子串，让模式串（子串）向右移动，不需要回溯主串指针
数组•
数组的定义•
数组是由类型相同的数据元素构成的有序集合，每个元素称为数组元素
数组是线性表的推广，特点是结构中的元素本身可以是具有某种结构的数据，但属于同一数据类型
一维数组：若线性表中的数据元素为非结构的简单元素则称为一维数组
二维数组：若一维数组中的数据元素又是一维数据结构，则称为二维数组
- 二维数组的逻辑结构：非线性结构，线性结构定长的线性表
数组的顺序存储•
一旦规定了其维度和各维度的长度，便可以为它分配空间
给出一组下标则可以求相应的数组元素的存储位置
特殊矩阵的压缩存储•
矩阵：一个由
mxn个元素排成的m行n列的表矩阵的常规存储：将矩阵描述为一个二维数组
矩阵的常规存储特点：
- 可以对其元素进行随机存取
- 矩阵的运算非常简单
- 存储密度为1
不适宜常规存储的矩阵：值相同的元素很多且某种规律分布；零元素多
压缩存储：多个值相同的元素只分配一个元素值的存储空间，对零元素不分配空间
能够压缩的矩阵
- 对称矩阵（关于主对角线左右元素相同）
- 三角矩阵（主对角线一边全为0/常数c）
- 对角矩阵（所有非零元素都集中在对角线中心的带状区域中，其他元素全为0）
- 稀疏矩阵（非零元素个数少）
广义表•
广义表的定义•
广义表是线性表的推广，也称为列表
对于线性表而言，存储的数据元素只能是单个元素，而在广义表中，数据元素可以是单个元素，称为原子，也可以是一个广义表，称为子表
广义表的定义是一个递归的定义
表头：非空广义表的第一个元素，可以是单原子，也可以是子表（广义表）
表尾：表头以外的全部元素构成的表，表尾一定是一个广义表
广义表的存储结构•
一对确定的表头和表尾可唯一确定广义表
表结点：由标志域，指示表头的指针域，指示表尾的指针域组成
原子结点：由标志域和值域组成
标志域：tag，tag=1表示结点为子表，tag=0表示结点为原子
广义表的深度：展开后所含的括号层数
广义表的长度：广义表第一层的元素个数（第一个括号里的元素个数）
微信- 支付宝
