考研系列-数据结构第四章：字符串

2024-06-18 03:20
文章标签 考研 数据结构 第四章 字符串 系列

本文主要是介绍考研系列-数据结构第四章：字符串，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

目录

写在前面：考纲内容

一、串的基本概念

1.串的定义

2.串和线性表对比

(1)存储方式与结构

(2)数据操作效率

(3)内存管理

(4)应用场景

3.串的基本操作

4.拓展：字符集编码

5.总结

二、串的存储结构

1.顺序存储（重点考察）

2.链式存储

3.基于顺序存储实现字符串的基本操作

(1)求子串

(2)比较操作

(3)定位操作

4.总结

三、串的模式匹配

1.朴素模式匹配算法

(1)朴素模式匹配算法图示

(2)代码实现

(3)时间复杂度计算

(4)总结

2.KMP算法

(1)算法推理过程介绍

(2)代码实现KMP算法

(3)朴素模式匹配算法和KMP算法对比

3.手算求next数组（超级重点，几乎必考！！）

4.KMP算法优化

(1) 使用nextval数组

(2)练习求nextval数组

四、易错题总结

1.选择题

2.简答题

五、参考

写在前面：考纲内容

大纲要求掌握字符串模式匹配，重点掌握：

        (1) KMP匹配算法的原理及next数组的推理过程。

        (2) 手工求next数组可以先计算出部分匹配值表然后变形，或根据公式来求解。

        (3)掌握nextval数组的求解方法。

一、串的基本概念

1.串的定义

2.串和线性表对比

        字符串是用于存储和操作一组字符的集合，数据对象限定为字符集（如中文、英文、数字、标点字符等），而线性表是一种更通用的数据结构，用于组织和处理一系列元素，并支持多种类型的操作。

(1)存储方式与结构

  • 字符串是连续的字符序列。
  • 线性表可以是数组（顺序存储）或链表（链接存储），前者提供随机访问，后者通过指针实现动态调整大小和高效插入删除操作。

(2)数据操作效率

  • 对于字符串，查找、替换、比较等通常需要遍历整个序列。
  • 线性表的操作依赖于其内部结构。例如，在数组中查找某个元素需要线性搜索（O(n)），而在链表中通过迭代可以更高效地进行。

(3)内存管理

  • 字符串一旦创建，如果类型不支持修改，则大小固定。
  • 线性表可以通过动态分配和释放来调整空间使用，更具灵活性。

(4)应用场景

  • 字符串：文本处理、字符串搜索、文本编辑等；
  • 线性表：记录管理、数据排序与查找、算法实现（如广度优先搜索中的队列）等。

3.串的基本操作

操作函数原型细节描述

赋值操作（StrAssign）

StrAssign(&T, chars)

将字符数组chars的值赋给串T。

复制操作（StrCopy）

StrCopy(&T, S)

将串S的值复制到串T中。

判空操作（StrEmpty）

StrEmpty(S)

检查串S是否为空。如果为空，则返回TRUE；否则返回FALSE。

求串长操作（StrLength）

StrLength(S)

返回串S的元素个数（即长度）。

清空操作（ClearString）

ClearString(&S)

将串S清空，即将其长度设置为0。

销毁串操作（DestroyString）

DestroyString(&S)

销毁串S，释放其占用的存储空间。

串联接操作（Concat）

Concat(&T, S1, S2)

将串S1和串S2连接，并将结果存储在串T中。

求子串操作（SubString）

SubString(&Sub, S, pos, len)

从串S的第pos个字符开始，截取长度为len的子串，并将结果存储在串Sub中。这里pos往往是指的下标，0就是指的第一个字符，但是在王道教材中因为首个位置不使用，所以pos=1就是第一个字符，看下面3.顺序存储结构实现基本操作。

定位操作（Index）

Index(S, T)

在串S中查找串T首次出现的位置。如果找到，则返回该位置；否则返回0。

比较操作（StrCompare）

StrCompare(S, T)

