<数据结构> 第4章习题

在数据结构的学习中，串是一种重要的数据类型，它是由一个或多个字符组成的有限序列。本章主要讨论了串的相关概念、操作以及算法。以下是基于题目内容的详细知识点解析： 1. **串的定义**：串是字符的有限序列，可以为空，但空串不等同于由空格构成的串。因此，选项B是错误的。 2. **串的操作**：模式匹配是串的基本运算之一，用于在一个串中查找另一个串（模式串）的出现位置。题目中的表达式涉及到了`concat`（连接）、`replace`（替换）、`substr`（子串提取）和`index`（查找子串首次出现的位置）等操作。 3. **子串与匹配**：如果一个串q是另一个串p的子串，那么在p中首次出现q的位置的算法称为匹配。例如，题目中的选项C对应的就是这种匹配算法。 4. **Next数组**：Next数组是KMP算法中的一个重要概念，用于记录模式串中每个字符前缀和后缀的最大公共长度。例如，对于串S=‘aaab’，Next数组是1123，表示在每个位置i，模式串的前i个字符与从i+1开始的最长公共前缀的长度。 5. **next数组和nextval数组**：next数组记录的是模式串中连续字符的最大公共前缀长度，而nextval数组则考虑了回溯的情况，例如串‘ababaabab’的next数组为012301232，nextval数组为0112322345。 6. **子串计数**：一个串的子串数目可以按照特定的公式计算，例如，串S=‘software’的子串数目是37，包括空串和自身。 7. **非平凡子串**：一个长度为n的字符串S中的互异非平凡子串（非空且不同于S本身）的个数为(n^2/2) + (n/2) - 1。这个数量不包括S本身和空串。 8. **串的长度**：串的长度是指串中字符的个数，包括空格。所以，选项B是错误的，串的长度不是不同字符的个数，也不是非空格字符的个数。 9. **KMP算法**：KMP算法在模式匹配时避免了不必要的回溯，即主串的指针不会变小，这是它的特点之一。 10. **串的特殊性质**：串作为一种特殊的数据结构，它的数据元素只能是字符，并且串的操作通常包括插入、删除、连接、查找、替换等。 填空题： 1. **空格串**：空格串是指由零个字符组成的串，其长度等于0。 2. **数据元素**：组成串的数据元素只能是字符。 3. **字**：由于题目未提供完整信息，这里假设是询问“字”的定义，字通常指单个的字符。 以上就是关于数据结构中第四章串的相关知识点，涵盖了串的定义、操作、模式匹配、Next数组等相关概念及其应用。