农夫过河问题数据结构C语言

好的，这里是一个用 C 语言实现的数据结构代码，它同样使用状态类来表示每个状态：

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

// 定义状态结构体
typedef struct {
    char farmer[6];     // 农夫的位置，"left" 或 "right"
    char wolf[6];       // 狼的位置，"left" 或 "right"
    char sheep[6];      // 羊的位置，"left" 或 "right"
    char cabbage[6];    // 卷心菜的位置，"left" 或 "right"
} State;

// 定义队列结构体
typedef struct {
    State* data[1000];
    int front;
    int rear;
} Queue;

// 初始化队列
void initQueue(Queue* q) {
    q->front = 0;
    q->rear = 0;
}

// 判断队列是否为空
bool isQueueEmpty(Queue* q) {
    return q->front == q->rear;
}

// 判断队列是否已满
bool isQueueFull(Queue* q) {
    return q->rear == 1000;
}

// 入队
void enqueue(Queue* q, State* state) {
    if(!isQueueFull(q)) {
        q->data[q->rear++] = state;
    }
}

// 出队
State* dequeue(Queue* q) {
    if(!isQueueEmpty(q)) {
        return q->data[q->front++];
    }
    return NULL;
}

// 判断状态是否相等
bool isStateEqual(State* state1, State* state2) {
    return strcmp(state1->farmer, state2->farmer) == 0 && strcmp(state1->wolf, state2->wolf) == 0 && strcmp(state1->sheep, state2->sheep) == 0 && strcmp(state1->cabbage, state2->cabbage) == 0;
}

// 判断状态是否可达
bool isStateValid(State* state) {
    if(strcmp(state->sheep, state->wolf) == 0 && strcmp(state->farmer, state->sheep) != 0) {
        return false;
    }
    if(strcmp(state->cabbage, state->sheep) == 0 && strcmp(state->farmer, state->cabbage) != 0) {
        return false;
    }
    return true;
}

// 获取下一个状态
void getNextStates(State* state, State* nextStates[]) {
    int index = 0;
    if(strcmp(state->farmer, "left") == 0) {
        if(strcmp(state->wolf, "left") == 0) {
            State* nextState = (State*)malloc(sizeof(State));
            strcpy(nextState->farmer, "right");
            strcpy(nextState->wolf, "right");
            strcpy(nextState->sheep, state->sheep);
            strcpy(nextState->cabbage, state->cabbage);
            if(isStateValid(nextState)) {
                nextStates[index++] = nextState;
            } else {
                free(nextState);
            }
        }
        if(strcmp(state->sheep, "left") == 0) {
            State* nextState = (State*)malloc(sizeof(State));
            strcpy(nextState->farmer, "right");
            strcpy(nextState->wolf, state->wolf);
            strcpy(nextState->sheep, "right");
            strcpy(nextState->cabbage, state->cabbage);
            if(isStateValid(nextState)) {
                nextStates[index++] = nextState;
            } else {
                free(nextState);
            }
        }
        if(strcmp(state->cabbage, "left") == 0) {
            State* nextState = (State*)malloc(sizeof(State));
            strcpy(nextState->farmer, "right");
            strcpy(nextState->wolf, state->wolf);
            strcpy(nextState->sheep, state->sheep);
            strcpy(nextState->cabbage, "right");
            if(isStateValid(nextState)) {
                nextStates[index++] = nextState;
            } else {
                free(nextState);
            }
        }
        State* nextState = (State*)malloc(sizeof(State));
        strcpy(nextState->farmer, "right");
        strcpy(nextState->wolf, state->wolf);
        strcpy(nextState->sheep, state->sheep);
        strcpy(nextState->cabbage, state->cabbage);
        if(isStateValid(nextState)) {
            nextStates[index++] = nextState;
        } else {
            free(nextState);
        }
    } else {
        if(strcmp(state->wolf, "right") == 0) {
            State* nextState = (State*)malloc(sizeof(State));
            strcpy(nextState->farmer, "left");
            strcpy(nextState->wolf, "left");
            strcpy(nextState->sheep, state->sheep);
            strcpy(nextState->cabbage, state->cabbage);
            if(isStateValid(nextState)) {
                nextStates[index++] = nextState;
            } else {
                free(nextState);
            }
        }
        if(strcmp(state->sheep, "right") == 0) {
            State* nextState = (State*)malloc(sizeof(State));
            strcpy(nextState->farmer, "left");
            strcpy(nextState->wolf, state->wolf);
            strcpy(nextState->sheep, "left");
            strcpy(nextState->cabbage, state->cabbage);
            if(isStateValid(nextState)) {
                nextStates[index++] = nextState;
            } else {
                free(nextState);
            }
        }
        if(strcmp(state->cabbage, "right") == 0) {
            State* nextState = (State*)malloc(sizeof(State));
            strcpy(nextState->farmer, "left");
            strcpy(nextState->wolf, state->wolf);
            strcpy(nextState->sheep, state->sheep);
            strcpy(nextState->cabbage, "left");
            if(isStateValid(nextState)) {
                nextStates[index++] = nextState;
            } else {
                free(nextState);
            }
        }
        State* nextState = (State*)malloc(sizeof(State));
        strcpy(nextState->farmer, "left");
        strcpy(nextState->wolf, state->wolf);
        strcpy(nextState->sheep, state->sheep);
        strcpy(nextState->cabbage, state->cabbage);
        if(isStateValid(nextState)) {
            nextStates[index++] = nextState;
        } else {
            free(nextState);
        }
    }
    nextStates[index] = NULL;
}

// 搜索函数
State** search(State* initialState, State* goalState) {
    Queue q;
    initQueue(&q);

    // 把初始状态加入队列
    State* initialPath[1000] = {initialState};
    enqueue(&q, initialPath[0]);

    while(!isQueueEmpty(&q)) {
        // 取出队首状态
        State* state = dequeue(&q);

        // 如果是目标状态，返回路径
        if(isStateEqual(state, goalState)) {
            return state;
        }

        // 获取下一个状态，并加入队列
        State* nextStates[5];
        getNextStates(state, nextStates);
        for(int i = 0; nextStates[i] != NULL; i++) {
            State* newPath[1000];
            memcpy(newPath, state, sizeof(State*) * 1000);
            newPath[i + 1] = nextStates[i];
            enqueue(&q, newPath[i + 1]);
        }
    }

    return NULL;
}

// 打印状态
void printState(State* state) {
    printf("Farmer:%s Wolf:%s Sheep:%s Cabbage:%s\n", state->farmer, state->wolf, state->sheep, state->cabbage);
}

int main() {
    // 测试
    State initialState = {"left", "left", "left", "left"};
    State goalState = {"right", "right", "right", "right"};
    State** path = search(&initialState, &goalState);
    for(int i = 0; path[i] != NULL; i++) {
        printState(path[i]);
    }
    return 0;
}

这个代码同样使用 BFS 搜索算法来搜索可行路径，使用一个队列来存储状态，使用一个 `isStateValid` 函数来判断状态是否可达，并使用一个 `getNextStates` 函数来获取下一个状态。