串的知识梳理思维导图

U732106906

2023-04-18

浏览量: 21

串的知识梳理

串

代码

编程

知识梳理

串的知识梳理

树图思维导图提供《串的知识梳理》在线思维导图免费制作，点击“编辑”按钮，可对《串的知识梳理》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：55770a0c20b763bfa3149d5cea43cd7a

思维导图大纲

相关思维导图模版

串思维导图模板大纲

定义

概念

串是一种线性结构，是由零个或多个字符组成的有限序列，也可以称之为字符串。在计算机中，我们通常使用ASCII或Unicode编码表示一个字符，从而可以将字符序列转化为一个串

空串

空串是指长度为零的串，也可以称为空字符串。它是一个特殊的串，不包含任何字符。例如，""就是一个空串

字串

子串是指在一个串中任意选取一段连续的字符组成的串，也可以称为子字符串。例如，在串"hello world"中，"hello"和"world"都是它的子串

主串

主串是指包含子串的串，也可以称为源字符串或母串。例如，在串"hello world"中，"hello world"是主串。

空格串

空格串是指由空格字符组成的串，也可以称为空白串。例如，" "和" "都是空格串。

串的长度

串的长度是指一个串中包含的字符数，也可以称为串长。例如，串"hello world"的长度是11。

串匹配

BP

BP算法是一种朴素的串匹配算法，也称为暴力匹配算法。它的基本思想是在文本串中从左到右依次比较子串和模式串中的字符，当子串和模式串完全匹配时，返回在文本串中的位置；否则，继续比较下一个位置，直到找到匹配或遍历完整个文本串。

BP算法的时间复杂度为O(n*m)，其中n和m分别为文本串和模式串的长度。

int bp_search(char *text, char *pattern) { int i, j, k, len_text, len_pattern; len_text = strlen(text); len_pattern = strlen(pattern); for (i = 0; i < len_text - len_pattern + 1; i++) { for (j = 0; j < len_pattern; j++) { if (text[i + j] != pattern[j]) { break; } } if (j == len_pattern) { return i; } } return -1; }

核心代码

KMP

KMP算法是一种高效的串匹配算法，它利用模式串的自重复性，在匹配过程中避免重复比较已经匹配的字符。KMP算法的核心部分是获取模式串的next数组，然后利用next数组进行匹配。

KMP算法的时间复杂度为O(n+m)，其中n和m分别为文本串和模式串的长度。

void getNext(char *p, int *next) { int i, j, len; len = strlen(p); next[0] = -1; i = 0; j = -1; while (i < len - 1) { if (j == -1 || p[i] == p[j]) { i++; j++; next[i] = j; } else { j = next[j]; } } }

核心代码

存储结构

定长数组

在串的定长顺序存储表示中，串被存储在一个定长数组中，该数组的长度为串的最大长度，通常用字符型数组来存储，每个元素存储一个字符。由于数组的长度是固定的，因此称为定长数组。

例如，假设有一个最大长度为10的串"hello"，则可以用一个长度为10的字符型数组来存储它，其中前5个元素存储"h"、"e"、"l"、"l"、"o"，后面的5个元素没有使用。

串的动态分配存储表示

在串的动态分配存储表示中，串被存储在一个动态分配的存储区中，该存储区的大小根据串的实际长度动态调整，不会浪费空间。通常使用指针来表示动态分配存储的串。

例如，假设有一个串"hello"，则可以先动态分配一个长度为5的存储区，然后将"h"、"e"、"l"、"l"、"o"存储在这个存储区中。如果串的长度增加了，可以再动态分配一个更大的存储区，将原来的串复制到新的存储区中，并释放原来的存储区。

串的链式存储模式

在串的链式存储模式中，串被存储在一个链表中，每个结点表示一个字符。通常使用链表中的结点来表示字符，结点中包含一个指向下一个结点的指针和一个表示字符的数据域。

例如，假设有一个串"hello"，则可以用一个包含5个结点的链表来存储它，其中每个结点表示一个字符，结点中的数据域存储字符，指针指向下一个结点。最后一个结点的指针为空，表示链表的末尾。

串应用

求重复最长字串

编码转化

查看更多

物流项目成本与绩效管理评价思维导图

树图思维导图提供《物流项目成本与绩效管理评价》在线思维导图免费制作，点击“编辑”按钮，可对《物流项目成本与绩效管理评价》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：485f615ac86bab948f39f08952b80c00

物流项目成本与绩效管理评价

平顶山市物流业对平顶山市制造业的影响思维导图

树图思维导图提供《平顶山市物流业对平顶山市制造业的影响》在线思维导图免费制作，点击“编辑”按钮，可对《平顶山市物流业对平顶山市制造业的影响》进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：315aaf17fc2644a008cff4579b72250a

平顶山市物流业对平顶山市制造业的影响

思维导图模板

高校与高等教育

正文

相似思维导图模版

杰弗里·乔叟的生平介绍脑图思维导图

2023-09-21 17:10:35

杰弗里·乔叟的生平介绍脑图

判断推理·翻译推理思维导图

2023-11-02 22:38:46

判断推理·翻译推理

材料力学思维导图

2023-06-11 12:11:42

材料力学

四级语法知识点思维导图

2022-07-15 14:43:57

四级语法知识点思维导图

英语时态一般现在时思维导图

2022-04-01 16:51:34

英语时态一般现在时

信号与系统思维导图

2023-05-21 22:08:25

信号与系统

思维导图模版推荐

第一章轴向拉伸和压缩思维导图

2023-04-18 22:12:48

第一章轴向拉伸和压缩

暑假英语学习计划合集12篇思维导图

2023-04-18 22:14:58

暑假英语学习计划合集12篇

适用于海洋和内陆的运输方式思维导图

2023-04-18 22:15:54

适用于海洋和内陆的运输方式

祝姐姐生日快乐祝福语大全(汇集25条)思维导图

2023-04-18 22:02:15

祝姐姐生日快乐祝福语大全(汇集25条)

姐姐过生日的祝福语短句(锦集24句)思维导图

2023-04-18 22:02:08

姐姐过生日的祝福语短句(锦集24句)

工作流程 workflow思维导图

2023-04-18 22:02:05

工作流程 workflow

首页

我的文件

我的团队

个人中心