图解数据结构串全面总结

千金一刻莫空度，老大无成空自伤。这篇文章主要讲述图解数据结构串全面总结相关的知识，希望能为你提供帮助。
一、基本概念

串（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 Blockchar 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++中的函数）,具体使用方法为：


函数	用法
常见操作
s.resize(10)	设置字符串长度为10
string s(" ABC" )	构造字符串s的值为ABC
s.empty()	判断字符串是否为空
s.length()或者s.size()	求解字符串长度
s.begin()	开始值
s.end()	结尾值
查找（查找成功返回元素位置，失败返回-1）
s.find(A)	查找字符A
s.find(" ABC" )	查找字符串ABC
s.find(A,2)	从位置2开始查找字符A
s.find(" ABCD" ,1,2)	从位置1开始，查找ABCD的前两个字符
s.rfind()	从字符串尾部开始查找
插入
s.insert(2,3,A)	在下标为2的地方添加三个A
s.insert(2," ABC" )	在下标为2的地方添加字符串ABC
s.insert(2," ABC" ,1)	在下标为2的地方添加ABC中的一个
s.insert(2," ABCD" , 2，2)	在下标为2的地方从字符串ABCD中位置2开始的2个字符
s.push_back(A)	在尾部添加字符A
替换
s.replace(2,4," ABCD" )	从下标2的位置，替换4个字符为 " ABCD"
删除
s.erase(2)	删除下标2以后的全部元素
s.erase(2,1)	删除下标2以后的第一个元素
翻转
reverse(s.begin(),s.end())	翻转所有字符串，即逆序输出
复制
s1=s.substring(2)	提取字符串s从2到尾部赋值给s1
s1=s.substring(2,3)	提取字符串s从2开始三个字符赋值给s1
const char*s1=s.data()	将string类转为字符串数组
s.copy(s1,2,3)	将s中从第3个位置拷贝2个字符到s1中
比较(假设原字符串为ABCD)
s.compare(" ABCD" )	相等返回0，大于原字符串返回1,小于返回-1
清空
s.assign(" ABC" )	清空字符串，并置为ABC
s.assign(" ABC" ,2)	清空字符串，并置为ABC的前2个字符AB
s.assign(" ABC" ,2，1)	清空字符串，并置为ABC的从2开始的1个字符
s.assign(5，‘A’)	清空字符串，并置为5个A
s.clear()	清空字符串所有字符