线性结构
每个元素最多只有1个出度和一个入度，表现为一条线状。线性表按存储方式分为顺序表和链表。
存储结构：
顺序存储：用一组地址连续的存储单元依次存储线性表中的数据元素，使得逻辑相邻的元素物理上也相邻。顺序表
链式存储：存储各数据元素的结点的地址并不要求是连续的，数据元素逻辑上相邻，物理上分开。单链表、循环链表、双向链表。
顺序结构和链式存储的对比：
栈和队列
队列、栈结构如下图，队列是先进先出，分队头和队尾；
栈是先进后出，只有栈顶能进出。
循环队列
设循环队列Q的容量为MAXSIZE，初始时队列为空，且 Q.read 和 Q.front 都等于0.
元素入队时修改队尾指针，即：Q.read=(Q.read+1)%MAXSIZE。
元素出队时修改队头指针，即：Q.front=(Q.front+1)%MAXSIZE。
根据队列操作的定义，当出队操作导致队列为空时，有Q.rear Q.front;
若入队操作导致队列满，则Q.rear Q.front。
- 在队列空和队列满的情况下，循环队列的队头、队尾指针指向的位置是相同的，此时仅仅根据 Q.rear 和 Q.front 之间的关系无法判定队列的状态。为了区别队空和队满的情况，可采用两种处理方式：
设置一个标志：以区别头、尾指针的值相同时间队列是空还是满；
牺牲一个存储单元：约定以“队列的尾指针所指位置的下一个位置是队头指针时”表示队列满。
![[Pasted image 20220425170659.png]]
字符串
字符串是一种特殊的线性表
空串：长度为0的字符串，没有任何字符。
空格串：由一个或多个空格组成的串，空格是空白字符，占一个字符长度。
子串：串中任意长度的连续字符构成的序列称为子串。含有子串的串称为主串，空串是任意串的子串。
串的模式匹配：子串的定位操作，用于查找子串在主串中第一次出现的位置的算法。
模式匹配算法：
朴素的模式匹配算法：也称为布鲁特-福斯算法，其基本思想是从主串的第1个字符起与模式的串的第1个字符比较，若相等，则继续逐个字符进行后续的比较；直至模式串中每个字符依次和主串中的一个连续的字符序列相等为止，此时成为匹配成功，否则称为匹配失败。
KMP算法：
对基本模式匹配算法的改进，其改进之处在于：每当匹配过程中出现相比较的字符不相等时，不需要回溯主串的字符位置指针，而是利用已经得到的“部分匹配”结果将模式串向右“滑动”尽可能远的距离，再继续进行比较。
当模式串的字符Pj与主串中相应的字符Si不相等时，因其前j个字符（“p0...pj-1”）已经获得了成功的匹配，所以若模式串中“p0...pk-1”与“pj-k...pj-1”相同，这时可令pk与Si进行比较，从而使i无须进行回退。
在 KMP 算法中，依据模式串的 next 函数值实现子串的滑动。若令 next[j] =k，则 next[j] 表示当模式串中的 pj 与主串中相应字符不相等时，令模式串的 next[j] 与主串的相应字符进行比较。
数组
数组是定长线性表在维度上的扩展，即线性表中的元素又是一个线性表。N维数组是一种 “同构” 的数据结构，其每个数据元素类型相同、结构一致。
可以表示为行向量形式或者列向量形式线性表，单个关系最多只有一个前驱和一个后驱，本质还是线性的。
数组结构的特点：数组元素固定；数据元素类型相同。数据元素的下标关系具有上下界的约束且下标有序。
数组元素固定，一般不做元素删除和插入运算，适合于采用顺序结构。
数组存储地址的计算：
假设每个数组元素占用存储长度为len，起始地址为a，存储地址计算如下（默认从0开始编号）：
矩阵
特殊矩阵：矩阵中的元素（或非0元素）的分布有一定的规律。常见的特殊矩阵有对称矩阵、三角矩阵和对角矩阵。
对称矩阵：aij=aji（1<i,j<=n）
对角矩阵：矩阵中的非零元素都集中在以主对角线为中心的带状区域。
三角矩阵：矩阵中主对角线上方都为非零元素，下方都为零元素（或相反）。
稀疏矩阵：在一个矩阵中，若非零元素的个数远远少于零元素个数，且非零元素的分布没有规律。
存储方式为三元结构，即存储每个非零元素的（行、列、值）
广义表
广义表是线性表的推广，是由0个或多个单元素或字表组成的有限序列。
广义表与线性表的区别：线性表的元素都是结构上不可分的单元素，而广义表的元素既可以单元素，也可以是有结构的表。
广义表一般记为：LS = （α1，α2，...,αn）
其中 LS 是表名，ai是表元素，它可以是表（称为子表），也可以是数据元素（称为原子）。其中n是广义表的长度（也就是最外层包含的元素个数），n=0的广义表为空表，而递归定义的重数就是广义表的深度，即定义中所含括号的重数（单边括号的个数，原子的深度为0，空表的深度为1）。
head()和tail():取表头（广义表第一个元素，可以是子表也可以是单元素）和取表尾（广义表中，除了第一个表元素之外的其他所有表元素构成的表，非空广义表的表尾必定是一个表，即使表尾是单元素）操作。
文章评论