大佬教程收集整理的这篇文章主要介绍了数据结构与算法--串，大佬教程大佬觉得挺不错的，现在分享给大家，也给大家做个参考。

串类型的定义

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

串

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

s = ‘a₁a₂……a_n’

其中，s表示串名，a₁a₂……a_n代表串值，a_i可以是字母、数字或其他字符。|s|表示串长，即串中字符的数目。a_i在序列中的序号（串中字符的序号从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] = '';
        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] = '';
    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] = '';
        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] = '';
    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;
}

大佬总结

以上是大佬教程为你收集整理的数据结构与算法--串全部内容，希望文章能够帮你解决数据结构与算法--串所遇到的程序开发问题。

如果觉得大佬教程网站内容还不错，欢迎将大佬教程推荐给程序员好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。