链串子串定位算法解析-清华大学数据结构讲义

"链串上的子串定位算法-清华大学数据结构讲义" 这篇讲义主要讨论的是数据结构中的一个重要概念——链串上的子串定位算法，这是字符串处理中的常见问题。链串，即使用单链表作为存储结构的字符串，这里每个结点的大小为1。在单链表中实现朴素的匹配算法时，由于链表没有存储长度信息，位移操作变成了结点地址的移动。 算法的具体步骤如下： 1. 定义指针`shift`指向链串`s`的起始位置，`q`指向模式串`t`的首结点，`p`用于遍历模式串。 2. 遍历链串`s`，每次将`shift`指针移动到下一个结点，相当于在字符串中右移一位。 3. 对比`shift`指向的结点和`p`指向的结点，如果匹配成功，就将`p`向后移动一位，继续比较下一个字符；如果不匹配，则将`shift`向后移动一位，重头开始比较。 4. 当`p`遍历完整个模式串`t`时，表示找到了一个匹配的子串，返回`shift`的值（即子串在链串中的起始结点地址）；如果遍历完链串`s`仍无匹配，返回空指针。 数据结构是计算机科学中的核心概念，它研究的是数据的组织方式以及在这些组织方式下执行操作的效率。在上述讲义中，数据结构不仅涉及链串，还包括其他如数组、表结构、向量等。这些结构的选择直接影响到算法的性能，例如在电话号码查询系统、图书馆书目检索系统等实际应用中，合适的数据结构能够提高查找和处理信息的效率。 讲义还介绍了基本概念和术语，如数据（Data），它是信息的载体，可以是数字、文字、图像等各种形式。数据结构则是数据的组织形式，包括逻辑结构（如线性结构、树形结构、图结构等）和物理结构（如顺序存储、链式存储等）。此外，讲义还提到了抽象数据类型（ADT），它定义了一组数据以及在这些数据上的一组操作，是数据结构理论的重要组成部分。 算法是解决问题的步骤集，其设计应考虑效率和可行性。在本讲义中，算法效率的度量通常通过时间复杂度和空间复杂度来评估，这两个指标对于理解和优化算法至关重要。算法的空间需求也是衡量其优劣的一个方面，特别是在资源有限的环境中。 该讲义深入浅出地介绍了数据结构中的关键概念，并以链串上的子串定位算法为例，展示了数据结构在实际问题中的应用。通过学习这样的讲义，读者可以更好地理解数据结构的重要性，并掌握如何在不同的问题场景中选择和使用合适的数据结构。