严蔚敏《数据结构》串的概念与操作

"该资源是清华大学严蔚敏教授编写的《数据结构》教材中的关于‘串’这一章节的教学笔记，包含学习要点和习题解答。笔记强调了串与线性表的区别，主要在于串的操作对象通常为整个子串，而非单个字符。串的抽象数据类型（ADTString）被详细定义，包括数据对象、数据关系以及一系列基本操作，如字符串赋值、复制、销毁、判断是否为空、比较、求长度、连接和提取子串等。" 在数据结构领域，"串"是处理字符序列的一种重要数据结构。在严蔚敏教授的讲解中，串与线性表虽然在逻辑结构上有相似之处，都是线性结构，但它们在操作上有着显著的不同。线性表的操作通常针对单个元素，而串的操作往往涉及整个子串，比如查找、插入、删除等。这体现了串在文本处理、字符串匹配等应用场景的独特优势。 串的抽象数据类型（ADTString）定义了以下几个关键操作： 1. **StrAssign**: 将给定的字符串常量赋值给一个串变量，初始化或改变串的值。 2. **StrCopy**: 复制一个已存在的串到另一个串，实现串的深拷贝。 3. **DestroyString**: 销毁一个串，释放其占用的内存空间。 4. **StrEmpty**: 检查一个串是否为空，返回TRUE或FALSE。 5. **StrCompare**: 比较两个串的值，返回正、负或零表示串的相对大小。 6. **StrLength**: 返回串的长度，即包含的字符数量。 7. **Concat**: 连接两个串，生成一个新的串。 8. **SubString**: 提取串的子串，根据指定起始位置和长度。 9. **Index**: 查找指定位置之后与给定子串匹配的第一个出现位置。 这些操作构成了处理串的基本工具，对于理解和实现字符串处理算法至关重要，例如KMP算法、Boyer-Moore算法等字符串匹配算法都依赖于对串操作的理解。此外，这些基本操作也为实现其他高级功能，如文本编辑、模式匹配、文件操作等奠定了基础。 严蔚敏教授的《数据结构》教学笔记提供了深入浅出的串操作解析，有助于学生掌握数据结构的核心概念，并为解决实际问题提供理论支持。结合习题解答，学生可以进一步巩固理论知识并提升实践能力。