2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】

本文涉及的产品
视觉智能开放平台,视频资源包5000点
视觉智能开放平台,图像资源包5000点
视觉智能开放平台,分割抠图1万点
简介: 数据结构与算法系列学习之串的定义和基本操作、串的储存结构、基本操作的实现、朴素模式匹配算法、KMP算法等代码举例及图解说明;【含常见的报错问题及其对应的解决方法】你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!

欢迎各位彦祖与热巴畅游本人专栏与博客

你的三连是我最大的动力

以下图片仅代表专栏特色 [点击箭头指向的专栏名即可闪现]

专栏跑道一

➡️网络空间安全——全栈前沿技术持续深入学习

image.gif

专栏跑道二

➡️ 24 Network Security -LJS

image.gif

image.gif

image.gif

专栏跑道三


➡️ MYSQL REDIS Advance operation

image.gif

专栏跑道四

➡️HCIP;H3C-SE;CCIP——LJS[华为、华三、思科高级网络]

image.gif

专栏跑道五

➡️RHCE-LJS[Linux高端骚操作实战篇]

image.png

专栏跑道六

➡️数据结构与算法[考研+实际工作应用+C程序设计]

image.gif

专栏跑道七

➡️RHCSA-LJS[Linux初级及进阶骚技能]

image.gif

image.gif

上节回顾



数据结构与算法系列学习之串

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’
  • image.gif
  • SubString(&Sub, S, pos, len): 求子串,用Sub返回串S的第pos个字符起长度为len的子串;
SubString(&T, S, 4, 6)
T = ‘one 14’

image.gif

  • 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即可

image.gif 编辑

2.串的储存结构

2.1顺序存储:

image.gif

代码实现:

#define MAXLEN 255   //预定义最大串长为255
typedef struct{
    char ch[MAXLEN];   //静态数组实现(定长顺序存储)
                       //每个分量存储一个字符
                       //每个char字符占1B
    int length;        //串的实际长度
}SString;

image.gif

  • 方案一:一个数组来储存字符,一个int变量length储存实际长度
  • 方案二:数组的ch[0]来充当length,优点:字符的位序和数组下标相同
  • 方案三:没有Length变量,以字符’\0’表示结尾(对应ASCII码的0),缺点:获取字符串长度需要遍历,时间复杂度高
  • 方案四:数组的ch[0]废弃不用,从看开始储存字符,外加一个int变量length储存实际长度

2.2链式存储

image.gif

代码实现:

typedef struct StringNode{
    char ch;           //每个结点存1个字符
    struct StringNode *next;
}StringNode, * String;
问题:存储密度低,每个字符1B,每个指针4B;
解决方案:每一个链表的结点存储多个字符——每个结点称为块——块链结构
typedef struct StringNode{
    char ch[4];           //每个结点存多个个字符
    struct StringNode *next;
}StringNode, * String;
image.gif
  • 推荐使用第二种方式,存储密度较高,ch数组未必一定是4个字符,也可以比4多

3.基本操作的实现(使用第四种方案):

image.gif 编辑

image.gif 编辑

image.gif 编辑

基本操作代码实现[方案4]:

#define MAXLEN 255
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相等的子串
}
image.gif

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

image.gif 编辑

设主串长度为 n,模式串长度为 m,则最坏时间复杂度 = O(n*m),最好时间复杂度 = O(n)

image.gif

朴素模式匹配算法代码实现:
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;
}
image.gif

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算法精髓:利用好已经匹配过的模式串的信息

image.gif 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; //匹配成功
}
image.gif

5.4KMP算法之求next数组

image.gif 编辑

5.4.1求next数组代码实现 [含图解]

image.gif 编辑

如上图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; //匹配成功
}

image.gif

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];
    }
}
image.gif


