如何实现C函数contains_cycle检测void*数组中的循环？

我需要实现C函数int contains_cycle(void *const array[], size_t length)，用来检测void指针数组里是否存在循环。数组里的元素要么指向数组内的某个元素地址，要么是NULL。我对指针不太熟悉，不知道怎么入手。

为明确循环定义，举几个例子（假设数组首元素地址为0x1，指针大小为1字节）：

• {NULL, 0x3, 0x2} → 返回1，array[1]和array[2]之间存在循环
• {0x2, 0x3, 0x1} → 返回1，所有元素构成循环
• {0x2, 0x3, NULL} → 返回0，无循环

我的思路是遍历数组，追踪指针看是否回到起点，只要有一个元素满足就说明存在循环。

核心思路与实现步骤 #

关键前提：指针转数组下标 #

数组中合法的指针必然指向数组内某个元素的地址，我们需要先把指针转换成对应的数组下标——这是整个检测的基础。比如数组首地址是array，array[i]的地址是(char*)array + i * sizeof(void*)，所以反过来计算下标：

size_t index = ((char*)ptr - (char*)array) / sizeof(void*);

同时要检查指针是否在数组的地址范围内（[array, array + length * sizeof(void*))），避免无效指针干扰。

高效检测循环：快慢指针法 #

比起逐个追踪起点是否重复，用**Floyd判圈算法（快慢指针）**更高效：慢指针每次走一步，快指针每次走两步，如果两者相遇，说明存在循环；如果走到NULL或无效指针，说明这条路径无循环。

完整代码实现 #

#include <stddef.h>

// 辅助函数：获取当前下标对应的下一个有效下标，无效则返回length作为标记
static size_t get_next_index(void *const array[], size_t length, size_t current) {
    void *ptr = array[current];
    if (ptr == NULL) {
        return length;
    }
    // 检查指针是否在数组的合法地址范围内
    if ((char*)ptr < (char*)array || (char*)ptr >= (char*)array + length * sizeof(void*)) {
        return length;
    }
    // 计算对应的数组下标
    size_t index = ((char*)ptr - (char*)array) / sizeof(void*);
    // 二次校验下标合法性，避免地址计算误差
    return (index < length) ? index : length;
}

int contains_cycle(void *const array[], size_t length) {
    if (length == 0) {
        return 0; // 空数组直接返回无循环
    }

    // 遍历每个元素作为起点检测循环
    for (size_t i = 0; i < length; i++) {
        size_t slow = i;
        size_t fast = get_next_index(array, length, i);

        // 快慢指针移动，直到遇到无效下标或相遇
        while (slow != length && fast != length && get_next_index(array, length, fast) != length) {
            if (slow == fast) {
                return 1; // 找到循环，直接返回
            }
            slow = get_next_index(array, length, slow);
            fast = get_next_index(array, length, get_next_index(array, length, fast));
        }
    }

    return 0; // 所有路径都无循环
}

代码说明 #

1. 合法性校验：确保只处理指向数组内部的有效指针，排除NULL和越界指针。
2. 快慢指针逻辑：时间复杂度O(n)，空间复杂度O(1)，无需额外内存记录访问轨迹。
3. 边界处理：空数组直接返回0，遇到无效指针立即终止当前路径的检测，避免无效遍历。

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