C语言链表添加元素时被覆盖而非追加的问题排查

问题现象 #

用C语言实现的链表管理程序，通过全局指针struct Node *dict维护链表。创建新链表功能正常，但向已有链表追加元素时，原有链表会被覆盖，仅显示最后添加的元素。例如先创建包含“apple orange peach”的链表，再添加“pear”，输出仅显示“pear”。

原添加逻辑代码片段：

if (dict == NULL) { // If previous list does not exist, global dict pointer should point to node array
    dict = words;
} else {  // Else find end of current linked list and point it to the new list
    struct Node *head = dict;
    while (head->next != NULL) {
        head = head->next;
    }
    head->next = words;
}

完整错误代码：

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

//// GUI Stuff ////
void drawDashedLine() {
    for (int i = 0; i < 30; i++) {
        printf("-");
    }
    printf("\n");
}
void drawDottedLine() {
    for (int i = 0; i < 30; i++) {
        printf(".");
    }
    printf("\n");
}
void drawArrowLine() {
    for (int i = 0; i < 30; i++) {
        printf(">");
    }
    printf("\n");
}
void drawStarLine() {
    for (int i = 0; i < 30; i++) {
        printf("*");
    }
    printf("\n");
}

struct Node {
    int length;
    char word[5];
    struct Node * next;
};
// Pointer to global linked list dictionary
struct Node *dict;

struct Node *newDict;


void printDict() {
    drawDottedLine();
    struct Node * head = dict;
    while (head != NULL) {
        printf("%s\n", head->word);
        head = head->next;
    }
    drawDottedLine();
    return;
}
void alphabetizeDict() { // Bubble sort
    //printf("%p --- %p\n", dict, dict->next);
    struct Node * head = dict;
    if (head == NULL) {
        return;
    }
    struct Node * ptr2 = NULL;

    int swapped = 1;
    while (swapped) {
        swapped = 0;
        head = dict;
        while (head->next != ptr2) {
            char * temp1 = strdup(head->word);
            char * temp2 = strdup(head->next->word);

            strupr(temp1);
            strupr(temp2);
            if (strcmp(temp1, temp2) > 0) {
                char temp[5];
                strcpy(temp, head->word);
                strcpy(head->word, head->next->word);
                strcpy(head->next->word, temp);
                swapped = 1;
            }
            head = head->next;
        }
        ptr2 = head;
    }
    return;
}
void createDict() {
    // To hold the string entered by the user
    char str[5000];
    // Holds 1000 words, each up to 5 characters long (4 plus a NULL char)
    char newString[1000][5];
    printf("\n");
    drawArrowLine();
    printf("Enter word(s): \n");
    fgets(str, sizeof str, stdin);

    int i, j, ctr;
    j = 0;
    ctr = 0; // ctr to iterate through words, j to iterate through letters
    for (i = 0; i <= (strlen(str)); i++) {
        if (str[i] == ' ' || str[i] == '\0') { // This is whitespace. add null character to terminate string. Start next word
            newString[ctr][j] = '\0';
            ctr++;
            j = 0;
        } else { // Else add letter to string
            newString[ctr][j] = str[i];
            j++;
        }
    }
    
        for (int i = 0; i < ctr; i++) {
            struct Node n;
            n.length = strlen(newString[i]);
            int c = 0;
            char sub[5];
            // Only use word's first four letters
            while (c < strlen(newString[i]) && c < 4) {
                sub[c] = newString[i][c];
                c++;
            }
            sub[c] = '\0';
            strcpy(n.word, sub);
            n.next = NULL;
            
            if (dict == NULL) {
                dict = &n;
            } else {
                n.next = dict;
                dict = &n;
                }
        }
    

        
    // alphabetizeDict();
    printf("Word(s) added succesfully\n");
    drawArrowLine();
    printf("\n");
    return;
}

void destroyDict() {
    printf("Starting new dictionary......\n");
    while (dict != NULL) {
        struct Node * temp = dict;
        dict = dict->next;
        temp->next = NULL;
    }
}
void caseInsensSearch(char * searchTerm) {
    for (int i = 0; searchTerm[i]; i++) {
        searchTerm[i] = tolower(searchTerm[i]);
    }
    struct Node * head = dict;
    int index = 0;
    while (head != NULL) {
        char lowercaseWord[5];
        for (int i = 0; head->word[i]; i++) {
            lowercaseWord[i] = tolower(head->word[i]);
        }
        if (strcmp(lowercaseWord, searchTerm) == 0) {
            printf("Found %s at index %i\n", head->word, index);
            drawDashedLine();
            return;
        }
        head = head->next;
        index++;
    }
    printf("Sorry, I couldn't find %s in your dictionary.\n", searchTerm);
    drawDashedLine();
    return;
}
void caseSensSearch(char * searchTerm) {
    struct Node * head = dict;
    int index = 0;
    while (head != NULL) {
        if (strcmp(head->word, searchTerm) == 0) {
            printf("Found %s at index %i\n", head->word, index);
            drawDashedLine();
            return;
        }
        head = head->next;
        index++;
    }
    printf("Sorry, I couldn't find %s in your dictionary.\n", searchTerm);
    drawDashedLine();
    return;
}

