[串](1)字符串

计算机上的非数值处理的对象基本上是字符串数据,在较早的程序设计语言中,字符串是作为输入和输出的常量出现的,随着语言加工程序的发展,产生了字符串处理,这样,字符串也就作为一种变量类型出现在越来越多的程序设计语言中,同时也产生了一系列字符串的操作,字符串一般简称为串

在汇编和语言的编译程序中,源程序及目标程序都是字符串数据,在事务处理程序中,顾客的姓名和地址以及货物的名称、产地和规格等一般也是作为字符串处理的,又如信息检索系统,文字编辑程序、问答系统、自然语言翻译系统以及音乐分析程序等,都是以字符串数据作为处理对象的。

然而,现今我们使用的计算机的硬件结构主要是反映数值计算的需要,因此,在处理字符串数据时比处理整数和浮点数要复杂的多。

而且,在不同类型的应用中,所处理的字符串具有不同的特点,要有效的实现字符串的处理,就必须根据具体请看使用合适的存储结构。

串类型的定义

串是一种特定的线性表,它的每一个元素都是一个字符。

串(string)是由零个或多个字符组成的有限序列,一般记为:S=‘a1a2...an’(n>=0)

其中,S是串名,用单引号括起来的字符序列就是串的值:ai(1<=i<=n)可以是字母、数字,或其他字符,串中字符的数目n称为串的长度,零个字符的串称为空串(null string),它的长度为零。

串中任意个连续字符组成的子序列称为该串的子串,包含子串的串相应的称为主串,通常称字符在序列中的序号为该字符在串中的位置,子串在主串中的位置则以子串的第一个字符在主串中的位置来表示

例如,假设a、b、c、d为如下的四个串:

  • a=‘BEI’
  • b=‘JING’
  • c=‘BEIJING’
  • d=‘BEI JING’

则它们的长度分别为3、4、7和8,并且a和b都是c和d的子串,a在c和d中的位置都是1,而b在c中的位置是4,在d中的位置则是5

称两个串是相等的,当且仅当这两个串的值相等,也就是说,只有当两个串的长度相等,并且各个对应位置的字符都相等时才相等,例如上例中的串a,b,c,d都不想等

值得一提的是,串值必须用一对单引号括起来,但单引号本身不属于串,它的作用只是为了避免与变量名或数的常量混淆而已。

例如:x=‘123’

则表明x是一个串变量名,赋给它的值是字符序列123,又如:tsing=‘TSING’中,tsing是一个串变量名,而字符序列TING是其值。

在各个应用中,空格常常是串的字符集合中的一个元素,因而可以出现在其他字符中间,由一个或多个空格组成的串‘ ’称为空格串(blank string)

串的逻辑结构和线性表极为相似,区别仅在于串的数据对象约束为字符集,然而,串的基本操作和线性表有很大差别,在线性表的基本操作中,大多以“单个元素”作为操作对象,例如在线性表中查找某个元素,求取某个元素、在某个位置上插入一个元素和删除一个元素第等,而在串的基本操作中,通常以“串的整体”作为操作对象,例如在串中查找某一个子串,求取一个子串、在串的某个位置上插入一个子串以及删除一个子串等。

串的抽象数据类型定义如下:

ADT String
{
    数据对象:D = {a[i] | a[i]属于CharacterSet,i = 1,2,...,n,n >= 0}
    数据关系:R1 = {<a[i - 1],a[i]> | a[i - 1],a[i]属于D,i = 2,...,n}
    基本操作:
           StrAssign(&T,chars)
        初始条件:chars是一个字符串常量
        操作结果:生成一个其值等于chars的串T
           
        StrCopy(&T,S)
        初始条件:串S已存在
        操作结果:由串S复制得串T
           
        StrEmpty(S)
        初始条件:串S存在
        操作结果:若串S为空串,则返回TRUE,否则返回FALSE
           
        Strcompare(S,T)
        初始条件:串S和T存在
        操作结果:若S > T,则返回值 > 0; 若S = T,则返回值 = 0,若S < T,则返回值 < 0
           
        StrLength(S)
        初始条件:串S存在
        操作结果:返回S的元素个数,称为串的长度
           
        ClearString(&S)
        初始条件:串S存在
        操作结果:将S清为空串
           
        Concat(&T,S1,S2)
        初始条件:串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 <= StreLength(S) + 1
        操作结果:在串S和第pos个字符之前插入串T
           
        StrDelete(&S,pos,T)
        初始条件:串S和T存在,1 <= pos <= StreLength(S) + 1
        操作结果:从串S中删除第pos个字符起长度为len的子串
           
        DestroyString(&S)
        初始条件:串S存在
        操作结果:串S被销毁

}ADT String

