【图解数据结构】串全面总结

一、基本概念

• 串（string）:由0个或多个字符组成的有序序列，称为字符串，记为s='abcdefg' 其中s是字符串的名字，a b c称为串的值，可以是字母、数字或者字符

• 串长度：串中元素个数

• 空串：不含任何字符的串，串长度为0

• 子串：主串中任意连续字符组成的字符串

• 串s1、s2相等的条件：

  1. s1、s2长度相等
  2. s1、s2对应位置的元素处处相等

二、串的类型

1.定长顺序串

定义：用一组地址连续的存储单元存储串值的字符序列，类似于线性表的顺序存储结构。

静态存储分布代码实现：

#define MAXLEN 30 // 用户可在255以内定义最大串长  typedef struct { char ch[MAXLEN]； int len；
} SString ;

动态演示：

• 其实就是依次插入

2.基本算法

串插入：

int StrInsert(SString *s, int pos, SString t) /*在串s中下标为pos的字符之前插入串t */ {    int i;
    if (pos<0 || pos>s->len) /*插入位置不合法*/         return 0; 
    if (s->len + t.len<=MAXLEN) /*插入后串长≤MAXLEN*/     {
        for (i=s->len + t.len-1;i>=t.len + pos;i--)
            s->ch[i]=s->ch[i-t.len]; //将插入位置现有字符后移         for (i=0;i<t.len;i++) 
           s->ch[i+pos]=t.ch[i]; //在空出的位置逐个插入字符串         s->len=s->len+t.len;
    }     else     { if (pos+t.len<=MAXLEN) /*插入后串长>MAXLEN,但串t的字符序列可以全部插入*/         {
            for (i=MAXLEN-1;i>t.len+pos-1;i--) 
               s->ch[i]=s->ch[i-t.len]; //将插入位置现有字符后移             for (i=0;i<t.len;i++)
                s->ch[i+pos]=t.ch[i]; //在空出的位置逐个插入字符串             s->len=MAXLEN;
        }
        else /*插入后串长>MAXLEN,并且串t的部分字符也要舍弃*/         {     for (i=0;i<MAXLEN-pos;i++)
                s->ch[i+pos]=t.ch[i];
            s->len=MAXLEN;
        }
        return 1;
    }
}

串删除：

int StrDelete(SString *s, int pos, int len) /*在串s中删除从下标pos起len个字符*/ { 
    int i;
    if (pos<0 || pos>(s->len-len)) /*删除参数不合法*/         return 0; 
    for (i=pos+len;i<s->len;i++)
        s->ch[i-len]=s->ch[i]; /*从pos+len开始至串尾依次向前移动，实现删除len个字符*/     s->len=s->len - len; /*s串长减len*/     return 1;
}

串复制：

void StrCopy(SString *s, SString t) /*将串t的值复制到串s中*/ { 
    int i;
    for (i=0;i<t.len;i++)
        s->ch[i]=t.ch[i];
    s->len=t.len;
}

串比较：

int StrCompare(SString s, SString t) /*若串s和t相等则返回0；若s>t则返回正数；若s<t则返回负数*/ { 
    int i;
    for (i=0;i<s.len&&i<t.len;i++)
        if (s.ch[i]!=t.ch[i]) 
            return(s.ch[i] - t.ch[i]); //按字符的字典顺序比较     return(s.len - t.len);
}

串连接：

int StrCat(SString *s, SString t) /*将串连接在串s的后面*/ {     int i, flag;
    if (s->len + t.len<=MAXLEN) /*连接后串长小于MAXLEN*/     { 
        for (i=s->len; i<s->len + t.len; i++)
            s->ch[i]=t.ch[i-s->len]; //t的下标从0开始         s->len+=t.len;
        flag=1;
   }
    else { if (s->len<MAXLEN) /*连接后串长大于MAXLEN，但串s的长度小于MAXLEN，即连接后串t的部分字符序列被舍弃*/         { 
         for (i=s->len;i<MAXLEN;i++)
                s->ch[i]=t.ch[i-s->len];
            s->len=MAXLEN;
            flag=0;
        }
     else             flag=0; /* 串s的长度等于MAXLEN ,串t不被连接*/     return flag;
    }

求子串：

int SubString(SString *sub, SString s, int pos, int len) /*将串s中下标pos起len个字符复制到sub中*/ {     int i; if (pos<0 || pos>s.len || len<1 || len>s.len-pos) //位置或长度不合法时 {
        sub->len=0;
        return 0; 
    }
    else     { for (i=0; i<len; i++)
        sub->ch[i]=s.ch[i+pos];
            
            sub->len=len; return 1;
    }
}

3.堆串

• 堆：自由存储区域，malloc()实现
• 以一组地址连续的存储单元存储串值的字符序列，在程序执行过程中由动态分配而得到

代码：

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

4.块链串

• 定义：与链表类似，但每一个结点可以存放多个字符，结尾增加尾指针

代码实现：

#define BLOCK_SIZE 4 // 可由用户定义的块大小  typedef struct Block { char ch[BLOCK_SIZE]; struct Block *next; } Block;

三、模式匹配

• 定义：求解子串首次在主串中出现的位置
• 模式匹配也称为子串的定位操作，用函数StrIndex(S,pos,T)实现，T被称为模式串。

代码：

int StrIndex(SString s,int pos, SString t) /*求从主串s的下标pos起，串t第一次出现的位置，成功返回位置序号，不成功返回-1*/ {     int i, j, start;
    if (t.len==0) return(0); /* 模式串为空串时，是任意串的匹配串 */     start=pos; i=start; j=0; /* 主串从pos开始，模式串从头（0）开始 */     while (i<s.len && j<t.len)
        if (s.ch[i]==t.ch[j]) 
        {    i++;   j++;    } /* 当前对应字符相等时推进 */         else         {   start++; /* 当前对应字符不等时回溯 */              i=start;    j=0; /* 主串从start+1开始，模式串从头（0）开始*/         } 
        if (j>=t.len) 
            return(start); /* 匹配成功时，返回匹配起始位置 */         else             return(-1); /* 匹配不成功时，返回-1 */ }

演示图：

解析：

• 设置两个指针i和k,输入目标串Hello World!,模式串orl
• 如果i指向的值和模式串首个元素不一致，则指针i j同时向后移动
• 如果i指向的值和模式串首个元素一致，则只是指针j向后移动
• 如果j指向的元素和模式串后续元素一致，继续移动，直到查找完成
• 如果j指向的元素和模式串后续元素不一致，指针i到k的位置，继续开始

四、总结与提高

在C++中，C++ 标准库提供了 string 类类型，支持上述所有的操作，另外还增加了其他更多的功能。

编程时加入头文件：

#include<string>//或者万能头文件#include<bits/stdc++.h> using namespace std;

String函数：

用string定义s类（定义什么都可以，只要把s变成定义的字母就可以调用C++中的函数）,具体使用方法为：

文档的具体内容可以参考：C++标准官方文档

五、附录：

几道经典的题目链接：

1.无重复的最长子串

2.最长回文串

3.模式匹配

4.回文串

5.最长回文子序列