【数据结构篇C++实现】- 特殊的线性表 - 串

这篇具有很好参考价值的文章主要介绍了【数据结构篇C++实现】- 特殊的线性表 - 串。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

友情链接:C/C++系列系统学习目录



🚀一、串的定义

串( string)是由零个或多个字符组成的有限序列,又名叫字符串。

  • 空串:零个字符的串称为空串。
  • 空格串:是只包含空格的串。注意它与空串的区别,空格串是有内容有长度的,而且可以不止一个空格。
  • 子串与主串:串中任意个数的连续字符组成的子序列称为该串的子串,相应地,包含子串的串称为主串。
  • 子串在主串中的位置就是子串的第一个字符在主串中的序号。

串的逻辑结构和线性表极为相似,区别仅在于串的数据对象限定为字符集。在基本操作上,串和线性表有很大差别。线性表的基本操作主要以单个元素作为操作对象,如查找、插入或删除某个元素等;而串的基本操作通常以子串作为操作对象,如查找、插入或删除一个子串等。

🚀二、串的存储结构

🛴(一)串的顺序存储结构

1、定长顺序存储表示

类似于线性表的顺序存储结构,用一组地址连续的存储单元存储串值的字符序列。在串的定长顺序存储结构中,为每个串变量分配一个固定长度的存储区,即定长数组。

#define MAXLEN 255	//预定义最大串长为255
typedef struct{
	char ch[MAXLEN];	//每个分量存储一个字符
	int length;	//串的实际长度
}SString;

串的实际长度只能小于等于MAXLEN,超过预定义长度的串值会被舍去,称为截断。串长有两种表示方法: 一是如上述定义描述的那样,用一个额外的变量len来存放串的长度;二是在串值后面加一一个不计入串长的结束标记字符“\0”,此时的串长为隐含值。需要遍历一下才能知道

在一些串的操作(如插入、联接等)中,若串值序列的长度超过上界MAXLEN,约定用“截断”法处理,要克服这种弊端,只能不限定串长的最大长度,即采用动态分配的方式。

2、堆分配存储表示

堆分配存储表示仍然以一组地址连续的存储单元存放串值的字符序列,但它们的存储空间是在程序执行过程中动态分配得到的。

typedef struct{
	char *ch;	//按串长分配存储区,ch指向串的基地址
	int length;	//串的长度
}HString;

在C语言中,存在一一个称之为“堆”的自由存储区,并用malloc()和free()函数来完成动则返回一个指向起始地址的指针,作为串的基地址,这个串由ch指针来指示;若分配失败,则返回NULL。已分配的空间可用free()释放掉。
上述两种存储表示通常为高级程序设计语言所采用。块链存储表示仅做简单介绍。

🛴(二)串的链式存储结构

3、块链存储表示

类似于线性表的链式存储结构,也可采用链表方式存储串值。由于串的特殊性(每个元素只有一个字符),在具体实现时,每个结点既可以存放一个字符, 也可以存放多个字符。每个结点称为块,整个链表称为块链结构。图(a)是结点大小为4 (即每个结点存放4个字符)的链表,最后一个结点占不满时通常用“#”补上;图(b)是结点大小为1的链表。

【数据结构篇C++实现】- 特殊的线性表 - 串,数据结构与算法,数据结构,c++

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

一个结点存多少个字符才合适就变得很重要,这会直接影响着串处理的效率,需要根据实际情况做出选择。
但串的链式存储结构除了在连接串与串操作时有一定方便之外,总的来说不如顺序存储灵活,性能也不如顺序存储结构好。

