数据结构之串和数组（实验）
126 浏览量
2023-12-16
10:26:49
上传
评论
收藏 908KB PDF 举报
串和数组
一 目的
1、掌握串的存储结构和模式匹配算法；
2、掌握特殊矩阵和稀疏矩阵的压缩存储方法及应用。
二 内容
1、实现串的模式匹配算法。
2、实现稀疏矩阵的三元组表压缩存储方法
3*、三元组表压缩存储方法基础上实现稀疏矩阵的转置，主要涉及矩阵中每
一行非零元素的个数的求解方法和转置矩阵的每一行中的第一个元素在其三元
组表中的存储位置的计算。
三 设计说明
1. 采用 KMP 方法实现串的模式匹配，KMP 算法是一种改进的字符串匹配算法，关键
是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。定义
next 函数来找出下一次目标函数与模式比较的位置.
2. 稀疏矩阵的压缩存储采用三元组的方法实现。其存储规则是：每一个非
零元素占一行，每行中包含非零元素所在的行号、列号、非零元素的数值。
四 功能说明
模式串中每个字符的最大真子串构成一个数组，定义为模式串的 next[j]函
数。模式串的 next[j]函数定义如下：next[j]函数表示的是模式串 t 中是否存
在最大真子串，以及最大真子串的字符个数 k。这里之所以称为最大真子串，是
因为：①求出的是所有子串中最大子串；②不允许 k 等于 j。
五 调试分析
1.串的查找操作也称作串的模式匹配操作，模式匹配操作的具体含义是：在
主串（也称作目标串）中，从位置 start 开始查找是否存在子串（也称作模式串）。
KMP 算法的核心是利用匹配失败后的信息，尽量减少模式串与内容串的匹配次数
以达到快速匹配的目的。具体实现就是通过一个 next[]数组来实现，next[]数
组本身包含了模式串的局部匹配信息。KMP 算法的时间复杂度 O(m+n)。
六 测试结果
资源评论
