Abo

数据结构-串

发表于 | 分类于 | 热度 ℃
字数统计 2.4k | 阅读时长 9

虽然课本已经不把串的抽象数据类型作为重点，但是毕竟有所提及，这里还是把串的相关笔记提交上来


startup

“你将不再是道具，而是人如其名的人”

  • 前言

    串(string)是由零个或多个字符组成的有限序列，又名叫字符串,一般记为s=”a1a2a3….an”(n≥0),其中s是串的名称，用双引号括起来的字符序列是串的值，注意单引号不属于串中的内容。

    串中的字符数目n称为串的长度

    零个字符的串称为空串(null string)，它的长度为0，可以直接用两双引号“”表示，也可以用希腊字母Ø表示

    空格串，是只包含空格的串，注意它与空串的区别，空格串是有长度的，而且可以不止一个空格

  • 字串和主串：串中容易个数的连续字符组成的子序列称为该串的字串，相应地，包含字串的串称为主串

    字串在主串中的位置就是字串的第一个字符在主串中的符号

串的比较

串的比较是通过组成串的字符之间的编码来进行的，而字符的编码指的是字符在对应字符集中的序号。

ASCII——扩展——Unicode——UTF-8的关系了解一波?

如果我们要在c语言中比较两个串是否相等，必须是它们串的长度以及它们各自对应位置的字符都相等时，才算是相等,而对于两个不相等的串，怎么判定它们的大小呢?

给定两个串：s=“a1a2….an”，t=“b1b2b3…bn”，当满足以下条件之一时，s<t.

  1. n<m，且ai=bi(i=1，2…..,n) 例如当s=”hap”,t=”happy”就有s<t
  2. 存在某个k≤min(m,n),使得ai=bi(i=1,2….k-1), ak<bk 例如当s=”happen”,t=”happy”因为两串的前4个字母均相同，而两串第五个字母(k)值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
    ClearStrng(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)。若主串S中存在和串T值相同的子串，则返回它在主串S中第pos个字符之后第一次出现的位置，否则返回0
    Index(S,T,pos):串S和T存在，T是非空串，1≤pos≤StrLength(S)。若主串S中存在和串T值相同的字串，则返回它在主串中第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的子串
endADTs

我们来看一个操作Index的实现算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*T为非空串。若主串S中第pos个字符之后存在与T相等的子串则返回第一个这样的字串在S中的位置，否则返回0*/
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);/*取主串第i个位置，长度与T相等子串给sub*/
            if(StrCompare(sub,T) != 0) /*如果两串不相等*/
                ++i;
            else
                return i;/*如果两串相等，则返回i值*/
        }
    }
    return 0;/*若无子串与T相等，返回0*/
}

串的顺序存储结构是用一组地址连续的存储单元来存储串中的字符序列的。按照预定义的大小，为每个定义的串变量分配一个固定长度的存储区。一般是用定长数组来定义

既然是定长数组，就存在一个预定义的最大串长度，一般可以将实际的串长度值保存在数组的0下标位置，有的书也会定义存储在数组的最后一个下标位置

有些是规定在串值后面加一个不计入串长度的结束标记字符，比如“\0”来表示串值的终结，这个时候你要想知道串长度，遍历计算一下即可

朴素的模式匹配算法(BF算法)(Brute Force)

子串的的定位操作通常称为串的模糊匹配，应该算是串中最重要的操作之一

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*返回子串在主串S中第pos个字符之后的位置，若不存在则返回值为0。T非空，1≤pos≤StrLength(S)*/
int Index(String S, String T, int pos)
{
    int i = pos;   /*i用于主串S中当前位置下标，若pos不为1则从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 = 1;  /*j退回到子串T的首位*/
        }
    }
    if(j > T[0])
        return i-T[0];
    else
        return 0;
}

KMP模式匹配算法

三位前辈发表一个模式匹配算法，可以大大避免重复遍历的情况，我们称之为克努特-莫里斯-普拉特算法，简称KMP算法

此处省略原理简介以及next数组的引入，自己看书，简述几个例子

  1. abcdex———011111
  2. abcabx———011123
  3. ababaaaba———011234223
  4. aaaaaaaab———012345678
  • KMP模式匹配算法实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    /*通过计算返回子串T的next数组*/
    void get_next(String T,int *next)
    {
        int i,j;
        i=1;
        j=0;
        next[1]=0;
        while(i<T[0])  /*此处T[0]表示串T的长度*/
        {
            if(j==0 || T[i]==T[j])  /*T[i]表示后缀的单个字符，T[j]表示前缀的单个字符*/
            {
                ++i;
                ++j;
                next[i] = j;
            }
            else
                j = next[j];      /*若字符不相同，则j值回溯*/
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/*返回子串T在主串S中第pos个字符之后的位置。若不存在，则函数返回值为0.。T非空，1≤pos≤StrLength(S)*/
int Index_KMP(String S, String T,int pos)
{
    int i = pos;  /*i用于主串S当前位置下标值，若pos不为1，则从pos位置开始匹配*/
    int j = 1;  /*j用于子串T中当前位置下标值*/
    int next[255]; /定义一next数组/
    get_next(T,next);/对串T作分析，得到next数组/
    while(i <= S[0] && k <= T[0])
    {
        if(j==0 || S[i] == T[j])  /两字母相等则继续，与朴素算法增加了j=0判断/
        {
            ++i;
            ++j;
        }
        else
        {
            j = next[j];  /j退回合适的位置，i值不变/
        }
    }
    if(j > T[0])
        return i-T[0];
    else
        return 0;
}

绿色注释部分为相对于朴素匹配算法增加的代码，改动不算大，关键就是去掉了i值回溯的部分。

对于get_next函数来说，若T的长度为m，因只涉及到简单的单循环，其时间复杂度为O(m)，而由于i值的不回溯，使得index_KMP算法效率得到了提高

while循环的时间复杂度为O(n),因此，整个算法的时间复杂度为O(n+m)，相较于朴素算法的O((n-m+1)*m)l来说，是要好一些。

KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才体现出它的优势，否则两者差异并不明显

KMP模式匹配算法改进

对next函数进行了改良,假设取代的数组为nextval(String T,int *nextval),注意观察两者区别

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/*求模式串T的next函数修正值并存入数组nextval*/
void get_nextval(String T,int *nextval)
{
    int i,j;
    i = 1;
    j = 0;
    nextval[1]=0;
    while(i <T[0])  /*此处T[0]表示串T的长度*/
    {
        if(j==0 || T[i] == T[j]) /*T[i]表示后缀的单个字符，T[j]表示前缀的单个字符*/
        {
            ++i;
            ++j;
            /*以下则是区别之处*/
            if(T[i] != T[j])  /*若当前字符与前缀字符不同*/
               nextval[i] = j;  /*则当前的j为nextval在i位置的值*/
            else
               nextval[i] = nextval[j];  /*如果与前缀字符相同，则将前缀字符的nextval值赋值给nextval在i位置的值*/
        }
        else
           j = nextval[j]; /*若字符不相同，则j值回溯*/
    }
}

实际匹配算法，只需要将”get_next(T,next);”改为”get_nextval(t,next);”j即可，这里不再重复

  • nextval数组值推导
  1. ababaaaba——011234223——010104210
  2. aaaaaaaab——012345678——000000008

总结改进过的KMP算法，它是在计算出next值的同时,如果a位字符与它next值指向的b位字符相等，则a位的nextval就指向b位的nextval值，如果不等，则该a位的nextval值就是它自己的a位的next的值。