王道数据结构课代表

2024-07-16 15:08:28| 来源: 网络整理| 查看: 265

本篇博客是考研期间学习王道课程传送门的笔记，以及一整年里对数据结构知识点的理解的总结。希望对新一届的计算机考研人提供帮助！！！关于对串章节知识点总结的十分全面，涵括了《王道数据结构》课程里的全部要点（本人来来回回过了三遍视频），其中还陆陆续续补充了许多内容，所以读者可以相信本篇博客对于考研数据结构“串”章节知识点的正确性与全面性；但如果还有自主命题的学校，还需额外读者自行再观看对应学校的自主命题材料。数据结构与算法笔记导航🚥🚥🚥

🥬 第一章绪论(无)🥕 第二章线性表🥪 第三章栈和队列🍊 第四章串-KMP(看毛片算法) ⇦当前位置🪂🍒 第五章树和二叉树🍀 第六章图🍚 第七章查找(B树、散列表)🧄 第八章排序 (内部排序：八大排序动图演示与实现 + 外部排序)🍔 数据结构与算法复试精简笔记 (未完成)🎨 408 全套初复试笔记汇总传送门 🏃‍🏃‍🏃‍

如果本篇文章对大家起到帮助的话，跪求各位帅哥美女们，求赞👍 、求收藏 👏、求关注！👀 你必考上研究生！我说的，耶稣来了也拦不住！😀😀😀

在这里插入图片描述

精准控时：如果不实际操作代码，只是粗略过一下知识点，需花费 30 分钟左右过一遍这个30分钟是我在后期冲刺复习多次尝试的时间，可以让我很好的在后期时间紧张的阶段下，合理分配复习时间；但是刚开始看这份博客的读者也许会因为知识点陌生、笔记结构不太了解，花费许多时间，这都是正常的。重点！！！学习一定要多总结多复习！重复、重复、再重复！！！

食用说明书：第一遍学习王道课程时，我的笔记只有标题和截图，后来复习发现看只看图片，并不能很快的了解截图中要重点表达的知识点。所以再第二遍复习中，我给每一张截图中标记了重点，以及每张图片上方总结了该图片对应的知识点以及自己的思考。最后第三遍，查漏补缺。所以，我把目录放在博客的前面，就是希望读者可以结合目录结构去更好的学习知识点，之后冲刺复习阶段脑海里可以浮现出该知识结构，做到对每一个知识点熟稔于心！请读者放心！目录展示的知识点结构是十分合理的，可以放心使用该结构去记忆学习！注意(⊙o⊙)！，每张图片上面的文字，都是该图对应的知识点总结，方便读者更快理解图片内容。

第4章串

文章目录第4章串4.1 串的定义和实现4.1.1 串的定义4.1.2 串的存储结构1、串的顺序存储2、串的链式存储3、串的基本操作4、4.1.2小结 4.2 串的模式匹配4.2.1 简单的模式匹配算法1、具体代码2、分析算法性能3、4.2.1小结 4.2.2 改进的模式匹配算法——KMP算法1、算法思想2、初步代码3、常考：求模式串的next数组例子方法总结练习 4、KMP算法性能分析5、4.2.2小结 4.2.3 KMP的进一步优化 —— nextval数组算法总结

4.1 串的定义和实现

在这里插入图片描述

4.1.1 串的定义子串：串中任意的连续的字符（空串也可以是子串）主串位置：位序

在这里插入图片描述

串也是线性表（数据类型有限制）

在这里插入图片描述

4.1.2 串的存储结构 1、串的顺序存储

在这里插入图片描述

2、串的链式存储链式存储缺点：存储密度低你会发现为了存储char类型的数据，反而还搭配了一个占据空间更大的指针，无疑是浪费！改进：提高结点里数据域所能表示的数据量

在这里插入图片描述

3、串的基本操作

在这里插入图片描述

4、4.1.2小结

在这里插入图片描述

4.2 串的模式匹配 4.2.1 简单的模式匹配算法模式匹配：在主串中找到与模式串相同的子串模式串与子串不是一个概念，未必在主串中存在下图中的红字在描述上不是那么准确（有误会），不过大致意思要明白