相关文章
|
3天前
|
弹性计算 双11 开发者
阿里云ECS“99套餐”再升级!双11一站式满足全年算力需求
11月1日,阿里云弹性计算ECS双11活动全面开启,在延续火爆的云服务器“99套餐”外,CPU、GPU及容器等算力产品均迎来了全年最低价。同时,阿里云全新推出简捷版控制台ECS Lite及专属宝塔面板,大幅降低企业和开发者使用ECS云服务器门槛。
|
21天前
|
存储 弹性计算 人工智能
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
阿里云弹性计算产品线、存储产品线产品负责人Alex Chen(陈起鲲)及团队内多位专家,和中国电子技术标准化研究院云计算标准负责人陈行、北京望石智慧科技有限公司首席架构师王晓满两位嘉宾,一同带来了题为《通用计算新品发布与行业实践》的专场Session。本次专场内容包括阿里云弹性计算全新发布的产品家族、阿里云第 9 代 ECS 企业级实例、CIPU 2.0技术解读、E-HPC+超算融合、倚天云原生算力解析等内容,并发布了国内首个云超算国家标准。
阿里云弹性计算_通用计算专场精华概览 | 2024云栖大会回顾
|
3天前
|
人工智能 弹性计算 文字识别
基于阿里云文档智能和RAG快速构建企业"第二大脑"
在数字化转型的背景下,企业面临海量文档管理的挑战。传统的文档管理方式效率低下,难以满足业务需求。阿里云推出的文档智能(Document Mind)与检索增强生成(RAG)技术,通过自动化解析和智能检索,极大地提升了文档管理的效率和信息利用的价值。本文介绍了如何利用阿里云的解决方案,快速构建企业专属的“第二大脑”,助力企业在竞争中占据优势。
|
1天前
|
人工智能 自然语言处理 安全
创新不设限,灵码赋新能:通义灵码新功能深度评测
自从2023年通义灵码发布以来,这款基于阿里云通义大模型的AI编码助手迅速成为开发者心中的“明星产品”。它不仅为个人开发者提供强大支持,还帮助企业团队提升研发效率,推动软件开发行业的创新发展。本文将深入探讨通义灵码最新版本的三大新功能:@workspace、@terminal 和 #team docs,分享这些功能如何在实际工作中提高效率的具体案例。
|
7天前
|
负载均衡 算法 网络安全
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
阿里云平台WoSign品牌SSL证书是由阿里云合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品,用户在阿里云平台https://www.aliyun.com/product/cas 可直接下单购买WoSign SSL证书,快捷部署到阿里云产品中。
1850 6
阿里云WoSign SSL证书申请指南_沃通SSL技术文档
|
10天前
|
Web App开发 算法 安全
什么是阿里云WoSign SSL证书?_沃通SSL技术文档
WoSign品牌SSL证书由阿里云平台SSL证书合作伙伴沃通CA提供,上线阿里云平台以来,成为阿里云平台热销的国产品牌证书产品。
1789 2
|
19天前
|
编解码 Java 程序员
写代码还有专业的编程显示器?
写代码已经十个年头了, 一直都是习惯直接用一台Mac电脑写代码 偶尔接一个显示器, 但是可能因为公司配的显示器不怎么样, 还要接转接头 搞得桌面杂乱无章,分辨率也低,感觉屏幕还是Mac自带的看着舒服
|
26天前
|
存储 人工智能 缓存
AI助理直击要害,从繁复中提炼精华——使用CDN加速访问OSS存储的图片
本案例介绍如何利用AI助理快速实现OSS存储的图片接入CDN,以加速图片访问。通过AI助理提炼关键操作步骤,避免在复杂文档中寻找解决方案。主要步骤包括开通CDN、添加加速域名、配置CNAME等。实测显示,接入CDN后图片加载时间显著缩短,验证了加速效果。此方法大幅提高了操作效率,降低了学习成本。
5386 15
|
13天前
|
人工智能 关系型数据库 Serverless
1024,致开发者们——希望和你一起用技术人独有的方式,庆祝你的主场
阿里云开发者社区推出“1024·云上见”程序员节专题活动,包括云上实操、开发者测评和征文三个分会场,提供14个实操活动、3个解决方案、3 个产品方案的测评及征文比赛,旨在帮助开发者提升技能、分享经验,共筑技术梦想。
1139 152
|
21天前
|
存储 缓存 关系型数据库
MySQL事务日志-Redo Log工作原理分析
事务的隔离性和原子性分别通过锁和事务日志实现,而持久性则依赖于事务日志中的`Redo Log`。在MySQL中,`Redo Log`确保已提交事务的数据能持久保存,即使系统崩溃也能通过重做日志恢复数据。其工作原理是记录数据在内存中的更改,待事务提交时写入磁盘。此外,`Redo Log`采用简单的物理日志格式和高效的顺序IO,确保快速提交。通过不同的落盘策略,可在性能和安全性之间做出权衡。
1585 14

热门文章

最新文章

  • 1
    2024重生之回溯数据结构与算法系列学习之串(12)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    12
  • 2
    2024重生之回溯数据结构与算法系列学习(11)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丟脸好嘛?】
    6
  • 3
    2024重生之回溯数据结构与算法系列学习之栈和队列精题汇总(10)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    9
  • 4
    2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    10
  • 5
    2024重生之回溯数据结构与算法系列学习(8)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    10
  • 6
    2024重生之回溯数据结构与算法系列学习(7)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    7
  • 7
    2024重生之回溯数据结构与算法系列学习之王道第2.3章节之线性表精题汇总二(5)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    7
  • 8
    23
    6
  • 9
    2024重生之回溯数据结构与算法系列学习之单双链表精题(4)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    9
  • 10
    2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
    6