清华大学严蔚敏：链串上子串定位的单链表算法

在清华大学计算机科学领域，严蔚敏教授的课程中深入探讨了链串上的子串定位算法，这是数据结构中的一个重要主题。当使用单链表作为数据结构来存储字符串时，由于链表的特点——结点大小为1且不包含长度信息，传统的匹配算法需要特殊的处理方式。这种算法的核心在于找到目标子串在主串中的起始位置，若找到则返回该位置指向的结点地址，否则返回空指针。 算法流程如下： 1. 定义指针`shift`指向主串`s`的第一个结点，`q`初始化为`shift`，`p`则指向子串`t`的第一个结点。 2. 使用循环结构，逐个比较`q`和`p`指向的结点，如果`q`指向的字符与`p`指向的字符相同，则继续移动`q`，否则，如果`q`到达链表末尾还没有找到匹配，说明子串不存在于主串中，返回空指针。 3. 如果找到匹配，即`q`到达子串`t`的末尾，这时`q`的位置即为子串在主串中的有效位移，返回`q`的地址。 这个算法强调了数据结构在实际问题中的应用，特别是对于链表这种非连续存储结构，如何通过巧妙的设计来解决查找子串的问题。在数据结构中，诸如链表、数组、向量等都是常见的数据存储方式，它们各自有不同的特点和适用场景，对算法设计有深远影响。例如，二维数组适合存储表格数据，而表结构和向量则更利于查找操作。 数据结构的研究不仅涉及数据的逻辑结构，如线性结构（如单链表）、树形结构和图结构等，还包括它们的物理存储结构，以及如何定义和实现针对不同结构的操作，如搜索、插入、删除等。此外，算法效率是衡量数据结构好坏的重要指标，包括时间复杂度和空间复杂度。在这个例子中，朴素的子串定位算法的时间复杂度是O(n)，其中n是主串的长度，因为最坏情况下可能需要遍历整个主串。 总结来说，严蔚敏教授在课程中讲解的链串上的子串定位算法，是数据结构课程中不可或缺的一部分，它展示了如何通过优化数据结构和算法来解决实际问题，提高程序的效率和性能。理解和掌握这类算法是编程和数据处理领域的基础，对于从事软件开发和信息技术工作的专业人士尤其重要。