递归实现C语言Flood Fill算法时遭遇栈溢出错误求助

栈溢出的原因 #

递归版Flood Fill在处理大图像或大面积连续区域时，会产生极深的调用栈——每次递归都会向栈中压入函数参数和局部变量，当调用栈深度超过系统默认的栈大小限制时，就会触发栈溢出错误。你的代码中每次递归都会调用四个方向，调用栈深度可能等于需要填充的像素总数，这在处理稍大的图像时很容易触发溢出。

解决方法 #

1. 改用迭代版Flood Fill（推荐） #

用堆内存的队列或栈模拟递归逻辑，堆的内存空间远大于栈，从根本上避免栈溢出。下面是基于BFS（广度优先搜索）的迭代实现：

#include "flood_fill.h"
#include <stdbool.h>
#include <stdlib.h>
#include "util.h"

// 存储像素坐标的结构体
typedef struct {
    int x;
    int y;
} coord_t;

void flood(image_t *img, int x, int y, pixel_t *target_color) {
    // 检查起始坐标是否越界
    if (x < 0 || y < 0 || x >= img->w || y >= img->h) return;

    // 保存起始点的原始颜色（后续会被覆盖，必须先存）
    pixel_t original_color = img->img[y * img->w + x];
    
    // 目标颜色与原始颜色相同，无需填充
    if (original_color.r == target_color->r &&
        original_color.g == target_color->g &&
        original_color.b == target_color->b) {
        return;
    }

    // 初始化队列：分配能容纳所有像素的内存（最坏情况）
    coord_t *queue = malloc(sizeof(coord_t) * img->w * img->h);
    if (!queue) return; // 内存分配失败直接返回

    int front = 0, rear = 0;
    // 起始点入队，并标记为目标颜色
    queue[rear++] = (coord_t){x, y};
    img->img[y * img->w + x] = *target_color;

    // 处理队列中的所有坐标
    while (front < rear) {
        coord_t curr = queue[front++];
        int cx = curr.x;
        int cy = curr.y;

        // 处理右侧像素
        if (cx + 1 < img->w) {
            pixel_t *curr_pixel = &img->img[cy * img->w + cx + 1];
            if (curr_pixel->r == original_color.r &&
                curr_pixel->g == original_color.g &&
                curr_pixel->b == original_color.b) {
                *curr_pixel = *target_color;
                queue[rear++] = (coord_t){cx + 1, cy};
            }
        }

        // 处理左侧像素
        if (cx - 1 >= 0) {
            pixel_t *curr_pixel = &img->img[cy * img->w + cx - 1];
            if (curr_pixel->r == original_color.r &&
                curr_pixel->g == original_color.g &&
                curr_pixel->b == original_color.b) {
                *curr_pixel = *target_color;
                queue[rear++] = (coord_t){cx - 1, cy};
            }
        }

        // 处理下方像素
        if (cy + 1 < img->h) {
            pixel_t *curr_pixel = &img->img[(cy + 1) * img->w + cx];
            if (curr_pixel->r == original_color.r &&
                curr_pixel->g == original_color.g &&
                curr_pixel->b == original_color.b) {
                *curr_pixel = *target_color;
                queue[rear++] = (coord_t){cx, cy + 1};
            }
        }

        // 处理上方像素
        if (cy - 1 >= 0) {
            pixel_t *curr_pixel = &img->img[(cy - 1) * img->w + cx];
            if (curr_pixel->r == original_color.r &&
                curr_pixel->g == original_color.g &&
                curr_pixel->b == original_color.b) {
                *curr_pixel = *target_color;
                queue[rear++] = (coord_t){cx, cy - 1};
            }
        }
    }

    free(queue); // 释放队列内存，避免内存泄漏
}

2. 递归优化（仅临时缓解） #

如果坚持用递归，可以调整递归顺序（比如先处理两个方向，再处理另外两个），或者通过编译器命令增大栈大小（例如GCC用-Wl,--stack,10485760指定10MB栈），但这种方法依赖系统环境，且处理大图像时仍可能溢出，不推荐。

纠正你的malloc错误 #

你尝试给current_color分配内存的写法完全错误：

pixel_t* current_color = malloc((&img->img[y * img->w + x]) * sizeof(pixel_t));

&img->img[y * img->w + x]是获取像素的地址（一个整数），用它乘以sizeof(pixel_t)会得到一个异常大的数值，导致malloc申请巨量内存，必然失败。

实际上你根本不需要malloc——current_color只需要指向图像中已经存在的像素，原代码里的：

pixel_t* current_color = &img->img[y * img->w + x];

是完全正确的，直接使用即可。

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