首页 > 代码库 > 数据结构与算法系列研究三——字符串

数据结构与算法系列研究三——字符串

字符串的研究和KMP算法分析和实现

一、串的定义

  串是计算机非数值处理的基本对象。串是一种特殊的线性表,它的每个结点仅由一个字符组成,并且单个元素是无意义的。
   1、串(string):是由0个或多个字符组成的有限序列,记作:
          S=“a1a2...an”  (n>=0)
          其中:S是串名,两个双引号括起来的字符序列为串的值。双引号不属于串。
                   ai(1<=i<=n)为字母、数字或其它符号。
                  空格符是一个有效字符。
   2、串中所有字符的个数n为串的长度。长度为0的串称为空串。
   3、空格串:全部由空格符组成的字符序列。
   4、子串:串中任意连续个字符的序列称为该串的子串。
   5、主串:包含该子串的串称为主串。
   6、字符在串中的序号称为该字符在串中的位置
   7、子串在串中的位置:用子串第一个字符在主串中的位置来表示。空串是任意串的子串。任意串是自身的子串。
   8、串常量:不能改变其值的量为常量,串常量一般用直接量表示。
       串变量:用于存放字符串值,并且其值可以改变的量。

   相关运算:(黄色为基本子集,有这几种操作可以产生其他复杂操作)
     Strassign (&S,chars):将常数串赋值给S,对应于strcopy。
     Strlength(S):求串S的长度,对应于strlen(s)。
     Strcompare(S1,S2):比较串S1和S2,对应于strcmp(s1,s2)。
     Concat(&S,S1,S2):将串S1和S2联接成一个串,并赋给S。
     Substring(&Sub,S,pos,len):在S串中求pos开始的长度为len的子串。
     Clearstring(&S):将串S置成空串。
     Strcopy (&S,S1):将串S1复制到变量S
     Strempty(&S):判断串S是否为空串。
     Index(S,Sub,pos):求子串sub在串S的pos开始后出现的位置。
     Replace(&S,Sub,T);用Sub替换S中所有与T相等的不重叠的子串。
     Strinsert(&S,pos,Sub):在串S的pos位置前插入子串Sub。
     Strdelete(&S,pos,len):在串S中删除pos位置开始长度为len的子串。
     Destroystring(&S):撤消串S。
  串的表示与实现—堆分配存储:

  分配一组地址连续的与串长一致的存储单元存放串值字符序列。与定长顺序表示的区别:采用动态分配;串空间与串长一致,串长变化将引起串空间的重新分配。
  堆存储表示:

技术分享
       typedef struct{
         char *ch;
         int length;
       }HString

