Chinaunix首页 | 论坛 | 博客
  • 博客访问: 342152
  • 博文数量: 97
  • 博客积分: 3996
  • 博客等级: 中校
  • 技术积分: 750
  • 用 户 组: 普通用户
  • 注册时间: 2005-05-24 22:27
文章分类

全部博文(97)

文章存档

2012年(1)

2011年(8)

2010年(5)

2008年(2)

2007年(26)

2006年(54)

2005年(1)

我的朋友

分类:

2006-07-07 23:51:20

第四章 串
  串(即字符串)是一种特殊的线性表,它的数据元素仅由一个字符组成,计算机非数值处理的对象经常是字符串数据,如在汇编和高级语言的编译程序中,源程序和目标程序都是字符串数据;在事物处理程序中,顾客的姓名、地址、货物的产地、名称等,一般也是作为字符串处理的。另外串还具有自身的特性,常常把一个串作为一个整体来处理,因此,在这一章我们把串作为独立结构的概念加以研究,介绍串的串的存储结构及基本运算。
4.1 串及其基本运算
4.1.1 串的基本概念
1.串的定义
串是由零个或多个任意字符组成的字符序列。一般记作:
s="s1 s2 … sn""
其中s 是串名;在本书中,用双引号作为串的定界符,引号引起来的字符序列为串值,引号本身不属于串的内容;ai(1<=i<=n)是一个任意字符,它称为串的元素,是构成串的基本单位,i是它在整个串中的序号; n为串的长度,表示串中所包含的字符个数,当n=0时,称为空串,通常记为Ф。
2.几个术语
子串与主串:串中任意连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。
子串的位置:子串的第一个字符在主串中的序号称为子串的位置。
串相等:称两个串是相等的,是指两个串的长度相等且对应字符都相等。
4.1.2 串的基本运算
串的运算有很多,下面介绍部分基本运算:
1.      求串长StrLength(s)
操作条件:串s存在
操作结果:求出串s的长度。
2.      串赋值StrAssign(s1,s2)
操作条件: s1是一个串变量,s2或者是一个串常量,或者是一个串变量(通常s2 是一个串常量时称为串赋值,是一个串变量称为串拷贝)。
操作结果:将s2的串值赋值给s1, s1原来的值被覆盖掉。
3.      连接操作 :StrConcat (s1,s2,s) 或StrConcat (s1,s2)
  操作条件:串s1,s2存在。
  操作结果:两个串的联接就是将一个串的串值紧接着放在另一个串的后面,连接成一   个串。前者是产生新串s,s1和s2不改变; 后者是在s1的后面联接s2的串值,s1改变, s2不改变。
例如: s1="he",s2=" bei",前者操作结果是s="he bei";后者操作结果是s1="he bei"。
4.      求子串SubStr (s,i,len):
操作条件:串s存在,1≤i≤StrLength(s),0≤len≤StrLength(s)-i+1。
操作结果:返回从串s的第i个字符开始的长度为 len 的子串。len=0得到的是空串。
  例如:SubStr("abcdefghi",3,4)= "cdef"
5.      串比较 StrCmp(s1,s2)
操作条件:串s1,s2存在。
操作结果:若s1==s2,操作返回值为0;若s1s2, 返回值>0。
6.      子串定位 StrIndex(s,t):找子串t在主串s中首次出现的位置
操作条件:串s,t存在。
操作结果:若t∈s,则操作返回t在s中首次出现的位置,否则返回值为-1。
如:StrIndex("abcdebda","bc")=2
    StrIndex("abcdebda","ba")=-1
7.      串插入 StrInsert(s,i,t)
操作条件:串s,t存在,1≤i≤StrLength(s)+1。
操作结果:将串t插入到串s 的第i个字符位置上,s的串值发生改变。
8.      串删除 StrDelete(s,i,len)
操作条件:串s存在,1≤i≤StrLength(s),0≤len≤StrLength(s)-i+1。
操作结果:删除串s 中从第i个字符开始的长度为len的子串,s的串值改变。
9.      串替换 StrRep(s,t,r)
操作条件:串s,t,r存在,t不为空。
操作结果:用串r 替换串s中出现的所有与串t相等的不重叠的子串,s的串值改变。
以上是串的几个基本操作。其中前5个操作是最为基本的,它们不能用其他的操作来合成,因此通常将这5个基本操作称为最小操作集。
4.2 串的定长顺序存储及基本运算
因为串是数据元素类型为字符型的线性表,所以线性表的存储方式仍适用于串,也因为字符的特殊性和字符串经常作为一个整体来处理的特点,串在存储时还有一些与一般线性表不同之处。
4.2.1 串的定长顺序存储
类似于顺序表,用一组地址连续的存储单元存储串值中的字符序列,所谓定长是指按预定义的大小,为每一个串变量分配一个固定长度的存储区,如:
#define MAXSIZE 256
char s[MAXSIZE];
则串的最大长度不能超过256。
如何标识实际长度?

