第3章--字符串-数组-特殊矩阵.ppt

数据结构DataStructures 化志章江西师范大学计算机信息工程学院E mail hzz 2 35 数据结构 引言第一章概论第二章线性表第三章广义表 字符串 数组和特殊矩阵第四章递归技术第五章树和二叉树第六章图第七章检索第八章内排序第九章外排序第十章动态存储管理 3 35 字符串概念及数据结构 实际存储方式 应用字符串的模式匹配朴素的模式匹配算法快速模式匹配算法 KMP算法 数组特殊的矩阵对称阵 三角阵 带状矩阵 X对角阵 稀疏矩阵广义表 第三章字符串 数组 广义表 特殊矩阵 4 35 1 字符串 概念及数据结构定义 由零个或多个字符构成的有限序列 一般可表示成如下形式 c1c2c3 cn n 0 当n 0时表示空串 ADTstring 数据对象D 由零个或多个字符构成的有限集合 数据关系R 其中ai ai 1 D i 1 2 n 1 字符串的基本操作如下 ADTstring 5 35 1 字符串 字符串的实际存储方式静态存储结构 即顺序存储结构 堆存储结构 顺序存储 动态分配 即总空间足够大 且顺序 地址连续 执行时在此空间动态分配 释放字符串 链式存储结构串名的存储映象 即建立串名和串值之间的对应关系的一个符号表 对C中的字符串 若从输入设备读取 最好定义为字符数组 而非字符指针 二者在空间分配方面有很大不同 6 35 1 字符串 相关知识串的表示 字符的表示 空串及其表示 主串 子串 子串在主串中的位置 串的相等 一一对应 基本运算 插入 删除 求子串 串的连接应用举例已知S xyz T x z y 试利用连接 求子串 substr s i j 和置换 replace s1 i j s2 等基本操作 将S转化为T 已知三个字符串分别为S ab abcaabcbca a S1 caab S2 bcb 利用所学字符串基本运算函数得到结果串为 S3 caabcbca aca a 1 s1 substr s 1 5 s1 xyz s2 substr s 3 1 s2 y s3 substr s 6 1 s3 s4 substr s 7 1 s4 replace s1 3 1 s3 s1 x z s s1 s4 s2 s x z y 2 a index S S1 1 定位caab的起始位置b index S S2 1 3 定位ca a的起始位置 3是S2的长度x substring s a strlength s a 1 y substring s b strlength s b 1 S3 concat x y 7 35 1 字符串的模式匹配 模式匹配的含义给定文本串t和模式串p 编制算法寻找模式p在文本串t中首次出现的起始位置 t p x 表示字符串x的长度 即判断p是否为t的一部分 若是 返回首次出现位置 朴素的模式匹配算法注意探测每一位置是否能匹配成功 能否优化 simpleMatch t p for i 0 i t i ifsuccess t p i returni return0 success t p i for j 0 j p j if t i j p j return0 return1 8 35 1 字符串的模式匹配 快速模式匹配算法 KMP算法D E Knuth V R Pratt J H Morris同时发现 时间复杂度为O m n m n分别为文本串和模式串的长度 策略 充分利用已匹配的结果 以便最大幅度减少无效匹配次数无效匹配 即明知无效仍实施的匹配 关键点 真前缀真后缀概念的产生next函数的产生关键词 已 部分 匹配串长度 当前比较点 9 35 1 字符串的模式匹配 KMP算法预备知识对字符串S ababab 前缀 空 a ab aba ababab后缀 空 b ab bab ababab真前缀和真后缀 若s既是t的前缀 又是t的后缀 则称s是t的真前缀和真后缀 例如 abcdxyzzabcdaaaaxyzzaaaa思考题真前缀和真后缀能带来什么好处 10 35 1 字符串的模式匹配 快速模式匹配算法 KMP算法 11 35 a 如何充分利用已匹配结果 说明 根据对k的假设 b必然是串p 0 a 1 的最大真前缀的长度 引出真 前后缀next a 表明p a 与t i 失配 时 t i 应与p next a 比较 此时部分匹配长度为p 0 a 1 的最大真前缀长度 即next a 某下标 p 0 a 1 的最大真前缀长度 真前缀的使用公式1 next a p 0 a 1 的最大真前缀长度if存在真前缀 当前匹配长度 线段p 0 a 1 最大真前缀长度 记做next a 即 公式2 next a 模式串的起始下标 0 if不存在真前缀 12 35 注意 其中a作为已匹配长度 下面的关键是求解next KMP主程序 算法思想 由于匹配长度就是模式串的当前比较字符的下标 二者合一 t p 分别表示t p的长度 KMP t p 1 a 0 i 0 2 while i t 13 35 next a p 0 a 1 的最大真前缀长度if存在真前缀模式串的起始下标 0 if不存在真前缀 假定已知 所有next 0 a 1 的值 令next a 1 b 求解 next a 即求解p 0 a 1 的最大真前缀的长度 14 35 综上可得求解next i 的方法 即对在求解过程的任一位置i 均有 令b next i 1 ifb 1 p i 1 p b next i b 1 else b next b 求解next 算法思想 c next p 1 next 0 1 i 1 b next i 1 2 while i p 3 if b 1 p i 1 p b next i b 1 b i elseb next b 注意 next a p 0 a 1 的真前缀长度 15 35 2 数组 数组可以看成是一种特殊的线性表 即线性表中数据元素本身也是一个线性表 例如 n维数组可看作一个一维数组 每一元素为一n 1维数组 数组的最大特点是存储空间连续 不论数组是多少维 其空间总是存储在一个线性一维空间 因此对多维数组 给出任一元素映射到一维空间的位置映射函数 是一项重要任务 行序为主序和列序为主序 16 35 3 特殊矩阵的压缩存储 对称矩阵 17 35 Loc aij Loc a11 i i 1 2 j 1 元素空间大小 3 特殊矩阵的压缩存储 三角矩阵 18 35 3 特殊矩阵的压缩存储 对角矩阵 b条对角线 b条对角线 按行序 列序 主对角线序存储 如书本约定 除第一行和最后一行外 每行都分配2b 1个元素的空间 将带状区域中的元素存储于 2b 1 n 2b L个存储单元之中 其中L为每个元素占用空间的大小 19 35 3 特殊矩阵的压缩存储 稀疏矩阵 定义 非零元较零元少 且分布没有一定规律的矩阵压缩存储原则 只存矩阵的行列维数和每个非零元的行列下标及其值 M由 1 2 12 1 3 9 3 1 3 3 6 14 4 3 24 5 2 18 6 1 15 6 4 7 和矩阵维数 6 7 唯一确定 为何加上矩阵的维数 顺序存储结构 三元组表 20 35 稀疏矩阵的压缩存储方法 678 1212 139 31 3 3614 4324 5218 6115 64 7 defineM20typedefstructnode inti j v JD JDma M ma 0 i ma 0 j ma 0 v分别存放矩阵行列维数和非零元个数 三元组表所需存储单元个数为3 t 1 其中t为非零元个数 21 35 稀疏矩阵的压缩存储方法 伪地址表示法伪地址 本元素在矩阵中 包括零元素再内 按行优先顺序的相对位置 012345678 伪地址法需存储单元个数为2 t 1 22 35 稀疏矩阵的转置 求三元组表的转置矩阵转置的含义 1 矩阵行 列维数互换2 3 重新按行有序 算法思想 普通转置 1 先将行列维数交换2 for i 1 i 原列数 i 从头至尾扫描三元组若是第i列的元素 则将其依次加入新三元组表 inttrans sparmat JDma JDmb intcol p n t k if ma 0 v 0 return 0 mb 0 i ma 0 j mb 0 j ma 0 i mb 0 v ma 0 v k 1 for col 1 col ma 0 j col for p 1 p ma 0 v p if ma p j col mb k i ma p j mb k j ma p i mb k v ma p v k return 1 算法分析 T n O 列数n 非零元个数t 若t与m n同数量级 则T n O m n2 23 35 768 13 3 1615 2112 2518 319 3424 46 7 6314 col 1 col 2 24 35 方法二 快速转置即按ma中三元组次序转置 转置结果放入b中恰当位置 此法关键是要预先确定M中每一列第一个非零元在mb中位置 为确定这些位置 转置前应先求得M的每一列中非零元个数 实现 设两个数组num col 表示矩阵M中第col列中非零元个数cpot col 指示M中第col列第一个非零元在mb中位置显然有 1 3 5 7 8 8 9 25 35 算法思想 1 初始化 交换行列维数等 2 置num 数组全为0 3 遍历三元组 填写num 即对第i个元素 其列值为k 则num k 4 根据公式填写数组cpot 5 遍历三元组 实施一步到位转置对第i个元素 其列值为k 填入第k行的起始地址处行 列 值 列 行 值第k行的起始地址 intfast transpos JDma JDmb intn col p k t intnum M cpot M n ma 0 j t ma 0 v mb 0 i n mb 0 j ma 0 i mb 0 v t if t 0 return 0 for col 0 col n col num col 0 for p 1 p t p k ma p j num k cpot 0 0 cpot 1 1 for col 2 col n col cpot col cpot col 1 num col 1 for p 1 p t p col ma p j k cpot col mb k i ma p j mb k j ma p i mb k v ma p v cpot col return 1 算法分析 T n O M的列数n 非零元个数t 若t与m n同数量级 则T n O m n 26 35 768 13 3 1615 2112 2518 319 3424 46 7 6314 4 6 2 9 7 5 3 27 35 稀疏矩阵的链式存储结构 带行指针向量的单链表表示1 每行的非零元用一个单链表存放 2 设置一个行指针数组 指向本行第一个非零元结点 若本行无非零元 则指针为空 表头结点与单链表结点类型定义 需存储单元个数为3t m 28 35 十字链表稀疏矩阵的每行 每列均对应一循环链表 形成十字 包含max 行值 列值 个表头结点的循环链表 指针数组h h i 指向第i个结点 代表第i行 列的表头 h 0 作为整个链表的表头 typedefstructmatrixnode introw col structmatrixnode right down union intval structmatrixnode next tag matrixnode typedefmatrixnode spmatrix typedefspmatrixheadspmatrix 100 对十字链表 为方便定位行 列 需要max 行数 列数 1个表头结点 这样 第i个表头结点的right down 分别对应第i行 第i列 29 35 普通的十字链表 节约空间 30 35 带指针数组的十字链表 方便定位 31 35 创建十字链表算法 创建带指针数组的十字链表定义足够大的数组 输入行数m 列数n 元素个数t 初始化表头 造max m n 1个表头结点的循环链表 h i 指向第i个结点 代表第i行 列的表头 h 0 指向整个链表的表头 for i 1 i 造结点Q 将h x right链的末尾指向Q 将h y down链的末尾指向Q 为高效 可将b c两步用头插法 算法分析 T n O t s 其中 t 非零元个数s max m n 32 35 带指针数组的十字链表的创建过程示意图 注意 此循环指针在每次插入新结点时修改 此处为方便画图 在最后才补充完整 列的循环指针