1. 数据结构与算法/

字符串数据结构

·247 字·2 分钟· loading
数据结构与算法 字符串数据结构 数据结构与算法 HTTP
demo007x
作者
demo007x

字符串数据结构
#

字符串被定义为字符数组。字符数组和字符串之间的区别在于字符串以特殊字符“\0”结尾。 下面是一些字符串示例:

“this”, “is”, “demo007”, “i”, “am”, “a”, “developer”

字符串在内存中是如何表示的?
#

在 C 中,可以使用字符指针或字符数组来引用字符串。当字符串被声明为字符数组时,它们的存储方式与 C 中其他类型的数组一样。例如,如果 str[] 是一个 auto 变量,则该字符串存储在堆栈段中,如果它是一个全局或静态变量,则存储在数据段中.

什么是字符串以及字符串在内存中的表示方式

对字符串执行的操作:
#

1. 字符串连接
#

将多个字符串组合在一起的过程称为串联。字符串连接是组合两个字符串的技术。

image-20230920075333821

2. 在字符串中查找
#

对字符串执行的一个非常基本的操作是在给定的整个字符串中查找某些内容。现在,这可以是在字符串中查找给定字符,或者在另一个字符串中查找完整的字符串。

在字符串中查找

a)查找字符串中的一个字符
#

给定一个字符串和一个字符,任务是找到该字符在字符串中的第一个位置。这些类型的问题是竞争非常激烈的编程问题,您需要找到字符串中字符的位置。

b)在另一个字符串中查找子字符串
#

考虑有一个长度为 N 的字符串和一个长度为 M 的子字符串。然后运行一个嵌套循环,其中外循环从 0 到 (NM),内循环从 0 到 M。对于每个索引,检查子字符串是否内循环遍历的字符串是否是给定的子字符串。

3.字符串替换
#

很多时候,对字符串进行修改非常重要。替换字符串中的字符、单词或短语是对字符串执行的另一种非常常见的操作。

解决给定问题的最简单方法是遍历字符串S,当找到任何字符串S1作为字符串S中的子字符串时,则将其替换为S2。请按照以下步骤解决此问题:

  • 初始化字符串ans 来存储替换字符串 S 中所有出现的子字符串 S1 到 S2 后的结果字符串。

  • 使用变量 i迭代字符串 S 的字符

    并执行以下步骤:

    • 如果字符串S的前缀子串从索引i开始等于S1,则将字符串S2添加到字符串ans中。
    • 否则,将当前字符添加到字符串 ans 中。
  • 完成上述步骤后,打印字符串 ans 作为结果。

4. 求字符串的长度
#

对字符串最常见的操作之一是查找给定字符串的长度/大小。长度定义为字符串中的字符数,称为该字符串的长度。

a )不使用任何内置方法的字符串长度:
#

下面是求两个字符串长度的算法:

SET LEN = 0 AND I = 0.
Repeat Steps 3 to 4 while STRING[I] is not NULL:
LEN = LEN + 1.
SET I = I + 1.
Exit.

6. 字符串的反转和旋转
#

反向操作是交换字符串中字符的位置,使第一个字符变为最后一个,第二个字符变为倒数第二个,依此类推。

a)字符串的旋转:
#

字符串的旋转

考虑一个字符串“demo007”,现在所有可能的旋转将是:

  • 7demo00
  • 70demo0
  • 700demo
  • 700odem
  • 700omde
  • 700omed

b)反转字符串:
#

字符串的反转只不过是将字符串的最后一个元素替换为字符串的第一个位置。

反转字符串

7. 字符串的子序列
#

序列是可以通过删除零个或多个元素从另一个序列导出的序列,而不改变剩余元素的顺序。

更一般地,我们可以说,对于大小为 n 的序列,总共可以有 (2n-1) 个非空子序列。

例如,考虑字符串“geeks”,有 15 个子序列。 他们是:

g, e, e, k, s,
ge, ge, gk, gs, ee, ek, es, ek, es, ks,
gee, gek, ges, gek, ges, gks, eek, ees, eks, eks,
geek, gees, eeks,
geeks

image-20230920080118238

9. 二进制字符串
#

二进制字符串是一种特殊的字符串,仅由两种类型的字符组成,例如 0 和 1。 例如:

输入: str = "01010101010"
输出: Yes, it is a Binary String

输入: str = "demo007"
输出: No, it is not a Binary String

10. 回文字符串
#

如果字符串的反转与该字符串相同,则称该字符串为回文。

例如: “abba”是回文,但“abbc”不是回文。

11. 词典模式
#

字典顺序模式是基于 ASCII 值的模式,或者可以按字典顺序表示。我们将字符的字典顺序视为它们的 ASCII 值的顺序。因此字符的字典顺序将是

“A”、“B”、“C”、...、“Y”、“Z”、“a”、“b”、“c”、...、“y”、“z”。

12. 模式搜索
#

