C语言递归遍历BMP红色像素栈溢出：500×500像素场景崩溃解决

你编写的递归扫描红色像素（充电站）代码在小图上运行正常，但处理500×500像素的图像时崩溃，核心原因是递归深度超出栈内存限制，同时链表操作存在效率问题，以下是具体修复方案：

问题根源 #

当图像存在大面积连续红色像素时，递归调用的深度会急剧增加（比如500×500全红区域，递归深度可达数万级），而程序默认栈内存大小有限（通常仅几MB），大量栈帧堆积会直接触发栈溢出崩溃。此外，原链表每次追加都遍历到尾部的操作，会让大尺寸图像的处理效率极低。

修复方案 #

1. 用迭代式DFS/BFS替代递归 #

把递归实现的深度优先搜索改成用栈（DFS）或队列（BFS）模拟，彻底避免栈溢出问题：

#include <stdlib.h>

// 辅助栈结构，存储像素坐标
typedef struct StackNode {
    int x;
    int y;
    struct StackNode* next;
} StackNode;

// 入栈操作
void push(StackNode** stack, int x, int y) {
    StackNode* newNode = (StackNode*)malloc(sizeof(StackNode));
    newNode->x = x;
    newNode->y = y;
    newNode->next = *stack;
    *stack = newNode;
}

// 出栈操作，返回1表示成功，0表示栈空
int pop(StackNode** stack, int* x, int* y) {
    if (*stack == NULL) return 0;
    StackNode* temp = *stack;
    *x = temp->x;
    *y = temp->y;
    *stack = temp->next;
    free(temp);
    return 1;
}

// 迭代式扫描单个充电站
pix_t* map_one_charger(unsigned char** map, int start_x, int start_y, int h, int w) {
    if (start_x < 0 || start_x >= w || start_y < 0 || start_y >= h || map[start_y][start_x] == 1) {
        return NULL;
    }

    pix_t* head = NULL;
    pix_t* tail = NULL;
    StackNode* stack = NULL;

    // 标记起始点并入栈
    map[start_y][start_x] = 1;
    push(&stack, start_x, start_y);

    int x, y;
    while (pop(&stack, &x, &y)) {
        // 创建新的坐标节点
        pix_t* newNode = (pix_t*)malloc(sizeof(pix_t));
        newNode->x_y_cordinates.x = x;
        newNode->x_y_cordinates.y = y;
        newNode->next = NULL;

        // 用尾指针直接追加到链表，避免遍历
        if (head == NULL) {
            head = newNode;
            tail = newNode;
        } else {
            tail->next = newNode;
            tail = newNode;
        }

        // 处理四个方向的相邻像素
        // 右
        if (x + 1 < w && map[y][x + 1] != 1) {
            map[y][x + 1] = 1;
            push(&stack, x + 1, y);
        }
        // 左
        if (x - 1 >= 0 && map[y][x - 1] != 1) {
            map[y][x - 1] = 1;
            push(&stack, x - 1, y);
        }
        // 下
        if (y + 1 < h && map[y + 1][x] != 1) {
            map[y + 1][x] = 1;
            push(&stack, x, y + 1);
        }
        // 上
        if (y - 1 >= 0 && map[y - 1][x] != 1) {
            map[y - 1][x] = 1;
            push(&stack, x, y - 1);
        }
    }

    return head;
}

2. 优化链表追加操作 #

原add_to_pixel_list每次都遍历到链表尾部，时间复杂度为O(n²)，大尺寸图像下效率极低。上面的迭代代码已经通过尾指针直接追加，把时间复杂度降到O(1)。如果要保留原链表结构，也可以修改函数如下：

// 优化后的链表追加，传入尾指针直接完成追加
void add_to_pixel_list(pix_t** tail, pix_t* to_add) {
    (*tail)->next = to_add;
    // 更新尾指针到新节点的末尾
    while ((*tail)->next != NULL) {
        *tail = (*tail)->next;
    }
}

3. 内存泄漏检查 #

使用完链表后，务必遍历释放所有pix_t节点，避免长期运行导致内存耗尽：

void free_pixel_list(pix_t** head) {
    pix_t* temp;
    while (*head != NULL) {
        temp = *head;
        *head = (*head)->next;
        free(temp);
    }
}

关键说明 #

• 迭代式DFS/BFS完全绕过了递归栈的限制，无论图像多大都不会出现栈溢出；
• 尾指针优化让链表操作效率大幅提升，处理500×500图像时速度会显著加快；
• 记得在程序结束或不需要链表时释放内存，避免内存泄漏累积。

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