冰楓論壇

標題: C語言-最短路徑樹(MST)問題 [打印本頁]
作者: 呂晨    時間: 2021-9-29 08:54
標題: C語言-最短路徑樹(MST)問題
本帖最後由 呂晨 於 2021-9-29 18:39 編輯

讀txt檔
1.PNG
我有查到兩種方法，一種是一個點一個點找，另一種拿上面這個file來解說，總共有11個點先扣掉起點N1，剩下10個點，各自找到最近的相鄰點成為一個group,會變成有5個gropu，這五個group再去找最近的相鄰group，連接成為新的group。
3.PNG
第二種會變成有分支出去，而第一種我已經寫出來了。
有兩個問題想詢問
第一個問題是第二種要怎麼去構思
第二個問題是把結果輸出後，會跑出很多空格，我是用memset把字串都變成'\0'，在小黑窗上面不會顯示這些，但輸出到txt後會跑出來
4.PNG
  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

  8. struct point
  9. {
  10.         char* name;
  11.         int x;
  12.         int y;
  13.         float howlong;
  14. }*matrix;

  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. }


  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);

  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. }
複製代碼

2.PNG (4.76 KB, 下載次數: 1)

2.PNG





歡迎光臨 冰楓論壇 (https://bingfong.com/) Powered by 冰楓