C语言描述的数据结构：串的定义与操作

"该资源是严蔚敏教授关于数据结构中串部分的PPT课件，主要涵盖了C语言描述下的串类型定义、存储实现以及模式匹配算法。" 在计算机科学中，数据结构是组织和管理数据的重要方式，串（String）作为其中的一种基本类型，是由零个或多个字符组成的有限序列。在本PPT中，主要讲解了以下几个核心知识点： 1. **串的定义**：串是由零个或多个字符组成的序列，可以表示为`s=‘a1a2an’`，其中`ai`是字符，`n`是串的长度。当`n=0`时，我们称之为空串，记为Ф。而由一个或多个空格组成的串被称为空白串，但空串与空白串是有区别的。 2. **子串的概念**：在主串中，任何连续字符组成的子序列都称为子串。子串的位置由其在主串中的第一个字符的序号决定。任何串都是自身的子串，而空串是所有串的子串。 3. **串的比较**：如果两个串的长度相等且对应位置的字符都相等，那么这两个串是相等的。反之，若内容不等，则通过比较第一个不同的字符的ASCII码来判断大小。例如，'chinese'大于'china'，因为尽管它们前三个字符相同，但'chinese'的长度更长。 4. **串的存储结构**： - **定长顺序存储表示**：在固定大小的数组中存储串，适用于长度固定的串。优点是访问速度快，但空间利用率不高，可能造成浪费。 - **堆分配存储表示**：动态分配内存来存储串，可以根据需要分配不同长度的空间，适合长度不固定的串。但这种表示法需要额外的指针来跟踪串的边界，增加了复杂性。 5. **串的模式匹配算法**：这是在主串中寻找子串出现位置的过程。常见的模式匹配算法有KMP算法等，这类算法高效地查找一个模式串在目标串中的出现位置，避免了不必要的字符比较。 6. **串的抽象数据类型（ADTString）**：串的ADT描述了一个数据对象，即字符集合构成的线性表，定义了一组操作，如串的创建、插入、删除、查找、比较等，以及相应的操作规则。 这个PPT深入浅出地介绍了串的基本概念和操作，对于理解和掌握数据结构中的串部分非常有帮助，特别是对于用C语言进行编程实现的场景。通过学习，读者能够理解串的基本操作，并能运用这些操作实现更复杂的串处理算法，比如模式匹配。