月份：2018年3月

串


串(String)是由零个或多个字符组成的有限序列,又名字符串


1.串的实现（定长顺序存储表示）

sstring.h下载

在实现之前先把需要使用到的库和头文件进行包含 
所需的头文件sstring.h已经在上方提供 

#include <stdio.h>
#include <stdlib.h>
#include "sstring.h"
1）生成一个其值等于chars的串T
Status StrAssign(SString &T,char *chars){
	//char是字符串常量
	//生成一个其值等于chars的串T
	int i = 0;
	while('\0' != *(chars+i) && i<MAXSTRLEN)
	{
		T[i+1] = *(chars+i);
		++i;
	 } 
	 T[0] = i; //串长度赋值给0号单元
	 return 0; 
}//StrAssign
2）串的复制
Status StrCopy(SString &T,SString S){ 
	//由串S复制得串T 
	int i;
	for(i=0;i<=S[0];i++){
		T[i] = S[i];
		
	}
	return 0; 
}//StrCopy
3）判断是否为空串
Status StrEmpTy(SString S){
	//串S存在
	//若S为空串，则返回TRUE，否则返回FALSE
	if(0==S[0])
	return TRUE;
	else
	return FALSE; 
}//StrEmpty
4）串的比较
Status StrCompare(SString S,SString T){
	//串S和T存在
	//若S>T则返回值>0，若S=T则返回值S=T，若S<T则返回值<0 
	int i = 1,j = 1;
	while(i<=S[0]&&j<=T[0])
	{
		if(S[i]>T[i])
		return 1;
		else if(S[i]<T[i])
		return -1;
		else{
			i++;
			j++;
		}
	}
	if(S[0]=T[0])
		return 0;
	else if(S[0]>T[0])
		return 1;
	else
	    return -1;
}//StrCompare
5）获取串的长度 
int StrLength(SString S){
	//返回S的元素个数，称为串的长度 
	return S[0];
}//StrLength
6）清空串
void ClearString(SString &S){
	//将S清为空串
	S[0] = 0; 
}//ClearString
7）串的拼接
void Concat(SString &T,SString S1,SString S2){
	//串S1和S2存在 
	//用T返回由S1和S2联接而成的新串
		int t = 1,s = 1;
		while(t<=MAXSTRLEN && s<=S1[0]+S2[0])
		{
			if(s<=S1[0])
			T[t++] = S1[s++];
			else
			{
			T[t++] = S2[s-S1[0]];
			++s;
			}
		} 
		T[0] = t-1;
}//Concat
8）串的遍历
void displayStr(SString T){
	//打印串
	int i ;
	for(i=1;i<=T[0];i++){
		printf("%c",T[i]); 
	}
}//displayStr
9）截取定长字符串
Status SubString(SString &Sub,SString S,int pos,int len){
	//用Sub返回串S的第pos个字符起长度为len的子串
	//1<=pos<=StringLength(S)且0<=len<=StrLength(S)-pos+1 
	int i,j;
	i = pos;
	j = 1;
	if(pos<1 || pos>S[0] || len<0 || len>S[0])
	return ERROR;
	while(j<=len)
	{
		Sub[j] = S[i];
		++i;
		++j;
	}
	Sub[0] = len;
	return 0;
}//SubString
10）判断是否为子串
int Index(SString S,SString T,int pos){
	//T为非空串，若主串S中第pos个字符之后存在于T相等的子串
	//则返回第一个这样的子串在S中的位置，否则返回0
	SString Sub;
	int n,m,i;
	if(pos>0)
	{
		n = StrLength(S);
		m = StrLength(T);
		i = pos;
		while(i <= n-m+1)
		{
			SubString(Sub,S,i,m);
			if(StrCompare(Sub,T)!=0)
			++i;
			else
			return i;				
		}
	} 
	return 0;
}//Index
11）替换不重叠子串
Status Replace(SString &S,SString T,SString V){
	//用V替换主串S中出现的所有与T相等的不重叠的子串
	int pos;
	pos = 1;
	pos = Index(S,T,pos);
	while(0!=pos)
	{
		StrDelete(S,pos,T[0]);
		StrInsert(S,pos,V);
		pos = Index(S,T,pos+V[0]);
	} 
	return OK;
}//Replace
12）在指定位置插入字符串
Status StrInsert(SString &S,int pos,SString T){
	//串S和T存在，1<=pos<=StrLength(S)+1;
	//在串S的第pos个字符之前插入串T 
	//遵循截断原则 
	int tlen,slen;
	int i,j,k;
	k=0;
	if(pos<1||pos>S[0]+1)
	return ERROR;
	tlen = T[0];
	slen = S[0];
	i = pos;
	j = 1;
	if(pos == S[0]+1){
		//插入在最后
		while(S[0]+j<=MAXSTRLEN && j<T[0]){
			S[S[0]+j] = T[j];
			j++;
		} 
		if(j<=T[0])//空间不足，截断
		S[0] = MAXSTRLEN;
		else
		S[0] = S[0]+T[0]; 
	}
	else{
		//在中间插入 
		for(i=S[0];i>=pos;i--){
			if(i+tlen<=MAXSTRLEN)
			S[i+tlen] = S[i];
			else
			k = 1;//溢出的位置 
		}
		i = pos;
		j = 1;
		while(i<=MAXSTRLEN && j<= tlen){
			S[i] = T[j];
			i++;
			j++;
		} 
		if(j<=T[0]){
			S[0] = MAXSTRLEN;
		}
		else
		{
			if(k != 0)//插入后溢出
			S[0] = MAXSTRLEN;
			else
			S[0]=S[0]+T[0]; 
		}
	}
	 return OK;
}//StrInsert
13）删除指定位置定长字符串
Status StrDelete(SString &S,int pos,int len){
	//串S存在，1<=pos<=StrLength(S)-len+1;
	//从串S中删除第pos个字符起长度为len的子串 
	int i,j;
	if(pos<1 || pos>S[0]-len+1)
	return ERROR;
	if(S[0] == pos+len-1){
		S[0] = S[0] - len;
	} 
	else{
		i = pos + len;
		while(i<=S[0]){
			//删除子串
			S[i-len]  = S[i];
			i++; 
		}
		S[0] = S[0]-len;
	}
	return OK;
}//StrDelete