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

在这个问题中，我们需要使用链表存储字符串，并设计一个算法 `Index()` 来查找给定子串 `S` 在主串 `T` 中首次出现的位置。由于是带头结点的单链表形式，我们可以定义节点结构如下：

// 定义链表节点
typedef struct Node {
    char data;         // 节点的数据部分
    struct Node* next; // 指向下一个节点的指针
} ListNode;

// 定义字符串结构体，包含头节点和长度
typedef struct {
    ListNode* head; // 链表的头节点
    int length;     // 字符串长度
} StringList;

接下来是 `Index()` 算法的描述：

// 函数原型
int Index(StringList* T, const char* S);

// 实现函数
int Index(StringList* T, const char* S) {
    ListNode* cur = T->head; // 从主串头开始遍历
    int index = -1;          // 子串索引，初始值-1表示未找到
    int si = 0;              // 子串索引，初始化为0

    // 搜索子串在主串中的匹配
    while (cur != NULL && si < strlen(S)) {
        if (cur->data == S[si]) {
            si++;
            if (si == strlen(S)) { // 如果找到了完整的子串，更新索引并返回
                index = T->length - si; // 因为链表的下标从0开始
                break;
            }
        } else {
            si = 0; // 如果字符不匹配，从头开始搜索
        }
        cur = cur->next;
    }

    return index;
}