1

Kriskal のアルゴリズムを C++ で実装しようとしていますが...

DAA.exe の 0x0127160d で未処理の例外: 0xC0000005: アクセス違反の読み取り場所 0xdd2021d4。

getRoot 関数の次の行で停止します。

while(都市[ルート].prev != NO_PARENT)

問題は都市配列のデータにあると思います。配列内のすべてのデータを印刷すると、それは私が望むものではありません。都市の名前は、「════════════════¤¤¤¤ллллллллю■ю■」と数字 (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;
}
4

2 に答える 2

1

「都市」を初期化する必要があります。n個の都市間に（m + k）のパスがありますが、これは必ずしもn個の都市すべてがこれらのパスに含まれることを意味するわけではありませんNO_PARENT。その前のメンバーが未定義であり、getRoot関数のインデックスとして使用すると、問題が発生するため、リストに表示されることはありませんwhile(cities[root].prev != NO_PARENT) root = cities[root].prev;。

于 2012-05-20T08:34:41.983 に答える
1

isListed() と getCityNumber() では、strcmp() を使用して文字列が等しいかどうかをチェックします。あなたがやっている方法には2つの問題があります：

  1. 2 つの文字列が等しい場合、strcmp は 0 を返すため、if( strcmp(...) == 0 ) を確認する必要があります。これは、C のこれらの奇妙なことの 1 つです。

  2. malloc の後で、cities[i].name を「unnamed」または単に「\0」などに設定する必要があります。そうしないと、初期化されていない文字列に対して strcmp が呼び出され、11 文字以内にヌル文字が含まれていない場合、失敗します。malloc 行の後に次のコードを追加します。

    for( int i = 0 ; i < n ; ++ i ) {
    cities[ i ].name[ 0 ] = '\0';
    cities[ i ].parent    = NO_PARENT;
}
于 2012-05-20T12:42:09.100 に答える