c - 从 C 语言的旅行推销员文件中获取输入

Question

我正在研究 TSP，它需要大量的城市，如 100,500 等。我已经使用贪婪算法编写了代码，并且使用命令行参数运行良好。但我需要从具有以下给定格式的文件中获取输入。

1. 第一行是城市数量

2. 第二行是“欧几里德”或“非欧几里德”

3. 现在从第 3 行开始，我们有了 n 个城市的坐标( float )

4. 在坐标之后，我们有每个城市的 nxn 距离矩阵。

类似的事情让我们将城市数量设为 5

5

欧几里得

1.3 4.2

1.6 -3.5

1.4 1.5

6.4 3.6

4 2.4

现在是 5x5 成本矩阵。

如何将所有输入存储在数组中？ (n，欧几里德/非欧几里德，坐标，矩阵) 接受输入后，我需要对矩阵本身进行处理。

Answer 1

我不会将其全部存储在一个数组中。首先，担心读取城市的数量。了解之后，您可以分配 2 个数组:其中一个包含包含每个城市坐标的结构，另一个是存储成本的二维数组。

这假设您查看城市并对其进行计数:在您的示例中，坐标为 1.3 4.2 的城市将是城市 0(存储在数组的位置 0 中)； 1.6 -3.5 的城市将位于位置 1，依此类推。所以，基本上你会这样做:

• 读取城市数量，x；
• 读取它是否是欧几里德，将其存储在某个变量中；
• 分配一个包含 x 元素的数组 cities，以及另一个x x x 的二维数组成本；
• 读取每个城市的坐标，并将其存储在cities[i](城市应是一个具有 2 个浮点的结构数组，用于存储坐标)；
• 对于每一行 i(i 从 0 开始)以及该行中的每一列 j(同样从 0 开始)，将 cost[i][j] 设置为输入。

以下是实现此方法的代码:

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUFSIZE 32

struct city {
    float c1;
    float c2;
};

int main(void) {
    int citiesNo, i, j;
    struct city *cities;
    float **cost;
    char line[BUFSIZE], euclidean[BUFSIZE];
    fgets(line, BUFSIZE, stdin);
    citiesNo = atoi(line);
    fgets(line, BUFSIZE, stdin);
    strcpy(euclidean, line);

    cities = malloc(sizeof(struct city)*citiesNo);
    cost = malloc(sizeof(float *)*citiesNo);

    for (i = 0; i < citiesNo; i++)
        cost[i] = malloc(sizeof(float)*citiesNo);

    /* Read coordinates */
    for (i = 0; i < citiesNo; i++)
        scanf("%f %f", &(cities[i].c1), &(cities[i].c2));

    /* Read costs */
    for (i = 0; i < citiesNo; i++)
        for (j = 0; j < citiesNo; j++)
            scanf("%f", &(cost[i][j]));

    /* Everything is stored now... */

    return 0;
}

一开始使用 fgets 是因为 scanf("%d", &citiesNo) 会在缓冲区中留下换行符，而后续的 fgets() 调用将返回一个空行。如果您愿意，可以将两个 fgets() 替换为 scanf()，我只是没有用 scanf 读取欧几里得字符串，因为它不进行缓冲区大小检查。如果您的输入始终格式良好，那么这不是问题。

此代码运行后，您将在变量 euclidean 中存储一个带有“euclidean”或“not euclidean”的字符串。