串
一、定义
串结构的定长顺序存储类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。
二、结构
在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，
则可用定长数组如下描述之。 typedef unsigned char SString[MAXLEN+1];
注意：
用SString[0]来存放串长信息；
串值后面加一个不计入串长度的标识符‘\0’；
串的实际长度可在予定义长度的范围内随意,超过予定义长度的串值则被舍去，称为“截断”
术语：
串的长度：串中字符的个数；零个字符的串称为空串，记为
空格串：由一个或多个空格组成的串，其长度为串中空格字符的个数
子串：串s中任意个连续的字符组成的子序列称为该串的子串，包含子串的串s相应地称为主串。
子串位置：字符在序列中的序号称为该字符在串中的位置。子串在主串中 的位置以第一个字符在主串中的位置来表示。
串相等：两个串相等，当且仅当这两个串的值相等。即，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。
串的类型定义
ADT string { 数据对象: 数据关系: 数据操作: StrAssign(&T,chars); //串赋值，生成一个值等于chars的串T StrCompare(S,T); //串比较，若S>T，返回值>0…… StrLength(S); //求串长 Concat(&T,S1,S2); //串连接，用T返回S1+S2的新串 SubString(&Sub,S,p,len); //求S中p位置起长度为len的子串 …… Index(S,T,p); //返回子串T在主串S中p字符之后首次出现的位置 Replace(&S,T,V); //用子串V代替串S中所有的子串T }string
串的基本操作
/—初始化—/
/*---初始化---*/ void InitSString(SString s) { s[0] = '\0'; }
/—串打印—/
/*---串打印---*/ void PrintString(SString s) { printf("\n%s",s+1); }
/—字符串的赋值—/
/*---字符串的赋值---*/ void StrAssign(SString s,char *str) { int len = strlen(str); for(int i = 0;i<len;i++) { s[i+1] = str[i]; } s[len+1] = '\0'; s[0] = len; }
/—求长度—/
/*---求长度---*/ int Strlenth(SString s) { int len = 0; while(*s!='\0') { len++; s++; } return len; }
/—创建串—/
/*---创建串---*/ bool CreatSString(SString s,char *str) { InitSString(s); //初始化 StrAssign(s,str); //串赋值 }
/—串连接—/
/*---串连接---*/ void Concat(SString t,SString s1,SString s2) { int lens1= (int)s1[0]; int lens2 = (int)s2[0]; int i = 1,j = 1; while(i<=lens1) { t[i] = s1[i]; i++; } t[0] = lens1; i--; //根据结束条件 i=lens1+1,故t[i]此时没有赋值 if((lens1+lens2)<MAXLEN) { while(j<=lens2) { t[i+j] = s2[j]; j++; } t[0] = lens1+lens2; } else { while(j<MAXLEN-lens1) { t[i+j] = s2[j]; j++; } t[0] = MAXLEN; } t[i+j+1] = '\0'; }
/—求子串—/
/*---求子串---*/ bool SubString(SString sub,SString s,int p,int len) { /*get substring */ int i; if(p<1||p>s[0]||len<0||len>s[0]-p+1) /*子串长度为零/当子串长度大于主串/子串长度小于零/子串长度大于主串截取位置到最后的长度，错误*/ return false; else { for(i=1;i<=len;i++) sub[i]=s[i+p-1]; /*复制字符 */ sub[i]='\0'; sub[0]=len; /*修改表长*/ return true; } }
/—字符串比较—/
/*---字符串比较---*/ int StrCompare(SString s,SString t) { int result = 0;//当比较结构相同时，为零。 /*从s[1] 和 t[1] 开始比较*/ s++; t++; while(*s!='\0' || *t!='\0') { result = *s - *t; if(result!= 0) break;/*如果不相等，得出结果并退出*/ /*相等，下一组比较*/ s++; t++; } return result; }
/—删除子串—/
/*---删除子串---*/ //删除字符串：删除字符串S从pos位置开始的len长度子串 void StrDelete(SString s,int pos,int len) { int s_len = Strlenth(s);//获取字符串的长度 for(int i = pos + len;i<=s_len;i++) { //将字符串中从pos+len位置开始的字符全部前移len个 s[i-len] = s[i]; } s[0] = s_len-len; s[s_len-len+1] = '\0'; }
/—字符串清除—/
/*---字符串清除---*/ void StrClear(SString s) { s[0] = '\0'; }
/—模式匹配（kmp算法）—/
/*---模式匹配（kmp算法）---*/ int StrIndex_kmp(SString s, char *str) { int i = 1; int j = 0; int next[MAXLEN]; int sLen = strlen(s); int pLen = strlen(str); GetNext(str,next); while (i < sLen && j < pLen) { //①如果j = -1，或者当前字符匹配成功（即S[i] == P[j]），都令i++，j++ if (j == -1 || s[i] == str[j]) { i++; j++; } else { //②如果j != -1，且当前字符匹配失败（即S[i] != P[j]），则令 i 不变，j = next[j] //next[j]即为j所对应的next值 j = next[j]; } } if (j == pLen) return i-pLen; else return -1; } /*---获得next数组---*/ void GetNext(char *t,int next[]) { int j=0,k=-1; next[0]=-1; int len = strlen(t); while(j<len) { if(k == -1 || t[j] == t[k]) { j++;k++; if(t[j]==t[k])//当两个字符相同时，就跳过 next[j] = next[k]; else next[j] = k; } else k = next[k]; } }
串的其他存储结构
1.顺序动态存储
typedef struct { char ch[maxsize]; int length; } String, *string;
2.链式存储
trpedef struct chunk{ char ch[maxlen]; struct chunk *next }chunk; typedef struct { chunk *head,*tail; int len; }lstring;
当maxlen= 1时，每个节点存放一个字符，便于进行插入和删除操作，但存储空间利用率太低；当maxlen>1时，每个节点存放多个字符，当最后一个字符未满是，不足处用特定字符（如“#”）补齐。此时提高了存储密度，但插入、删除的处理方法比较复杂，需要考虑节点的分拆和合并。
