串的知识梳理思维导图
串的知识梳理
树图思维导图提供 串的知识梳理 在线思维导图免费制作，点击“编辑”按钮，可对 串的知识梳理 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：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个结点的链表来存储它，其中每个结点表示一个字符，结点中的数据域存储字符，指针指向下一个结点。最后一个结点的指针为空，表示链表的末尾。
串应用
求重复最长字串
编码转化
相关思维导图模板
树图思维导图提供 904名中国成年人第三磨牙相关知识、态度、行为和病史的横断面调查 在线思维导图免费制作，点击“编辑”按钮，可对 904名中国成年人第三磨牙相关知识、态度、行为和病史的横断面调查 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：10b9a8a2dd2fb4593f8130ef16c320fc
树图思维导图提供 9.战斗的基督教 在线思维导图免费制作，点击“编辑”按钮，可对 9.战斗的基督教 进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：33d168acd0cd9f767f809c7a5df86e3a
沪公网安备 31011502019485号
上海工商