data structure——串

生存还是毁灭，这是一个值得思考的问题。
　　　　　　　　　　　——莎士比亚《哈姆雷特》

特点：
串的逻辑结构和线性表类似，串是限定了元素为字符串的线性表，但是，两者在操作上有很大区别：线性表的操作主要是针对的表内的某一个元素，而串操作主要是对串内的一个子串。

定义：
定长顺序存储定义：

1
2
3
4
5
typedef struct
{
	char str[maxsize+1];
	int length;
}Str;

定长存储结构不需要分配和释放空间，但是如果想要改变空间大小，需要重新定义结构体。

变长分配存储定义：

1
2
3
4
5
typedef struct
{
	char *ch;  //用malloc函数分配一个类型为char的连续存储空间,
	int length;  //后用ch指针指向这个空间的起始地址
}Str;

可以通过这样来使用变长结构体

1
2
3
Str S;  //定义一个名为S的变量
S.length=L;  //将长度设置为L
S.ch=(char*)malloc((L+1)*sizeof(char));  //为其分配空间，指针ch指向这个空间的首地址

操作：
1.赋值操作

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
int strassign(Str& str,char* ch) 
{
	if(str.ch)  //这个我们将要赋值的串，如果已经指向某个存储空间了，
		free(str.ch);  //那就先将他的存储空间释放掉
	int len=0;
	char *c=ch;  //定义一个指针c内容为ch的地址
	while(*c)  //当指针c所指的元素的值不为0就执行该循环
	{
		++len;  //c指针不为空，长度加一
		++c;  //指针向后移动，再看是否为空
	}  //求这个我们拿来赋值的数组中的字符的个数
	if(len==0)
	{
		str.ch=NULL;
		str.length=0;
		return 1;
	}
	else
	{
		str.ch=(char*)malloc(sizeof(char)*(len+1));
		if(str.ch==NULL)  //防止分配不到内存
			return 0;
		else
		{
			c=ch;  //让c指针指向ch
			for(int i=0;i<=len;++i,++c)
				str.ch[i]=*c;
			str.length=len;
			return 1;		
		}
	}
}

2.取串长度

1
2
3
4
int strlength(Str str)
{
	return str.length;
}

3.串比较操作 (ASCII码和长度的“数值”比较)

1
2
3
4
5
6
7
int strcompare(Str s1,Str 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];  //s1大于s2就返回一个大于0的数，反之同理
	return s1.length-s2.length;  
}

4.串连接操作

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
int concat(Str& str,Str str1,str2)
{
	if(str.ch)  //如果ch指针不为空就执行if语句
	{
		free(str.ch);
		str.ch=NULL;
	}
	str.ch=(char* )malloc(sizeof(char)*(str1.length+str2.length+1));
	if (str.ch==NULL)  //如果存储空间分配失败就返回0
		return 0;
	int i=0;
	while(i<str1.length)
	{
		str.ch[i]=str1.ch[i];
		++i;
	}
	int j=0;
	while(j<=str2.length)
	{
		str.ch[i+j]=str2.ch[j];
		++j;
	}
	str.length=str1.length+str2.length;
	return 1;
}

5.求子串操作(以下是实现了求str串从pos位置开始，len长度的子串，由substr返回)

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
int substring(Str& substr,Str str,int pos,int len)
{
	if(pos<0||pos>=str.length||len<0||len>str.length-pos)
		return 0;
	if(substr.ch)
	{
		free(substr.ch);
		substr.ch=NULL;
	}
	if(len==0)  //如果是空串的情况的话
	{
		substr.ch=NULL;
		substr.length=0;
		return 1;
	}
	else
	{
		substr.ch=(char*)malloc(sizeof(char)*len+1);
		int i=pos;
		int j=0;
		while(i<pos+len)
		{
			substr.ch[j]=str.ch[i];
			++i;
			++j;
		}
		substr.ch[j]='\0';  //这里j已经移到了一个空白位置，所以在这里加上\0就好
		substr.length=len;
		return 1;
	}
}

6.串清空操作

1
2
3
4
5
6
7
8
9
10
int cleanstring(Str &str)
{
	if(str.ch)
	{
		free(str.ch);
		str.ch=NULL;
	}
	str.length=0;
	return 1;
}

7.字符串模式匹配：
简单模式匹配算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int naive(Str str,Str substr)
{
	int i=1,j=1,k=i;  //从数组下标1开始存储，下标0不存储，k为主串中第一次匹配的位置
	while(i<str.length && j<=substr.length)
	{
		if(str.ch[i]==substr.[j])
		{
			++i;
			++j;
		}
		else
		{
			j=1;
			i=++k;
		}
	}
	if(j>substr.length)
		return k;
	else
		return 0;
}

KMP算法

在模式串j出发生不匹配时，只需要将F前移，使得F_l与F_n重合即可。
假如F串的左部和右部有不止一对F_l和F-n，我们取第一个满足条件的一对（即较长的一对）。

若想直接由s_k状态跳转到s_k+1，只需要移动指针j即可，i指针可以保持不变。

next数组是用来存储，当发生模式串与主串不匹配的时候，下一需要跳转到的位置。

模式串中第j个位置与主串中的第i个位置发生不匹配的时候，应从模式串中的第next[j]个位置与主串第i个位置重新比较。

KMP算法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

int KMP(Str str, Str substr ,int next[])
{
	int i=1,j=1;
	while(i<str.length&&j<=substr.length)
	{
		if(j==0||str.ch[i]==substr.ch[j])
		{
			++i;
			++j;
		}
		else
		{
			j=next[j];
		}
	}
	if(j>substr.length)
		return i-substr.length;
	else
		return 0;
}

next数组的计算：