目录
一、串的顺序存储
1、静态数组实现（定长顺序存储）
#define MAXLEN 255 //预定义最大长串为255 typedef struct{ char ch[MAXLEN]; //每个分量存储一个字符 int length; //串的实际长度 }SString;
2、动态数组实现（堆分配存储）
typedef struct{ char *ch; //按串长分配存储区，ch指向串的基地址 int length; //串的长度 }HString; //用完需要手动free HString S; S.ch = (char *) malloc(MAXLEN * sizeof(char)); S.length = 0;
3、存储方案
4、串的链式存储
（一）
typedef struct StringNode{ char ch; struct StringLNode *next; }StringNode,*String;
缺点：存储密度低，每个字符1B，每个指针4B
（二）
typedef struct StringNode{ char ch[4]; //每个结点存多个字符 struct StringNode * next; }StringNode, *String;
存储密度提高
5、基本操作的实现
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联接而成的新串———可能会导致存储空间的扩展；
6、求子串的实现方式
//求子串 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+1] = S.ch[i]; Sub.length = len; return false; }
7、比较俩个串的大小
StrCompare（S,T）：比较操作。若S>T，则返回值>0;若S=T，则返回值 = 0；若S< T则返回值<0.
int StrCompare(SString S,SString T) { for(int i = 0;i <= S.length && i <= T.length;i ++){ if(S.ch[i] != T.ch[i]) return S.ch[i] - T.ch[i]; } //扫描过的所有字符都相同，则长度长的串更大 return S.length - T.length; }
8、定位操作
Index(S,T) ：定位操作。若主串S中存在与串T值相同的子串，则返回它与主串S中第一次出现的位置；否则函数值为0
// 3. 定位操作 int Index(SString S, SString T){ int i=1; n = StrLength(S); m = StrLength(T); SString sub; //用于暂存子串 while(i<=n-m+1){ SubString(Sub,S,i,m); if(StrCompare(Sub,T)!=0) ++i; else return i; // 返回子串在主串中的位置 } return 0; //S中不存在与T相等的子串 }