模式搜索是在字符串中搜索给定的模式。这是字符串的高级内容。模式搜索算法有时也称为字符串搜索算法,并被视为字符串算法的一部分。这些算法在搜索另一个字符串中的字符串的情况下非常有用。

模式搜索

字符串的应用、优点和缺点
#

  • 字符串数据结构是编程语言的支柱和通信的构建块**。**字符串数据结构是计算机科学和编程中最基本、最广泛使用的工具之一。它们允许以多种方式表示和操作文本和字符序列。字符串数据结构是一个强大的工具,可以用来存储和处理大量的文本数据,从简单的字符串到复杂的句子、段落,甚至整本书。
  • 它是表示文本或其他形式的数据的字符序列。它是一种基本数据结构,在许多编程语言中用于存储和操作基于文本的数据。在大多数编程语言中,字符串被实现为字符数组,每个字符在数组中都有唯一的索引位置。

字符串表示

字符串的应用:
#

  • **匹配检查器:**字符串可用于使用字符串匹配算法在很短的时间内查找代码和内容中的抄袭行为。使用这个,计算机可以轻松地告诉我们代码的百分比,以及任意两个用户编写的文本匹配的百分比。
  • **编码/解码(密文生成):**字符串可用于编码和解码,以确保数据从发送者到接收者的安全传输,以确保传输过程中没有人能够读取您的数据,因为它们可以执行主动和被动操作攻击。您作为消息传输的文本在发送者端被加密,并在接收者端被解码。
  • **信息检索:**字符串应用程序帮助我们从未知数据源(用作输入的大型数据集)检索信息,并借助字符串匹配/检索模块帮助我们检索重要信息。
  • **针对近似后缀-前缀重叠问题的改进过滤器:**字符串及其算法应用帮助我们为近似后缀-前缀重叠问题提供改进的过滤器。近似后缀-前缀重叠问题是从给定集合中查找所有字符串对,使得一个字符串的前缀与另一个字符串的后缀相似。
  • **网络通信:**字符串用于对通过网络发送的数据进行编码和解码,例如 HTTP 请求和响应。
  • **文件处理:**字符串用于操作文件路径和名称,以及读取和写入文件。
  • **数据分析:**字符串可用于从大量文本数据中提取有意义的见解,例如自然语言处理和情感分析。

字符串的优点:
#

  • **文本处理:**字符串用于表示编程语言中的文本。它们可用于以各种方式操纵和处理文本,例如搜索、替换、解析和格式化。
  • **数据表示:**字符串可用于表示其他数据类型,例如数字、日期和时间。例如,您可以使用字符串来表示“YYYY-MM-DD”格式的日期,或“HH:MM:SS”格式的时间。
  • **易于使用:**字符串易于使用和操作。它们可以被连接、切片和反转等。它们还具有简单直观的语法,使所有技能水平的程序员都可以使用它们。
  • **兼容性:**字符串在各种编程语言中广泛使用,使其成为通用数据类型。这意味着字符串可以在不同的系统和平台之间轻松传输,使其成为可靠且高效的通信和共享数据的方式。
  • **内存效率:**字符串通常存储在连续的内存块中,这使得它们的分配和释放效率很高。这意味着它们可以用来表示大量数据而不占用太多内存。

字符串的缺点:
#

  • **内存消耗:**字符串可能会消耗大量内存,尤其是在处理大字符串或许多字符串时。这在内存受限的环境中可能是一个问题,例如嵌入式系统或移动设备。
  • **不变性:**在许多编程语言中,字符串是不可变的,这意味着它们一旦创建就无法更改。当处理需要频繁修改的大型或复杂字符串时,这可能是一个缺点,因为它可能导致效率低下和内存开销。
  • **性能开销:**字符串操作可能比其他数据类型的操作慢,尤其是在处理大型或复杂的字符串时。这是因为字符串操作通常涉及复制和重新分配内存,这可能非常耗时。
  • **编码和解码开销:**字符串可以具有不同的字符编码,这可能会导致在它们之间进行转换时产生开销。当处理来自不同源的数据或与使用不同编码的系统通信时,这可能会成为问题。
  • **安全漏洞:**如果处理不当,字符串可能容易受到安全漏洞的影响,例如缓冲区溢出或注入攻击。这是因为攻击者可以操纵字符串来执行任意代码或访问敏感数据。

Related

跟我一起探索HTTP-协议升级机制
计算机网络 HTML HTTP
协议升级机制HTTP/1.1 协议提供了一种使用Upgrade (en-US) 标头
跟我一起探索HTTP-HTTP/1.x 的连接管理
计算机网络 HTTP
连接管理是一个 HTTP 的关键话题:打开和保持连接在很大程度上影响着网站和 We
跟我一起探索HTTP-典型的 HTTP 会话
计算机网络 HTTP HTML
在像 HTTP 这样的客户端——服务器(Client-Server)协议中,会话分为三个