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

在处理字符串采用带头结点的单链表存储的情况下，我们可以使用动态规划的思想来设计模式匹配算法，例如KMP（Knuth-Morris-Pratt）算法。首先，我们需要声明与链表相关的类型：

// 定义链表节点结构
typedef struct Node {
    char data;       // 节点字符
    struct Node* next; // 指向下一颗节点
} ListNode;

// 定义字符串列表结构
typedef struct {
    ListNode* head; // 头节点
} LinkedListString;

接下来，我们可以编写 `Index` 函数来实现KMP算法：

#include <string.h>

// 计算KMP失败函数
void computeFailArray(int* fail, const char* pattern, int length) {
    int k = 0;
    for (int i = 1; i < length; i++) {
        while (k > 0 && pattern[i] != pattern[k]) {
            k = fail[k - 1];
        }
        if (pattern[i] == pattern[k]) {
            k++;
        }
        fail[i] = k;
    }
}

// 模式匹配函数
int Index(const LinkedListString* S, const LinkedListString* T) {
    int* fail = (int*)malloc(sizeof(int) * T->length); // 初始化失败函数数组
    computeFailArray(fail, T->head->data, T->length); // 计算T的失败函数

    ListNode* S_cur = S->head;
    ListNode* T_cur = T->head;
    int index = 0; // 当前匹配位置

    while (S_cur != NULL && T_cur != NULL) {
        if (S_cur->data == T_cur->data) {
            index++;
            S_cur = S_cur->next;
            T_cur = T_cur->next;
        } else if (index > 0) {
            // 如果在S中有匹配失败，尝试从之前的失败位置开始查找
            index = fail[index - 1];
        } else {
            // 如果S和T当前字符不匹配，且无法回退，返回-1
            S_cur = S_cur->prev;
            T_cur = T_cur->prev;
        }
    }

    free(fail); // 释放内存
    return index == T->length ? index : -1; // 如果完全匹配，返回索引，否则返回-1
}

在这个算法中，`computeFailArray` 函数用于计算模式串T的失败函数，`Index` 函数则遍历主串S，利用失败函数跳过不必要的比较，提高了搜索效率。当匹配结束时，返回当前索引，如果没有找到匹配，返回-1。