Kruskal算法實現

我綁實現Kriskal在C++算法，但...Kruskal算法實現

在0x0127160d在DAA.exe未處理的異常訪問衝突讀取位置0xdd2021d4。

它停止在這條線中getRoot功能：（！城市[根] .prev = NO_PARENT）

而

我認爲問題是與在城市陣列數據。當我在prinf陣列中的所有數據這不是我想要的。城市的名字是這樣的「════════════════¤¤¤¤ллллллллю■ю■」和數字（INT） - 這樣的（-842150451）。以下是完整的代碼。

#include<iostream> 
#include<cstdio> 
#include<algorithm> 
#include<cstring> 

#define NO_PARENT -1 

struct city { 
    char name[11]; 
    int prev; 
}; 

struct path { 
    unsigned i, j, price; 
}; 

bool comparsion(path p1, path p2) { 
    return p1.price > p2.price; 
} 

int getRoot(city *cities, int cityNumber) { 
    int root = cityNumber, tmp; 

    while(cities[root].prev != NO_PARENT) 
     root = cities[root].prev; 

    while(cityNumber != root) { 
     tmp = cityNumber; 
     cityNumber = cities[cityNumber].prev; 
     cities[tmp].prev = root; 
    } 

    return root; 
} 

bool isListed(city *cities, int n, char cityName[]) { 
    for(int i = 0; i < n; i++) 
     if(strcmp(cities[i].name, cityName)) 
      return true; 
    return false; 
} 

int getCityNumber(city *cities, int n, char cityName[]) { 
    for(int i = 0; i < n; i++) 
     if(strcmp(cities[i].name, cityName)) 
      return i; 
    return NO_PARENT; 
} 

int minPrice(city *cities, path *paths, int cityCount, int pathCount) { 
    unsigned minPrice = 0; 
    // sort paths by price 
    std::sort(paths, &paths[pathCount-1], comparsion); 

    for(int k = 0; k < pathCount; k++) { 
     printf("path: %d - %d\n", paths[k].i, paths[k].j); 
     int c1 = getRoot(cities, paths[k].i), c2 = getRoot(cities, paths[k].j); 
     if(c1 != c2) { 
      minPrice += paths[k].price; 
      cities[c2].prev = c1; 
     } 
    } 

    return minPrice; 
} 

    int main() { 
    int n, m, k; 
    do { 
     scanf("%d %d %d", &n, &m, &k); 
    } while(n < 2 || n > 10001 || m < -1 || m > 100001 || k < -1 || k > 100001); 

    city* cities = (city*)malloc(n*sizeof(city)); 
    path* paths = (path*)malloc((m + k)*sizeof(path)); 
    int addCities = 0; 
    char city1[11], city2[11]; 
    for(int i = 0; i < (m + k); i++) { 
     scanf("%s %s", city1, city2); 

     if(addCities < n && !isListed(cities, n, city1)) { // if city1 is not into cities 
      // add it 
      strcpy(cities[addCities].name, city1); 
      cities[addCities].prev = NO_PARENT; 
      addCities++; 
     } 
     paths[i].i = getCityNumber(cities, n, city1); // number of city1 

     if(addCities < n && !isListed(cities, n, city2)) { // if city2 is not into cities 
      // add it 
      strcpy(cities[addCities].name, city2); 
      cities[addCities].prev = NO_PARENT; 
      addCities++; 
     } 
     paths[i].j = getCityNumber(cities, n, city1); // number of city2 

     if(i >= m) 
      scanf("%d", &paths[i].price); 
    } 

    for(int i = 0; i < (m + k); i++) 
     printf("%s: %d\n", cities[i].name, cities[i].prev); 

    // Calculate min price 
    printf("%d ", minPrice(cities, paths, n, k + m)); 

    system("pause"); 
    return 0; 
}

來源

2012-05-20 micobg

你爲什麼不使用std :: string類而不是爲城市名稱的所有那些醜陋的陣列？然後，比較字符串也會更容易。 – betabandido

你能告訴我們，如果解決我給解決您的問題，或者如果你仍然有問題。 – cristicbz

你必須初始化「城市」。有（M + K）n個城市之間的路徑，但這並不一定意味着所有n個城市都包括在這些路徑，因爲你設置了城市NO_PARENT的上一頁成員時，它的上市爲city1或城2，當一個城市的決沒有上市，其上一頁成員將是不確定的，當你在getRoot功能while(cities[root].prev != NO_PARENT) root = cities[root].prev;使用它作爲一個指標，這將導致該問題。

來源

2012-05-20 08:34:41

我使用NO_PARENT afret malloc實現城市[i] .name，空字符串和城市[i] .parent，並且程序成功結束。但它不能正常工作。城市中的數據也是一樣的。：/ – micobg

在isListed（）和getCityNumber（）中，您使用strcmp（）來檢查字符串是否相等。這樣做有兩個問題：

strcmp在兩個字符串相等時返回0，因此您需要檢查是否（strcmp（...）== 0）。這是在C.
這些奇怪的事情一個malloc'ing你之後需要到例如設置城市[I]。名稱的東西「未命名」或只是「\ 0」。否則，STRCMP將調用上未初始化字符串 - 如果他們沒有在11個字符包含空字符，它就會失敗。 malloc的行之後添加以下代碼：
```
for(int i = 0 ; i < n ; ++ i) { 
    cities[ i ].name[ 0 ] = '\0'; 
    cities[ i ].parent = NO_PARENT; 
} 
```

來源

2012-05-20 12:42:09 cristicbz

Kruskal算法實現

回答

相關問題