空串：长度为0的串
空格串：由一个或多个空格组成的串
串常用的3种机内表示方法：
定长顺序存储表示：
用一组地址连续的存储单元存储串的字符序列，每一个串变量都有一个固定长度的存储区,可用定长数组来描述。
#define MAXLEN 255 typedef unsigned char Sstring[MAXLEN+];/*0号单元存放串的长度*/
1.串连接
当串s1,s2连接后的结果串t超过了定长MAXLEN时，即s1[0]+s2[0]>MAXLEN，输出相应的信息
void Concat(Sstring t,Sstring s1,Sstring s2)
{/*将s1串和s2串连接后存入t串中*/
int i,j;
int m,n;
m = s1[],n = s2[];
if(m + n > MANXLEN)
printf("两串连接后超过串的定长!\n");
else{
for(i = ;i <= m;i++) t[i] = s1[i];
for(j = ;j <= n;j++) t[i+j] = s2[j];
t[] = m + n; /*将两串连接后的长度存至t[0]中*/
}
}
2.求子串
设子串的起始位置为pos,子串的长度为len
当pos<1或pos>s[0]时，子串位置非法;
当len<0或len>s[0]-pos+1时，子串长度非法。
void SubString(Sstring sub,Sstring s,int pos,int len)
{/*将s中序号pos起len个字符复制到sub中*/
int i;
if(pos<||pos>s[]||len<||len>s[]-pos+)
printf("子串的开始位置或长度错误！\n");
else{
for(i = ;i <= len; i++)
sub[i] = s[i+pos-];
sub[] = len;
}
}
堆分配存储表示：
仍用一组地址连续的存储单元存放串的字符序列，但每个串的存储空间是在程序执行过程中动态分配而得。
堆空间：存放所有串可利用的空间
heap[MAXSIZE]表示堆空间，free指向heap中未分配区域的开始地址，初始化为0
/*====堆分配存储====*/
typedef struct{
char *ch; //串的起始地址
int len; //串的长度
} HSt
1.串连接
void Concat(HString * t,HString * s1,HString * s2)
{/*将s1,s2连接后，存入t串，返回t串*/
int i;
if(t->ch) free(t->ch);//如果串t已存在，先释放掉旧空间
if(!(t->ch=(char *)malloc((s1->len+s2->len)*sizeof(char))))
printf("溢出错误\n");//分配空间失败
else{
for(i=;i<s1->len;i++)
t->ch[i]=s1->ch[i];
for(i=;i<s2->len;i++)
t->ch[i+s1->len]=s2->ch[i];
t->len=s1->len+s2->len;
}
}
2.求子串
void SubString(HString * sub,HString * s,int pos,int len)
{//将s中从pos个位置起的len个字符复制到sub中
int i;
if(pos<||pos>=s->len||len<||len>s->len-pos+)
printf("子串的开始位置或长度错误！\n");
if(sub->ch) free(t->ch);//如果串t已存在，释放旧空间
if(!len) {sub->ch=NULL;sub->len=;}//如果子串为空串
else{
for(i = ;i <len;i++)
sub->ch[i]=s->ch[i+pos];
sub->len=len;
}
}
串的块链存储表示：
可采用链表方式存储串值
#define CHUNKSIZE 80
typedef struct Chunk{
char ch[CHUNKSIZE];
struct Chunk * next;
}Chunk;
typedef struct {
Chunk * head, * tail;
int len;
}LString;
模式匹配：
简单的模式匹配：时间复杂度O(n×m) 效率低，时间主要浪费在指针的回溯上
着重来讲一下
KMP：主要消除了主串指示器变量i的回溯，时间复杂度为O(m+n)