串是字符串的简称,是计算机中常见且非常重要的一种数据结构。
串本质上是由零个或多个字符组成的有限序列。
注:
- 串中字符个数是可以是零个,被称为空串。如:
""
。- 串中的字符个数也可以是多个。如:
"helll wolrd"
。- 但串中的字符个数必须是有限个。
- 串中字符的个数称为串的长度。
如用 C 语言定义一个名为 str
的串:
char str[] = "abcdef";// 一个串
如用 Java 语言定义一个名为 str
的串:
String str = "abcdefg";// 一个串
注:通常串用一个字符数组来表示,在 Java 中
String
底层仍然是字符数组。从这个角度来看,数组str
内存储的字符分别为'a'
、'b'
、'c'
、'd'
、'e'
、'f'
和'
,其中'
''a'
''b'
是特别的,作为编译器识别串结束的标记。而串中字符实际为'c'
、'd'
、'e'
、'f'
、str
、str
。因此数组abcd
的长度为 7,而串a
的长度为 6。
串中还有一些概念:
- 子串:串中任意连续的字符组成的子序列称为该串的子串。如串
ab
中bc
、abcd
、 - 主串:包含子串的串称为主串。 、
- 字符的位置:通常把某个字符在串中的序号称为这个字符的位置。如串
'c'
中 - 空格串:空格也是字符,也可以组成串。通常由一个或多个空格组成的串称为空格串。但注意,区分空格串与空串,空格串不是空串。 字符的位置序号是 3,但如果用数组下标的方式说明 /** * 串结构体定义 */ 字符的位置则是 2。通常将子串第一个字符的位置作为子串在主串中的位置。typedef
abcde
都是该串的子串。'c'
串的逻辑结构和线性表类似,串是限定了元素为字符的线性表。从 *** 作上来看,串与线性表有很大的区别,线性表的 *** 作主要针对表内的某一个元素(如查找、插入或删除某个元素),而串的 *** 作主要针对串内的一个子串(如查找、插入或删除一个子串)。
但也因此串的许多 *** 作的算法思想可以借鉴线性表 *** 作的算法思想,它们是相近的。
结构体定长顺序存储表示结构体定义:
struct
/**
* 定长分配存储串,数组
*/ char {
[
+ ch1MAXSIZE];// 存储字符,多出的一个位置存储字符串的结尾字符 '/**
* 串的长度,即实际字符个数
*/';MAXSIZE 是已经定义好的常量,表示串的最大长度int;
}
; length/**
* 串结构体定义
*/
typedef Stringstruct
变长分配存储表示结构体定义:
/**
* 变长分配存储串,表示指向动态分配存储区首地址的字符指针
*/
char * {
;
/**
* 串的长度,即实际字符个数
*/ intch;
}
; lengthMAXSIZE+1
malloc()
Stringlength
注:
- 变长分配存储表示又叫做动态分配存储表示,因为是在程序执行过程中根据需要动态分配。所谓的动态分配就是需要多少个字符空间就分配多少个,而不是像定长分配那样先分配一个
char
的空间,可能会造成空间浪费。- 这种方式在使用时会使用函数
free()
来分配一个长度为malloc()
、类型为ch
型的连续存储空间,分配的空间可以用NULL
函数释放掉。如果用函数- 对比两种分配方式,发现变长分配存储表示有顺序存储结构的特点(实际上也可以通过下标来访问), *** 作中还可以根据实际需要来设定串长,更加灵活,更常用。
分配存储空间成功,则返回一个指向起始地址的指针,作为串的基地址,通常也是串第一个字符的地址,这个地址由void init(String *str)
指针来指向;如果分配失败,则返回str
。int assign(String *str, char *ch)
除此之外,还有一种块链存储表示,就是用链式存储结构,这里不多说明,因为不常用。
特点无。
基本 *** 作 概述串的常见 *** 作如下:
-
=
:串的初始化。其中=
表示未初始化的串。 -
ch
:串的赋值 *** 作不能直接用str
直接实现。因为串是一个数组,如果将一个数组的值赋给另一个数组,直接用str
是不可行的,必须对数组中的每个元素进行逐一赋值 *** 作。功能是将一个常量字符串ch
赋值给int copy(String *dest, String src)
。其中src
是未初始化的字符串,待赋予值;dest
是一个常量字符串。如果赋值成功则返回 1,否则返回 0 表示赋值失败。 -
dest
:复制字符串,从串src
复制得到串int isEmpty(String str)
。其中str
表示目标串,是复制后的串;int length(String str)
是源字符串,待复制的字符串。如果复制成功则返回 1,否则返回 0。 -
str
:判断串是否为空。其中int compare(String s1, String s2)
表示串。如果串为空则返回 1,否则返回 0 表示非空。 -
s1
:获取字符串的长度。其中s2
表示字符串。返回字符串的实际字符个数,即长度。 -
s1
:比较字符串的大小。其中s2
表示第一个待比较的字符串;s1
表示第二个待比较的字符串。如果返回正数则表示串s2
大于串int concat(String *str, String s1, String s2)
;如果返回负数表示串str
小于串s1
;如果返回 0 表示两个串完全相等。 -
s2
:将两个串首尾相接,合并成一个字符串。其中int substring(String *substr, String str, int pos, int len)
用来存储合并后的字符串;substr
表示待合并的第一个字符串;str
表示待合并的第二个字符串。如果合并成功则返回 1,否则返回 0 表示合并失败。 -
pos
:求从给定串中某一位置开始到某一位置结束后的串。其中len
用来存储得到的子串;int index(String str, String substr)
是总串;str
是起始位置,从 0 开始;substr
表示待求的子串的长度。如果获取子串成功则返回 1,否则返回 0 表示失败。 -
str
:对串substr
中某子串substr
进行匹配。其中str
是主串;void clear(String *str)
是子串,或称为模式串。如果匹配成功则返回子串str
在主串init
中的位置;如果匹配不成功,则返回一个可区别于主串所有位置的标记。 -
String str
:清空串。其中ch
是待清空的字符串。
length
初始化串。由于用结构体声明的一个串(ch
),其实是不能直接使用的,因为它的 NULL
指针指向和 length
都不是初始状态。例如:
为了能够之后的使用不出现什么问题,所以我们要将 ch
指针指向 NULL
,同时将 length
置为 0 表示是空串。初始化后如图:
实现步骤:
- 将串的 /** * 初始化串 * @param str 未初始化的串 */ 指针指向 void。
- 将串的 init 置为 0 表示空串。
实现代码如下:
(
* )=String NULLstr; {
str->ch = 0;
str->length } assign
=
=
str
赋值 *** 作。与普通变量赋值 *** 作不同,串的赋值 *** 作不能直接用 ch="hello world"
直接实现。因为串是一个数组,如果将一个数组的值赋给另一个数组,直接用 str
是不可行的,必须对数组中的每个元素进行逐一赋值 *** 作。如下函数的功能是将一个常量字符串赋值给 ch
,赋值 *** 作成功则返回 1,否则返回 0。以 len
为例如图所示:
实现步骤:
- 参数校验,如果串
len
是非空串,那么释放掉原来的空间。 - 统计常量字符串
str
中字符个数len
。 - 如果常量字符串的长度
str
为 0 则直接将len+1
初始化为空串然后返回; - 如果常量字符串的长度
'
不为 0,则为str
'length
分配长度为len
的存储空间,多分配一个存储空间是为了存储串的结束标记 - 最后返回 1 表示赋值成功。 字符。
- 如果分配成功则扫描常量字符串的每一个字符,将其一一赋值给新串 /** * 将一个常量字符串赋给一个串 * @param str 串 * @param ch 常量字符串 * @return 如果赋值成功则返回 1,否则返回 0 表示赋值失败 */。
- 赋值完毕后,修改新串的长度 int 为常量字符串的长度 assign。 (
实现代码如下:
*
, char*String )str// 0.参数校验,如果 str 中已有字符,那么释放原串空间,因为我们会给它重新分配空间 if (ch!= {
NULL
) freestr->ch ( ); {
=NULLstr->ch;}
str->ch // 1.统计常量字符串 ch 中的字符个数,只有知道它的字符个数,我们才能清楚为 str 分配多少个字符空间 // 局部变量,存储常量字符串 ch 中的字符个数int
=
0
;
// 注意,我们不能直接 *** 作 ch,因为是一个指针变量,在下面的 *** 作后我们会移动指针,会修改掉 ch 原本的值,后面如果需要再使用就不是传入的参数值,所以要创建一个临时局部变量引用它的值来进行 *** 作 len char *=
;
// 从头到尾扫描常量字符串,以结束标记 'while' 作为循环结束条件 (c * ch!=
')'
// 计数器加一 ++;c // 指针加一,继续下一个字符 ++; {
}
len// 2.为串 str 分配空间并赋值// 2.1 如果常量字符串长度为 0,那么串 str 也该为一个空串
if
c(==
0
)
=
NULL ;len = 0; {
str->ch return 1;
str->length } // 2.2 如果常量字符串长度不为 0,那么将常量字符串中所有字符赋给串 strelse
// 2.2.1 给串分配 len+1 个存储空间,多分配一个空间是为了存放 '=' 字符 (char
*
)
malloc {
(
str->ch sizeof (char )* (+1)); // 2.2.2 判断是否分配空间成功 // 2.2.2.1 如果分配空间失败,则返回 0len if (==NULL)
// 如果分配空间失败,则返回 0
return
0 ;str->ch } // 2.2.2.2 如果分配空间成功,则遍历常量字符串中的每个字符,依次赋给串 strelse {
// 局部变量,保存常量字符串 ch 的首地址,后续用于 *** 作
= ;// 2.2.2.2.1 扫描整个常量字符串,依次将每个字符赋给新串 str
for
(
int {
=
c 0 ch;
<=
; ++) i // 之所以在循环条件中使用 <=。是为例将常量字符串最后的 '[' 字符也复制到新串中作为结束标记 ]= i * len( i+) {;
str->ch}i// 2.2.2.2.2 给新串赋予长度,即常量字符串的长度 = ;// 2.2.2.2.3 返回 1 表示赋值成功c return i1;// 其实也可以使用 str->ch[i]=c[i];
}
}
str->length } lencopy
String
参数校验。 dest
src
src
dest
dest
length
复制串 *** 作。同上面的赋值 *** 作类似,不同复制 *** 作两个参数都是串结构体 src
类型的,而非常量字符串。将一个串中所有字符复制到另外一个串中。如果复制成功则返回 1,否则返回 0 表示复制失败。
实现步骤:
- 最后返回 1 表示复制成功。
- 给目标串 /** * 复制 *** 作,从串 src 复制得到串 dest * @param dest 目标串 * @param src 源串 * @return 如果复制成功则返回 1,否则返回 0 表示失败 */ 分配跟源串 int 一样长度加一的存储空间。
- 然后从头到尾扫描源串 copy 中所有字符,依次赋值给目标串 (。
- 将目标串 * 的长度 , 修改为跟源串 ) 一样的长度。 // 0.参数校验
实现代码如下:
if
( !=NULLString )destfree String src( {
)
// 0.1 参数校验,如果 dest->ch 不为 NULL,则释放其空间
; =dest->ch NULL ;} {
// 0.2 参数校验,如果 src.ch 为 NULL,那么 dest 串一定是空串,返回 1 表示复制成功ifdest->ch(.
dest->ch == NULL||
.
==
0 )src=ch NULL ; = src0length ; return1 {
dest->ch ; }// 1.复制字符串
dest->length = (char
* )malloc
(
sizeof
// 1.1 为 str->ch 分配长度为 src.length+1 个空间,多分配一个空间是为了存放 '\0' 字符
dest->ch ( char) *( .+1)); // 1.2 将串 src 中的每个字符依次赋值给串 dest forsrc(length int =0;<=
.
; ++) i // src.ch 表示串 src.ch 的首地址 // *src.ch 可以取出串 src.ch 的首个字符// *(src.ch+i) 可以取出 src.ch 的第 i 个字符 i [ src]length= i*( {
.
+
)
// 其实也可以用数组下标的方式取值,如:dest->ch[i]=src.ch[i];
dest->ch;i} // 1.3 将串 src 的长度也赋值给 dest 的长度 =.src;ch // 1.4 返回 1 表示复制成功 ireturn1
;
}
dest->length isEmpty
srclength
length/**
* 判断串是否是空串
* @param str 串
* @return 如果串是空串则返回 1,否则返回 0 表示非空
*/
int
isEmpty ()
// 判断串的长度是否为零,即可以判断它是否是空串
return
判断串是否为空。
实现步骤:
- 只需要判断串长度 . 是否等于 0 即可。
实现代码如下:
==
0 ;}String strlength
{
length
length
str/**
* 获取串的长度
* @param str 串
* @return 串的长度,即串的字符个数
*/length int length(
)
// 由于串的 length 属性记录了串的长度,所以直接返回即可,不需要遍历串中的所有字符去统计字符个数
获取串的长度,由于有一个成员 return 记录串中字符个数,所以直接返回即可。不需要从头到尾扫描串来统计字符个数。
实现步骤:
- 直接返回串的成员 . 即可。
实现代码如下:
;
} compare
s1
String strs2
{
s1
s2
strc1
lengthc2
c1
c2
串比较 *** 作。通常比较串中字符的大小,是比较它们的 ASCII 码值大小。两个串 s1
和 s2
比较大小的规则如下:
- 如果串
c1-c2
和c1
中待比较的字符是c2
和s1
,如果s2
的 ASCII 码值小于c1-c2
的 ASCII 码值,则返回串c1
小于c2
的标记。通常是s1
,即返回一个负数表示小于的情况。 - 如果
s2
的 ASCII 码值大于s1.length-s2.length
的 ASCII 码值,则返回串s1="hello"; s2="hellx"
大于i
的标记。通常是s1
,即返回一个正数表示大于的情况。 - 如果
s2
的 ASCII 码值等于s1
的 ASCII 码值,则继续两个串中的下一对字符。 - 经过上述步骤,在没有比较出串
s2
和s1
大小的情况下,先结束的为较小串,即s2
结果就是比较结果,两串同时结束则返回两串相等的标记,即 0。
以 s1
为例如图所示:
实现步骤:
- 声明变量
s2
,同时用来遍历串 - 如果当前字符相等,则继续判断两个串的下一对字符。 和
- 从头到尾同时扫描串
s1
和s2
,如果当前字符不相等,则返回它们之差。即如果差是一个正数则表示s1
比s1
大,如果是一个负数则表示s2
比s2
小。 /**
* 比较两个串
* @param s1 第一个待比较的串
* @param s2 第二个待比较的串
* @return 如果串 s1 大于串 s2 那么返回正数;如果串 s1 等于串 s2 那么返回 0;如果串 s1 小于串 s2 那么返回负数
*/ - 扫描结束后,返回 int,如果返回一个正数表示串 compare 比串 ( 长则表示 , 更大;如果返回一个负数表示串 ) 比串 // 局部变量,同时用来遍历串 s1 和 s2 短则表示 int 更大;如果返回 0 表示两个串一样的长,并且相等。
s1.length-s2.length
。实现代码如下:
=
0 ;// 同时扫描串 s1 和 s2 中相同下标处的字符String s1while String s2( {
<
. i && <.
)
// 如果当前两个字符不等,那么两个串一定不等,两个字符的差值就是对应 ASCII 码的差值,如果是正数则表示前者的 ASCII 码值更大,那么也就是串更大,否则相反 ifi ( s1.length [ i ] s2!=length. {
[
] )s1returnch.i[ ] s2-ch.i[] {
; s1}ch// 如果当前两个字符相等,则变量加一继续比较下一对字符i++ ; s2}ch// 循环完成后,表示前 i 个字符都相等并且两个串的长度不等,那么谁更长就更大ireturn.
-
.
i;}
concat
s1="hello"; s2="world"
参数校验。 s1str
length s1.length+s2.length+1
s2's1
'
lengthstr
s2
str
串连接 *** 作,将两个串首尾相接,合并成一个新字符串。以 s1.length
为例如图所示:
实现步骤:
- 首先给新串
length
分配长度为s1.length+s2.length
的空间,多分配一个空间是用来存放串的结束标记 - 最后返回 1 表示连接成功。 的。
- 接着将串 /** * 连接字符串,用 str 返回由 s1 和 s2 连接而成的新串 * @param str 用来保存连接后的新串 * @param s1 第一个串 * @param s2 第二个串 * @return 如果连接成功则返回 1,否则返回 0 */ 中所有字符依次复制到串 int 中。
- 接着将串 concat 中所有字符依次复制到串 ( 中,但是从 * 位置开始复制的。
- 修改新串 , 的长度 , 为 ),表示合并后串的长度。 // 0.参数校验
str
实现代码如下:
// 0.1 参数校验,如果 str 是非空串,则释放其原本的空间,因为要存储合并后的串内容
if (!=String NULLstr) String s1free String s2( {
)
;
= NULLstr->ch ; }// 0.2 参数校验,如果两个串的长度之和为 0,那么新串一定是一个空串 {
if(str.+
str->ch . ==0
)
=
NULL ;s1=length 0 s2;length return 1; {
str->ch } // 1.连接串 s1 和 s2=
str->length ( char*
) malloc(
sizeof
(
// 1.1 为串 str->ch 分配空间,长度应该为 s1.length+s2.length+1,多出来的一个空间用来存放串的结束标记 '\0' 字符
str->ch char )* (. +.+1)) ; // 如果分配空间失败则返回 0s1iflength ( s2==length NULL )return0;
}
// 1.2 先将串 s1 中的所有字符复制到串 str 中 forstr->ch ( int= {
0 ;<
.
;
++ )[ i ] =* i ( s1.length+ i); {
str->ch}i// 1.3 接着将串 s2 中的所有字符复制到串 str 中 for (ints1=ch 0 i;<=
.
;
++ )// 将串 s2 中的结束标记 '[' 也复制过来 i . +] i = s2*length( i.+ {)
str->ch;s1}length // 1.4 为连接后的串指定长度 i= . +.s2;ch // 1.5 返回 1 表示连接成功 ireturn1
;
}
str->length substring
s1str
length pos
s2len
lengthsubstr
str="hello world"; pos=3; len=6
参数校验。 len+1
'pos
'
len
'len
'
求子串 *** 作。求从给定串中某一位置开始到到某一位置结束的串的 *** 作叫做求子串 *** 作,规定开始位置总是在结束位置前边。以下是求
实现步骤:
- *
- 首先为子串分配长度为 , 的存储空间,多出来的一个空间用来存放串的结束标记 ,。
- 然后将主串中第 int 位置(包括本身)之后的 , 个字符复制到子串中。
- 将子串最后一个位置赋予串的结束标记 int。
- 置子串的长度为 )。 // 0.参数校验
实现代码如下:
// 0.1 校验参数 pos,位置必须在 [0, str.length) 之间,即下标的范围内,否则就是不合法
if (<String 0substr|| String str. ) posreturn 0 len; {
}
// 0.2 校验参数 len,子串长度不能小于 0;也不能大于 length-pos
if (pos < 0 || pos >= str.length- {
< )return
0
;
} // 0.3 如果要求的子串长度为 0,那么返回的子串为空串,直接返回即可len if ( == str0length ) pos = lenNULL {
; =0
;
return
1 ;len } // 1.求子串// 1.1 为子串分配长度为 len+1 的空间,多出来的一个空间用来存放串的结束标记 '=' {
substr->ch ( char*
substr->length ) malloc(
sizeof (char
)
*
(
substr->ch + 1) ); // 1.2 将主串中第 pos 个位置(包括本身)之后的 len 个字符复制到子串中int=0;for ( =len 0 ;<;++
)
[ i ] =*
( .i + +) i ; len} i// 1.3 让串的最后一个字符是 '[',表示是串的结束标记] {
// 星号用来取值,其实也可以写成这样:substr->ch[i]=str.ch[pos+i];
substr->ch=i';' // 1.4 置子串的长度为 len =;str// 1.5 返回 1 表示求子串成功ch return pos 1 i;}
index
'str="helxworhellold"; substr="hello"
'
substr->chi
ij
i
j
i
i-j+1
substr->length j
lenj==substr.length
'/**
* 定位子串,若主串 str 中存在与串 substr 值相同的子串,则返回它在主串 str 中第一次出现的位置
* @param str 主串
* @param substr 子串
* @return 如果存在子串则返回第一次出现的位置,否则返回 0
*/'
int index(
,
)
简单模式串匹配,对一个串中某子串进行定义。算法的基本思想是:从主串的第一个位置(下标为 0)起和子串的第一个字符开始比较,如果相等,则继续逐一比较后续字符;如果不相等则从主串的第二个字符开始,再重新用上一步的方法与子串中的字符做比较。以此类推,直到比较完子串中的所有字符。若匹配成功,则返回子串在主串中的位置;若匹配失败,则返回一个可用于区别主串所有位置的标记,如 // 变量,i 记录串 str 中字符的下标,j 记录串 substr 中字符的下标。以 int 为例如图所示:
实现步骤:
- 声明变量 = 和 0,分别用于扫描主串和子串,初始为 0,表示串中的第一个字符的位置。
- 同时扫描主串和子串中的所有字符,比较 , 和 = 所指向的字符是否相等,如果相等则都加一,继续比较主串和子串中的下一对字符。
- 如果不相等,则恢复 0 为 ;,即下一个字符;置 // 同时扫描主串 str 和子串 substr 为 0,表示又从子串的第一个字符开始比较。
- 扫描完成后,如果 while 表示子串存在于主串中,则返回子串在主串中第一次出现的位置。否则返回 ( 表示未找到。
实现代码如下:
<
. &&<String str. String substr) {
// 如果主串中的字符与子串中的字符相等,则继续比较下一对字符
if i ( .[ j ] ==.
[
] )i // 同时加一,指向串的下一个字符 str++length ; j ++ substr;length} {
// 如果不相等,那么就继续比较主串中下一个字符开始的串与子串,注意,需要恢复 i 和 j
else // 恢复主串中的 i,回到第 i-j 个字符,然后加一表示下一个字符str=ch-i+ 1 substr;ch// 而 j 要恢复为子串的第一个字符的下标,即为 0,又要从 0 开始比较起走j=0 {
;
i}}
j// 如果循环结束 j 等于 length,那么表示主串中一定存在子串if
(
==
. {
)
i // 则返回子串第一次出现的位置 i return j - ;}
else
j // 如果不相等,则表示子串不存在于主串中,在返回标记 0 return';'
}
}
clear
释放串所指向的空间。 ch
j NULL
substrlength
length/**
* 清空串
* @param str 串
*/ {
void
clear i ( j*
) // 释放原串空间 {
if
( !=NULL
)
free
(
清空串。
实现步骤:
- )
- 然后将其初始化,指针 ; 指向 },长度 // 然后指向 NULL 和将长度置为 0 置为 0。
实现代码如下:
=
NULL ;=String 0str; {
}
length
length
str->ch 'O(n)
'
length
O(1)
{
''length
'
'
ch1
str->chch2
Example002-实现串 str 的逆转函数,如果 str 为空串,则什么都不做
ch
Example004-从串 str 中的 pos 位置起,求出与 substr 串匹配的子串的位置
str->ch Example005-采用定长顺序存储表示串,编写一个函数,删除串中从下标为 i 的字符开始的 j 个字符 str1
str2
str->length Example007-编写一个函数,计算一个子串在一个主串中出现的次数并且不考虑子串重叠 str1
str2
注意事项
为什么要在结构体内定义一个
我们看串的结构体定义,无论是定长顺序存储还是变长顺序存储表示的结构体定义中都有一个 成员,该成员表示串的长度。
虽然串以 字符作为串的结束标记,因此可以利用这一点来计算串的长度,但是求串长的时候需要扫描整个串来统计字符的出现个数,时间复杂度为 。
所以专门定义了一个变量 来存储串的长度,这样求串长就变成了时间复杂度为 的 *** 作。
练习题注:不同参考资料中对串的结构体定义是有所不同的,有的用 作为结束标记,有的不用。而本篇中同时用 作为串尾的结束标记,也设定 表示串的长度。虽然会多一个存储空间,但更加方便。
- Example001-将串 str 中所有值为 的字符转换成 字符
- Example003-删除 str 中值为 的所有字符
- Example006-编写一个函数,将串 中的下标 i 到下标 j 之间的字符(包括 i 和 j 两个位置上的字符)用串 替换
- Example008-构造串的链表结点数据结构(每个结点内存储一个字符),编写一个函数,找出串 中第一个不在串 中出现的字符
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)