串的表示与实现—块链表示
  块:一组连续的字符。
  块链存储表示:把串分成指定等长的块,每一块用一个结点表示,把各块链成一个链表。
                     当一个结点不满时,用特殊字符(如‘#’)填充。
                     若块的长度为1,就是以单字符为结点的链表结构。
                     块的大小与存储密度有关:存储密度=串值所占存储位/实际分配存储位。

  单字符结点:插入、删除方便;存储密度小,存储占用量大。

技术分享

 

  多字符结点:存储密度大;插入、删除存在结点的分离,降低存储密度。

 

技术分享

二、字符串的KMP算法

  2.1、串的模式匹配算法
     串的模式匹配:求子串P在主串T中的位置的定位操作称为串的模式匹配。
     模式串:子串。
 2.2、简单的模式匹配算法:
     从主串T的第一个字符起,与模式串P的第一个字符比较,若相等,则继续逐个比较后继字符,否则从主串T的第二个字符起再重新和模式串P的第一个字符比较。依次类推,直到模式串P中的每个字符依次和主串T中的一个连续的字符序列相等,则称匹配成功,返回与P匹配的主串T的字符序列的第一个字符序号。否则称匹配失败,函数值为0(或-1)。简单模式匹配算法存在的问题:在模式匹配过程中存在已比较的字符重复比较。实际上已比较过的字符不必重复比较。

技术分享
 1      int Index(SString T,SString P,int pos)
 2      {       
 3              int i,j,k;
 4              int m=strlen(P);
 5              int n=strlen(T);
 6              for(i=pos-1;i<n-m;i++)
 7              {  
 8                  for(j=0,k=i;j<m&&T[k]==P[j]; k++; j++);
 9                      if(j==m) reurn i;
10               }
11               return -1;
12      }
View Code

 2.3、KMP算法实现

  2.3.1、输入和输出
        输入:输入主串和模式串,以及开始比较的位置
        输出:输出模式串和主串开始匹配的起始位置,若不匹配则返回0,若匹配则返回匹配的位置。
  2.3.2、关键数据结构与算法描述
        数据结构:字符数组和整形数组
        算法描述:使用KMP算法,进行字符串匹配,最大的特点和优点就是i指针不回溯。首先要找到模式串对应的next数组的值。由于找到next数组是为了更好的进行匹配,因此再进行模式串与模式串的匹配求next数组时,可以对next数组进行优化,亦即如果t[i]==t[j],在进行i++,j++后如果t[i]==t[j],则next[i]=next[j];如果不相等,next[i]=j。求出next数组之后,就是KMP算法的主体了,要是j==-1或者s[i]==t[j],i,j都要加一,要不然j=next[j];继续进行比较,直至子串或主串结束。
     2.3.2.1、求next的算法

技术分享
 1 void  get_nextval(char *t,int next[])
 2 {
 3     int i=0,j=-1;
 4     int size=strlen(t);
 5         next[0]=-1;
 6     while(i<size-1)
 7     {
 8         if(j==-1||t[i]==t[j])
 9         {
10             i++;
11             j++;
12         
13             if(t[i]==t[j])
14             {
15                 next[i]=next[j];
16             }
17             else
18                 next[i]=j;
19         }
20         else
21             j=next[j];
22     }
23 }
View Code

     2.3.2.2、KMP算法主体

技术分享
 1 int   KMP(char *s,char *p,int position,int next[])
 2 {
 3     int i=position-2;//position 为比较位置,从1开始读
 4     int j=-1;
 5     int S_SIZE=strlen(s),P_SIZE=strlen(p);
 6     while(i<S_SIZE&&j<P_SIZE)
 7     {
 8         if(j==-1||s[i]==p[j])
 9         {
10             i++;
11             j++;
12         }
13         else
14             j=next[j];
15     }
16     if(j<P_SIZE)
17         return 0;
18     else
19         return i-j+1;
20 }
View Code

 2.3.3、测试与理论
  1.主串:abcabdsfegabcdsdfg
   模式串:abdsfe
   起始位置:2,5
   理论结果:4,0
  2.主串:qqwerttryuriopazgdjcvjkfn
   模式串:ttryu
   起始位置:3,7
   理论结果:6,0
技术分享技术分享

 2.3.4、所有代码

技术分享
 1 #include"stdio.h"
 2 #include"string.h"
 3 void  get_nextval(char *t,int next[])
 4 {
 5     int i=0,j=-1;
 6     int size=strlen(t);
 7         next[0]=-1;
 8     while(i<size-1)
 9     {
10         if(j==-1||t[i]==t[j])
11         {
12             i++;
13             j++;
14         
15             if(t[i]==t[j])
16             {
17                 next[i]=next[j];
18             }
19             else
20                 next[i]=j;
21         }
22         else
23             j=next[j];
24     }
25 }
26 
27 int   KMP(char *s,char *p,int position,int next[])
28 {
29     int i=position-2;//position 为比较位置,从1开始读
30     int j=-1;
31     int S_SIZE=strlen(s),P_SIZE=strlen(p);
32     while(i<S_SIZE&&j<P_SIZE)
33     {
34         if(j==-1||s[i]==p[j])
35         {
36             i++;
37             j++;
38         }
39         else
40             j=next[j];
41     }
42     if(j<P_SIZE)
43         return 0;
44     else
45         return i-j+1;
46 }
47 
48 int  main()
49 {
50   char  s[100];
51   char  t[100];
52   int  next[100],pos=1;
53   while(1)
54   {
55 
56      printf("请输入主串:\n");
57      scanf("%s",s);
58      printf("请输入模式串:\n");
59      scanf("%s",t);
60      printf("请输入开始比较的位数(默认为一)\n");
61      scanf("%d",&pos);
62 
63      get_nextval(t,next);
64      printf("开始匹配的起始位置为(若为0则不匹配)\n");
65 
66      printf("%d\n",KMP(s,t,pos,next));
67   }
68    return 0;
69 }
View Code

 

 




 


 
 

 



 

 

 

数据结构与算法系列研究三——字符串