🚀三、串的基本操作

  • StrAssign(&T, chars): 赋值操作。把串T赋值为 chars

  • Strcopy(&T, S): 复制操作。由串S复制得到串T。

  • StrEmpty(S): 判空操作。若S为空串,则返回TRUE,否则返回 FALSE

  • StrCompare(S,T): 比较操作。若S>T,则返回值>0;若S=T,则返回值=0;若S<T,则返回值<0。

    事实上,串的比较是通过组成串的字符之间的编码来进行的,而字符的编码指的是字符在对应字符集中的序号。

  • StrEngth(S): 求串长。返回串S的元素个数

  • Substring(&Sub,S,pos,1en):求子串。用Sub返回串S的第pos个字符起长度为len的子串。

  • Concat(&T,S1,S2): 串联接。用T返回由S1和S2联接而成的新串。

  • Index(S,T): 定位操作。若主串S中存在与串T值相同的子串,则返回它在主串S中第一次出现的位置;否则函数值为0

  • Clearstring(&S): 清空操作。将S清为空串

  • Destroystring(&S): 销毁串。将串S销毁

不同的高级语言对串的基本操作集可以有不同的定义方法。在上述定义的操作中,串赋值StrAssign、串比较 StrCompare、求串长 Strength、串联接 Concat及求子串 Substring五种操作构成串类型的最小操作子集,即这些操作不可能利用其他串操作来实现;反之,其他串操作(除串清除 Clearstring和串销毁 Destroystring外)均可在该最小操作子集上实现。

例如,可利用判等、求串长和求子串等操作实现定位函数 Index(S,T)。

int Index(Sring S, String T){
	int i = 1, n = StrLength(S), m = StrLength(T);
	String sub;
	while(i <= n-m+1){
		SubString(sub, S, i, m);	//取主串第i个位置,长度为m的串给sub
		if(StrCompare(sub, T) != 0){
			++i;
		}else{
			return i;	//返回子串在主串中的位置
		}
	}
	return 0;	//S中不存在与T相等的子串
}

🚀四、串的模式匹配(重点)

🛴(一)简单的模式匹配算法

子串的定位操作通常称为串的模式匹配,它求的是子串(常称模式串)在主串中的位置。这里采用定长顺序存储结构,给出一种不依赖于其他串操作的暴力匹配算法。

int Index(SString S, SString T){
	int i = 1, j = 1;
	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;
	}
}

下图展示了模式串T = ′ a b c a c ′ 和主串S的匹配过程

【数据结构篇C++实现】- 特殊的线性表 - 串,数据结构与算法,数据结构,c++

简单的模式匹配算法的最坏时间复杂度为O(nm),其中n和m分别为主串和模式串的长度。

🛴(二)KMP算法

在上面的简单匹配中,每趟匹配失败都是模式后移一位再从头开始比较。而某趟已匹配相等的字符序列是模式的某个前缀,这种频繁的重复比较相当于模式串在不断地进行自我比较,这就是其低效率的根源。对于要匹配的子串T来说,“abcac”首字母“a”与后面的串“bc”中任意一个字符都不相等。那么既然要全部和主串相等,意味着子串T的首字符“a”不可能与S串的第2、3位字符相等,所以对这两位的判断是多余的

因此,可以从分析模式本身的结构着手,如果已匹配相等的前缀序列中有某个后缀正好是模式的前缀,那么就可以将模式向后滑动到与这些相等字符对齐的位置,主串i指针无须回溯,并继续从该位置开始进行比较。而模式向后滑动位数的计算仅与模式本身的结构有关,与主串无关。

KMP算法的特点就是:仅仅后移模式串,比较指针不回溯。很是牛掰。

1、字符串的前缀、后缀和最大公共前后缀长度

