基于数组实现的C语言字典删除功能BUG修复求助

问题描述 #

当前实现的字典使用数组+索引链表维护有序结构，添加功能正常，但删除功能存在以下问题：

• 删除中间元素时功能正常；
• 删除第一个元素时，会误删其他所有元素仅保留第一个；
• 删除最后一个元素时，程序会陷入死循环。

预期删除逻辑：将待删除元素与最后一个元素交换，删除最后一个元素，再为交换后的元素找到正确位置。

问题根源分析 #

1. 删除尾元素判断错误：原代码先执行size--，再判断delete_index == size，此时size已经是原最后一个元素索引的前一位，导致本该进入尾元素处理的逻辑进入了交换分支，错误修改next指针造成死循环。
2. 交换元素后未重新排序：将最后一个元素移到待删位置后，直接复用原待删位置的next指针，没有重新将该元素插入到有序链表的正确位置，破坏了链表的有序性，同时导致指针指向混乱。
3. 首元素删除后的指针维护缺失：删除首元素时，仅修改了start，但未处理原最后一个元素在链表中的原有指针，造成链表断裂或循环。

修复后的完整代码 #

#include <stdio.h> 
#include <string.h> 
#include <ctype.h> // 补充tolower所需头文件

#define MAX_SIZE 10 
#define WORD_SIZE 20 

struct dictionary { 
    char english[WORD_SIZE]; 
    char turkish[WORD_SIZE]; 
}; 

int main() { 
    struct dictionary dict[MAX_SIZE]; 
    int next[MAX_SIZE]; 
    int size = 0; 
    int start = -1; 

    char input[WORD_SIZE]; 
    int choice = 0; 

    // 初始化next数组
    for (int i = 0; i < MAX_SIZE; i++) { 
        next[i] = i + 1; 
    } 
    next[MAX_SIZE - 1] = -1; 

    // 菜单循环
    while (choice != 4) { 
        printf("\n\nDictionary Menu:\n"); 
        printf("1. Add a word\n"); 
        printf("2. Delete a word\n"); 
        printf("3. View the dictionary\n"); 
        printf("4. Quit\n"); 

        printf("\nEnter your choice: "); 
        scanf("%d", &choice); 

        switch (choice) { 
            case 1: 
                if (size >= MAX_SIZE) { 
                    printf("The dictionary is full.\n"); 
                } else { 
                    // 添加新单词
                    printf("Enter the English word: "); 
                    scanf("%s", input); 
                    // 转为小写
                    for (int i = 0; i < strlen(input); i++) { 
                        input[i] = tolower(input[i]); 
                    } 
                    strcpy(dict[size].english, input); 

                    printf("Enter the Turkish word: "); 
                    scanf("%s", input); 
                    strcpy(dict[size].turkish, input); 

                    // 找到新单词的正确位置
                    int curr = start; 
                    int prev = -1; 
                    while (curr != -1 && strcmp(dict[curr].english, dict[size].english) < 0) { 
                        prev = curr; 
                        curr = next[curr]; 
                    } 

                    // 将新单词插入正确位置
                    if (prev == -1) { 
                        next[size] = start; 
                        start = size; 
                    } else { 
                        next[prev] = size; 
                        next[size] = curr; 
                    } 
                    size++; 
                    printf("Word added successfully.\n"); 
                } 
                break; 
                
            case 2: 
                if (size == 0) { 
                    printf("The dictionary is empty.\n"); 
                } else { 
                    // 删除单词
                    printf("Enter the English word to delete: "); 
                    scanf("%s", input); 
                    // 转为小写
                    for (int i = 0; i < strlen(input); i++) { 
                        input[i] = tolower(input[i]); 
                    } 

                    int curr = start; 
                    int prev = -1; 
                    int delete_index = -1; 
                    int last_prev = -1; // 记录最后一个元素的前驱节点

                    // 同时找到待删元素和最后一个元素的前驱
                    while (curr != -1) { 
                        if (strcmp(dict[curr].english, input) == 0) { 
                            delete_index = curr; 
                        }
                        if (next[curr] == -1) {
                            last_prev = prev;
                        }
                        prev = curr; 
                        curr = next[curr]; 
                    } 

                    if (delete_index == -1) { 
                        printf("The word '%s' is not in the dictionary.\n", input); 
                    } else { 
                        int last_idx = size - 1;
                        // 情况1：待删元素就是最后一个元素
                        if (delete_index == last_idx) {
                            if (last_prev == -1) {
                                // 只有一个元素
                                start = -1;
                            } else {
                                next[last_prev] = -1;
                            }
                            size--;
                        } else {
                            // 情况2：待删元素不是最后一个，先移除最后一个元素在原链表中的位置
                            if (last_prev == -1) {
                                // 最后一个元素是首元素
                                start = next[last_idx];
                            } else {
                                next[last_prev] = next[last_idx];
                            }

                            // 把最后一个元素复制到待删位置
                            strcpy(dict[delete_index].english, dict[last_idx].english);
                            strcpy(dict[delete_index].turkish, dict[last_idx].turkish);

                            // 重新为这个元素找到正确的插入位置（复用添加时的逻辑）
                            int new_curr = start;
                            int new_prev = -1;
                            while (new_curr != -1 && strcmp(dict[new_curr].english, dict[delete_index].english) < 0) {
                                new_prev = new_curr;
                                new_curr = next[new_curr];
                            }

                            // 插入到正确位置
                            if (new_prev == -1) {
                                next[delete_index] = start;
                                start = delete_index;
                            } else {
                                next[new_prev] = delete_index;
                                next[delete_index] = new_curr;
                            }

                            size--;
                        }
                        printf("The word '%s' has been deleted from the dictionary.\n", input); 
                    } 
                } 
                break; 
            case 3: 
                if (size == 0) { 
                    printf("The dictionary is empty.\n"); 
                } else { 
                    // 打印所有单词
                    printf("English\tTurkish\n"); 
                    printf("-----------------\n"); 
                    int curr = start; 
                    while (curr != -1) { 
                        printf("%s\t%s\n", dict[curr].english, dict[curr].turkish); 
                        curr = next[curr]; 
                    } 
                } 
                break; 
            case 4: 
                printf("Goodbye!\n"); 
                break; 
            default: 
                printf("Invalid choice.\n"); 
        } 
    } 

    return 0; 
}

关键修改说明 #

1. 补充头文件：添加<ctype.h>，解决tolower函数的隐式声明问题。
2. 修复尾元素判断：先获取原最后一个元素索引last_idx = size - 1，直接判断待删索引是否等于该值，避免size--后的判断错误。
3. 移除原最后一个元素的链表节点：在交换前，先把原最后一个元素从链表中移除，避免指针残留导致循环。
4. 重新插入交换后的元素：复用添加功能中的有序插入逻辑，将交换到待删位置的元素重新插入到正确的排序位置，保证链表的有序性。
5. 维护首元素指针：处理最后一个元素是首元素的情况，正确更新start指针，避免链表断裂。

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