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

在清华大学严蔚敏的数据结构课程中，重点讨论了链串上的子串定位算法，这是一种针对链表存储结构的字符串匹配方法。当使用链表作为数据结构，其中每个节点包含一个字符，而长度信息并不存储在链表中时，朴素的匹配算法变得较为复杂。算法的关键在于处理节点地址而非整数位移，并且在找不到匹配子串时返回空指针。 算法的具体步骤如下： 1. 定义函数 `lindex(lstring s, lstring t)`，其中`s` 是主串（原始链表），`t` 是子串（要查找的链表）。 2. 初始化指针 `shift` 指向主串的起始位置 `S`，`q` 和 `p` 分别指向 `shift` 和子串 `t` 的起始位置。 3. 在循环中，比较 `q` 指向的子串字符与 `p` 指向的主串字符是否相等。如果不相等，或者 `p` 超过了主串的末尾，说明子串不存在，返回空指针。 4. 如果字符匹配，将 `p` 向后移动一位，`q` 也相应移动，继续比较。 5. 当 `q` 遍历完子串 `t`，表示找到匹配，返回 `p` 所指向的节点地址，即子串在主串中的有效位移。 这个算法体现了数据结构中的关键概念，如数据表示、存储结构（链表）和算法设计。数据结构的选择直接影响算法的效率，例如链表结构使得查找和插入操作相对较慢，但适合空间有限的情况。同时，算法设计不仅要考虑问题的逻辑结构，如电话号码查询系统的二维数组、表结构或向量表示，还要关注其实现细节，如如何处理位移和边界条件。 此外，课程还涵盖了数据结构的基础概念，如数据（Data）的概念，它是信息的载体，可以是有组织的信息集合，如电话簿中的姓名和电话号码。数据结构包括数据的逻辑结构（如数组、列表、树等）和物理结构（实际在计算机内存中的存储方式），以及定义在其上的基本操作，如查找、插入、删除等。 通过实例，如图书馆书目检索系统、教师资料档案管理系统和交通灯控制，数据结构的重要性得以展现，它对于解决实际问题中的高效计算和存储管理至关重要。因此，学习和理解数据结构对于IT专业人士来说是必不可少的，它能帮助优化程序性能，提高系统设计的质量。