使用c语言实现基于链表结构的字符串匹配算法

以下是使用c语言实现基于链表结构的字符串匹配算法的示例代码：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

/* 链表结构体 */
typedef struct node {
    char c;  // 存储字符
    struct node *next;  // 指向下一个节点的指针
} Node;

/* 创建新的链表节点 */
Node* create_node(char c) {
    Node *node = (Node*)malloc(sizeof(Node));
    node->c = c;
    node->next = NULL;
    return node;
}

/* 释放链表节点的内存 */
void free_node(Node *node) {
    if (node == NULL) {
        return;
    }
    free_node(node->next);
    free(node);
}

/* 在链表末尾添加新的字符节点 */
void append_node(Node **head, char c) {
    if (*head == NULL) {
        *head = create_node(c);
        return;
    }
    Node *current = *head;
    while (current->next != NULL) {
        current = current->next;
    }
    current->next = create_node(c);
}

/* 在链表中查找是否存在某个字符 */
int find_node(Node *head, char c) {
    Node *current = head;
    while (current != NULL) {
        if (current->c == c) {
            return 1;
        }
        current = current->next;
    }
    return 0;
}

/* 基于链表的字符串匹配算法 */
int match_string(Node *pattern, char *text) {
    Node *current = pattern;
    int i = 0;
    while (text[i] != '\0') {
        if (current->c == text[i]) {
            current = current->next;
            if (current == NULL) {
                return 1;  // 匹配成功
            }
        } else {
            if (find_node(pattern, text[i])) {
                current = pattern;
            } else {
                return 0;  // 匹配失败
            }
        }
        i++;
    }
    return 0;  // 匹配失败
}

int main() {
    Node *pattern = NULL;
    char *text = "hello world";
    int i;
    for (i = 0; i < strlen("hello"); i++) {
        append_node(&pattern, "hello"[i]);
    }
    printf("Pattern: ");
    Node *current = pattern;
    while (current != NULL) {
        printf("%c", current->c);
        current = current->next;
    }
    printf("\n");
    if (match_string(pattern, text)) {
        printf("Match found.\n");
    } else {
        printf("Match not found.\n");
    }
    free_node(pattern);
    return 0;
}

在这个示例代码中，我们首先定义了一个链表结构体 `Node`，其中包含一个 `char` 类型的成员变量 `c`，用来存储字符，以及一个指向下一个节点的指针 `next`。然后我们定义了一些操作链表的函数，比如 `create_node` 用来创建新的节点，`append_node` 用来在链表末尾添加新的字符节点，`find_node` 用来在链表中查找是否存在某个字符等等。最后我们定义了一个基于链表的字符串匹配算法 `match_string`，该函数接受一个链表作为模式串和一个字符串作为文本串，然后在文本串中查找是否存在与模式串匹配的子串。

在 `main` 函数中，我们首先创建了一个模式串 `pattern`，然后使用 `append_node` 函数将字符串 "hello" 中的字符逐一添加到链表中。然后我们调用 `match_string` 函数，将 `pattern` 和字符串 "hello world" 作为参数传入，该函数会在文本串中查找是否存在与模式串匹配的子串。最后我们释放了 `pattern` 链表的内存。