0

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

  1. 第一行是城市数量

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

  3. 现在从第 3 行开始，我们有 n 个城市的坐标（浮点数）

  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，欧几里得/非欧几里得，坐标，矩阵）在接受输入后，我需要处理矩阵本身。

4

1 回答 1

1

我不会将它们全部存储在一个数组中。首先，担心阅读城市的数量。知道之后，您可以分配 2 个数组：其中一个包含每个城市的坐标结构，另一个是存储成本的 2D 数组。

这假设您查看城市并计算它们：在您的示例中，坐标为 1.3 4.2 的城市将是城市 0（存储在数组的位置 0 中）；1.6 -3.5 的城市将位于位置 1，依此类推。所以，基本上你会做：

  • 读取城市数量，x；
  • 读取它是否是欧几里得，将其存储在某个变量中；
  • 分配一个x元素的数组city，另外一个x的二维数组cost x x；
  • 读取每个城市的坐标，并将它们存储在 city [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() 调用将返回一个空行。如果你愿意，你可以用 scanf() 替换这两个 fgets()，我只是没有用 scanf 读取欧几里得字符串，因为它不检查缓冲区大小。如果您的输入总是格式正确，那么这不是问题。

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

于 2013-10-10T09:29:24.987 回答