C语言递归函数引发Segmentation Fault错误排查及循环检测需求

我有一个存储胜者（winner）和败者（loser）的pair结构体数组，败者可能在其他pair中作为胜者，且一个败者可能对应多个以其为胜者的pair。我需要检测这类胜负链是否形成循环（loop）：若不存在循环，将二维数组locked的对应pair位置设为true；若存在循环则设为false。但程序运行时出现Segmentation Fault（段错误），无法定位原因。

#include <stdio.h>
#include <stdbool.h>
#define MAX 5

int preferences[MAX][MAX] = {0};

bool locked[MAX][MAX];

bool visited[MAX][MAX];

typedef struct
{
    int winner;
    int loser;
} pair;

pair pairs[] ={{0,2}, {0,1}, {0,3}, {1,2}, {0,4}, {3,1}, {3,2}, {3,4}, {4,1}, {4,2}};
int pair_count = MAX*(MAX - 1)/2;

void clear_workspace(void);
bool check_for_loop(int start, int end);
bool branches(int loser, int arr[]);
void lock_pairs(void);

int main(void)
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            locked[i][j] = false;
        }
    }
    lock_pairs();
}
void lock_pairs(void)
{
    for (int i = 0;i < pair_count;i++)
    {
        int start = pairs[i].winner;
        int end = pairs[i].loser;
        clear_workspace();
        if(check_for_loop(start, end) == false)
        {
            locked[start][end] = true;
        }
    }
}
bool check_for_loop(int start, int end)
{
    visited[start][end] = true;
    int arr[MAX * MAX] = {-1};
    if (branches(end,arr) == true)
    {
        for (int i = 0;i < MAX;i++)
        {
            if (arr[i] != -1 && visited[end][arr[i]] == true)
            {
                return true;
            }
            if (arr[i] != -1 && check_for_loop(start, arr[i]) == true)
            {
                return true;
            }
        }
    }
    return false;
}
bool branches(int loser, int arr[])
{
    int arr_index;
    arr_index = 0;
    int flag = 0;
    for (int i = 0;i < pair_count;i++)
    {
        if (pairs[i].winner == loser)
        {
            arr[arr_index] = pairs[i].winner;
            arr_index++;
            flag = 1;
        }
    }
    for (int i = arr_index;i < MAX;i++)
    {
        arr[i] = -1;
    }
    if (flag == 1)
    {
        return true;
    }
    else
    {
        return false;
    }
}
void clear_workspace(void)
{
    for (int i = 0;i < MAX;i++)
    {
        for (int j = 0;j < MAX;j++)
        {
            visited[i][j] = false;
        }
    }
}

1. 核心逻辑错误：branches函数赋值错误 #

在branches函数中，需要收集当前loser作为胜者时击败的对象（即新的败者），但代码错误地将pairs[i].winner存入数组，导致后续递归追踪同一个节点（当前loser自己），引发逻辑混乱甚至死循环。

修复：将arr[arr_index] = pairs[i].winner;改为arr[arr_index] = pairs[i].loser;

2. 循环检测逻辑缺失：未判断是否回到起点 #

当前check_for_loop函数没有检测是否回到初始的start节点，这是判断循环的核心条件——从start出发最终回到start即形成循环。

修复：在check_for_loop函数开头添加判断：

if (end == start) {
    return true;
}

3. Visited数组使用错误：追踪节点而非边 #

原代码用二维visited数组标记边是否被访问，但实际需要追踪路径中的节点是否被访问，避免重复遍历导致栈溢出（段错误的主要原因之一）。

修复：将二维visited[MAX][MAX]改为一维visited[MAX]，并修改相关函数逻辑：

• clear_workspace改为重置一维数组：

void clear_workspace(void)
{
    for (int i = 0;i < MAX;i++)
    {
        visited[i] = false;
    }
}

• check_for_loop中标记当前节点为已访问，并添加回溯逻辑：

bool check_for_loop(int start, int end)
{
    if (end == start) {
        return true;
    }
    if (visited[end]) {
        return false;
    }
    visited[end] = true;
    
    int arr[MAX * MAX] = {-1};
    if (branches(end, arr) == true)
    {
        for (int i = 0; arr[i] != -1; i++)
        {
            if (check_for_loop(start, arr[i]) == true)
            {
                return true;
            }
        }
    }
    visited[end] = false;
    return false;
}

4. 数组遍历边界错误 #

原check_for_loop中固定循环MAX次，但实际有效元素可能少于MAX，改为遍历到arr[i] != -1即可，避免访问无效元素。

#include <stdio.h>
#include <stdbool.h>
#define MAX 5

int preferences[MAX][MAX] = {0};

bool locked[MAX][MAX];

bool visited[MAX]; // 修改为一维数组，标记节点是否被访问

typedef struct
{
    int winner;
    int loser;
} pair;

pair pairs[] ={{0,2}, {0,1}, {0,3}, {1,2}, {0,4}, {3,1}, {3,2}, {3,4}, {4,1}, {4,2}};
int pair_count = MAX*(MAX - 1)/2;

void clear_workspace(void);
bool check_for_loop(int start, int end);
bool branches(int loser, int arr[]);
void lock_pairs(void);

int main(void)
{
    for (int i = 0; i < MAX; i++)
    {
        for (int j = 0; j < MAX; j++)
        {
            locked[i][j] = false;
        }
    }
    lock_pairs();
    
    // 可选：打印locked数组验证结果
    printf("Locked array:\n");
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            printf("%d ", locked[i][j]);
        }
        printf("\n");
    }
}

void lock_pairs(void)
{
    for (int i = 0;i < pair_count;i++)
    {
        int start = pairs[i].winner;
        int end = pairs[i].loser;
        clear_workspace();
        if(check_for_loop(start, end) == false)
        {
            locked[start][end] = true;
        }
    }
}

bool check_for_loop(int start, int end)
{
    // 终止条件：回到起点，形成循环
    if (end == start) {
        return true;
    }
    // 已访问过该节点，无需继续遍历
    if (visited[end]) {
        return false;
    }
    visited[end] = true;
    
    int arr[MAX * MAX] = {-1};
    if (branches(end, arr) == true)
    {
        // 遍历所有后续节点，直到遇到-1
        for (int i = 0; arr[i] != -1; i++)
        {
            if (check_for_loop(start, arr[i]) == true)
            {
                return true;
            }
        }
    }
    // 回溯，取消节点访问标记
    visited[end] = false;
    return false;
}

bool branches(int loser, int arr[])
{
    int arr_index = 0;
    int flag = 0;
    for (int i = 0;i < pair_count;i++)
    {
        if (pairs[i].winner == loser)
        {
            // 存入当前胜者击败的败者，而非胜者自己
            arr[arr_index] = pairs[i].loser;
            arr_index++;
            flag = 1;
        }
    }
    // 末尾补-1，标记数组结束
    arr[arr_index] = -1;
    return flag == 1;
}

void clear_workspace(void)
{
    for (int i = 0;i < MAX;i++)
    {
        visited[i] = false;
    }
}

内容的提问来源于stack exchange，提问作者Level-0