对于串的基本操作集可以有不同的定义方法,在使用高级程序设计语言中的串类型时,应以该语言的参照手册为准,在上述抽象数据类型定义的13种操作中:

串赋值StrAssign、串比较StrConmpare、求串场StrLength、串联接Concaty,以及求子串SubString。5种操作构成串类型的最小操作子集。即这些操作不可利用其他串操作来实现,反之,其他串操作(除串清除ClearString和串销毁DestroyString外)均可在这个最小操作子集上实现

例如,可利用判等、求串长和求子串等操作实现定位函数Index(S,T,pos),算法的基本思想为:在主串S中取从第i(i的初值为pos)个字符起,长度和串T相等的子串和串T比较,若相等,则求的函数值为i,否则i值增1,直至串S中不存在和串T相等的子串为止,

int Index(String S, String T, int pos)
//T为非空串,若主串S中第pos个字符之后存在与T相等的子串
//则返回第一个这样的子串在S中的位置,否则返回0;
{
    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;//S中不存在与T相等的子串
}

串的表示和实现

如果在程序设计语言中,串只是作为输入或输出的常量出现时,则只需要存储此串的串值,即字符序列即可,但在多数非数值处理的程序中,串也以变量的形式出现

串有3中机内表示方法,分别介绍如下。

定位顺序存储表示

类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列,在串的定长顺序存储结构中,按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区,则可用定长数组如下描述:

#define MAXSTRLEN 255
typedef  unsigned char String[MAXSTRLEN + 1];

上述代码中串的长度为255,定义一个char类型的数组长度为255+1,则是因为在0号下标的时候存储的是串当时的长度

串的实际长度可在这预定义长度范围内随意,超过预定义长度的串值则被舍去,称之为“截断”

对串长有两种表示方法:

  • 一是如上所述,以下标为0的数组分量存放串的实际长度。
  • 二是在串值后面加一个不计入串长的结束标记字符,如在有C语言中以“0”空字符表示串值的终结,此时的串长为隐含值,显然不便于进行某些串操作

在这种存储结构表示时如何实现串的操作,下面以串联接和求子串为例讨论

  • 串联接Concat(&T,S1,S2)

假设S1和S2都是String型的串变量,且串T是由串S1联结串S2得到的,即串T的值的前一段和串S1的值相等,串T的值的后一段和串S2的值相等,则只要进行相应的“串值复制”操作即可,只是需按前所述约定,对超长部分实施“截断”操作,基于串S1和S2长度的不同操作,串T值产生可能有如下3种情况:

  1. S1[0]+S2[0]<=MAXSTRLEN,则S1加上S2的串长在约定范围内,得到的T为正确的
  2. S1[0]<MAX-STRLEN,而S1[0]+S2[0]>MAXSTRLEN,则S2能放多少就放多少,多去的部分截断,得到的T只包含S2的一个子串
  3. S1[0]=MAXSTRLEN,则得到的串T并非包含联接的结果,而是与S1相等

上述算法如下描述所示

Status Concat(String& T, String S1, String S2)
//用T返回由S1和S2联接而成的新串,若未截断,则返回TRUE,否则FALSE
{
    if (S1[0] + S2[0] <= MAXSTRLEN)//未截断
    {
        T[1....S1[0]] = S1[1....S1[0]];
        T[S1[0] + 1...S1[0] + S2[0]] = S2[1...S2[0]];
        T[0] = S1[0] + S2[0];
        uncut = TRUE;
    }
    else if (S1[0] < MAXSTRLEN)//截断
    {
        T[1...S1[0]] = S1[1...S1[0]];
        T[S1[0] + 1...MAXSTRLEN] = S2[1...MAXSTRLEN - S1[0]];
        T[0] = MAXSTRLEN;
        uncut = FALSE;
    }
    else//截断,仅取S1
    {
        T[0...MAXSTRLEN] = S1[0...MAXSTRLEN];//T[0]==S1[0]==MAXSTRLEN
        uncut = FALSE;
    }
    return uncut;
}

求子串SubString(&Sub,S,pos,len)

求子串的过程即为复制字符序列的过程,将串S中从第pos个字符开始长度为len的字符序列复制到串Sub中,显然,本操作不会有需截断的情况,但有可能产生用户给出的参数不合法的初始条件,当参数非法时,返回ERROR,其算法描述如下:

