Login
C- Kod
347 просмотров
Перейти к просмотру всей ветки
in Antwort scorpi_ 12.03.07 02:29
Я нашла на wikipedia.de следуюшее Musterlösung для Дийкстры:
#define INFINITY 100000000
struct Kante {
int ziel;
int kosten;
};
struct Knote {
struct Kante* kanten;
int knote_id;
int kante_anzahl;
int distance;
int isDead;
};
struct graph {
int knote_anzahl;
struct Knote* knoten;
} graph_;
void Dijkstra() {
int i, j;
int source = 1000;
struct Knote *zeiger;
for(i = 0; i < nodecount; i++) {
if(i == source) {
zeiger .distance = 0;
zeiger .isDead = 0;
} else {
zeiger .distance = INFINITY;
zeiger .isDead = 0;
}
}
for(i = 0; i < nodecount; i++) {
int next;
int min = INFINITY+1;
for(j = 0; j < nodecount; j++) {
if(!zeiger[j].isDead && zeiger[j].distance< min) {
next = j;
min = zeiger[j].distance;
}
}
for(j = 0; j < zeiger[next].kante_anzahl; j++) {
if(zeiger[zeiger[next].kanten[j].ziel].distance > (zeiger[next].distance + zeiger[next].kanten[j].kosten))
{
zeiger[zeiger[next].kanten[j].ziel].distance =
zeiger[next].distance + zeiger[next].kanten[j].kosten;
}
}
zeiger[next].isDead = 1;
}
for(i = 0; i < nodecount; i++) {
printf("The distance between nodes %ii and %i is %i\n",source, i, zeiger.distance);
}
}
Для этого я расширила Структуту Knoten из вашего Lösunga еше на один Елемент : distance. Насколько я понимаю, в этой Variable сохраняется расстояние от актуальной точки до стартовой точки. В самом начале этой Funktion этой Variable присваивается 0, если речь идет о Стартовой точкев, это вроде логично. Но в следуюшей schleife zeiger[j].distance сравнивается с Variable min. Вот на этом месте мне не особо понятно откуда в zeiger[j].distance должен на этом месте появится Wert, ведь он же до этого нигде не присваивается. Короче этот код выдает „segmentatioin fault“, и ошибка по-моему начинается на этом месте.
Поетому прежде чем я тут совсем мозги сломаю, решила спросить у вас.
#define INFINITY 100000000
struct Kante {
int ziel;
int kosten;
};
struct Knote {
struct Kante* kanten;
int knote_id;
int kante_anzahl;
int distance;
int isDead;
};
struct graph {
int knote_anzahl;
struct Knote* knoten;
} graph_;
void Dijkstra() {
int i, j;
int source = 1000;
struct Knote *zeiger;
for(i = 0; i < nodecount; i++) {
if(i == source) {
zeiger .distance = 0;
zeiger .isDead = 0;
} else {
zeiger .distance = INFINITY;
zeiger .isDead = 0;
}
}
for(i = 0; i < nodecount; i++) {
int next;
int min = INFINITY+1;
for(j = 0; j < nodecount; j++) {
if(!zeiger[j].isDead && zeiger[j].distance< min) {
next = j;
min = zeiger[j].distance;
}
}
for(j = 0; j < zeiger[next].kante_anzahl; j++) {
if(zeiger[zeiger[next].kanten[j].ziel].distance > (zeiger[next].distance + zeiger[next].kanten[j].kosten))
{
zeiger[zeiger[next].kanten[j].ziel].distance =
zeiger[next].distance + zeiger[next].kanten[j].kosten;
}
}
zeiger[next].isDead = 1;
}
for(i = 0; i < nodecount; i++) {
printf("The distance between nodes %ii and %i is %i\n",source, i, zeiger.distance);
}
}
Для этого я расширила Структуту Knoten из вашего Lösunga еше на один Елемент : distance. Насколько я понимаю, в этой Variable сохраняется расстояние от актуальной точки до стартовой точки. В самом начале этой Funktion этой Variable присваивается 0, если речь идет о Стартовой точкев, это вроде логично. Но в следуюшей schleife zeiger[j].distance сравнивается с Variable min. Вот на этом месте мне не особо понятно откуда в zeiger[j].distance должен на этом месте появится Wert, ведь он же до этого нигде не присваивается. Короче этот код выдает „segmentatioin fault“, и ошибка по-моему начинается на этом месте.
Поетому прежде чем я тут совсем мозги сломаю, решила спросить у вас.