要了解子串的结构,首先要弄清楚几个概念:前缀后缀部分匹配值。前缀指除最后一个字符以外,字符串的所有头部子串;后缀指除第一个字符外,字符串的所有尾部子串;部分匹配值则为字符串的前缀和后缀的最大公共前后缀长度。下面以′ a b a b a ′ ’ ababa’′ababa′为例进行说明

  • ′ a ′ 的前缀和后缀都为空集,最大公共前后缀长度为0。
  • ′ a b ′ 的前缀为{ a } ,后缀为{ b } , ${ { a } } ∩ { { b } }= N U L L $,最大公共前后缀长度长度为0。
  • ′ a b a ′ 的前缀为{ a , ab } , 后缀为{ a , ba } , ${ { a,ab } } ∩ { { a,ba } }= {{a}} $, 最大公共前后缀长度为1
  • ′ a b a b ′ ,前缀∩后缀,{ a , a b , a b a } ∩ { b , a b , b a b } = {ab},最大公共前后缀长度为2。
  • ′ a b a b a ′ ,前缀∩后缀, { a , a b , a b a , a b a b } ∩ { a , b a , a b a , b a b a } = {a,aba}, 公共元素有两个,最大公共前后缀长度长度为3。

故字符串′ a b a b a ′ 的最大公共前后缀长度为00123。这个值有什么作用呢?回到最初的问题,主串为 ′ a b a c a b c a c b a b ′,子串为 ′ a b c a c ′ 。利用上述方法容易写出子串′ a b c a c ′ 的最大公共前后缀长度为00010,将最大公共前后缀长度值写成数组形式,就得到了最大公共前后缀长度(Partial match,PM)的表。

【数据结构篇C++实现】- 特殊的线性表 - 串,数据结构与算法,数据结构,c++

下面用PM表来进行字符串匹配:

【数据结构篇C++实现】- 特殊的线性表 - 串,数据结构与算法,数据结构,c++

  • 第一趟匹配过程:

    发现c 与a 不匹配,前面的2个字符′ a b ′是匹配的,查表可知,最后一个匹配字符b对应的部分匹配值为0,因此按照下面的公式算出子串需要向后移动的位数:
    移动位数 = 已匹配的字符数 − 失配字符上一位字符对应最大公共前后缀长度 移动位数 = 已匹配的字符数 − 失配字符上一位字符对 应 最 大 公 共 前 后 缀 长 度 移动位数=已匹配的字符数失配字符上一位字符对应最大公共前后缀长度

    因为2 − 0 = 2,所以将子串向后移动2位,如下进行第二趟匹配:

    【数据结构篇C++实现】- 特殊的线性表 - 串,数据结构与算法,数据结构,c++

  • 第二趟匹配过程:

    发现c 与b 不匹配,前面4个字符′ a b c a ′是匹配的,最后一个匹配字符a对应的部分匹配值为1,4 − 1 = 3 ,将子串向后移动3位,如下进行第三趟匹配:

    【数据结构篇C++实现】- 特殊的线性表 - 串,数据结构与算法,数据结构,c++

  • 第三趟匹配过程:

    子串全部比较完成,匹配成功。整个匹配过程中,主串始终没有回退,故KMP算法可以在O ( n + m ) 的时间数量级上完成串的模式匹配操作,大大提高了匹配效率。

2、求next数组

使用部分匹配值时,每当匹配失败,就去找它前一个元素的部分匹配值,这样使用起来有些不方便,所以将PM表右移一位,这样哪个元素匹配失败,直接看它自己的部分匹配值即可。将上例中字符串′ a b a c ′的PM表右移一位,就得到了next数组:

【数据结构篇C++实现】- 特殊的线性表 - 串,数据结构与算法,数据结构,c++
移动位数 = 失配字符所在位置 − 失配字符对应的 n e x t 值。(涉及到数组,记得位置是从 0 开始的) 移动位数 = 失配字符所在位置 - 失配字符对应的next值。(涉及到数组,记得位置是从0开始的) 移动位数=失配字符所在位置失配字符对应的next值。(涉及到数组,记得位置是从0开始的)
通过代码递推计算next 数组:

对于next的数组的计算,可以采用递推来算。根据上面的分析,我们知道如果模式串当前位置j之前有k个相同的前缀后缀,那么可以表示为next[j] = k,所以如果当模式串的p[j]跟文本串失配后,我们可以用next[j]处的字符继续和文本串匹配,相当于模式串向右移动了j - next[j]位。那么问题就来了,如何求出next[j+1]的值呢,我们还是来看例子吧:

