C语言计算环形排列点最短距离并生成结果矩阵的实现方法

现有代码问题排查 #

• 存在死循环：while(m>0 && n>0)代码块内未修改m、n的取值，程序会卡死在该循环内
• 距离计算逻辑错误：当前累加逻辑未关联起点i，仅基于终点j计算，完全不符合点对(i,j)的路径计算要求
• 数组索引越界：反向累加时t从n开始访问ptr[t]，而动态数组的合法索引范围是0~l-1，会触发内存访问错误
• 输出格式不匹配：矩阵元素输出未加空格，和示例输出格式不符

实现思路 #

环形路径的最短距离计算可以简化为：

1. 先计算环形所有边的总长度sum_total，任意两点的顺时针路径长度 + 逆时针路径长度 = sum_total
2. 对任意点对(i,j)：
   • 若i==j，距离直接取0
   • 先计算顺时针从i走到j的路径长度clockwise_dis
   • 逆时针路径长度为sum_total - clockwise_dis
   • 取两者较小值作为点对(i,j)的最短距离

修复后完整代码 #

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

int main()
{
    int* ptr;
    int l, i, j, t;
    int **p;
    int sum_total = 0;

    // 输入数组长度
    scanf("%d", &l);
    ptr = (int*)malloc(l * sizeof(int));
    if (ptr == NULL) {
        exit(0);
    }
    // 输入数组元素
    for (i = 0; i < l; ++i) {
        scanf("%d", &ptr[i]);
        if(ptr[i]<0) {
            exit(0);
        }
        sum_total += ptr[i];
    }
    // 输出第一行原数组元素
    for (i = 0; i < l; ++i) {
        printf("%d ", ptr[i]);
    }
    printf("\n");

    // 初始化距离矩阵
    p = (int**)malloc(l * sizeof(int*));
    for (i = 0; i < l; i++) {
        p[i] = (int*)malloc(l * sizeof(int));
        for (j = 0; j < l; j++) {
            if (i == j) {
                p[i][j] = 0;
                continue;
            }
            int clockwise_dis = 0;
            int cur = i;
            // 计算顺时针从i到j的距离
            while (cur != j) {
                clockwise_dis += ptr[cur];
                cur = (cur + 1) % l;
            }
            int reverse_dis = sum_total - clockwise_dis;
            p[i][j] = clockwise_dis < reverse_dis ? clockwise_dis : reverse_dis;
        }
    }

    // 输出距离矩阵
    for (i = 0; i < l; i++) {
        for (j = 0; j < l; j++) {
            printf("%d ", p[i][j]);
        }
        printf("\n");
    }

    // 释放内存避免泄漏
    for (i = 0; i < l; i++) {
        free(p[i]);
    }
    free(p);
    free(ptr);
    return 0;
}

验证说明 #

输入示例的长度为5，数组元素为2 3 4 1 1，总长度为11，计算得到的矩阵和示例输出完全一致。

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