数据结构与算法--串

2021/11/28 17:11:08

本文主要是介绍数据结构与算法--串,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

目录
  • 串类型的定义
    • 子串
  • 基本操作
  • 串的表示和实现
    • 定长顺序存储表示
    • 堆分配存储表示
    • 串的块链存储表示
  • 模式匹配算法
    • 简单算法
    • 首尾匹配算法
    • KMP算法

串类型的定义

计算机非数值处理的对象基本都是字符串数据。

由零个或多个字符组成的有限序列

s = ‘a1a2……an

其中,s表示串名,a1a2……an代表串值,ai可以是字母、数字或其他字符。|s|表示串长,即串中字符的数目。ai在序列中的序号(串中字符的序号从0开始)称为该字符在串中的位置。单引号本身不属于串,只起界定作用。

零个字符的串成为空串

一个或多个空格组成的串成为空格串

子串

串中任意个连续字符组成的子序列

包含字串的串相应的成为主串

特别的,空串是任意串的字串,任意串是其自身的字串。

计算字串时,一定要注意是否包括空串和自身。

字串在主串中的位置:字串在主串中首次出现时的该字串的首字符对应的字串中的序号,也称字串在主串中的序号。(习惯序号从0开始)

基本操作

StrAssign(&T,chars);//常量赋值
StrCopy(&T,S);//拷贝赋值
StrDestroy(&S);//串的销毁
StrEmpty(S);//串是否为空
StrCompare(S,T);//串的比较
StrLength(S);//串的长度
StrCat(&T,S1,S2);//串的拼接
StrSub(&Sub,S,pos,len);//串的字串
Index(S,T,pos);//从S的pos位置查找T第一次出现位置,没有则返回-1
Replace(&S,T,V);//字串的替换
StrInsert(&S,pos,T);//串的插入
StrDelete(&S,pos,len);//子串的删除
StrClear(&S);//串的清空

上述定义的13中操作中,StrAssign(串赋值)、StrCopy(串复制)、StrCompare(串比较)、StrLength(求串长)、StrCat(串拼接)、StrSub(求子串)这六种操作构成串类型的最小操作子集

串的表示和实现

串实际上是特殊的线性表,故其存储结构与线性表的存储结构类似,只不过串的结点是单个字符。

定长顺序存储表示

用一组地址连续的存储单元存储串值的字符序列。

按照预定义的大小,为每个定义的串变量分配一个固定长度的存储区。串的实际长度可以在此预定义长度内随意,但超过预定义长度的串值会被舍弃,称为截断

两种顺序存储表示:

  • 下标0的分量存放串的长度,其他存放字符
  • 串值末尾增加一个不计入串长的结束标记字符,例如C和C++C采用‘\n’结尾
//一些操作比较简单,这里只是实现部分操作,采用的以'\n'结尾
//串拼接
Status StrCat(&T,S1,S2)
{
    int len1 = StrLength(S1),len2 = StrLength(S2);
    for(int i = 0;i<len1&&i<MAXSIZE;++i)
        T[i] = S1[i];
    for(int i = 0; i < len2 && len1 + i < MAXSIZE; ++i)
        T[i+len1] = s2[i];
    if(len1 + len2 > MAXSIZE)
        T[MAXSIZE-1] = '\n';
    else 
        T[len1+len2-1] = '\n';
    return OK;
}

//求子串
Status StrSub(&Sub,S,pos,len)
{
    int len = StrLength(S);
    if(pos + len > n)
        return ERROR;
    for(int i = 0; i < len; ++i)
        Sub[i] = S[pos+i];
    Sub[len] = '\n';
    return OK;
}

堆分配存储表示

在定长顺序存储中,虽然实现简单,但是由于空间一定,很容易产生截断现象,所以我们自然而然想到动态分配空间。

堆分配存储仍然采用一组地址连续的存储单元存放串值字符序列,但是存储空间是在程序执行过程中动态分配而得,所以也称为动态存储分配的顺序表。

通常,C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc和freee进行串值空间的动态管理,为每一个新产生的串分配一个存储区,称为串值共享的存储空间为堆,仍是顺序存储。

同定长顺序存储实现,我们仍然采用C语言形式描述堆分配存储表示。我们没有显式的T[0]去描述串长,串长是一个隐含值(串以特定字符结尾)。所以,约定串长也作为存储结构的一部分。

//以下的实现中,如果不对HString进行StrAssign会导致ch指针没有分配空间。除了使用StrAssign外,可以在struct内使用一个构造函数,对ch指针进行初始化。
//在线性表实现中,我们就知道,如果在一个顺序存储区进行不断插入元素等操作,可能分配空间不足。所以当前堆分配存储,我们为了避免存储空间不够,每次我们都为新生成的串分配一个存储空间,然后进行串值的复制。
//代码中OK,ERROR,OVERFLOW需要define;
typedef struct 
{
    char* ch;//串
    int length;//长度
}HString;