模式串:    A  B  C  D  A  B  C  E
next值:   -1  0  0  0  0  1  2  ?  
索引:             k           j

如上所示,模式串为"ABCDABCE",且j=6, k = 2,我们有next[j] = k,这表示j位置上的字符C之前的最大前后缀长度为2,即AB。现在我们要求next[j+1]的值,

  • 因为 p [ k ] = = p [ j ] p[k] == p[j] p[k]==p[j],所以 n e x t [ j + 1 ] = n e x t [ j ] + 1 = k + 1 = 3 next[j+1] = next[j] + 1 = k + 1 = 3 next[j+1]=next[j]+1=k+1=3。即字母E之前的最大前后缀长度为3,即ABC。

  • 那么我们再来看 p [ k ] ! = p [ j ] p[k] != p[j] p[k]!=p[j]的情况下怎么处理,还是来看例子:

模式串:    A  B  C  D  A  B  D  E
next值:   -1  0  0  0  0  1  2  ?  
索引:             k           j

这个例子把上面例子中的第二个’C’换成了’D’,所以字符’E’前面的相同后缀就不再是3了,所以我们希望在k前面找出个k’位置,使得p[k’]为D,这样 n e x t [ j + 1 ] = k ′ + 1 next[j+1] = k' +1 next[j+1]=k+1,但是这个例子中不存在这样的’D’,所以next[j+1] = 0。

  • 我们再看一个能在前缀中找到’D’的例子:
模式串:    D  A  B  C  D  A  B  D  E
next值:   -1  0  0  0  0  1  2  3  ?  
索引:                k           j

这个例子上面例子的最前面加上了个’D’,此时j = 7, k = 3了,我们有next[j] = k,这表示j位置上的字符D之前的最大前后缀长度为3,即DAB。要求next[j+1]的值,我们发现此时 p [ k ] ! = p [ j ] p[k] != p[j] p[k]!=p[j],然后我们寻找k’或者直接让 k = n e x t [ k ] = 0 k = next[k] = 0 k=next[k]=0,此时p[0]是D,那么 n e x t [ j + 1 ] = k + 1 = 1 next[j+1] = k + 1 = 1 next[j+1]=k+1=1了,这说明字母E之前的最大前后缀长度为1,即D。综上所述,我们可以写出next的生成函数如下:

vector<int> getNext(string p) {
    int n = p.size(), k = -1, j = 0;
    vector<int> next(n, -1);
    while (j < n - 1) {
        if (k == -1 || p[j] == p[k]) {  //P[J]表示后缀的单个字符,P[K]表示前缀的单个字符,匹配成功
            ++k; ++j;
            next[j] = k;    //第一步就是next[1] = 0,每匹配成功一个就加一
        } else {
            k = next[k];   //如果匹配失败
        }
    }
    return next;
}
3、next数组的优化

上面这种计算next数组的方式可以进一步的优化,可以优化的原因是因为上面的方法存在一个小小的问题,如果用这种方法求模式串ABAB,会得到next数组为[-1 0 0 1],我们用这个模式串去匹配ABACABABC:

ABACABABC
ABAB

我们会发现C和B失配,那么根据上面的规则,我们要向右移动j - next[j] = 3 - 1 = 2位,于是有:

ABACABABC
  ABAB

