数据结构与算法--串
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;
}
这篇关于数据结构与算法--串的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-11-23Springboot应用的多环境打包入门
- 2024-11-23Springboot应用的生产发布入门教程
- 2024-11-23Python编程入门指南
- 2024-11-23Java创业入门：从零开始的编程之旅
- 2024-11-23Java创业入门：新手必读的Java编程与创业指南
- 2024-11-23Java对接阿里云智能语音服务入门详解
- 2024-11-23Java对接阿里云智能语音服务入门教程
- 2024-11-23JAVA对接阿里云智能语音服务入门教程
- 2024-11-23Java副业入门：初学者的简单教程
- 2024-11-23JAVA副业入门：初学者的实战指南