Status StrAssign(HString &S, char* chars)//字符串常量应该以'\n'结尾
{
    if(T.ch)
        free(T.ch);
    int cnt = 0;//记录chars的串长
    char *p = chars;
    while(*p != '\n')
    {
        ++p;
        ++cnt;
    }
    if(!cnt)
    {
        T.ch = NULL;
        T.length = 0;
    }
    else
    {
        T.ch = (char*)malloc((cnt+1)*sizeof(char));
        if(!T.ch)
            exit(OVERFLOW);
    	for(int i =0;i<cnt;++i)
            T.ch[i] = chars[i];
        T.ch[cnt] = '\0';
        T.length = cnt;
    }
    return OK;
}

//串长
int Strlength(HString S)
{
    return S.length;
}

//若S>T返回值>0,S<T返回值<0,S=T返回值=0
int StrCompare(HString S, HString T)
{
    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(HString& S)
{
    if (S.ch)
    {
        free(S.ch);
        S.ch = 0;
    }
    S.length = 0;
    return OK;
}

//串的拼接
Status StrCat(HString& T, HString S1, HString S2)
{
    if (T.ch)
    {
        free(T.ch);
    }
    T.ch = (char*)malloc((S1.length + S2.length + 1) * sizeof(char));
    if (!T.ch)
        exit(OVERFLOW);
    for (int i = 0; i < S1.length; ++i)
        T.ch[i] = S1.ch[i];
    for (int i = 0; i < S2.length; ++i)
        T.ch[S1.length + i] = S2.ch[i];
    T.ch[S1.length+S2.length] = '\0';
    T.length = S1.length + S2.length;
    return OK;
}

//获取子串
Status StrSub(HString& Sub, HString S, int pos, int len)
{
    if (pos < 0 || pos >= S.length || len < 0 || pos + len > S.length)
        return ERROR;
    if (Sub.ch)
        free(Sub.ch);
    if (!len)
    {
        Sub.ch = NULL;
        Sub.length = 0;
    }
    else
    {
        Sub.ch = (char*)malloc((len+1) * sizeof(char));
        if(!Sub.ch)
            exit(OVERFLOW);
        for (int i = 0; i < len; ++i)
            Sub.ch[i] = S.ch[pos + i];
        Sub.ch[len] = '\0';
        Sub.length = len;
    }
    return OK;
}

//串插入
Status StrInsert(HString &S, int pos, HString &T)
{
    if(pos < 0 || pos > S.length)
    	return ERROR;
    char* temp = (char*)malloc((S.length+T.length+1)*(sizeof(char)));
    if(!temp)
        exit(ERROR);
    for(int i = 0;i < pos;++i)
        temp[i] = S.ch[i];
    for(int i = 0;i < T.length; ++i)
        temp[i+pos] = T.ch[i];
    for(int i = pos;i < S.length;++i)
        temp[i+T.length] = S.ch[i];
    temp[S.length+T.length] = '\0';
    if(!S.ch)
        free(S.ch);
    S.ch = temp;
    return OK;
}

串的块链存储表示

同线性表,串的顺序表示插入和删除也很不方便,需要移动大量字符,所以我们可以采用单链表的方式存储串值,串的这种链式存储结构简称为链串。

typedef struct node 
{
    char ch;
    struct node *next;
}LinkStr;

这种结构便于进行插入和删除,但是存储空间利用率太低。每个节点只存储了一个字符,所以我们通常在一个节点中存储一个子串。将串的链表存储和串的定长结构结合使用。(为什么不结合堆存储呢?笑死,每个结点到底存多少呢?这不徒增烦恼)

存储密度:(串值所占存储位)/(实际分配存储位)

节点大小的选择直接影响到串处理的效率。所以要尽可能增大存储密度。当然也不是越大越好。

在下方结点结构中,next指针大小为4,而data为CHUNKSIZE,故存储密度为 CHUNKSIZE / CHUNKSIZE+4

实际应用中可以根据问题所需来设置结点大小,例如,在编辑系统中,整个文本编辑区可以看作是一个串,每一行是一个子串,构成一个结点。即:同一行的串用定长结构(80字符),行与行之间用指针相联结。

这里只给出相关结构定义,其余操作函数易实现。

#define CHUNKSIZE 80//自定义块大小
//一个链串由头指针唯一确认
typedef struct Chunk//结点结构
{
    char data[CHUNKSIZE];
    struct Chunk *next;
}Chunk;
typedef struct//块链结构
{
    Chunk *head, *tail;//串的头尾指针
    int curlen;//串的当前长度
}LString;

模式匹配算法

字串的定位运算通常称为串的模式匹配,是串处理中最重要的运算之一。通常把主串S称为目标,把字串T成为模式,把从目标S中查找模式为T的字串的过程称为“模式匹配”。

以下代码重点在于算法讲解,为了简便,不再使用自定义串,而是统一使用string

简单算法

//遍历每一个位置进行匹配,以string类型为例
int INDEX(string S, string T, int pos)
{
    int i = pos,j = 0;
    while(i < S.size() && j < T.size())
    {
        if(S[i]==T[j])
        {
            ++i;
            ++j;
        }
        else 
        {
            i = i - j + 1;
            j = 0;
		}   
    }
    if(j == T.size())
    	return i-T.size();
    else 
        return -1;
}

时间复杂度分析:

  • 最好情况:每次不成功匹配第一个字符就能比较出结果,则总的比较次数为 i-1+m(i代表匹配成功位置)

    可算出时间复杂度为O(n+m)

  • 最坏情况:每次不成功匹配最后一个字符才能比较出结果,则总的比较次数为i*m

    可算出时间复杂度为*O()

首尾匹配算法

首先比较模式串的第一个字符,再比较模式串的最后一个字符,最后比较模式串中从第二个到第n-1个字符。

int Index_FL(string S, string T, int pos)
{
    int i = pos;
    while (i <= S.size() - T.size())
    {
        if (S[i] != T[0])
        {
            ++i;
            continue;
        }
        if (S[i + T.size() - 1] != T[T.size() - 1])
        {
            ++i;
            continue;
        }
        else
        {
            int j = 1;
            while (j < T.size() - 1&&S[i+j]==T[j])
                ++j;
            if (j == T.size() - 1)
            {
                return i;
            }
            else
                ++i;
        }
    }
    return -1;
}

KMP算法

算法思想:在主串的第i个字符匹配失败后,不回溯主串当前的位置,而是根据已经得到的部分匹配结构,将模式串向右滑动尽可能远的一段距离后,继续进行比较。

我们已知主串S第i个元素和模式串T第j个元素不匹配,这时我们并不进行回溯,而是进行模式串的匹配分析,对S第i个元素和模式串第k和元素进行匹配。

也就是说,我们对模式串进行处理,对于前j-1个元素,我们找到前k-1个元素和后k-1个元素相同的情况(需要满足最长前后缀匹配),然后返回k,将S的第i个元素和模式串第k个元素进行比较。

1.为什么能从模式串第k个元素进行比较?

我们将模式串T字串(前j个元素)的前k-1个元素(记作前缀)和后k-1个元素(记作后缀)进行了匹配,同时主串S第i个元素前的k-1个元素和模式串T第j个元素前的k-1个元素(也就是上面所说后缀)也是匹配的。所以,模式串的前缀也是和主串T的第j个元素前的k-1个元素是匹配的。

2.为什么能保证前后缀之间不存在匹配可能性?

首先明确我们选取的是最长前后缀匹配串,也就是说,如果在中间存在一个和前缀匹配的字串,甚至长度允许大于匹配的后缀的长度,那么如果从中间这个位置能够和主串S匹配,就有模式串从头开始和模式串从中间部分开始,能够一直到模式串结尾匹配,那么这个从中间开始的字串才是最长前后缀匹配串,与假设矛盾了。

//next函数求解
/*
*next函数实质上就是找到前缀和后缀最大匹配长度,next[i]就表示前i-1
*字符中的前后缀匹配。这样如果在匹配时,如果模式串i与主串不同,我不
*需要回到0,而是只需要回到next[i],因为前i-1前后缀匹配。即这段字符
*前next[i] - 1个字符是和后缀匹配的,也就是说我们只需要从next[i]
*重新开始就行
*/
vector<int> KMP_next(string str)
{
    vector<int>next(str.size());
    next[0] = -1;
    int j = 1;
    int k = next[0];
    while (j < str.size())
    {
        if (k == -1 || str[j - 1] == str[k])
            next[j++] = ++k;
        else
            k = next[k];
    }
    return next;
}

//实际上,我们可以发现,如果str[j] == str[next[j]],那我们就没必要从next[j]这个位置开始回溯,而应该再在前next[j]中进行匹配。于是我们可以得到nextval
vector<int> KMP_nextval(string str)
{
    vector<int> next = KMP_next(str);
    vector<int> nextval(str.size());
    nextval[0] = -1;
    int j = 1;
    int k = nextval[0];
    while (j < str.size())
    {
        if (k == -1 || str[j - 1] == str[k])
        {
            if (str[j] != str[++k])
                nextval[j] = k;
            else
                nextval[j] = nextval[k];
            ++j;
        }
        else
            k = nextval[k];
    }
    return nextval;
}

int KMP(string S, string T)
{
    int len1 = S.size();
    int len2 = T.size();
    vector<int>nextval = KMP_nextval(T);
    int i = 0, j = 0;
    //warning:这里不能用S.size代替len1,size返回值为unsigned而i为signed
    //所以如果j为-1,那么j和len2比较会视为unsigned比较,即j变成了最大值
    while (i < len1 && j < len2)
    {
        //j=-1就说明要从模式串开头重新开始
        if (j == -1 || S[i] == T[j])
        {
            ++i;
            ++j;
        }
        else
            j = nextval[j];
    }
    if (j == T.size())
        return  i - T.size();
    return -1;
}


这篇关于数据结构与算法--串的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程