第五章 串

串的定义

串是由零个或者多个字符组成的有限序列，又叫字符串。

一般记为s=”a1a2…an”(n≥0)，s是串的名字，引号中的字符序列是串的值而不是内容。ai(1≤i≤n)可以是字母、数字等，i是改字符在串中的位置。

串中的字符数目n称为串的长度，定义中谈到“有限”指的是长度n是有一个有限的数值。

零个字符的串称为空串，长度为0，直接用两个“”””表示。

所谓的序列，说明串的相邻字符之间有前驱和后继的关系。

空格串：只是包含空格的串。

字串和主串：串中任意个数的连续字符组成的子序列称为该串的子串，包含字串的串称为主串。

字串在珠串的位置就是字串的第一个字符在主串的序号。

串的比较

对于两个不相等的串进行判断大小：

给定义两个串：s=“a1a2…an”，t=“b1b2…bm”，当满足以下条件之一时，s<t。

（1）n<m，且ai = bi（i=1,2,…,n）

例如：s=“hap”，t=“happy”，s<t

（2）存在某个≤min(m,n)，使得ai=bi(i=1,2,…,k-1),ak<bk

例如：当s-“happen”，t-“happy”，因为两串的前4个字母均相同，而两串第5个字母(k值)，字母e的ASCII码是101，而字母y的ASCI码是121，显然e<y，所以s<t。

串的抽象数据类型

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
ADT 串 (string）
Data
串中元素仅由一个字符组成，相邻元素具有前驱和后继关系
Operation
        StrAssign(T,*chars):生成一个其值等于字符串常量 chars 的串T。
        StrCopy(T,S):串s存在，由串S复制得串T。
        Clearstring(s):串s存在，将串清空。
        stringEmpty(S):若串S为空，返回true，否则返回 false。
        strLength(s):返回串s的元素个数，即串的长度。
        StrCompare(s,T):若S>T,返回值>0,若S=T,返回0,若S<T,返回值<0。
        Concat(T,s1,S2):用T返回由S1和S2联接而成的新串。
        Substring(Sub,s,pos,len):串s存在,1≤pos≤StrLength(s),且            0≤len≤StrLength(s)-pos+1，用Sub返回串s的第pos个字符起长度为 len的子串。 
        Index(S,T,pos):串S和T存在,T是非空串,1≤pos≤StrLength(s)。若主串s中存在和串T值相同的子串，则返回它在主串s中第pos个字符之后第一次出现的位置，否则返回0。
        Replace(s,T,V):串S、T和V存在,T是非空串。用v替换主串s中出现的所有与T相等的不重叠的子串。
        StrInsert(s,pos,T):串S和T存在,1≤pos≤StrLength(s)+1。在串s的第pos个字符之前插入串 T。
        StrDelete(s,pos,len):串s存在,1≤pos<strLength(s)-len+1。从串s中删除第pos个字符起长度为 len 的子串。
endADT

Index算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int Index(String S,Strinf T,int pos)
{
    int n,m,i;
    String sub;
    if(pos>0){
     n = StrLength(S); //得到主串S的长度
     m = StrLength(T); //得到字串T的长度
     i = pos;
     while(i <= n-m+1){
          SubString(sub,S,i,m);//主串中第i个位置开始长度与T相等的字串给sub
          if(SubString(sub,T)!=0)//如果两串不相等
                  ++i;
          else
                  return i; 
       }
    }
reteun 0;
}

串的存储结构

串的顺序存储结构

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。

比如：计算机中寸在一个自由存储区，叫做“堆”。这个堆可由C语言的动态分配函数malloc()和free()来管理

串的链式存储结构

如果是简单地应用链表存储串值，一个结点对应一个字符，就会存在很大的空间浪费。因此一个结点，可以存放一个字符，也可以考虑放多个字符，最后一个结点若是未被沾满，可以用“#”等非串字符补传，比如：

https://cdn.jsdelivr.net/gh/weixuna/MyPic/24/11/image_719f922a2a3a5e5ff62159498d7564a9.png

模式匹配算法

去找一个单词在一篇文章中的定位为，这种字串的定位操作通常称做串的模式匹配。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int Index(Strinf S,String T,int pos){
      int i = pos;       //i用于字串S中当前的位置下标值，从pos位置开始匹配
      int j = 1;         //j用于字串T当前位置下标值
      while(i≤S[0]&&j≤T[0]){    //当i小于S的长度并且j小于T的长度是，循环继续
           if(S[i] == T[j])    //两字母相等则继续
           {
               ++i;
               ++j;
           }else{              //指针后退重新开始匹配
                i = i-j+2;     //i退回上次匹配首尾的下一位
                j = i;        //j退回到字串T的首位
            }
     }
      if(j >T[0]){
         return i-T[0];
     }else{
         retrun 0;
     }
}