void search() {
    int isSens;
    drawDashedLine();
    printf("Enter 1 for Case sensitive\n2 for case insensitive\n");
    drawDashedLine();
    scanf("%d", & isSens);
    while (isSens < 1 || isSens > 2) {
        printf("Please enter a number between 1 and 2:\n");
        scanf("%d", & isSens);
    }
    drawDashedLine();
    printf("Enter a word to search for:\n");
    char searchTerm[5];
    scanf("%s", searchTerm);
    searchTerm[4] = '\0';
    if (isSens == 1) {
        caseSensSearch(searchTerm);
    } else {
        caseInsensSearch(searchTerm);
    }
}

int promptUser() {
    drawStarLine();
    printf("1) Search for a word\n2) Add word(s)\n3) Print dictionary\n4) Start new dictionary\n5) Exit\n");
    drawStarLine();
    printf("\nEnter a number between 1 and 5:\n");

    int choice;
    scanf("%1d", & choice);
    while (choice < 1 || choice > 5) {
        printf("Please enter a number between 1 and 5:\n");
        scanf("%d", & choice);
    }
    return choice;
}

int main() {

    for (;;) {
        int choice = promptUser();
        fflush(stdin);
        if (choice == 1) {
            search();
        } else if (choice == 2) {
            createDict();
        } else if (choice == 3) {
            printDict();
        } else if (choice == 4) {
            destroyDict();
        } else if (choice == 5) {
            return 0;
        }
    }

    return 1;
}

错误原因 #

1. 局部变量内存失效：在createDict函数中，struct Node n是栈上的局部变量，函数执行完毕后，栈内存会被回收。此时dict指向的是已释放的内存地址，成为野指针，后续操作会导致未定义行为。
2. 追加逻辑错误：原代码中每次添加新节点时，都是将新节点的next指向当前dict，然后让dict指向新节点（头插逻辑），但由于节点是局部变量，每次调用createDict都会覆盖之前的栈内存，最终只剩最后一个节点的无效地址。

修复方案 #

1. 使用malloc动态分配每个节点的内存，确保节点在堆上，函数结束后不会被释放。
2. 实现正确的尾插逻辑（追加到链表尾部），符合用户追加元素的需求。

修复后的createDict函数 #

void createDict() {
    // To hold the string entered by the user
    char str[5000];
    // Holds 1000 words, each up to 5 characters long (4 plus a NULL char)
    char newString[1000][5];
    printf("\n");
    drawArrowLine();
    printf("Enter word(s): \n");
    fgets(str, sizeof str, stdin);

    // 处理fgets读取的换行符
    size_t len = strlen(str);
    if (len > 0 && str[len-1] == '\n') {
        str[len-1] = '\0';
    }

    int i, j, ctr;
    j = 0;
    ctr = 0; // ctr to iterate through words, j to iterate through letters
    for (i = 0; i <= (strlen(str)); i++) {
        if (str[i] == ' ' || str[i] == '\0') { // This is whitespace. add null character to terminate string. Start next word
            newString[ctr][j] = '\0';
            // 跳过空单词（比如连续空格的情况）
            if (j > 0) {
                ctr++;
            }
            j = 0;
        } else { // Else add letter to string
            newString[ctr][j] = str[i];
            j++;
        }
    }
    
    for (int i = 0; i < ctr; i++) {
        // 动态分配节点内存
        struct Node *n = (struct Node*)malloc(sizeof(struct Node));
        if (n == NULL) {
            printf("Memory allocation failed!\n");
            return;
        }
        n->length = strlen(newString[i]);
        int c = 0;
        char sub[5];
        // Only use word's first four letters
        while (c < strlen(newString[i]) && c < 4) {
            sub[c] = newString[i][c];
            c++;
        }
        sub[c] = '\0';
        strcpy(n->word, sub);
        n->next = NULL;
        
        // 尾插逻辑：追加到链表末尾
        if (dict == NULL) {
            dict = n;
        } else {
            struct Node *head = dict;
            while (head->next != NULL) {
                head = head->next;
            }
            head->next = n;
        }
    }
    
    // alphabetizeDict();
    printf("Word(s) added successfully\n");
    drawArrowLine();
    printf("\n");
    return;
}

补充修复：完善destroyDict函数 #

原destroyDict未释放动态分配的内存，会导致内存泄漏，修复后：

void destroyDict() {
    printf("Starting new dictionary......\n");
    while (dict != NULL) {
        struct Node * temp = dict;
        dict = dict->next;
        free(temp); // 释放节点内存
    }
}

修复后效果 #

现在添加“apple orange peach”后，再添加“pear”，打印链表会显示：

apple
orange
peach
pear

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