​ 串，即字符串（String）是由零个或多个字符组成的有限序列。一般记为S=’a1a2…an’ (n＞=0)
​ 其中，S是串名，单引号括起来的字符序列是串的值；a可以是字母、数字或其他字符；串中字符的个数n称为串的长度。n=0时的串称为空串（用の表示）。

串的定义

​ 串也是一种特殊的线性表，数据元素之间呈线性关系，其基本操作如增删改查通常以子串为操作对象。

串的基本操作

  • StrAssign(&T,chars):赋值操作。把串T赋值为chars。
  • StrCopy(&T,S):复制操作。由串s复制得到串T。
  • StrEmpty(S)：判空操作。若s为空串，则返回TRUE，否则返回FALSE。
  • StrLength(S)：求串长。返回串s的元素个数。
  • ClearString(&S)：清空操作。将s清为空串。
  • DestroyString(&S)：销毁串。将串s销毁（回收存储空间）。
  • Concat(&T,S1,S2)：串联接。用T返回由S1和S2联接而成的新串
  • SubString(&Sub,S,pos,len):求子串。用Sub返回串s的第pos个字符起长度为len的子串。
  • Index(S,T)：定位操作。若主串s中存在与串T值相同的子串，则返回它在主串S中第一次出现的
    位置；否则函数值为0。
  • StrCompare(S,T)：比较操作。若S>T，则返回值>0；若S=T，则返回值=0；若S<T，则返回值<0。

串的存储结构

串的顺序存储
1
2
3
4
5
6
7
8
9
10
11
12
13
#define MAXLEN 255//预定义最大串长为255
typedef struct{
	char ch[MAXLEN];//每个分量存储一个字符
	int length;//串的实际长度
}SString;

typedef struct{
	char *Ch;//按串长分配存储区，ch指向串的基地址
	int length;//串的长度
}HString;
HString S;
S.ch = (char *)malloc(MAXLEN *sizeof(char));
S.length = 0;
串的链式存储
1
2
3
4
5
6
7
8
9
typedef struct StringNode{
	char ch;//每个结点存1个字符
	struct StringNode * next;
}StringNode, * String;
 
typedef struct StringNode{
	char ch[418]//每个结点存多个字符
	struct stringNode * next;
}StringNode, * String;

基本操作的实现

1
2
3
4
5
6
7
8
9
10
11
//求子串
//实现于顺序存储的结构下
bool SubString(SString &Sub, SString S, int pos,int len){
	//子串范围越界
	if(pos+len-1>S.length)
		return false
	for(int i=pos; i<pos+len; i++)
		Sub.ch[i-pos+l]= S.ch[il;
	Sub.length = len;
	return true;
}
1
2
3
4
5
6
7
8
9
//比较操作。若S>T，则返回值>0；若S=T，则返回直=0；若S<T，则返回值<0
int StrCompare(SString S，SString T)
	for (int i=1; i<=S.length && i<=T.length; i++){
		if (S.ch[i]!=T.ch[i])
			return S.ch[i]-T.ch[il;
    }
//扫描过的所有字符都相同，则长度长的串更大
	return S.length-T.length;
}
1
2
3
4
5
6
7
8
9
10
int Index(SString S, SString T){
	int i=1, n=StrLength(S), m=StrLength(T);
	SString sub;//用于暂存子串
	while(i<=n-m+l){
		SubString(sub,S, i,m);
		if(StrCompare(sub, T)!=0)++i;
		else return i;//返回子串在主串中的位置
    }
	return 0;//S中不存在与T相等的子串
}