[求助] C語言-最短路徑樹(MST)問題

7 主題	0 好友	221 積分

Rank: 3 Rank: 3

發表於 2021-9-29 08:54:32 |顯示全部樓層

本帖最後由呂晨於 2021-9-29 18:39 編輯

讀txt檔

我有查到兩種方法，一種是一個點一個點找，另一種拿上面這個file來解說，總共有11個點先扣掉起點N1，剩下10個點，各自找到最近的相鄰點成為一個group,會變成有5個gropu，這五個group再去找最近的相鄰group，連接成為新的group。

第二種會變成有分支出去，而第一種我已經寫出來了。
有兩個問題想詢問
第一個問題是第二種要怎麼去構思
第二個問題是把結果輸出後，會跑出很多空格，我是用memset把字串都變成'\0'，在小黑窗上面不會顯示這些，但輸出到txt後會跑出來

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#pragma warning( disable : 4996 )
#define N 13
struct point
{
char* name;
int x;
int y;
float howlong;
}*matrix;
void findpoint(struct point* matrix, int line)
{
struct point temp;
int times = 1, i = 0;
int x = 0, y = 0;
float v = 20000;
while (line>=times)
{
printf("YES");
for (i = times ; i < line; i++)
{
matrix[i].howlong = pow(matrix[i].x - matrix[i-1].x, 2) + pow(matrix[i].y - matrix[i-1].y, 2);
}
for (x = times; x < line; x++)
{
for (y = times; y < line - 1; y++)
{
if (matrix[y].howlong > matrix[y + 1].howlong)
{
temp = matrix[y];
matrix[y] = matrix[y + 1];
matrix[y + 1] = temp;
}
}
}
printf("(%s,%s) Length = %f", matrix[times - 1].name, matrix[times].name, sqrt(matrix[times].howlong));
times++;
}
}
int main()
{
int i, line=0, tmp;
char name[N];
char value[N];
printf("enter the file name:(.txt)");
scanf("%s", &name);
FILE* fp;
fp = fopen(name, "r");
if (fp == NULL)
{
puts("error");
}
while ((i = fgetc(fp)) != EOF)
{
if (i == '\n') line++;
}
fseek(fp, 0L, SEEK_SET);
i = 0;
matrix = (struct point*)malloc(line * sizeof(struct point));
while ((fgets(value, sizeof(value), fp)) != NULL)
{
char* token = strtok(value, "(");
matrix[i].name = (char*)malloc(sizeof(char) * N);
strcpy(matrix[i].name, token);
token = strtok(NULL, ",");
tmp = atoi(token);
matrix[i].x = tmp;
token = strtok(NULL, ")");
tmp = atoi(token);
matrix[i].y = tmp;
i++;
}
findpoint(matrix, line);
free(matrix);
}