Status SubString(String& Sub, String S, int pos, int len)
//用Sub返回串S的第pos个字符起长度为len的子串
//其中,1<=pos<=StrLength(S),且0<=len<=StrLength(S)-pos+1
{
    if (pos<1 || pos>S[0] || len<0 || len>S[0] - pos + 1)
    {
        return ERROR;
    }
    Sub[1...len] = S[pos...pos + len - 1];
    Sub[0] = len;
    return OK;
}

综上两个操作可见,在顺序存储结构中,实现串操作的原操作为“字符序列的复制”,操作的时间复杂度基于复制的字符序列的长度,另一操作特点是,如果在操作中出现串值序列的长度超过上界MAXSTRLEN时,约定用截尾法处理,这种情况不仅在求联接串时可能发生,在串的其他操作中,如插入、置换等也可能发生,克服这个弊病唯有不限定长的最大长度,即动态分配串值的存储空间。

堆分配存储表示

这种存储表示的特点是,仍以一组地址连续的存储单元存放串值字符序列,但他们的存储空间是在程序执行过程中动态分配而得,在C语音中,存在一个称之为“堆”的自由存储区,并由C语言动态分配函数malloc和free来管理,利用函数malloc为每个新产生的串分配一块实际串长所需的存储空间,若分配升高,则返回一个指向起始地址的指针,作为串的基地址,同时,为了以后处理方便,约定串长也为存储结构的一部分

typedef struct
{
    char* ch;//若是非空串,则按串长分配存储区,否则ch为NULL
    int length;//串长度
}HString;

这种存储结构表示时的串操作仍是基于“字符序列的复制”进行的,例如

串复制操作StrCopy(&T,S)的实现算法是:

  • 若串T已存在,则先释放串T所占空间,当串S不空时,首先为串T分配大小和串S长度相等的存储空间,再将串S的值复制到串T中。

又如串操作StrInsert(&S,pos,T)的实现算法是:

  • 为串S重新分配大小等同串S和串T长度之和的存储空间,然后进行串值赋值,如下所示
Status StrInsert(HString& S, int pos, HString T)
//1 <= pos <= StrLength(S) + 1
{
    if (pos<1 || pos>S.length + 1)
    {
        return ERROR;//pos不合法
    }
    if (T.length)//T非空,则重新分配空间,插入T
    {
        if (!(S.ch = (char*)realloc(S.ch, (S.length + T.length) * sizeof(char))))
        {
            exit(0);
        }
        for (i = S.length - 1; i >= pos - 1; --i)
        {
            S.ch[i + T.length] = S.ch[i];
        }
        S.ch[pos - 1...pos + T.length - 2] = T.ch[0...T.length - 1];//插入T
        S.length = S.length + T.length;
    }
    return OK;
}

以上两种存储表示通常为高级程序设计语言所采用,由于堆分配存储结构的串既有顺序存储结构的特点,处理方便,操作中对串长又没有任何限制,更显灵活,因此,在串处理应用程序中也常被选用,一下所示未只含最小操作子集的动态顺序串类型的模块说明

typedef struct
{
    char* ch;/*若非空串,则按串长分配存储区,否则ch为NULL*/
    int length;/*串长度*/
}String;

//基本操作函数说明

Status StrAssign(String* S, char* chars);
//生成一个其值等于串常量chars的串T

int StrLength(String S);
//返回S串的元素个数,称之为串长

int StrCompare(String S, String T);
//若S>T,则返回值>0;若S=T,则返回值=0,若S<T,则返回值<0

Status ClearString(String* S);
//将S清为空串

Status Concat(String* T, String S1, String S2);
//1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
//返回串S的第pos个字符起长度为len的子串

以下为基本算法描述

Status StrAssign(String* T, char* chars)
//生成一个其值等于串常量chars的串T
{
    if (T->ch != NULL)
    {
        free(T->ch);
    }
    for (int i = 0; char* c = chars; *c; i++, c++);

    if (!i)
    {
        T->ch = NULL;
        T->length = 0;
    }
    else
    {
        T->ch = (char*)malloc(sizeof(char) * i);
        if (T->ch == NULL)
        {
            printf("失败\n");
            exit(0);
        }
        T->ch[0....i - 1] = chars[0...i - 1];
        T->length = i;
    }
    return OK;
}

int StrLength(String S)
//返回S的元素个数,称为串的长度
{
    return S.length;
}


int StrCompare(String S, String T)
//若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0
{
    for (int i = 0; i < S.length && i < T.length; i++)
    {
        if (S.ch[i] != T.ch[i])
        {
            return S.ch[i] - T.ch[i];
        }
        return S.length - T.length;
    }
}


