数据结构串的定义及操作

串的定义

概念

  • 是由零个多个字符数组组成的有限序列。
  • 串中字符的个数称为串的长度,含有零个元素的叫空串。
  • 串是限定了元素为字符的线性表

(注:串与一般的线性表操作有很大区别,线性表主要针对表内的某个元素,而串操作主要针对子串

代码

C语言中,一个串可以如下定义,但仅以’\0’作为结束符时需要我们遍历整个数组,时间复杂度为O(n),这并不是我们想要的最优结果,

其他方法会在下文“串的结构体定义”部分有详细描述,这里仅举个例子

1
char str[] = "as123";

C语言来讲,串主要由一个字符数组表示,上方字符串str中的字符有 ‘a’ ,’s’, ‘1’,’2’,’3’,’\0’

下对**’\0’**单独介绍

‘\0’

‘\0’是转译字符,意思是告诉编译器,这不是字符0,而是空字符,是字符串的结束标志

字符数组str长度为7,而串str长度为6

串相关的术语

  • 串中任意连续的字符组成的子序列称为该串的子串
  • 包含子串的串称为主串
  • 某个字符在串中的序号称为这个字符的位置
  • 有一个或多个空格组成的串称为空格串

串的结构体定义

串的储存结构主要分为定长顺序储存变长分配储存两种

定长顺序储存

用额外一个变量来存放串的长度,这样求串长时间复杂度就降为了O(1)

1
2
3
4
5
6
7
8
9
#define MAXSIZE 1024

//串的定长顺序储存结构
typedef struct _str
{
char str[MAXSIZE+1];
int length;
}Str;

变长分配储存

1
2
3
4
5
6
7
//串的变长储存结构
typedef struct _str_p
{
char *ch;
int length;
}Str_p;

串的操作

此处以变长储存为例(定长顺序储存没什么太值得好说的)

1
2
3
4
5
6
7
8
9
//先定义一个串的结构体
typedef struct _str_p
{
char *ch;
int length;
}Str_p;

//定义一个串
Str_p str;

串的初始化

1
2
3
4
5
6
bool initStr(Str_p &str)
{
str.length = 0;
str.ch = nullptr;
return true;
}

串的赋值

1
2
3
ISO C++11 does not allow conversion from string literal to 'char *'
注意:在C++11里,指针指向的内容如果不可修改,就建议把该指针确认为const指针类型,否则会有个warning
也就是说我们这里要用 const char* ch 而非 char* ch
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
//参数:串, 串的内容
bool inputString(Str_p &str, const char* ch)
{
if(str.ch) free(str.ch);

int len = 0;
const char *c = ch;
while(*c)
{
++len;
//因为内存连续,所以可以对c进行自增
++c;
}

//若赋值为空,即该串为空串
if(!len)
{
str.ch = nullptr;
str.length = 0;
return true;
}
else
{
//len+1是为了存放'\0'
str.ch = (char*)malloc(sizeof(char)*(len+1));

if(!str.ch) return false;
else
{
c = ch;
for(int i=0; i<len; i++,c++)
str.ch[i] = *c;
str.length = len;
return true;
}

}

}

获取串的长度

1
2
3
4
int getStrLen(Str_p str)
{
return str.length;
}

串的比较

1
2
3
4
5
6
7
8
//串的比较
int strCompare(Str_p s1, Str_p s2)
{
for(int i=0; i<s1.length && i<s2.length; i++)
if(s1.ch[i]!=s2.ch[i])
return s1.ch[i] - s2.ch[i];
return s1.length - s2.length;
}

合并串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//参数: 合并后的字符串, 子串1, 子串2
bool conStr(Str_p &str, Str_p s1, Str_p s2)
{
initStr(str);
if(str.ch)
{
free(str.ch);
str.ch = nullptr;
}

str.ch =
(char*)malloc(sizeof(char*)*(s1.length+s2.length+1));

if(!str.ch) return false;

//将s1的字符保存到str
int i;
for(i=0; i<s1.length;i++)
str.ch[i] = s1.ch[i];

//同理
int j;
//此处取等号是为了把'\0'放进去
for(j=0; j<=s2.length; j++)
str.ch[i+j] = s2.ch[j];

str.length = s1.length + s2.length;

return true;
}

求子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
//参数: 子串, 父串, 起始位置, 切片长度
bool subStr(Str_p &substr,Str_p str, int pos, int len)
{
initStr(substr);
if(pos<0||
pos>str.length||
len<0||
len>str.length-pos)
return false;
if(substr.ch)
{
free(substr.ch);
substr.ch = nullptr;
}

//所求子串为空串
if(!len)
{
substr.ch = nullptr;
substr.length = 0;
return true;
}
else{
substr.ch =
(char*)malloc(sizeof(char)*(len+1));
int i = pos, j = 0;
while(i<pos+len)
{
substr.ch[j] = str.ch[i];
i++;
j++;
}

substr.ch[j] = '\0';
substr.length = len;

return true;
}

}

清空串

1
2
3
4
5
6
7
8
9
10
bool clearStr(Str_p &str)
{
if(str.ch)
{
free(str.ch);
str.ch = nullptr;
}
str.length = 0;
return true;
}
作者

CairBin

发布于

2021-11-04

更新于

2021-11-05

许可协议

评论