链表实现字符串替换遇连续匹配失效问题求助及代码排查

问题描述 #

基于链表存储字符序列实现指定字符串替换功能时，当目标字符串连续出现（如whatwhat），仅能替换第一个，第二个会被忽略。需求为：匹配到目标串后，定位到目标串末尾的下一个节点，将替换串的新链表连接到原链表对应位置。

原代码 #

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

struct node { 
    int value_c;
    struct node *next_c;
    struct node *prev_c;
};

typedef struct node string;

int compare(string *head, char *word) {
    int counter = 0;
    string *temp = head;
    for (int i = 0; i < strlen(word); i++) {
        if (temp->value_c == word[i]) {
            temp = temp->next_c;
            counter++;
        }
    }
    if (counter == strlen(word))
        return 1;
    else
        return 0;
}

void print_c(string *head) {
    while (head != NULL) {
        printf("%c", head->value_c);
        head = head->next_c;
    }
}

void append_c(string **head, char thing) {
    string *newNode = (string *)malloc(sizeof(string));

    newNode->value_c = thing;
    newNode->next_c = NULL;
    
    if (*head == NULL) {
        *head = newNode;
        newNode->prev_c = NULL;
        return;
    }
    
    string *temp = *head;

    while (temp->next_c != NULL)
        temp = temp->next_c;

    temp->next_c = newNode;
    newNode->prev_c = temp;
}

string *replace_all1(string *head, char *what, char *with_what) {
    string *temp = head;
    while (temp != NULL) {
        printf("%c ", temp->value_c);
        if (compare(temp, what) == 1) {
            printf("%i ", 1); 
            printf("%c ", temp->value_c);
            string *new = temp;
            for (int i = 0; i < strlen(what) - 1; i++) {
                new = new->next_c;
            }
            string *word = NULL;
            for (int i = 0; i < strlen(with_what); i++) {
                append_c(&word, with_what[i]);
            }

            string *word_temp = word;
            while (word_temp->next_c != NULL) {
                word_temp = word_temp->next_c;
            }

            word_temp->next_c = new->next_c;
            if (temp->prev_c != NULL) {
                temp->prev_c->next_c = word;
            } else {
                head = word;
                print_c(head);
                temp = word;
                print_c(temp);
                word->prev_c = NULL;
            }
        }
        temp = temp->next_c;
    }
    printf("\n");
    return head;
}

string *String(char *str) {
    string *st = NULL;
    int i = 0;
    while (str[i] != '\0') {
        append_c(&st, str[i]);
        i++;
    }
    return st;
}

string *input() {
    char *a = (char *)malloc(sizeof(char));
    scanf("%[^\n]", a); //maximum of 1408
    string *stri = String(a);
    return stri;
    free(a);
}

int main() {
    string *list = NULL;

    string *big_boy_string = input();
    print_c(replace_all1(big_boy_string, "a", "b"));
}

问题分析 #

1. compare函数逻辑缺陷：
   • 未检查链表节点是否为空，若链表长度短于目标串会触发空指针访问。
   • 字符不匹配时未立即终止循环，存在无效遍历逻辑，可能导致错误的匹配判断。
2. replace_all1函数遍历逻辑错误：
   • 替换完成后，temp仍从原目标串起始节点的下一个节点开始遍历，若替换串与目标串长度不同，会导致遍历错位，无法匹配后续连续目标串。
   • 非头节点替换时未设置替换串的prev指针，导致双向链表的prev链断裂。
3. input函数内存问题：
   • free(a)在return之后，永远无法执行，造成内存泄漏。
   • 仅分配1个char空间，必然触发缓冲区溢出。

修复方案 #

1. 修复compare函数 #

增加空指针检查，字符不匹配立即返回0，逻辑更严谨：

int compare(string *head, char *word) {
    string *temp = head;
    int len = strlen(word);
    for (int i = 0; i < len; i++) {
        // 链表提前结束或字符不匹配，直接返回0
        if (temp == NULL || temp->value_c != word[i]) {
            return 0;
        }
        temp = temp->next_c;
    }
    return 1;
}

2. 修复replace_all1函数 #

调整遍历逻辑，替换后跳转到替换串末尾确保后续遍历正确；完善双向链表的prev指针设置；添加原节点释放逻辑避免内存泄漏：

string *replace_all1(string *head, char *what, char *with_what) {
    string *temp = head;
    int what_len = strlen(what);
    int with_len = strlen(with_what);
    
    while (temp != NULL) {
        if (compare(temp, what) == 1) {
            // 定位目标串的末尾节点
            string *target_end = temp;
            for (int i = 0; i < what_len - 1; i++) {
                target_end = target_end->next_c;
            }
            string *next_node = target_end->next_c; // 保存目标串后的节点
            
            // 创建替换串链表
            string *word = NULL;
            for (int i = 0; i < with_len; i++) {
                append_c(&word, with_what[i]);
            }
            
            // 定位替换串末尾节点
            string *word_temp = word;
            while (word_temp->next_c != NULL) {
                word_temp = word_temp->next_c;
            }
            
            // 连接双向链表
            word_temp->next_c = next_node;
            if (next_node != NULL) {
                next_node->prev_c = word_temp;
            }
            
            if (temp->prev_c != NULL) {
                // 非头节点：连接前驱与替换串
                temp->prev_c->next_c = word;
                word->prev_c = temp->prev_c;
            } else {
                // 头节点：更新链表头
                head = word;
                word->prev_c = NULL;
            }
            
            // 释放原目标串节点，避免内存泄漏
            string *to_free = temp;
            while (to_free != next_node) {
                string *next_free = to_free->next_c;
                free(to_free);
                to_free = next_free;
            }
            
            // 将temp设置为替换串末尾，下一次遍历从原目标串之后开始
            temp = word_temp;
        }
        temp = temp->next_c;
    }
    return head;
}

3. 修复input函数 #

调整free位置，分配足够空间：

string *input() {
    // 分配足够空间避免溢出，可根据需求调整大小
    char *a = (char *)malloc(1024 * sizeof(char));
    if (a == NULL) {
        perror("malloc failed");
        exit(1);
    }
    scanf("%[^\n]", a);
    string *stri = String(a);
    free(a); // 移至return前，确保执行
    return stri;
}

测试验证 #

输入whatwhat is the weather today?，替换what为how，将得到howhow is the weather today?，连续的目标串均能被正确替换。

内容的提问来源于stack exchange，提问作者Bambi2k21