Status ClearString(String* S)
//将S清为空串
{
    if (S->ch)
    {
        free(S->ch);
        S->ch = NULL;
    }
    S->length = 0;
    return OK;
}

Status Concat(String* T, String S1, String S2)
//用T返回由S1和S2联接而成的新串
{
    if (T->ch)
    {
        free(T->ch);
    }
    T->ch = (char*)malloc(sizeof(char) * (S1.length + S2.length));
    if (T->ch == NULL)
    {
        printf("错误\n");
        exit(0);
    }
    T->ch[0..S1.length - 1] = S1.ch[0...S1.length - 1];
    T->length = S1.length + S2.length;
    T->ch[S1.length...T.length - 1] = S2.ch[0...S2.length - 1];
    return OK;
}

Status SubString(String* Sub, String S, int pos, int len)
//用Sub返回串S的第pos个字符起长度为len的子串
//其中,1<=pos<=StrLength(S)且0<=len<=StrLength(S)-pos+1
{
    if (pos<1 || pos>S.length || len<0 || len>S.length - pos + 1)
    {
        printf("参数不合法\n");
        exit(0);
    }
    if (Sub->ch)
    {
        free(Sub->ch);
    }
    if (!len)
    {
        Sub->ch = NULL;
        Sub->length = 0;
    }
    else
    {
        Sub->ch = (char*)malloc(sizeof(len * sizeof(char)));
        Sub->ch[0...len - 1] = S.ch[pos - 1...pos + len - 2];
        S.length = len;
    }
    return OK;
}

以上为基本操作的算法模板,由于采用的是动态顺序存储结构,则字符存放起始位置能从0或1开始,对应的算法和操作也不同,需要注意的就是下标控制。

串的块链存储表示

和线性表的链式存储结构相类似,也可采用链表的方式存储串值,需要注意的是,链式串的每个元素都是一个字符,则在使用链表存储串值时,存在一个“结点大小”的问题,即每个节点可以存放一个字符,也可以存放多个字符,当结点大小大于1时,由于串长不一定是结点大小的整数倍,则链表中的最后一个结点不一定全被串值占满,此时通常补上“#”或其他非串值字符(通常“#”不属于串的字符集,是一个特殊的符号)

如下图所示:

img第一个为节点大小为4
第二个为节点大小为1

为了便于进行串的操作,当以链表存储串值时,除头指针外还可附设一个尾指针指示链表中最后一个结点,并给出当前串的长度,称如此定义的串存储结构为块链结构,说明如下:

#define CHUNKSIZE 80//可有用户定义的块大小
typedef struct Chunk
{
    char ch[CHUNKSIZE];
    struct Chunk* next;
}Chunk;
typedef struct
{
    Chunk* head, * tail;//串的头和尾指针
    int curlen;
}LString;

由于在一般情况下, 对串进行操作时,只需要从头向尾顺序扫描即可,则对串值不必建立双向链表,设立尾指针的目的是为了便于进行联结操作,但应注意联结时需处理第一个串尾的无效字符

在链式存储方式中,结点大小的选择和顺序存储方式的格式选择一样都很重要,它直接影响着串处理的效率,在各串的处理系统中,所处理的串往往很长或很多,例如:一本书的几百万个字符,情报资料的成千上万个条目,这要求我们考虑串值的存储密度

存储密度=串值所占的存储位/实际分配的存储位

当存储密度小的时候,运算处理方便,但是存储占用量大,如果在串处理过程中需进行内、外存交换,则会因为内外存交换操作过多而影响处理的总效率。

应该看到,串的字符集的大小也是一个重要因素,一般的,字符集小,则字符的机内编码就短,这也影响串值的存储方式的选取

串值的链式存储结构对某些串操作,如联接操作等有一定方便之处,但总得来说不如动态顺序存储和静态顺序存储(堆分配和约定串长)灵活,它占用存储量大且操作复杂,此外,串值在链式存储结构时,串操作的实现和线性表在链表存储结构中的操作类似,故我们将重心放在另两种存储结构即可

串的模式匹配算法(BF算法)

子串的定位操作但通常称作串的模式匹配,其中T为模式串:Index(S,T,pos),是各种串处理系统中最重要的操作之一,一般的算法就是古典的暴力破解法,也成为穷举法,把所有可能都尝试一遍,直到匹配上了为止,算法如下:

