欢迎各位彦祖与热巴畅游本人专栏与博客
你的三连是我最大的动力
以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]
专栏跑道一
➡️网络空间安全——全栈前沿技术持续深入学习
专栏跑道二
➡️ 24 Network Security -LJS
专栏跑道三
➡️ MYSQL REDIS Advance operation
专栏跑道四
➡️HCIP;H3C-SE;CCIP——LJS[华为、华三、思科高级网络]
专栏跑道五
➡️RHCE-LJS[Linux高端骚操作实战篇]
专栏跑道六
➡️数据结构与算法[考研+实际工作应用+C程序设计]
专栏跑道七
➡️RHCSA-LJS[Linux初级及进阶骚技能]
上节回顾
数据结构与算法系列学习之串
1.串的定义和基本操作
1.1定义:
- 串,即字符串(String)是由零个或多个字符组成的有限序列。一般记为S = ‘a1a2······an' (n ≥0)
- 其中,S是串名,单引号括起来的字符序列是串的值;ai可以是字母、数字或其他字符;串中字符的个数n称为串的长度。n = 0时的串称为空串(用∅表示)。
- 有的地方用双引号(如Java、C),有的地方用单引号(如Python)
- 例如:S=”HelloWorld!”T=‘iPhone 14 Pro Max?’
- 子串:串中任意个连续的字符组成的子序列。Eg:’iPhone’,’Pro M’是串T的子串
- 主串:包含子串的串。Eg:T是子串’iPhone’的主串
- 字符在主串中的位置:字符在串中的序号。Eg:’1’在T中的位置是8(第一次出现)
- 子串在主串中的位置:子串的第一个字符在主串中的位置。Eg:’14Pro’在T中的位置为8
- 每个空格字符占1B,不是空串
- 串的位序从1开始而不是从0开始
- 串是一种特殊的线性表,数据元素之间呈线性关系
- 串的数据对象限定为字符集(如中文字符、英文字符、数字字符、标点字符等)
- 串的基本操作,如增删改查等通常以子串为操作对象,因为人类的语言通常要多个字符组成的序列才有现实意义
1.2串的基本操作
假设有串 T = ''
, S = 'iPhone 14 Pro Max?'
, W = 'Pro'
- StrAssign(&T, chars): 赋值操作,把串T赋值为chars;
- StrCopy(&T, S): 复制操作,把串S复制得到串T
- StrEmpty(S): 判空操作,若S为空串,则返回TRUE,否则返回False;
- StrLength(S): 求串长,返回串S的元素个数;
- ClearString(&S): 清空操作,将S清为空串;
- DestroyString(&S): 销毁串,将串S销毁——回收存储空间;
- Concat(&T, S1, S2): 串联联接,用T返回由S1和S2联接而成的新串———可能会导致存储空间的扩展;
- 例:
Concat(&T, S, W) T = ‘iPhone 14 Pro Max?Pro’
SubString(&Sub, S, pos, len)
: 求子串,用Sub返回串S的第pos个字符起长度为len的子串;
SubString(&T, S, 4, 6) T = ‘one 14’
- Index(S, T): 定位操作,若主串S中存在与串T值相同的子串,则返回它再主串S中第一次出现的位置,否则函数值为0;
- StrCompare(S, T): 串的比较操作,参照英文词典排序方式;若S > T,返回值>0; S = T,返回值=0 (需要两个串完全相同) ; S < T,返回值<0;
1.3字符集编码:
- 任何数据存到计算机中一定是二进制数。
- 需要确定一个字符和二进制数的对应规则这就是“编码”
- “字符集”:英文字符,ASCII字符集,中英文,Unicode字符集
- 基于同一个字符集,可以有多种编码方案,如:UTF-8,UTF-16
- 注:采用不同的编码方式,每个字符所占空间不同,考研中只需默认每个字符占1B即可
编辑
2.串的储存结构
2.1顺序存储:
代码实现:
//预定义最大串长为255 typedef struct{ char ch[MAXLEN]; //静态数组实现(定长顺序存储) //每个分量存储一个字符 //每个char字符占1B int length; //串的实际长度 }SString;
- 方案一:一个数组来储存字符,一个int变量length储存实际长度
- 方案二:数组的ch[0]来充当length,优点:字符的位序和数组下标相同
- 方案三:没有Length变量,以字符’\0’表示结尾(对应ASCII码的0),缺点:获取字符串长度需要遍历,时间复杂度高
- 方案四:数组的ch[0]废弃不用,从看开始储存字符,外加一个int变量length储存实际长度
2.2链式存储
代码实现:
typedef struct StringNode{ char ch; //每个结点存1个字符 struct StringNode *next; }StringNode, * String; 问题:存储密度低,每个字符1B,每个指针4B; 解决方案:每一个链表的结点存储多个字符——每个结点称为块——块链结构 typedef struct StringNode{ char ch[4]; //每个结点存多个个字符 struct StringNode *next; }StringNode, * String;
- 推荐使用第二种方式,存储密度较高,ch数组未必一定是4个字符,也可以比4多
3.基本操作的实现(使用第四种方案):
编辑
编辑
编辑
基本操作代码实现[方案4]:
typedef struct{ char ch[MAXLEN]; int length; }SString; // 1. 求子串 bool SubString(SString &Sub, SString S, int pos, int len){ //子串范围越界 if (pos+len-1 > S.length) return false; for (int i=pos; i<pos+len; i++) Sub.cn[i-pos+1] = S.ch[i]; Sub.length = len; return true; } // 2. 比较两个串的大小 int StrCompare(SString S, SString T){ for (int i; 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; } // 3. 定位操作 int Index(SString S, SString T){ int i=1; n = StrLength(S); m = StrLength(T); SString sub; //用于暂存子串 while(i<=n-m+1){ SubString(Sub,S,i,m); if(StrCompare(Sub,T)!=0) ++i; else return i; // 返回子串在主串中的位置 } return 0; //S中不存在与T相等的子串 }
4.朴素模式匹配算法
4.1字符串模式匹配:
- 在主串中找到与模式串相同的子串,并返回其所在位置。
- 子串:主串的一部分,一定存在
- 模式串:不一定能在主串中找到
- 要掌握朴素模式匹配算法、KMP算法两种方法
4.2朴素模式匹配算法(两种实现方法):
- 将主串中所有长度为m的子串依次与模式串对比,直到找到一个完全匹配的子串,或所有的子串都不匹配为止。
- 主串长度为n,模式串长度为 m,最多对比 n-m+1 个子串
- 上节讲的index定位操作就是朴素模式匹配算法中其中一种实现方法
- 也可以使用两个指针i和j来进行匹配。若当前子串匹配失败,则主串指针 i 指向下一个子串的第一个位置,模式串指针 j 回到模式串的第一个位置,即i = i - j + 2; j = 1;
- 若 j > T.length,则当前子串匹配成功,返回当前子串第一个字符的位置即i - T.length
编辑
设主串长度为 n,模式串长度为 m,则最坏时间复杂度 = O(n*m),最好时间复杂度 = O(n)
朴素模式匹配算法代码实现:
int Index(SString S, SString T){ int i=1; //扫描主串S int j=1; //扫描模式串T while(i<=S.length && j<=T.length){ if(S.ch[i] == T.ch[j]){ ++i; ++j; //继续比较后继字符 } else{ i = i-j+2; j=1; //指针后退重新开始匹配 } } if(j>T.length) return i-T.length; else return 0; }
5.KMP算法
5.1KMP算法的概念
- 由D.E.Knuth,J.H.Morris和V.R.Pratt提出,因此称为 KMP算法
- 是对朴素模式匹配算法的优化
- 优化的原理就是减少了i指针的回溯,通过已经计算好的next指针,提高算法的整体运行效率
next数组记录了当第几个元素匹配失败时候,j的取值例如:
- 对于模式串 T = ‘abaabc’
- 当第6个元素匹配失败时,可令主串指针 i 不变,模式串指针 j=3
- 当第5个元素匹配失败时,可令主串指针 i 不变,模式串指针 j=2
- 当第4个元素匹配失败时,可令主串指针 i 不变,模式串指针 j=2
- 当第3个元素匹配失败时,可令主串指针 i 不变,模式串指针 j=1
- 当第2个元素匹配失败时,可令主串指针 i 不变,模式串指针 j=1
- 当第1个元素匹配失败时,匹配下一个相邻子串,令 j=0, i++, j++
next数组只和短短的模式串有关,和长长的主串无关
5.2KMP算法的优点
- 之所以只和模式串有关,是因为如果在哪里匹配失败,同时说明在这之前的部分主串和模式串是相同的
- KMP算法,最坏时间复杂度 O(m+n),其中,求 next 数组时间复杂度 O(m),模式匹配过程最坏时间复杂度 O(n)
- KMP算法精髓:利用好已经匹配过的模式串的信息
5.3KMP算法代码实现:
int Index_KMP(SString S, SString T, int next[]){ int i=1; //主串 int j=1; //模式串 while(i<S.length && j<=T.length){ if(j==0 || S.ch[i]==T.ch[j]){ //第一个元素匹配失败时 ++j; ++i; //继续比较后继字符 } else j=next[j] //模式串向右移动 } if(j>T.length) return i-T.length; //匹配成功 }
5.4KMP算法之求next数组
编辑
5.4.1求next数组代码实现 [含图解]
编辑
如上图next数组的求法: 对于任何模式串,当第1个字符不匹配时,只能匹配下一个子串,因此,next[1] = 0——表示模式串应右移一位,主串当前指针后移一位,再和模式串的第一字符进行比较; int Index_KMP(SString S, SString T, int next[]){ int i=1; //主串 int j=1; //模式串 while(i<S.length && j<=T.length){ if(j==0 || S.ch[i]==T.ch[j]){ //第一个元素匹配失败时 ++j; ++i; //继续比较后继字符 } else j=next[j] //模式串向右移动 } if(j>T.length) return i-T.length; //匹配成功 }
5.4.1next数组的作用:
- 当模式串的第 j 个字符失配时,从模式串的第 next[j] 的继续往后匹配
5.5KMP算法之求nextval数组
定义:
- nextval数组是对next数组的优化,用nextval替代next数组,减少了无意义的对比
nextval数组的求法:
- 先根据上面的方法算出next数组
- 先令nextval[1]=0
- 再根据下面代码算出后面的nextval数组
求nextval数组代码实现[此处本人理解可能有点小问题,但是问题不大;理论任然成立]
for(int j = 2; j <= T.length; j++) { //让第next值个元素的值和当前元素比较 if(T.ch[next[j]] == T.ch[j]) { //若相等则让第next值个元素的nextval值复制给当前元素的nextval值 nextval[j] = nextval[next[j]]; } else { //若不等则让当前元素的next值赋值给当前元素的nextval值 nextval[j] = next[j]; } }