右移2位后,b又跟c失配。事实上,因为在上一步的匹配中,已经得知p[3] = b,与s[3] = c失配,而右移两位之后,让p[ next[3] ] = p[1] = b 再跟s[3]匹配时,必然失配。问题出在哪呢?原因是当p[j] != s[i]时,下一步要用 p [ n e x t [ j ] ] 和 s [ i ] p[next[j]]和s[i] p[next[j]]s[i]去匹配,而如果 p [ j ] = = p [ n e x t [ j ] ] p[j] == p[next[j]] p[j]==p[next[j]]了,再用 p [ n e x t [ j ] ] 和 s [ i ] p[next[j]]和s[i] p[next[j]]s[i]去匹配必然会失配。所以我们要避免出现 p [ j ] = = p [ n e x t [ j ] ] p[j] == p[next[j]] p[j]==p[next[j]]的情况,一旦出现了这种情况,我们可以再次递归, n e x t [ j ] = n e x t [ n e x t [ j ] ] next[j] = next[next[j]] next[j]=next[next[j]],修改后的代码如下:

vector<int> getNext(string p) {
    int n = p.size(), k = -1, j = 0;
    vector<int> next(n, -1);
    while (j < n - 1) {
        if (k == -1 || p[j] == p[k]) {  //P[J]表示后缀的单个字符,P[K]表示前缀的单个字符
            ++k; ++j;
            next[j] = (p[j] != p[k]) ? k : next[k];
        } else {
            k = next[k];
        }
    }
    return next;
}
4、KMP算法实现

当想要在C++中实现KMP算法进行字符串匹配时,可以按照以下步骤进行:文章来源地址https://www.toymoban.com/news/detail-619320.html

  1. 构建next数组:计算模式串的前缀表,用于在不匹配时快速移动模式串。
  2. 使用KMP算法进行字符串匹配。
#include <iostream>
#include <vector>
#include <string>

// 构建next数组
vector<int> getNext(string p) {
    int n = p.size(), k = -1, j = 0;
    vector<int> next(n, -1);
    while (j < n - 1) {
        if (k == -1 || p[j] == p[k]) {  //P[J]表示后缀的单个字符,P[K]表示前缀的单个字符
            ++k; ++j;
            next[j] = (p[j] != p[k]) ? k : next[k];
        } else {
            k = next[k];
        }
    }
    return next;
}

// 使用KMP算法进行字符串匹配
int kmpSearch(const std::string& text, const std::string& pattern) {
    int n = text.size();
    int m = pattern.size();
    std::vector<int> next = getNext(pattern);
    int i = 0;
    int j = 0;

    while (i < n) {
        if (j == -1 || text[i] == pattern[j]) {
            ++i;
            ++j;
            if (j == m) {
                return i - j;  // 匹配成功,返回匹配的起始位置
            }
        } else {
            j = next[j];
        }
    }

    return -1;  // 未找到匹配的子串
}

int main() {
    std::string text = "ABABDABACDABABCABAB";
    std::string pattern = "ABABCABAB";

    int index = kmpSearch(text, pattern);

    if (index != -1) {
        std::cout << "在位置 " << index << " 处找到匹配的子串" << std::endl;
    } else {
        std::cout << "未找到匹配的子串" << std::endl;
    }

    return 0;
}

行文至此,落笔为终。文末搁笔,思绪驳杂。只道谢不道别。早晚复相逢,且祝诸君平安喜乐,万事顺意。

