数据结构
串
本质
-
内容受限的线性表
- 数据元素是一个字符
概念
-
子串
- 一个字符串中任意一个连续字符组成的子序列
- 空串是任何字符串的子串
-
空格串
- 空格字符组成的字符串
- 长度为空格字符的数目
模式匹配
-
BF算法
-
时间复杂度
- 最好情况下：O(m+n)
- 最坏情况下：O( m*n)
-
-
KMP算法
-
next数组计算
-
nextval数组计算
-
特点
- 主串指针不需要回溯
- next数组时间复杂度O(m)
-
数组
按行存储
按列存储
压缩存储
-
对称矩阵
- 存储下三角以及对角线上的元素
-
三角矩阵
-
稀疏矩阵
-
三元组顺序表
-
三元组
- row|col|value
-
triElems|maxsize|rows|cols|num
-
基本操作
-
转置
-
关键
- 矩阵的行数 n 和列数 m 的值交换
- 将三元组中的 i 和 j 调换
- 转换之后的表同样按照行序（置换前的列序）为主序，进行排序
-
简单转置
- 将矩阵的行数和列数进行调换
- cols次遍历三元组顺序表，将同一行的元素按顺序转置存放到转置矩阵中
- 一定程度上节省了空间，但是时间复杂度很高
-
快速转置
- cNum:记录原矩阵中每一列的非零元个数
- cPos:记录每一列第一个非零元在转置矩阵的位置
- 直接将结果放到转置矩阵对应位置中
-
-
-
提取指定元素都需要遍历整个数组，效率低
-
-
行逻辑链接的顺序表
- 将矩阵中的非 0 元素采用三元组的形式存储到一维数组 data 中
- 使用数组 rpos 记录矩阵中每行第一个非 0 元素在一维数组中的存储位置
-
十字链表
-
三元组+right|down
-
rowHead|colHead|rows|cols|num
-
行链表与列链表
-
基本函数实现
- 取/修改指定位置元素
- 加法运算
-
-
广义表
定义
- 广义表是线性表的推广，广义表中每个元素可以是原子，也可以是子表，原子即单个元素，而子表是广义表
概念
-
长度
- 第一层所含的元素个数
-
深度
-
max(每个元素深度) + 1
- 括号深度
-
存储
-
链式存储
-
tag|ref/data/hlink|tlink
-
tag
-
tag=0
-
专用头节点
- ref:记录该广义表被引用次数
-
-
tag=1
-
单元素结点
- data:存放数据
-
-
tag=2
-
子表结点
- hlink:存放指向子表表头的结点
-
-
-
tlink
- tag = 0时存放指向表头结点的指针
- 存放指向同一层下一个结点的指针
-
操作
-
前提
- 非空广义表
-
求表头
- head(A)
- 可以为表/空表/单元素值
-
求表尾
- 除去表头以外其余元素组成的表，一定是个广义表
- tail(A)
-
表头表尾都是空表的广义表
-
只有一个空的子表的广义表
- （（））
-
长度1，深度2
-
应用
- n元多项式
