0

g++ でコードをコンパイルできますが、何らかの理由でプログラムを実行すると、数秒後にクラッシュします。

また、割り当てが C の b に想定されていることにも気付きましたが、その言語についてはあまり知りませんし、問題がどこにあるのかもわかりません。誰かが私にヒントを与えることができれば、それは素晴らしいことですが、大したことではありません.

プログラムは問題なくコンパイルされるため、エラーの場所を知りたいだけです

ここにコードがあり、メイン関数は教授のテスト コードです。

#include <cstdlib>
#include <iostream>
#include <stdio.h>
using namespace std;

struct listnode {
struct listnode * next;
int vertexnumber;
};

struct listnode * shortest_path(int n, int s, int t, int * dist) {

struct listnode * pathlist = NULL;
    struct listnode * temp = NULL;
    struct listnode * pathlisthead = NULL;

    int i, j, k, S[9999], cost[9999], path[9999], p, min;

    for (i = 0; i < n; i++) {
        S[i] = 0;
        cost[i] = 9999;
    }

    p = 0;
    path[++p] = s;
    pathlist = new struct listnode;
    pathlisthead = pathlist;
    pathlist->vertexnumber = s;
    S[s] = 1;
    cost[s] = 0;
    for (i = 1; i < n - 1; i++) {
        k = -1;
        min = 9999;
        for (j = 0; j < n; j++) {
            if (cost[j] < min && S[j] != 1) {
                min = cost[j];
                k = j;
            }
        }
        if (*(dist + i*n + j) <= cost[k]) {
            p = 1;
            pathlist = pathlisthead;
        }
        path[++p] = k;
        pathlist->next = new struct listnode;
        pathlist = pathlist->next;
        pathlist->vertexnumber = k;
        struct listnode * tmp = pathlisthead;
        while (tmp != NULL) {
            tmp = tmp->next;
        }
        S[k] = 1;
        for (j = 0; j < n; j++)
            if (*(dist + i*n + j) != 9999 && cost[j] >= cost[k] + *(dist + i*n + j) && S[j] != 1)
                cost[j] = cost[k] + *(dist + i*n + j);
        if (k == t)
            break;
    }
    return pathlisthead;
}

int main(void)
{  int dist[1000][1000];
   int i,j;
   struct listnode *tmp;
   for(i=0; i< 1000; i++)
     for( j =0; j< 1000; j++ )
     {  if( i<500 && j<500 )
           dist[i][j] = 110 + ((i*i +j*j + 13*(i+j) )%20);
        else
           dist[i][j] = 200 + ((i*i +j*j + 13*(i+j) )%20);
     }


   for(i=0; i< 1000; i++)
     dist[i][i]=0;
   for(i=0; i< 100; i++)
   {  dist[i][2*i+1] = 15; dist[2*i+1][i] = 15;
      dist[i][2*i+2] = 15; dist[2*i+2][i] = 15;
   }
   dist[0][128] = 100; dist[128][0]=100;
   dist[128][500] = 1; dist[500][128]= 1;
   for( i = 0; i< 100; i++)
   {  dist[300+ (7*i)%100][300+(7*i+7)%100] = 1; 
      dist[300+ (7*i+7)%100][300+(7*i)%100] = 1; 
      dist[300+i][450] = 2; dist[450][300+1] = 2;
   }
   for(i=502; i<900; i++)
   { dist[450][i] = 3; dist[i][450]=3;
     dist[500][i] = 2;   dist[i][500]=2;
     dist[501][i] = 10; dist [i][501] = 10;
   }
   dist [500][900] = 50; dist[900][500]=50;
   dist [899][900] = 49; dist[899][900]=49;
   dist [900][999] = 1; dist [999][900] = 1;
   printf("constructed distance matrix for graph with 1000 vertices\n");
   tmp =  shortest_path(1000, 0, 999, &(dist[0][0]));
   printf("The shortest path from 0 to 999 uses the vertices\n");
   while( tmp != NULL )
   {  printf("%d, ", tmp->vertexnumber);
      tmp = tmp->next;
   }
   printf("End test\n");
   exit(0);
}

教授は、結果は次のようになるはずだと言いました。

1000 個の頂点を持つグラフの構築された距離行列

0 から 999 までの最短パスは頂点を使用します

0、128、500、900、999、テスト終了

4

1 に答える 1

1

クラッシュの原因となる場所が少なくとも 1 つあります。ここで新規作成する場合listnode:

    pathlist->next = new struct listnode;
    pathlist = pathlist->next;
    pathlist->vertexnumber = k;

nextへのポインタを初期化しませんNULL。したがって、ここでリストを反復処理し始めると、次のようになります。

    struct listnode * tmp = pathlisthead;
    while (tmp != NULL) {
        tmp = tmp->next;
    }

pathlistheadの初期値を指し始めますpathlist。これは、作成したばかりnextの newを指し、メモリ内のランダムな場所を指しています。listnodenext

その結果、while ループが最終的に爆発します。

また、最初の 1000 x 1000 配列がスタック オーバーフローを引き起こしたとしても驚かないでしょうがmain、それはシステム設定に依存する可能性があります。

于 2013-05-12T00:31:46.117 に答える