在这里插入图片描述

朴素模式匹配算法：暴力匹配

在这里插入图片描述

1、具体代码

在这里插入图片描述

2、分析算法性能算法性能分析在图中已经介绍的很清楚了，这里不再解释了

在这里插入图片描述

3、4.2.1小结

在这里插入图片描述

4.2.2 改进的模式匹配算法——KMP算法 1、算法思想主要思想：当模式匹配失败时，该回溯到哪里呢？看下图中“关键”指出的next[]数组

在这里插入图片描述

2、初步代码

在这里插入图片描述

3、常考：求模式串的next数组本节探讨：手算方式求模式串的next数组例子

在这里插入图片描述

方法总结后缀指的是主串，前缀指的是模式串前缀后缀都是指一个串里截取部分串（连续）出来，只是前缀必须有第一个字符，不能有最后一个字符后缀同理其实这种方法总结太麻烦了，不如直接自己看，next[i]选择能匹配最多字符的位置例如next[7]可以等于5，也可以等于3，但是优先选择3注意注意注意！后缀的尾对前缀的头，后缀在上前缀在下

在这里插入图片描述

练习 next[1]一定为0，next[2]一定为1模式串第一个元素不匹配，next[1]为0就是说：主串直接匹配下一个模式串第二个元素不匹配，只能从一个重新匹配了模式串第三个元素不匹配，这个时候才考虑从第一个还是第二个开始匹配所以，做题直接考虑第三个

在这里插入图片描述

4、KMP算法性能分析 O（m）：模式串的长度mO（n）：主串的长度n

在这里插入图片描述

5、4.2.2小结 KMP的关键思想：主串的扫描指针i不回溯（i一直+1），模式串的扫描指针j回溯KMP还存在缺陷

在这里插入图片描述

4.2.3 KMP的进一步优化 —— nextval数组当主串的第4个字符和模式串的第4个字符发生不匹配时next[4]=1，可是模式串1位置和4位置一样都是g，还是和l不匹配，这样就多余一次

在这里插入图片描述

算法总结

在这里插入图片描述

上面图片中的案例解析：

步骤原因操作1nextva[1] = 02next[2]==1 看S[1] && a!=bnextva[2] = next[2] =13next[3]1 看S[1] && aanextva[3] = nextva[1]4next[4]2 看S[2] && bbnextva[4] = nextva[2]5next[5]3 看S[3] && aanextva[5] = nextva[3]6next[6]=4 看S[4] && b!=anextva[6] = next[6] = 4

考验人加油！！！

【本文地址】

公司简介

联系我们

今日新闻

点击排行

实验室常用的仪器、试剂和: 说到实验室常用到的东西，主要就分为仪器、试剂和耗

不用再找了，全球10大实验: 01、赛默飞世尔科技（热电）Thermo Fisher Scientif

三代水柜的量产巅峰T-72坦: 作者：寞寒最近，西边闹腾挺大，本来小寞以为忙完这

通风柜跟实验室通风系统有: 说到通风柜跟实验室通风，不少人都纠结二者到底是不

集消毒杀菌、烘干收纳为一: 厨房是家里细菌较多的地方，潮湿的环境、没有完全密

实验室设备之全钢实验台如: 全钢实验台是实验室家具中较为重要的家具之一，很多

图片新闻

实验室药品柜的特性有哪些: 实验室药品柜是实验室家具的重要组成部分之一，主要

小学科学实验中有哪些教学: 计算机计算器一般打孔器打气筒仪器车显微镜

实验室各种仪器原理动图讲: 1.紫外分光光谱UV分析原理：吸收紫外光能量，引起分

高中化学常见仪器及实验装: 1、可加热仪器：2、计量仪器：（1）仪器A的名称：量

微生物操作主要设备和器具: 今天盘点一下微生物操作主要设备和器具，别嫌我啰嗦

浅谈通风柜使用基本常识: 　众所周知，通风柜功能中最主要的就是排气功能。在

王道数据结构课代表

王道数据结构课代表

今日新闻

点击排行

推荐新闻

图片新闻

专题文章