C語言-最短路徑樹(MST)問題

呂晨

讀txt檔

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

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

1. #include<stdio.h>
   
2. #include<stdlib.h>
   
3. #include<string.h>
   
4. #include<math.h>
   
5. #pragma warning( disable : 4996 )
   
6. #define N 13
   
7. 
   
8. struct point
   
9. {
   
10.         char* name;
    
11.         int x;
    
12.         int y;
    
13.         float howlong;
    
14. }*matrix;
    
15. 
    
16. void findpoint(struct point* matrix, int line)
    
17. {
    
18.         struct point temp;
    
19.         int times = 1, i = 0;
    
20.         int  x = 0, y = 0;
    
21.         float v = 20000;
    
22.        
    
23.         while (line>=times)
    
24.         {
    
25.                 printf("YES");
    
26.                 for (i = times ; i < line; i++)
    
27.                 {
    
28.                         matrix[i].howlong = pow(matrix[i].x - matrix[i-1].x, 2) + pow(matrix[i].y - matrix[i-1].y, 2);
    
29.                 }
    
30.                 for (x = times; x < line; x++)
    
31.                 {
    
32.                         for (y = times; y < line - 1; y++)
    
33.                         {
    
34.                                 if (matrix[y].howlong > matrix[y + 1].howlong)
    
35.                                 {
    
36.                                         temp = matrix[y];
    
37.                                         matrix[y] = matrix[y + 1];
    
38.                                         matrix[y + 1] = temp;
    
39.                                 }
    
40.                         }
    
41.                 }
    
42.                 printf("(%s,%s) Length = %f", matrix[times - 1].name, matrix[times].name, sqrt(matrix[times].howlong));
    
43.                 times++;
    
44.         }
    
45. }
    
46. 
    
47. 
    
48. int main()
    
49. {
    
50.         int i, line=0, tmp;
    
51.         char name[N];
    
52.         char value[N];
    
53.         printf("enter the file name:(.txt)");
    
54.         scanf("%s", &name);
    
55. 
    
56.         FILE* fp;
    
57.         fp = fopen(name, "r");
    
58.         if (fp == NULL)
    
59.         {
    
60.                 puts("error");
    
61.         }
    
62.         while ((i = fgetc(fp)) != EOF)
    
63.         {
    
64.                 if (i == '\n') line++;
    
65.         }
    
66.        
    
67.         fseek(fp, 0L, SEEK_SET);
    
68.         i = 0;
    
69.         matrix = (struct point*)malloc(line * sizeof(struct point));
    
70.         while ((fgets(value, sizeof(value), fp)) != NULL)
    
71.         {
    
72.                 char* token = strtok(value, "(");
    
73.                 matrix[i].name = (char*)malloc(sizeof(char) * N);
    
74.                 strcpy(matrix[i].name, token);
    
75.                 token = strtok(NULL, ",");
    
76.                 tmp = atoi(token);
    
77.                 matrix[i].x = tmp;
    
78.                 token = strtok(NULL, ")");
    
79.                 tmp = atoi(token);
    
80.                 matrix[i].y = tmp;
    
81.                 i++;
    
82.         }
    
83.         findpoint(matrix, line);
    
84.         free(matrix);
    
85. }

複製代碼