一、 串类型的定义

  串的定义

串（string）（或字符串）是由零个或多个字符组成的有序序列，一般记为

              S=”a1a2…an”   (n>=0)

其中，s是串的名，用双引号括起来的字符序列是串的值；ai (1≤i≤n)可以是字母、数字或其他字符；串中字符的数目n成为串的长度。零个字符的串称为空串(null string),它的长度为0。

串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应的称为主串。通常称字符在序列中的序号为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。

例如，假设有a、b、c、d四个字符串：

           a=”BEI”        b=”JING”

           c=”BEIJING”    d=”BEI JING”

则它们的长度分别为3、4、7、8；并且a、b都是c、d的子串，a在c和d中的位置都是0，而b在c中的位置是3，在d中的位置是4；可见字符串的索引是从0开始的。

称两个串相等的，当且仅当这两个串的值相等。也就是说，只有当两个字符串的长度相等，并且各个对应位置的字符都相等才相等。例如上例子中a、b、c、d都互不相等。

值得一提的是，串值必须用一对双引号括起来，但双引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆而已。另在高级语言中，如C语言中字符串中隐藏一个特殊的字符即’\0’,它的作用是标识字符串结束，因此称’\0’为字符串结束符。

 串的操作

字符串可以有丰富的操作，在日常非数值运算大量的都是字符串的操作。归纳总结可以大致分为以下操作：

赋值           strcpy(数组名、字符串)；

判空           strlen()    strcmp()   

字符串比较     strcmp

求字符串长度   strlen

字符串拷贝     strcpy

字符串连接     strcat

求字符串子串（截取字符串） 

二、 串类型的表示和实现

串的表示

（1）定长顺序存储表示：类似线性表的顺序存储结构，用一组地址连续的存储单元存储字符串的字符序列。

（2）堆分配存储表示：这种存储方式特点是：仍一一组连续的存储单元存放字符串序列，但它们的存储空间是在程序执行过程中动态分配而得的。

（3）块链存储表示：和线性表的链式存储类似，也是用链表来保存字符串的值。根据串的特殊，若每个字符占一个结点太小，则采取每个结点可以存放一个也可以存放多个字符。如图所示：图a就是块链存储方式，而图b则过于浪费空间。

串的实现

首先串的存储方式不同其实现方式就是不一样的，这里我们采用第一种存储方式即定长顺序存储表示。

     #define MAX 255       //用户可在255以内定义最大串长

typedef unsigned char SString[MAX+1];     //最后以’\0’结束标识字符串结束

当如此顶以后串的各种操作就可以实现了，有一些C语言中自带的系统可完成一部分，如字符串拷贝strcpy，字符串连接strcat，字符串比较strcmp，求字符串长度strlen。也有另外一部分需要自己实现，比如截取字符串substring：

int get_next(char t[],int next[])  //计算next[j]的函数{int i=0,j=0;next[0]=0;while(i<strlen(t)){if(j==0||t[i]==t[j]){i++;j++;next[i]=j;}else{j=next[j];}}
}int index(char s[],char t[],int pos)  //子串定位函数{int i,j;int next[256];get_next(t,next); for(j=0;j<strlen(t);j++){printf("%d\t",next[j]);}i=pos;j=0;while(i<strlen(s)&&j<strlen(t)){if(j==-1||s[i]==t[j]){i++;j++;}else{j=next[j]-1;    //失配时只滑动模式串到next[j]-1的位置继续比较即可}}if(j>=strlen(t)){return i-strlen(t);}else{return -1;  //没有匹配到}
}
void main()
{char s[100]="ababcabcacbaab";char t[100]="abcac";int pos=0;printf("%d",index(s,t,pos));  //打印子串在主串的位置
}