1. 类似顺序表,用一个指针来指向最后一个字符,这样表示的串描述如下:
typedef struct
{ char data[MAXSIZE];
int   curlen;
} SeqString;
定义一个串变量:SeqString s;
这种存储方式可以直接得到串的长度:s.curlen+1。如图4.1所示。
0      1      2      3      4      5      6      7      8      9      10      ...                  MAXSIZE-1
a      b      c      d      e      f      g      h      i      j      k                   …      



图4.1 串的顺序存储方式1

2. 在串尾存储一个不会在串中出现的特殊字符作为串的终结符,以此表示串的结尾。比如C语言中处理定长串的方法就是这样的,它是用’\0’来表示串的结束。这种存储方法不能直接得到串的长度,是用判断当前字符是否是’\0’来确定串是否结束,从而求得串的长度。

char s[MAXSIZE];
0      1      2      3      4      5      6      7      8      9      10      ...                  MAXSIZE-1
a      b      c      d      e      f      g      h      i      j      k      \0             …      

图4.2 串的顺序存储方式2

3. 设定长串存储空间:char s[MAXSIZE+1]; 用s[0]存放串的实际长度,串值存放在s[1]~s[MAXSIZE],字符的序号和存储位置一致,应用更为方便。

4.2.2 定长顺序串的基本运算
本小节主要讨论定长串联接、求子串、串比较算法,顺序串的插入和删除等运算基本与顺序表相同,在此不在赘述。串定位在下一小节讨论,设串结束用'\0'来标识。
1.串联接:把两个串s1和s2首尾连接成一个新串s ,即:s<=s1+s2。
int StrConcat1(s1,s2,s)
char s1[],s2[],s[];
{ int i=0 , j, len1, len2;
len1= StrLength(s1); len2= StrLength(s2)
if (len1+ len2>MAXSIZE-1) return 0 ; /* s长度不够*/
j=0;
while(s1[j]!=’\0’) { s
=s1[j];i++; j++; }
j=0;
while(s2[j]!=’\0’) { s
=s2[j];i++; j++; }
s
=’\0’;   return 1;
}
算法 4.1
2.求子串
int StrSub (char *t, char *s, int i, int len)
/* 用t返回串s中第个i字符开始的长度为len 的子串1≤i≤串长*/
{ int slen;
slen=StrLength(s);
if ( i<1 || i>slen || len<0 || len>slen-i+1)
{ printf("参数不对"); return 0; }
for (j=0; jt[j]=s[i+j-1];
t[j]=’\0’;
return 1;
}
算法 4.2
3.      串比较
int StrComp(char *s1, char *s2)
{ int i=0;
while (s1
==s2 && s1!=’\0’) i++;
return (s1
-s2);
}
算法 4.3
4.2.3 模式匹配
串的模式匹配即子串定位是一种重要的串运算。设s和t是给定的两个串,在主串s中找到等于子串t的过程称为模式匹配,如果在s中找到等于t的子串,则称匹配成功,函数返回t在s中的首次出现的存储位置(或序号),否则匹配失败,返回-1。t也称为模式。为了运算方便,设字符串的长度存放在0号单元,串值从1号单元存放,这样字符序号与存储位置一致。
1.简单的模式匹配算法
算法思想如下:首先将s1与t1进行比较,若不同,就将s2与t1进行比较,...,直到s的某一个字符si和t1相同,再将它们之后的字符进行比较,若也相同,则如此继续往下比较,当s的某一个字符si与t的字符tj不同时,则s返回到本趟开始字符的下一个字符,即si-j+2,t返回到t1,继续开始下一趟的比较,重复上述过程。若t中的字符全部比完,则说明本趟匹配成功,本趟的起始位置是i-j+1或i-t[0],否则,匹配失败。
设主串s="ababcabcacbab",模式t="abcac",匹配过程如图4.3所示。
























依据这个思想,算法描述如下:
int StrIndex_BF (char *s,char *t)
  /*从串s的第一个字符开始找首次与串t相等的子串*/
{ int 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 –1;
}
算法 4.4

该算法简称为BF算法。下面分析它的时间复杂度,设串s长度为n,串t长度为m。
匹配成功的情况下,考虑两种极端情况:
在最好情况下,每趟不成功的匹配都发生在第一对字符比较时:
例如:s="aaaaaaaaaabc"
t="bc"
设匹配成功发生在si处,则字符比较次数在前面i-1趟匹配中共比较了i-1次,第i趟成功的匹配共比较了m次,所以总共比较了i-1+m次,所有匹配成功的可能共有n-m+1种,设从si开始与t串匹配成功的概率为pi,在等概率情况下pi=1/(n-m+1),因此最好情况下平均比较的次数是:
   

 

即最好情况下的时间复杂度是O(n+m)。
在最坏情况下,每趟不成功的匹配都发生在t的最后一个字符:
例如:s="aaaaaaaaaaab"
t="aaab"
设匹配成功发生在si处,则在前面i-1趟匹配中共比较了(i-1)*m次,第i趟成功的匹配共比较了m次,所以总共比较了i*m次,因此最坏好情况下平均比较的次数是:





即最坏情况下的时间复杂度是O(n*m)。
上述算法中匹配是从s串的第一个字符开始的,有时算法要求从指定位置开始,这时算法的参数表中要加一个位置参数pos:StrIndex(shar *s,int pos,char *t),比较的初始位置定位在pos处。算法4.4是pos=1的情况。

*2.改进后的模式匹配算法
  BF算法简单但效率较低,一种对BF算法做了很大改进的模式匹配算法是克努特(Knuth),莫里斯(Morris)和普拉特(Pratt)同时设计的,简称KMP算法。
(1)      KMP算法的思想
分析算法4.4的执行过程, 造成BF算法速度慢的原因是回溯,即在某趟的匹配过程失败后,对于s串要回到本趟开始字符的下一个字符,t串要回到第一个字符。而这些回溯并不是必要的。如图4.3所示的匹配过程,在第三趟匹配过程中,s3 ~ s6和t1~ t4是匹配成功的,s7≠t5匹配失败,因此有了第四趟,其实这一趟是不必要的:由图可看出,因为在第三趟中有s4=t2,而t 1≠t2,肯定有t1≠s4 。同理第五趟也是没有必要的,所以从第三趟之后可以直接到第六趟,进一步分析第六趟中的第一对字符s 6和t1的比较也是多余的,因为第三趟中已经比过了s6和t4,并且s6=t4,而t 1=t4,必有s 6=t1,因此第六趟的比较可以从第二对字符s7和t2开始进行,这就是说,第三趟匹配失败后,指针i不动,而是将模式串t向右“滑动”,用t2 “对准” s 7继续进行,依此类推。这样的处理方法指针i 是无回溯的。
综上所述,希望某趟在si和tj匹配失败后,指针i不回溯,模式t向右“滑动”至某个位置上,使得tk 对准 s i 继续向右进行。显然,现在问题的关键是串t“滑动”到哪个位置上?不妨设位置为k,即si和tj匹配失败后,指针i不动,模式t向右“滑动”,使tk和si对准继续向右进行比较,要满足这一假设,就要有如下关系成立:
    "t1 t2 … tk-1 " ="si-k+1 si-k+2 … si-1 "     (4.1)
(4.1)式左边是tk前面的k-1个字符,右边是si 前面的k-1个字符。
而本趟匹配失败是在si和tj之处,已经得到的部分匹配结果是:
    "t1 t2 … tj-1 " ="si-j+1 si-j+2 …  si-1 "     (4.2)
因为k    "tj-k+1 tj-k+2 … tj-1 " ="si-k+1 si-k+2 …  si-1 "   (4.3)
(4.3)式左边是 tj前面的k-1个字符,右边是si 前面的k-1个字符,
通过(4.1)和(4.3)得到关系:
"t1 t2 … tk-1 " ="tj-k+1 tj-k+2 … tj-1 "       (4.4)
结论:某趟在si和tj匹配失败后,如果模式串中有满足关系(4)的子串存在,即:模式中的前k-1个字符与模式中tj字符前面的k-1个字符相等时,模式t就可以向右“滑动”至使tk和si对准,继续向右进行比较即可。
(2)next函数
模式中的每一个tj都对应一个k值,由(4.4)式可知,这个k值仅依赖与模式t本身字符序列的构成,而与主串s无关。我们用next[j]表示tj对应的k值,根据以上分析,next函数有如下性质:
① next[j]是一个整数,且0≤next[j]② 为了使t的右移不丢失任何匹配成功的可能,当存在多个满足(4.4)式的k 值时,应取最大的,这样向右“滑动”的距离最短,“滑动”的字符为j-next[j]个。
③ 如果在tj前不存在满足(4.4)式的子串,此时若t1≠tj,则k=1; 若t1=tj,则k=0; 这时“滑动”的最远,为j-1个字符即用t1 和sj+1继续比较。
因此,next函数定义如下 :






设有模式串:t="abcaababc",则它的next函数值为:
     
  j      1      2      3      4      5      6      7      8      9
模式串      a      b      c      a      a      b      a      b      c
next[j]      0      1      1      0      2      1      3      1      1

(3) KMP算法
在求得模式的next函数之后,匹配可如下进行:假设以指针i和j分别指示主串和模式中的比较字符,令i的初值为pos,j的初值为1。若在匹配过程中si≠tj,则i和j分别增1,若si≠tj 匹配失败后,则i不变,j退到next[j]位置再比较,若相等,则指针各自增1,否则j再退到下一个next值的位置,依此类推。直至下列两种情况:一种是j退到某个next值时字符比较相等,则i和j分别增1继续进行匹配; 另一种是j退到值为零(即模式的第一个字符失配),则此时i和j也要分别增1,表明从主串的下一个字符起和模式重新开始匹配。
设主串s="acabaabaabcacaabc",子串t="abaabcac",图4.4是一个利用next函数进行匹配的过程示意图。

在假设已有next函数情况下,KMP算法如下:
int StrIndex_KMP(char *s,char *t,int pos)
  /*从串s的第pos个字符开始找首次与串t相等的子串*/
{ int i=pos,j=1,slen,tlen;
  while (i<=s[0] && j<=t[0] ) /*都没遇到结束符*/
if (j==0||s
==t[j]) { i++; j++; }
    else j=next[j];   /*回溯*/
  if (j>t[0]) return i-t[0]; /*匹配成功,返回存储位置*/
  else return –1;
}
      算法4.5

   



(4)如何求next函数
由以上讨论知,next函数值仅取决于模式本身而和主串无关。我们可以从分析next函数的定义出发用递推的方法求得next函数值。
由定义知:
next[1]=0                             (4.5)
设next[j]=k,即有:
"t1 t2 … tk-1 " ="tj-k+1 tj-k+2 … tj-1 "         (4.6)
next[j+1]=? 可能有两种情况:
第一种情况:若tk =tj 则表明在模式串中
"t1 t2 … tk " ="tj-k+1 tj-k+2 … tj "             (4.7)
这就是说next[j+1]=k+1,即
next[j+1]=next[j]+1                       (4.8)
第二种情况:若tk ≠tj 则表明在模式串中
"t1 t2 … tk "≠"tj-k+1 tj-k+2 … tj "             (4.9)
此时可把求next函数值的问题看成是一个模式匹配问题,整个模式串既是主串又是模式,而当前在匹配的过程中,已有(4.6)式成立,则当tk ≠tj 时应将模式向右滑动,使得第next[k]个字符和“主串”中的第j个字符相比较。若next[k]=k′,且t k′=tj,则说明在主串中第j+1个字符之前存在一个最大长度为k′的子串,使得
"t1 t2 … t k′ "="tj-k′+1 tj- k′+2 … tj "             (4.10)
因此:   next[j+1]=next[k]+1                       (4.11)
  同理若t k′ ≠tj,则将模式继续向右滑动至使第next[k′]个字符和tj 对齐,依此类推,直至tj 和模式中的某个字符匹配成功或者不存在任何 k′(1< k′否则若t1=tj+1 ,则有:next[j+1]=0                           (4.13)
综上所述,求next函数值过程的算法如下:
void GetNext(char *t,int next[ ])
    /*求模式t的next值并寸入next数组中*/
 { int i=1,j=0;
    next[1]=0;
    while (i    { while (j>0&&t
!=t[j]) j=next[j];
      i++; j++;
if (t
==t[j]) next=next[j];
      else next
=j;
    }
}
算法4.6

算法4.6的时间复杂度是O(m);所以算法4.5的时间复杂度是O(n*m),但在一般情况下,实际的执行时间是O(n+m)。当然KMP算法和简单的模式匹配算法相比,增加了很大难度,我们主要学习该算法的设计技巧。
4.3 串的堆存储结构
4.3.1 串名的存储映象
串名的存储映象是串名-串值内存分配对照表,也称为索引表。表的形式有多种表示,如设s1="abcdef",s2="hij",常见的串名-串值存储映象索引表有如下几种:

1. 带串长度的索引表 
如图4.4所示,索引项的结点类型为:
typedef struct
{ char name[MAXNAME]; /*串名*/
int length; /*串长*/
char *stradr; /*起始地址*/
} LNode;


2. 末尾指针的索引表
如图4.5所示,索引项的结点类型为:
typedef struct
{ char name[MAXNAME]; /*串名*/
char *stradr,*enadr;  /*起始地址,末尾地址*/

} ENode;


  3. 带特征位的索引表
当一个串的存储空间不超过一个指针的存储空间时,可以直接将该串存在索引项的指针域,这样即节约了存储空间,又提高查找速度,但这时要加一个特征位tag以指出指针域存放的是指针还是串。
如图4.6所示,索引项的结点类型为:
typedef struct
{ char name[MAXNAME];
int tag; /*特征位*/
union  /*起始地址或串值*/
{char *stradr;
char value[4];
}uval;
} TNode;
 

4.3.2 堆存储结构
  在应用程序中,参与运算的串变量之间的长度相差较大,并且操作中串值的长度变化也较大,因此为串变量预分配固定大小的空间不尽合理。堆存储结构的基本思想是:在内存中开辟能存储足够多的串、地址连续的存储空间作为应用程序中所有串的可利用存储空间,称为堆空间,如设store[SMAX+1]; 根据每个串的长度,动态的为每个串在堆空间里申请相应大小的存储区域,这个串顺序存储在所申请的存储区域中,当操作过程中若原空间不够了,可以根据串的实际长度重新申请,拷贝原串值后再释放原空间。
如图4.8所示,是一个堆结构示意图。阴影部分是已经为存在的串分配过的,free为未分配部分的起始地址,每当向store中存放一个串时,要填上该串的索引项。

4.3.3 基于堆结构的基本运算
堆结构上的串运算仍然基于字符序列的复制进行,基本思想是:当需要产生一个新串时,要判断堆空间中是否还有存储空间,若有,则从free指针开始划出相应大小的区域为该串的存储区,然后根据运算求出串值,最后建立该串存储映象索引信息,并修改free指针。
设堆空间为: char store[SMAX+1];
自由区指针:int free;
串的存储映象类型如下:
typedef struct
{ int length; /*串长*/
int stradr; /*起始地址*/
} HString;

 1. 串常量赋值
void StrAssign(HString *s1,char *s2)
/*将一个字符型数组s2中的字符串送入堆store中,free是自由区的指针*/
{ int i=0,len;
  len=StrLength(s2);
if (len<0||free+len-1>SMAX)
  return 0;
else {for (i=0;istore[frre+i] =s2
;
  s1.stradr=free;
s1.len.=len;
free=free+len;
}
}
算法 4.7

  2. 赋值一个串
void StrCopy(Hstring *s1,Hstring s2)
/*该运算将堆store中的一个串s2复制到一个新串s1中*/
{ int i;
  if (free+s2.lengt-1>SMAX) return error ;
  else { for(i=0; i        store[free+i]=store[s2.atradr+i];
s1->length=s2.length;
    s1->stradr=free;
    free=free+s2.length;
    }
}
算法 4.8
3. 求子串
void StrSub(Hstring *t, Hstring s,int i,int len)
/*该运算将串s中第i个字符开始的长度为len 的子串送到一个新串t中*/
{ int i;
  if (i<0 || len<0 || len>s.len-i+1) return error ;
  else { t->length=len;
    t->stradr=s.stradr+i-1;
    }
}
算法 4.9

3.      串联接
void Concat(s1,s2,s)
HString s1,s2;
HString *s;
{ HString t;
StrCopy (s,s1);
StrCopy (&t,s2);
s->length=s1.length+s2.length;
}
算法 4.10

  以上堆空间和算法是由算法编写者自己设计和编写来实现的,在这里,重点介这种存储的处理思想,很多问题及细节尚未涉及,比如,废弃串的回归、自由区的管理问题等等。在常用的高级语言及开发环境中,大多系统本身都提供了串的类型及大量的库函数,用户可直接使用,这样会使算法的设计和调试更方便容易,可靠性更高
阅读(2503) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~