数据结构考研资料（串）
来源：凯程　 日期：2008年08月22日　 阅读次数：242
一.串的定义 由n(n>=0)个字符组成的有限序列.
二.串的存储结构

  1.行结构 struct string {   或char a[max];
     char ch[maxsize] ;
     int strlen;
    };
  2.堆结构 struct string {//串值的存储
     char ch[maxsize] ;
     int free;
    };
     int strname[maxn];//串名
三.模式匹配(index)
index(char s[],char t[],int &i){/求模式串t在主串s中位置的定位
   i=1; j=1;// 指针初始化
   while (i<=s[0] && j<=t[0])
   if ( s==t[j]) {i++; j++;} //继续比较后继字符
   else {i＝i-j+2; j=1};//指针后退重新开始匹配
   if (j>t[0]) return(i-t[0]) else return(0);
}
例1 s=’”bcabcabbcabcabcabcab’  t=’bcabcabc’
  bcabcabcabc {i=8,j=8} 下一个j=?  j=5
  j        1        2        3        4        5        6        7        8
  t        b        c        a        b        c        a        b        c
next[j]        0        1        1        1        2        3        4        5
   i=1; j=1;// 指针初始化
   while (i<=s.srtlen && j<=t.strlen)
   if ( s.ch==t.ch[j]) {i++; j++;} //继续比较后继字符
   else j:=next[j];//模式串向右滑动
   if (j>t.curlen) return(i-t.strlen) else return(0);
求next[j]:
j=1;  k=1; next[1]=0;
while (j<t[0])
if (k==0)||t[j]==t[k]) {j++;k++;net[j]=k;}
else k=next[k];