C语言随机索引生成函数长密钥下无限循环问题求助

先直接点出你代码里的两个核心问题，这也是长密钥下无限循环的根源：

1. 逻辑顺序完全颠倒 #

你现在的代码是先把索引存入已访问数组，再检查是否重复——这就导致第一次存入后，马上就会匹配到自己，强制进入循环生成新索引。更糟的是，当已访问数组快被填满时（比如im->height是500，已经存了499个），rand()要随机到那唯一剩下的索引概率极低，直接陷入无限循环。

2. 重复检查效率极低 #

每次用线性遍历数组检查重复，当数组元素多的时候（比如接近600个），每次检查都要遍历几百次，不仅慢，还加剧了高负载下的循环问题。

修复后的代码 #

我给你重构了逻辑，同时用布尔数组优化了重复检查的效率：

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

// 建议把已访问标记数组作为参数传入（不推荐全局变量）
int getNewIndex(PPM *im, int initialIndex, bool *isVisited, int *visitedCount) {
    int index;

    // 先判断是否已经没有可用像素了
    if (*visitedCount >= im->height) {
        perror("Cannot encode anymore: pixels limit reached");
        exit(1);
    }

    // 确保初始索引在合法范围内
    index = initialIndex % im->height;
    // 循环找到第一个未被访问的索引
    while (isVisited[index]) {
        index = rand() % im->height;
        // 加个安全计数器，防止极端情况下无限循环
        int safetyCounter = 0;
        while (isVisited[index] && safetyCounter < im->height * 2) {
            index = rand() % im->height;
            safetyCounter++;
        }
        if (safetyCounter >= im->height * 2) {
            perror("Failed to find available index after multiple attempts");
            exit(1);
        }
    }

    // 标记为已访问，更新计数
    isVisited[index] = true;
    (*visitedCount)++;

    return index;
}

使用说明 #

1. 初始化布尔数组：在调用这个函数前，需要先创建一个长度为im->height的布尔数组，初始化为false：

   bool *isVisited = calloc(im->height, sizeof(bool));
   if (!isVisited) {
       perror("Failed to allocate memory for visited array");
       exit(1);
   }
   int visitedCount = 0;
   

2. 密钥与随机序列：长密钥的问题本质是srand(key)的种子会让rand()生成的序列偏向某些区间，重复概率升高。但用布尔数组做O(1)级别的重复检查后，即使随机到重复值也能立刻跳过，不会陷入长时间循环。如果需要更均匀的随机序列，可以考虑用arc4random这类更优的生成器（注意跨平台适配）。

为什么长密钥会触发无限循环？ #

当密钥很长时，srand(key)的种子值会让rand()的生成序列出现集中重复的情况。加上你原来先存后检查的逻辑，当已访问数组接近满时，rand()要命中唯一剩下的索引几乎是碰运气，直接卡死。修复后的逻辑是先检查再标记，配合高效的布尔检查，哪怕随机到重复值也能立刻跳过，彻底解决循环问题。

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