1.串的定义
串（string）（或字符串）是由零个或多个字符组成的有限序列，一般记为：
其中，s是串的名，用单括号括起来的字符序列是串的值; $a_i(1\leq i\leq n)$可以是字母、数字或其他字符；串中字符的数目n称为串的长度。零个字符的串称为空串，它的长度为0。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。通常称字符在序列中的序号为该字符在串中的位置子串在主串中的位置则以子串的第一个字符在主串的位置来表示。
称两个串是相等的，当且仅当这两个串的值相等。也就是说，只有当两个串的长度相等，并且各个对应位置的字符都相等时才相等。
由一个或多个空格组成的串‘ ’叫做空格串，它的长度为串中空格字符的个数。为了清楚起见，以后我们用符号“$\varnothing$”来表示空串。
串的抽象数据类型：
ADT 串 (String)
Data
串中的元素仅由一个字符组成，相邻元素具有前驱和后继关系.
Operation
StrAssign (&T, chars)
初始条件：chars是字符串常量。
操作结果：生成一个其值等于chars的串T。
StrCopy (&T, S)
初始条件：串S存在。
操作结果：由串S复制得串T。
StrEmpty(S)
初始条件：串S存在。
操作结果：若S为空串，则返回TRUE，否则返回FALSE。
StrCompare(S, T)
初始条件：串S和T存在。
操作结果：若S>T，则返回值>0；若S=T，则返回值＝0；若S < T，则返回值 < 0。
StrLength(S)
初始条件：串S存在。
操作结果：返回S的元素个数，称为串的长度。
ClearString (&S)
初始条件：串S存在。
操作结果：将S清为空串。
Concat (&T, S1, S2)
初始条件：串S1和S2存在。
操作结果：用T返回由S1和S2联接而成的新串。
SubString(&Sub, S, pos, len)
初始条件：串S存在,1≤pos≤StrLength(S)且0≤len≤StrLength(S)-pos+1
操作结果：用Sub返回串S的第pos个字符长度为len的子串。
Index(S, T, pos)
初始条件：串S和T存在,T是非空串，1≤pos≤StrLength(S)。
操作结果：若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置;否则函数值为0。
Replace (&S, T, V)
初始条件：串S, T和V存在，T是非空串。
操作结果：用V替换主串S中出现的所有与T相等的不重叠的子串。
StrInsert (&S, pos, T)
初始条件：串S和T存在, 1≤pos≤StrLength(S)+1。
操作结果：在串S的第pos个字符之前插入串T。
StrDelete (&S, pos, len)
初始条件：串S存在, 1≤pos≤StrLength(S)－len+1。
操作结果：从串S中删除第pos个字符起长度为len的子串。
DestroyString (&S)
初始条件：串S存在。
操作结果：串S被销毁。
endADT
2.串的表示和实现
串有3种机内表示方法，分别介绍如下。
1.定长顺序存储表示
类似于线性表的顺序存储结构，用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中，按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述之。
#define MAXSTRING 255
typedef unsigned char SString[MAXSTRING+1];
串的实际长度可以在预定义的长度范围内自定义，超过预定义长度的串值将被舍去，称之为“截断”。对串长有两种表示方法，一种是用下标为0的数组分量来存放串的实际长度，另一种是在串值后加一不计入串长的结束标记字符，如\0。
1.串联接
将S1和S2联接并存给T
算法实现：
Status Concat(SString &T,SString S1,SString S2)
{
//用T返回由S1和S2连接成的新串。若未截断，返回TRUE，否则FALSE
int i,j,uncut;
if(S1[0] + S2[0] <= MAXSTRLEN)
{ //未截断
for(i = 1;S1[i] != '\0'; i++)
T[i] = S1[i];
for(j = 1;S2[j] != '\0'; j++)
T[S1[0]+j] = S2[j];
T[S1[0]+j+1] = '\0';
T[0] = S1[0] + S2[0];
uncut = TRUE;
}
else if(S1[0] < MAXSTRLEN)
{ //截断
for(i = 1;S1[i] != '\0'; i++)
T[i] = S1[i];
for(i =1;i <= MAXSTRLEN-S1[0];i++)
T[S1[0]+i] = S2[i];
T[S1[0]+i+1] = '\0';
T[0] = MAXSTRLEN;
uncut = FALSE;
}
else{ //截断（仅S1）
for(i =1;S1[i] != '\0'; i++)
T[i] = S1[i];
T[i+1] = '\0';
T[0] = S1[0];
uncut = FALSE;
}
return uncut;
}
2.求子串
算法实现：
Status SubString(SString &Sub, SString S, int pos, int len)
{
//用Sub返回串S的第pos个字符起长度为len的子串
//其中，1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
int i,j;
if(pos < 1 || pos >S[0] || len < 0 || len > S[0]-pos+1)
return ERROR;
for(i = 1 ,j = pos; i <=len && j <= pos+len-1; i++,j++)
Sub[i] = S[j];
Sub[i+1] = '\0';
Sub[0] = len;
return OK;
}
2.堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但它们的存储空间是在程序执行过程中动态分配而得。在C语言中，存在一个称之为“堆”的自由存储区，并由C语言的动态分配函数malloc（）和free（）来管理。
typedef struct{
char *ch;//若是非空串，则按串长分配存储区，否则ch为NULL
int length;//串长度
}HString;
/*赋值*/
bool StrAssign(HString &T,char *chars)
{
//求chars长度
int charsLen;
char *c;
for (charsLen=0,c=chars;*c;charsLen++,c++);
if (!charsLen)
{
T.ch=NULL;
T.length=0;
}
else
{
//分配所需空间
T.ch=(char*)malloc(sizeof(char)*charsLen);
if (!T.ch)
{
return false;
}
int tempi=0;
char *head=T.ch;
do
{
tempi++;
*T.ch=*chars;
T.ch++;
chars++;
} while(tempi!=charsLen);
T.ch=head;
T.length=charsLen;
return true;
}
}
/*求串长*/
int StrLength(HString S)
{
return S.length;
}
/*串比较 S>T返回>0 S=T返回=0 SS.length||len<0||len>S.length-pos+1)
{
return false;
}
if (Sub.ch)
{
free(Sub.ch);
}
if (!len)
{
Sub.ch=NULL;
Sub.length=0;
return true;
}
else
{
Sub.ch=(char*)malloc(sizeof(char)*len);
Sub.length=len;
char *head=Sub.ch;
S.ch+=pos-1;
for (int i=0;i 3.块链存储表示
和线性表的链式存储结构相类似，也可以采用链表方式存储串值。（注意：结点大小等即可）
#define CHUNKSIZE 80
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk *next;
}Chunk;
typedef struct{
Chunk *head,*tail;
int curlen;
}LString;
$存储密度=\frac{串值所占的存储位}{实际分配的存储位}$
3.串的模式匹配算法
1.求子串位置的定位函数Index(S,T,pos)
子串的定位操作通常称作串的模式匹配（其中T称为模式串），是各种串处理系统中最重要的操作之一。
int Index(SString S,SString T,int pos){
i=pos;j=1;
while(i<=S[0]&&j<=T[0])
{
if(S[i]==T[j]){++i;++j}
else{i=i-j+2;j=1;}
}
if(j>T[0]) return i-T[0];
else return 0;
}
2.模式匹配的一种改进算法（KMP算法）
int Index_KMP(SString S,SString T,int pos)
{
i=pos;j=1;
while(i<=S[0]&&j<=T[0])
{
if(j==0||s[i]==T[j]){++i;++j;}
else j=next[j];
}
if(j>T[0]) return i-T[0];
else return 0;
}
void get_next(SString T,int next[]){//求next
i=1;next[1]=0;j=0;
while(i关于KMP算法
