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算法实现

回答

相关问题