比较串S和串T。如果S大于T，则返回大于0的值；如果S等于T，则返回0；如果S小于T，则返回小于0的值。

这里着重提一下比较操作，常见的说法是按照字典序排列：

4.拓展：字符集编码

5.总结

二、串的存储结构

1.顺序存储（重点考察）

2.链式存储

3.基于顺序存储实现字符串的基本操作

(1)求子串

#include <iostream>  
#include <cstring>  // 定义字符串结构体  
typedef struct {  char ch[MAXLEN_255]; // 假设MAXLEN_255已定义，例如#define MAXLEN_255 255  int length;  
} SString;  // 求子串函数  
bool SubString(SString &Sub, SString S, int pos, int len) {  // 检查子串范围是否越界  if (pos + len - 1 >= S.length) {  return false;  }  // 复制子串到Sub中  for (int i = 0; i < len; i++) {  Sub.ch[i] = S.ch[pos + i];  }  Sub.length = len;  return true;  
}  int main() {  SString S;  strcpy(S.ch, "wangdao");  S.length = 7;  SString Sub;  int pos = 1; // 从第2个字符开始  int len = 4; // 长度为4的子串  if (SubString(Sub, S, pos, len)) {  std::cout << "提取的子串为: " << Sub.ch << std::endl;  } else {  std::cout << "子串范围越界或长度错误" << std::endl;  }  return 0;  
}

(2)比较操作

