C语言实现Gale-Shapley稳定婚姻算法出现无限循环求助

你的代码存在三个核心问题，导致了无限循环和功能失效：

1. 未匹配男性的判断逻辑错误 #

stable_marriage函数中，你错误地用engaged[i] == -1来寻找未匹配的男性，但engaged数组的语义是记录女性的匹配对象（索引为女性编号，值为对应的男性编号），完全和男性的匹配状态无关。正确的做法是遍历match数组，寻找值为-1的男性（match[m] == -1表示男性m未匹配）。

2. match数组未初始化 #

main函数中没有对match数组进行初始化，导致其初始值为随机垃圾值。这会使得男性的匹配状态判断失效，无法进入求婚循环，进而让未匹配男性一直留在队列中，导致while循环无限执行。

3. 女性偏好比较逻辑错误 #

当前代码直接使用pref_w[w][m] < pref_w[w][m1]比较女性对男性的偏好，但pref_w存储的是女性的偏好顺序列表（即pref_w[w][k]是女性w第k喜欢的男性编号），而非男性在女性偏好中的排名。这种比较方式完全无法反映女性的真实偏好，会导致匹配逻辑错误。需要构建一个反向的rank_w数组，存储每个男性在对应女性偏好中的排名（排名越小越受欢迎）。

修复后的完整代码 #

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

#define MAX_N 10

int n;
int pref_m[MAX_N][MAX_N], pref_w[MAX_N][MAX_N];
int match[MAX_N], engaged[MAX_N];
int rank_w[MAX_N][MAX_N]; // 新增：rank_w[w][m] = 男性m在女性w偏好中的排名

void stable_marriage()
{
    int i, m, w, m1;
    // 初始化engaged：女性初始未匹配，值为-1
    for (i = 0; i < n; i++)
        engaged[i] = -1;
    
    while (1) {
        m = -1;
        // 寻找第一个未匹配的男性（遍历match数组）
        for (i = 0; i < n; i++) {
            if (match[i] == -1) {
                m = i;
                break;
            }
        }
        if (m == -1) {
            break; // 所有男性已匹配，退出循环
        } 
        
        // 男性m按偏好顺序求婚
        for (i = 0; i < n && match[m] == -1; i++) {
            w = pref_m[m][i];
            if (engaged[w] == -1) {
                // 女性w未匹配，直接订婚
                engaged[w] = m;
                match[m] = w;
            } else {
                m1 = engaged[w];
                // 比较女性w对m和m1的偏好：rank越小越喜欢
                if (rank_w[w][m] < rank_w[w][m1]) {
                    // 女性w更喜欢m，替换匹配
                    match[m1] = -1; // m1变为未匹配
                    engaged[w] = m;
                    match[m] = w;
                }
            }
        }
    }
}

int main()
{
    char filename[256];
    printf("Enter file name: ");
    scanf("%s", filename);
    FILE *file = fopen(filename, "r");
    if (!file) { // 新增：文件打开失败判断
        perror("Failed to open file");
        return 1;
    }
 
    fscanf(file, "%d", &n);
    printf("n = %d\n", n);
    int i, j;
    
    // 读取男性偏好
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            fscanf(file, "%d", &pref_m[i][j]);
            pref_m[i][j]--; // 转换为0索引
        }
    }
    
    // 读取女性偏好并构建rank_w数组
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            fscanf(file, "%d", &pref_w[i][j]);
            pref_w[i][j]--; // 转换为0索引
            // 女性i的第j个偏好是男性pref_w[i][j]，所以该男性的排名是j
            rank_w[i][pref_w[i][j]] = j;
        }
    }
    fclose(file);
    
    // 初始化match数组：男性初始未匹配，值为-1
    for (i = 0; i < n; i++) {
        match[i] = -1;
    }
    
    stable_marriage();
    
    printf("Solution:\n");
    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (match[i] == j) {
                printf("1 ");
            } else {
                printf("0 ");
            }
        }
        printf("\n");
    }
    return 0;
}

修复说明 #

1. 初始化match数组：在main中添加了match数组的初始化，确保所有男性初始状态为未匹配（值为-1）。
2. 修正未匹配男性的查找逻辑：改为遍历match数组寻找未匹配男性，而非错误地使用engaged数组。
3. 新增rank_w数组：构建女性偏好的反向排名数组，正确比较女性对不同男性的偏好程度。
4. 修正匹配替换逻辑：移除了错误的engaged[m1] = -1，改为通过match[m1] = -1标记男性m1为未匹配。
5. 新增文件打开失败判断：避免文件不存在时程序崩溃。

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