3. 字符串采用带头结点的单链表存储（非紧凑格式），设计模式匹配算法Index(S, T)。要求： ⑴声明与存储结构相关的类型； ⑵用C/C++语言描述解决问题的算法。

⑴ 在这种情况下，我们需要定义一个字符节点类型，每个节点包含一个字符和指向下一个节点的指针。另外，还需要一个链表头节点，它不存储字符，仅用于链接各个节点。这里是一个简单的链表节点定义示例：

struct ListNode {
    char data;
    ListNode* next;
};

⑵ 算法的设计思路是使用KMP（Knuth-Morris-Pratt）算法或Rabin-Karp算法，它们都是高效的字符串搜索算法，能够避免无效的回溯。这里我们选择KMP算法，因为它对动态模式匹配非常有效。

void computePrefixFunction(const string& pattern) {
    vector<int> prefix(pattern.size());
    prefix[0] = -1;
    for (int i = 1, j = -1; i < pattern.size(); ++i) {
        while (j != -1 && pattern[i] != pattern[j + 1]) {
            j = prefix[j];
        }
        if (pattern[i] == pattern[j + 1]) {
            ++j;
        }
        prefix[i] = j;
    }
}

int indexHorspool(const string& text, const string& pattern) {
    computePrefixFunction(pattern);
    int text_index = 0;
    int pattern_index = 0;

    while (text_index < text.size() && pattern_index < pattern.size()) {
        if (text[text_index] == pattern[pattern_index]) {
            text_index++;
            pattern_index++;
        } else if (pattern_index > 0) {
            pattern_index = prefix[pattern_index - 1];
        } else {
            text_index++;
        }
    }

    if (pattern_index == pattern.size()) {
        return text_index - pattern.size();
    } else {
        return -1; // 没有找到匹配
    }
}

`computePrefixFunction` 函数计算了模式串的前缀函数，`indexHorspool` 函数则是实际的搜索过程，它使用前缀函数加速比较。