int Index_BF(String* S, String* T, int pos)
{
    if (pos<1 || pos>S->length)
    {
        printf("参数不合法\n");
        exit(0);
    }

    int i = pos, j = 1;

    while (i < S->length && j < T->length)
    {
        if (S->ch[i] == T->ch[j])
        {
            i++;
            j++;
        }
        else
        {
            i = i - j + 2;
            j = 1;
        }

    }

    if (j >= T->length)
    {
        return i - T->length + 1;
    }
    else
    {
        printf("子串不存在\n");
        return -1;
    }
}

在上述算法中,分别利用计数指针i和j指示主串S和模式串T中当前正待比较的字符位置。

算法的基本思想是:

  • 从主串S的第pos个字符起和模式的第一个字符比较,若相等,则继续逐个比较后续字符,否则从主串的下一个字符起再重新和模式串的第一个字符比较,以此类推,直到模式T中的每个字符依次和主串S中的一个连续的字符序列相等,则匹配成功,函数值为和模式T中第一个字符相等的字符在主串S中的序号,否则为匹配不成功,函数值为-1.

视频演示:

此算法虽然易懂,但是它的平均时间复杂度为O(n*m),最坏的情况需要进行多次回溯,下面介绍KMP算法

KMP模式匹配算法

此算法不需要进行回溯,而是通过对模式串构造一个next数组,通过数组中的值来确定模式串游标下一个位置是哪里,换句话说,当主串的第i个字符与模式串中第j个字符不匹配的时候,主串i的第i个字符应与模式串的第哪个字符匹配?

那么这个第哪个字符就是模式串当前j指向元素的最大相等前后缀

而next数组则是由前缀表构成,前缀表的定义如下:

假定给定一个模式串abaccacaba

  • 它的前缀是不包含尾元素的字符序列:abaccacab
  • 它的后缀是不包含首元素的字符序列:baccacaba

又它的前后缀求的最大相等字符序列,最大的定义就是前缀组合和后缀组合中相等的最大子串序列,例如上述前后缀组合为:

img

那么它的最大相等前后缀就是3

abaccacaba对应的next则为:

img

再求的next数组后,匹配可如下进行:

  • 假设以指针i和j分别指示主串和模式中正待比较的字符

    • 令i的初值为pos,j的初值为1
  • 若在匹配过程中,S[i]==T[j],则i和j分别增1,否则i不变,而j退到next[j]的位置再做匹配。
  • 以此类推,直至下列有两种可能

    1. 一种是j退到某个next值时字符比较相等,则指针各增1,继续进行匹配
    2. 另一种是j退到值为0(即模式串第一个字符失配)的情况,则从主串当前位置的下一位置开始匹配

它的算法如下所示

int Index(String* S, String* T,int pos)
{
    int i = pos; int j = 1;
    if (pos<1 || pos>S->length)
    {
        printf("错误\n");
        exit(0);
    }

    int* next = NULL;
    next = get_next(*T, next);

    while (i < S->length && j < T->length)//边界
    {
        if (j == 0 || S->ch[i] == T->ch[j])
        {
            i++;
            j++;
        }
        else
        {
            j = next[j];//退回j的next值
        }
    }

    if (j >= T->length)
    {
        printf("%d,%d,%d", i, T->length, j);
        return i - T->length + 1;
    }
    else
    {
        printf("未找到子串\n");
        return -1;
    }
}

而KMP最核心的就是next数组,而next数组怎么求呢?看小甲鱼的教程:

算法如下所示:

int* get_next(String T, int next[])
{
    next = (int*)malloc(sizeof(int) * T.length + 1);
    int i = 1, j = 0;
    next[1] = 0;
    while (i < T.length)
    {
        if (j == 0 || T.ch[i] == T.ch[j])
        {
            i++;
            j++;
            next[i] = j;
        }
        else
        {
            j = next[j];//j回溯,前缀是固定的,而后缀是相对的
        }
    }

    return next;

}

对于视频教程的理解,next数组就是把模式串分为两个部分,前缀和后缀,如果匹配,则前缀和后缀继续判断下一个字符,直到不匹配的时候,得到的就是最大相等前后缀。而第一个字符因为无前后缀,所以next的值都是0。

而next的值就是失配的地方,那么当不匹配的时候,前缀需要进行回溯到上一个失配的地方继续匹配,来寻求最大相等前后缀

从代码可以看到,主函数和next构造函数的结构大同小异,换句话来说,next函数寻求的就是在当前位置上,前缀和后缀有多少个字符相等,把前缀当作T串,后缀当作S串。

而此算法的时间复杂度可提升到O(m+n)

了解了next后来看青岛大学王卓老师的课程:教程地址

本文链接:

https://nullcode.fun/28.html
1 + 6 =
快来做第一个评论的人吧~