第五章串_Java

第五章串

1 串的定义

串是由零个或多个字符组成的有限序列，又名叫字符串。
零个字符串称为空串。
串中任意个数的连续字符组成的子序列称为该串的子串，相应的，包含子串的串称为主串。
子串在主串中的位置就是子串的第一个字符在主串中的序号。

2 串的比较

字母a 有大于无

3 串的抽象数据类型线

性表更关注的是单个元素的操作，比如查找一个元素，插入或删除一个元素.
串中更多的是查找子串位置、得到指定位置子串、替换子串等操作

ADT 串（string）
Data
    串中元素仅由一个字符组成，相邻元素具有前驱和后继关系。
Operation
    StrAssign(T, *chars);//生成一个其值等于字符串常量chars的串T。
    StrCopy(T, S);//串S存在，由串S复制得串T。
    ClearString(S);//串S存在，将串清空
    StringEmpty(S);//若S为空，返回true，否则返回flase。
    StrLength(S);//返回串S的元素个数，即串的长度。
    StrCompare(S, T);//若S>T，返回值>0；若S=T，返回0；若S 
Index的实现 
int Index(String S, String T, int pos)
{
    int n, m, i;
    String sub;
    if (pos > 0)
    {
        n = StrLength(S);              
        m = StrLength(T);                   
        i = pos;
        while (i <= n - m + 1)
        {
            SubString(sub, S, i, m);    
         								       
            if (StrCompare(sub, T) != 0)    
                ++i;
            else                                           
                return i;                    
        }
    }
    return 0;                               
}
 
用到了StrLength、SubString、StrCompare等基本操作来实现 
4 串的存储结构 
4.1 串的顺序存储结构 
串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列。
 串值后面加一个不计入串长度的结束标记符，比如来表示串值的终结。
 串值的存储空间可在程序执行过程中动态分配而得。计算机中存在一个自由存储区，叫做堆。可由C语言的分配函数malloc()和free()来管理。 
4.2 串的链式存储结构 
串结构中的每个元素数据是一个字符，如果也简单的应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此，一个结点可以存放一个字符，也可以考虑存放多个字符，最后一个结点若是未被占满时，可以用“#”或其他非串值字符补全。 
5 朴素的模式匹配算法 
子串的定位操作通常称为串的模式匹配。
 不用串的其他操作，只用基本的数组来实现算法Index。假设主串和要匹配的子串的长度存在
    
     
      
       
        S
       
       
        [
       
       
        0
       
       
        ]
       
      
      
       S[0]
      
     
    S[0]与
    
     
      
       
        T
       
       
        [
       
       
        0
       
       
        ]
       
      
      
       T[0]
      
     
    T[0]中。 

int Index(String S, String T, int pos)
{
    int i = pos;                  
    int j = 1;                
   
    while (i <= S[0] && j <= T[0])   
    {                                  
        if (S[i] == T[j])             
        {
            ++i;
            ++j;
        }
        else                         
        {
            i = i - j + 2;                        
            j = 1;                   
        }
    }
    if (j = T[0])
        return i - T[0];
    else
        return 0;
}
 
6 KMP模式匹配算法 
6.1 KMP模式匹配算法原理 
  
void get_next(String T, int *next)  
{  
    int i,j;  
    i=1;  
    j=0;  
    next[1]=0;  
    while (i 
  
  
int Index_KMP(String S, String T, int pos)  
{  
    int i = pos;          
    int j = 1;            
    int next[255];        
    get_next(T, next);    
    while (i <= S[0] && j <= T[0])   
    {  
        if (j==0 || S[i] == T[j])     
        {  
            ++i;  
            ++j;  
        }  
        else              
            j = next[j];  
    }  
    if (j > T[0])  
        return i-T[0];  
    else  
        return 0;  
}
 
对于get_next函数来说，若T的长度为m，因只涉及到简单的单循环，其时间复杂度为O(m)，而由于i值的不回溯，使得index_KMP算法效率得到了提高，while循环的时间复杂度为O(n)。因此，整个算法的时间复杂度为O(n＋m)。相较于朴素模式匹配算法的O((n-m+1)*m)来说，是要好一些。 
KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势，否则两者差异并不明显

第五章 串

Java相关栏目本月热门文章

第五章串