C语言实现区域填充算法 (栈方法)

以下是使用C语言编写的区域填充算法，使用栈实现：

#include <stdio.h>

#define MAX_STACK_SIZE 1000

// 定义坐标结构体
typedef struct {
    int x;
    int y;
} Point;

// 定义栈结构体
typedef struct {
    Point data[MAX_STACK_SIZE];
    int top;
} Stack;

// 初始化栈
void initStack(Stack *stack) {
    stack->top = -1;
}

// 判断栈是否为空
int isStackEmpty(Stack *stack) {
    return stack->top == -1;
}

// 判断栈是否已满
int isStackFull(Stack *stack) {
    return stack->top == MAX_STACK_SIZE - 1;
}

// 入栈
void push(Stack *stack, Point point) {
    if (isStackFull(stack)) {
        printf('Stack is full.\n');
        return;
    }
    stack->data[++stack->top] = point;
}

// 出栈
Point pop(Stack *stack) {
    if (isStackEmpty(stack)) {
        printf('Stack is empty.\n');
        Point point = {0, 0};
        return point;
    }
    return stack->data[stack->top--];
}

// 区域填充
void fill(int x, int y, char oldColor, char newColor, char image[][8]) {
    Stack stack;
    Point point = {x, y};
    initStack(&stack);
    push(&stack, point);
    while (!isStackEmpty(&stack)) {
        point = pop(&stack);
        if (image[point.x][point.y] == oldColor) {
            image[point.x][point.y] = newColor;
            if (point.x > 0) {
                Point north = {point.x - 1, point.y};
                push(&stack, north);
            }
            if (point.x < 7) {
                Point south = {point.x + 1, point.y};
                push(&stack, south);
            }
            if (point.y > 0) {
                Point west = {point.x, point.y - 1};
                push(&stack, west);
            }
            if (point.y < 7) {
                Point east = {point.x, point.y + 1};
                push(&stack, east);
            }
        }
    }
}

int main() {
    char image[8][8] = {
        {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', '*', '*', ' ', ' '},
        {' ', ' ', ' ', ' ', '*', '*', ' ', ' '},
        {' ', ' ', '*', '*', ' ', ' ', ' ', ' '},
        {' ', '*', '*', ' ', ' ', ' ', ' ', ' '},
        {' ', '*', '*', ' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '},
        {' ', ' ', ' ', ' ', ' ', ' ', ' ', ' '}
    };
    printf('Before fill:\n');
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            printf('%c ', image[i][j]);
        }
        printf('\n');
    }
    fill(2, 2, ' ', 'O', image);
    printf('\nAfter fill:\n');
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            printf('%c ', image[i][j]);
        }
        printf('\n');
    }
    return 0;
}

上述程序中，首先定义了一个坐标结构体和一个栈结构体，以便于后续的操作。然后，实现了栈的初始化、判断栈是否为空和已满，入栈和出栈等基本操作。最后，实现了区域填充算法的核心部分，即使用栈实现的迭代方式进行深度优先搜索。程序在填充前后打印了图片，以便于观察填充结果。