到了这里,关于【数据结构篇C++实现】- 特殊的线性表 - 串的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【数据结构和算法】--队列的特殊结构-循环队列

    循环队列是队列的一种特殊结构,它的 长度是固定的 k ,同样是 先进先出 ,理论结构是 首尾相连的环形循环结构 。其理论结构大致如下: 具体结构描述可以参考 LeetCode : 622. 设计循环队列的题目要求,大致如下: 设计你的循环队列实现。 循环队列是一种 线性数据结构 ,

    2024年02月04日
    浏览(45)
  • 数据结构中: 一元多项式的运算(相加,相减,相乘)------用C语言 / C++来实现。 数据结构线性表的操作和应用(顺序存储)

    线性表的操作和应用(顺序存储)。用顺序存储实现一元多项式,并进行加、减、乘运算。 (1)一元多项式结构体创建  (2)初始化 (3)一元多项式赋值             (4)打印一元多项式 (5)加法运算                        (6)减法运算 (7)乘法运算    全部代

    2024年02月01日
    浏览(57)
  • 算法 数据结构分类 数据结构类型介绍 数据结构线性非线性结构 算法合集 (一)

     数据结构分为:                            a.线性结构                            b.非线性结构  a.线性结构:                       数据与结构存在一对一的线性关系; a . 线性结构 存储 分为:                                   顺序存储

    2024年02月10日
    浏览(49)
  • 【数据结构与算法C++实现】3、排序算法

    原视频为左程云的B站教学 外层循环 :n个数需要冒n-1个泡上去,剩下的一个必然是最小的。所以外层循环执行n-1轮 内层循环 :比大小,第1个泡需要比n-1次,第2个泡,比较n-2次… 选择: 每次从待排序序列中选择 最小的一个 放在已排序序列的后一个位置 原理类似于对扑克牌

    2024年02月11日
    浏览(56)
  • 扎实打牢数据结构算法根基,从此不怕算法面试系列之004 week01 02-04 使用泛型实现线性查找法

    在数组中逐个查找元素,即遍历。 在 扎实打牢数据结构算法根基,从此不怕算法面试系列之003 week01 02-03 代码实现线性查找法中,我们实现了如下代码: 之前实现的局限: 只支持int型。 需求: 支持所有的Java基本数据类型以及自定义的类类型。 很简单,很多语言都有这个处

    2023年04月16日
    浏览(45)
  • 【Python数据结构与算法】线性结构小结

    🌈个人主页: Aileen_0v0 🔥系列专栏:PYTHON学习系列专栏 💫\\\"没有罗马,那就自己创造罗马~\\\"   目录 线性数据结构Linear DS 1.栈Stack 栈的两种实现 1.左为栈顶,时间复杂度为O(n) 2.右为栈顶,时间复杂度O(1)   2.队列Queue 3.双端队列Deque 4.列表List 5.链表 a.无序链表的实现 b.有序链表的实

    2024年02月04日
    浏览(40)
  • 数据结构与算法 - 线性表

    编程要求 本关任务是实现 step1/Seqlist.cpp 中的SL_InsAt、SL_DelAt和SL_DelValue三个操作函数,以实现线性表中数据的插入、删除与查找等功能。具体要求如下: SL_InsAT: 在顺序表的位置i插入结点x,即插入d[i]之前,i的有效范围[0,slist-len]; SL_DelAt:删除顺序表slist的第i号结点, i的有

    2024年02月01日
    浏览(82)
  • 数据结构-线性表及其应用(C++)

    线性表是最基本、最简单、也是最常用的一种数据结构。它是由n个具有相同特性的数据元素的有限序列。其数据元素之间的关系是一对一的关系,即除了第一个和最后一个数据元素之外,其它数据元素都是首尾相接的。其主要的物理存储方式分为顺序表(相邻数据元素在底层

    2024年02月02日
    浏览(37)
  • Rust 数据结构与算法:2线性数据结构 之 栈

    1、线性数据结构 数组、栈、队列、双端队列、链表这类数据结构都是保存数据的容器,数据项之间的顺序由添加或删除时的顺序决定,数据项一旦被添加,其相对于前后元素就会一直保持位置不变,诸如此类的数据结构被称为线性数据结构。线性数据结构有两端,称为“左

    2024年02月21日
    浏览(46)
  • [算法与数据结构]:LRU Cache 的原理与C++实现

    ​ LRU全称是Least Recently Used,即 最近最久未使用,是一种简单的缓存策略。顾名思义,LRU 算法会选出最近最少使用的数据进行淘汰。 ​ 那么什么是缓存(Cache)呢?缓存是一种提高数据读取性能的技术,可以有效解决存储器性能和容量的矛盾,是一种空间换时间的设计思想,比

    2024年01月20日
    浏览(46)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包