#include <iostream>  
#include <cstring>  // 假设有一个字符串结构体的定义  
typedef struct {  char ch[MAXLEN]; // MAXLEN 应为定义的字符串最大长度，如255  int length;  
} SString;  // 字符串比较函数  
int StrCompare(SString S, SString T) {  int i;  for (i = 0; i < S.length && i < T.length; i++) { // 注意循环条件应该从0开始  if (S.ch[i] != T.ch[i]) {  return S.ch[i] - T.ch[i]; // 返回两个字符的ASCII码之差  }  }  // 扫描过的所有字符都相同，则长度长的串更大  return S.length - T.length;  
}  int main() {  SString S;  S.length = 7;  strcpy(S.ch, "wangdao"); // 使用strcpy将字符串复制到S.ch中  // 假设T是另一个字符串，这里为了演示我们简化为与S相同  SString T;  T.length = 7;  strcpy(T.ch, "wangdao");  int result = StrCompare(S, T);  if (result > 0) {  std::cout << "S > T" << std::endl;  } else if (result < 0) {  std::cout << "S < T" << std::endl;  } else {  std::cout << "S = T" << std::endl;  }  return 0;  
}  // 注意：MAXLEN 需要在代码中定义，例如 #define MAXLEN 255

(3)定位操作

利用上面的求子串和比较函数实现

4.总结

三、串的模式匹配

目的：在主串中找到与模式串相同的子串，并返回其所在位置

1.朴素模式匹配算法

属于暴力求解算法，将主串中所有长度为m的子串依次与模式串对比（主串的起始下标每次向后移动一个字符），直到找到一个完全匹配的子串，或者所有子串都不匹配为止，可以计算得到，最多对比n-m+1个子串。

(1)朴素模式匹配算法图示

(2)代码实现

注意：为了和前面对应，下标是从1开始的。

// 朴素模式匹配算法  
int Index(SString S, SString T) {  int i = 1, j = 1; // 初始索引从1开始  while (i <= S.length && j <= T.length) {  if (S.ch[i] == T.ch[j]) {  ++i;  ++j;  } else {  i = i - j + 2; // 当不匹配时，主串的指针回到匹配开始的后一个位置  j = 1; // 模式串的指针重置  }  }  // 如果j达到了T的长度，表示找到了匹配  if (j > T.length) {  return i - T.length; // 返回匹配在主串中的开始位置  } else {  return 0; // 没有找到匹配  }  
}

(3)时间复杂度计算

(4)总结

2.KMP算法

        在朴素模式匹配算法中，每次匹配失败，主串的 i 指针可能需要前移，在下面例子中，在i=6时匹配失败时，朴素模式匹配算法 i 需要移动到5再次匹配。

(1)算法推理过程介绍

推导过程比较抽象，推荐好好看看王道这块视频讲解再来看这块总结，这里把关键步骤截取出来是为了后期复习使用。

如果子串的第3个字母匹配不成功：其实这里i不需要往后移动，只需要将子串指针j指向1，和i=6开始的子串进行匹配比较即可。

那我们再来看一下如果子串的第6个字母匹配不成功：

其实前面的ab子串已经确定相同了，所以j只需要移动到3开始比较即可，免于从1开始比较了

(2)代码实现KMP算法

一定要注意：next数组只与模式串（也就是给出的子串）有关，和主串没有关系。

在获得next数组基础上，使用next数组来匹配字符串的KMP算法代码实现：

#include "KMPAlth.hpp"//KMP算法，已经得到了next数组
int index_KMP(string S,string T,int next[]){int i=1,j=1;while(i<=S.length()&&j<T.length()){if(j==0||S.at(i)==T.at(j)){i++;j++;}else{j=next[j];}}if(j>T.length()){return i-(int)T.length();}else{return 0;}
}

(3)朴素模式匹配算法和KMP算法对比

3.手算求next数组（超级重点，几乎必考！！）

模式串在主串上匹配不符的位置，右移元素直到前部分能匹配成功最多项(对应的j匹配的最大下标位置)，这块描述起来很抽象，还是要多看一下王道视频讲解。

4.KMP算法优化

(1) 使用nextval数组

使用nextval的目的是更加简化模式串指针j的移动过程，避免多次判断，直接一次到位。

可以通过下面的代码算法，把KMP算法的next数组优化成nextval数组

nextval[0]直接写0

(2)练习求nextval数组

四、易错题总结

一定要区别于KMP算法和简单模式匹配算法！！！！KMP算法的指针i是不会回溯的，时间复杂度是O(M+N)

1.选择题

题目：

解答：

题目：

解答：

题目：

解答：

这两个题目比较来看，6题答案隐含的是，串下标是从0开始的，所以next数组里的值整体减1了；7题是没有减1的，做这些一定要细心！！！

题目：

解答：

我还是按照简单匹配来做了，应该老老实实按照next数组的下标去进行j指针的移动，然后进行比较！！！！！！！！

2.简答题

问题：

解答：

问题：这个题目只是提醒注意一下问法

五、参考

📚课件来源：王道考研

📚课本及题目：《2024数据结构考研复习指导-王道论坛》

欢迎大家交流学习，如有错误请批评指正！

下一章：树与二叉树

这篇关于考研系列-数据结构第四章：字符串的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1071164。

相关文章

2390.从字符串中移除星号

2390.从字符串中移除星号

给你一个包含若干星号 * 的字符串 s 。 在一步操作中，你可以： 选中 s 中的一个星号。 移除星号左侧最近的那个非星号字符，并移除该星号自身。 返回移除 所有 星号之后的字符串。 注意： 生成的输入保证总是可以执行题面中描述的操作。 可以证明结果字符串是唯一的。 示例 1： 输入：s = “leet**cod*e” 输出：“lecoe” 解释：从左到右执行移除操作： 距离第 1 个
阅读更多...
Python 字符串占位

Python 字符串占位

在Python中，可以使用字符串的格式化方法来实现字符串的占位。常见的方法有百分号操作符 % 以及 str.format() 方法 百分号操作符 % name = "张三"age = 20message = "我叫%s，今年%d岁。" % (name, age)print(message) # 我叫张三，今年20岁。 str.format() 方法 name = "张三"age
阅读更多...
JavaWeb系列二十: jQuery的DOM操作 下

JavaWeb系列二十: jQuery的DOM操作 下

jQuery的DOM操作 CSS-DOM操作多选框案例页面加载完毕触发方法作业布置jQuery获取选中复选框的值jQuery控制checkbox被选中jQuery控制(全选/全不选/反选)jQuery动态添加删除用户 CSS-DOM操作 获取和设置元素的样式属性: css()获取和设置元素透明度: opacity属性获取和设置元素高度, 宽度: height(), widt
阅读更多...
【数据结构】线性表：顺序表

【数据结构】线性表：顺序表

文章目录 1. 线性表2. 顺序表2.1 概念及结构2.2 接口实现2.3 顺序表的问题及思考 1. 线性表 线性表是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使用的数据结构，常见的线性表：顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构，也就说是连续的一条直线。但是在物理结构上并不一定是连续的，线性表在物理上存储时，通常以数组和链式结构的形式
阅读更多...
数据结构9——排序

数据结构9——排序

一、冒泡排序 冒泡排序（Bubble Sort），顾名思义，就是指越小的元素会经由交换慢慢“浮”到数列的顶端。 算法原理 从左到右，依次比较相邻的元素大小，更大的元素交换到右边；从第一组相邻元素比较到最后一组相邻元素，这一步结束最后一个元素必然是参与比较的元素中最大的元素；按照大的居右原则，重新从左到后比较，前一轮中得到的最后一个元素不参4与比较，得出新一轮的最大元素；按照上述规则，每一轮结
阅读更多...
C语言入门系列：探秘二级指针与多级指针的奇妙世界

C语言入门系列：探秘二级指针与多级指针的奇妙世界

文章目录 一，指针的回忆杀1，指针的概念2，指针的声明和赋值3，指针的使用3.1 直接给指针变量赋值3.2 通过*运算符读写指针指向的内存3.2.1 读3.2.2 写 二，二级指针详解1，定义2，示例说明3，二级指针与一级指针、普通变量的关系3.1，与一级指针的关系3.2，与普通变量的关系,示例说明 4，二级指针的常见用途5，二级指针扩展到多级指针 小结 C语言的学习之旅中，二级
阅读更多...
剑指offer（C++）--左旋转字符串

剑指offer（C++）--左旋转字符串

题目 汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！ class Solution {public:string LeftRotateStri
阅读更多...
PAT-1039 到底买不买（20）（字符串的使用）

PAT-1039 到底买不买（20）（字符串的使用）

题目描述 小红想买些珠子做一串自己喜欢的珠串。卖珠子的摊主有很多串五颜六色的珠串，但是不肯把任何一串拆散了卖。于是小红要你帮忙判断一下，某串珠子里是否包含了全部自己想要的珠子？如果是，那么告诉她有多少多余的珠子；如果不是，那么告诉她缺了多少珠子。为方便起见，我们用[0-9]、[a-z]、[A-Z]范围内的字符来表示颜色。例如，YrR8RrY是小红想做的珠串；那么ppRYYGrrYBR2258可以
阅读更多...
JavaWeb系列六: 动态WEB开发核心(Servlet) 上

JavaWeb系列六: 动态WEB开发核心(Servlet) 上

韩老师学生 官网文档为什么会出现Servlet什么是ServletServlet在JavaWeb项目位置Servlet基本使用Servlet开发方式说明快速入门- 手动开发 servlet浏览器请求Servlet UML分析Servlet生命周期GET和POST请求分发处理通过继承HttpServlet开发ServletIDEA配置ServletServlet注意事项和细节 Servlet注
阅读更多...
js小题：通过字符串执行同名变量怎么做

js小题：通过字符串执行同名变量怎么做

在JavaScript中，你不能直接使用一个字符串来直接引用一个变量，因为JavaScript是一种静态类型语言（尽管它的类型在运行时可以变化），变量的名字在编译时就被确定了。但是，有几种方法可以实现类似的功能： 使用对象（或Map）来存储变量： 你可以使用一个对象来存储你的变量，然后使用字符串作为键来访问这些变量。 let myVars = { 'var1': 'Hello', 'var
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2