- 考研数据结构与算法(四)字符串
- 一、基本概念
- 1.1 主串和字串
- 1.2 串的操作函数
- 二、存储结构
- 2.1 定长顺序存储
- 2.2 堆分配存储
- 2.3 块链存储
- 三、串的匹配算法
- 3.1 暴力匹配
- 3.2 KMP匹配
- 3.2.1 next数组
- 3.2.2 NextVal数组
串(String)是由零个或多个字符组成的有限序列。一般记为: S = ′ a 1 a 2 … … a n ′ ( n > = 0 ) S='a_1a_2……a_n'(n>=0) S=′a1a2……an′(n>=0) 其中 S S S 是串名,单引号括起来的字符串序列是串的值, a i a_i ai 可以是字母、数字、或者其他字符,串中的 n n n 代表的是串的长度,当 n = 0 n=0 n=0 时,称其为空串
串的逻辑结构和线性表极为相似,区别仅在于串的数据对象限定在字符集中,在基本操作上也有很大的区别,例如线性表的操作通常是单个元素的操作,而串的操作是以子串(子串的大小是不确定的)为操作对象。
1.1 主串和字串串中任意个连续的字符组成的子序列称为该串的 子串 。包含字串的串则称为该子串的 主串
例如,假设有一字串 abb
那么它的 主串 可以是 aabbb
也可以是 abbbc
或者其他任何包含该子串的串
Concat(&T,S1,S2)
将字符串
S
1
S1
S1 和
S
2
S2
S2 连接并复制给
T
T
T 串SubString(&Sub,S,pos,len)
将字符串
S
S
S 从
p
o
s
pos
pos 到
p
o
s
+
l
e
n
pos+len
pos+len 的子串取出并赋值给
S
u
b
Sub
Sub 串StrCopy(&T,S)
将字符串
S
S
S 的值复制给字符串
T
T
TStrLength(S)
求字符串
S
S
S 的长度Index(S,T)
如果
S
S
S 中存在子串
T
T
T 则返回第一次出现的位置,否则返回
0
0
0
二、存储结构
2.1 定长顺序存储
和线性表的顺序存储结构相同,用一组连续的空间存储字符序列,结构如下:
#define MAXLEN 255
typedef struct {
char ch[MAXLEN];
int length;
}SString;
串的长度最多能为 MAXLEN
但是考虑到字符串以 KaTeX parse error: Undefined control sequence: \0 at position 1: \̲0̲ 结尾,也就是需要给字符串结束标识符留一个位置,那么实际的串长为 MAXLEN-1
但是由于我们这里设计该字符串结构的时候有一个 length
表示,所以我们可以使用到完整的 MAXLEN
的长度
堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列 ,但它们的存储空间是在程序执行过程中 动态分配 得到的,结构如下:
typedef struct {
char *ch;
int length;
}SString;
我们在堆的这个自由存储区去定制话分配空间,在C语言中,通过 malloc
和 free
函数可以完成动态存储管理。利用 malloc
)为每个新产生的串分配一块实际串长所需的存储空间,若分配成功则会返回一个指向分配空间起始地址的一个指针,作为字符串的基地址,我们则可以通过 ch
指针来访问这块空间,若分配失败,则返回 NULL
。
当然这里通过堆分配存储的话,需要我们自动管理内存,所以每当我们 malloc
了一个空间,我们需要在合适的地方去 free
掉,不然申请的空间越来越多最后就会没有空间可以使用,造成内存泄漏
这个就类似线性表的链式存储,不同的是对于每一个单元结点我们都将其当作一个定长字符串也就是一个块,那么不难得出如下结构:
#define MAXLEN 255
typedef struct SString{
char ch[MAXLEN];
struct SString * next;
}SString;
当然如果对于每一块的长度不定的话,我们同样可以通过堆空间的分配来做
#define MAXLEN 255
typedef struct SString{
char *ch;
int length;
struct SString * next;
}SString;
那么可以想象到这个结构:
在串 S S S 中找到子串 T T T 第一次出现的位置,如果没找到则返回 − 1 -1 −1
3.1 暴力匹配我们将串 T T T 不断的从串 S S S 的第一个位置往后一一比较,如果匹配失败则整体往后移动一位,操作如下图所示:
不难得出代码:
int Index(SString S,SString T) {
for(int i = 0,len = S.length - T.length + 1;i
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?