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

我可以看到至少有一个地方会导致它崩溃。当你在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指向listnode你刚刚构造的新值，它有一个指向next内存中的随机位置。

结果是while循环最终爆炸。

如果开头的 1000 x 1000 数组main导致堆栈溢出，我也不会感到惊讶，但这可能取决于您的系统设置。

于 2013-05-12T00:31:46.117 回答