阅读链接列表不能正常工作c++

Question

我被这个问题困了好几个小时了，谁来帮帮我。

输入格式为

5
1 2  9.0
1 3 12.0
2 4 18.0
2 3  6.0
2 5 20.0
3 5 15.0
0
1 5

第一个数字是图中顶点的个数。接下来到0的线是图的边。第一个和第二个数字是顶点，第三个数字是它们之间的边的距离。试图读取数据并将边存储到该顶点的邻接列表中的位置。这个例子将创建一个有5个顶点的图，这些顶点的边从1到2。2到4&3&1等也存储相反的EX. 21 9.0。它没有正确存储数据。当读取每个顶点的新数据时，将覆盖之前的数据。它将数据存储在多个listCells中，因为当打印出来时，我得到

1 3 12.000
1 3 12.000
2 5 20.000
2 5 20.000
2 5 20.000
2 5 20.000
3 5 15.000
3 5 15.000
3 5 15.000

所以写的是细胞数只是错误的信息。

#include <cstdio>
using namespace std;
int tracing= 1;
struct ListCell
{
   ListCell* next;
   int vertex;
   double weight;
   ListCell(int v, double w, ListCell* nxt)
   {
      vertex = v;
      weight = w;
      next = nxt;
   }
};
typedef ListCell* List;
struct Vertex
{
   bool signaled;
   long distance;
   List adjacency;    
};
struct Graph
{
   int     numVertices;
   Vertex* vertexInfo;
   Graph(int n)
   {
      numVertices = n;
      vertexInfo  = new Vertex[n+1];
      for(int i = 1; i <= n; i++)
      {
         vertexInfo[i].signaled = false;
      }
   }
};
//==============================================================
//                   tail
//==============================================================
// 
//==============================================================
   List tail(List L)
   {
      return L->next;
   }
//==============================================================
//                   isEmpty
//==============================================================
// 
//==============================================================
   bool isEmpty(List L)
   {
      return L == NULL;
   }
//==============================================================
//                   readIn
//==============================================================
// 
//==============================================================
Graph readIn()
{
   int g;
   int p1;
   int p2;
   float edge;
   scanf("%i ", &g);
   Graph myGraph(g);
   scanf("%i", &p1);
   while(p1 != 0)
   {
      scanf("%i", &p2);
      scanf("%f", &edge);
      if(tracing >0)
      {
         printf("Edge from %i to %i is %5.3fn", p1, p2, edge);
      }
      myGraph.vertexInfo[p1].adjacency = new ListCell 
      (p2,edge,myGraph.vertexInfo[p1].adjacency);

      myGraph.vertexInfo[p2].adjacency = new ListCell
      (p1, edge, myGraph.vertexInfo[p2].adjacency);
      scanf("%i", &p1);
   }
   return myGraph;
}
//==============================================================
//                   printOut
//==============================================================
// 
//==============================================================
void printOut(Graph myGraph)
{  
   int n;
   int length = myGraph.numVertices;
   float d;
   List p;
   printf("There are %i vertices.n", length);
   printf("The edges are as follows. nn");
   for(int i=1; i<=length; i++)
   {
      p= myGraph.vertexInfo[i].adjacency;
      for(p=p; !isEmpty(p); p=tail(p))
      {
         n = myGraph.vertexInfo[i].adjacency -> vertex;
         d = myGraph.vertexInfo[i].adjacency -> weight; 
         if(i<n)
         {
            printf("%i %i %7.3f n",i,n,d);
         }
      }
   }
}
//==============================================================
//                   main
//==============================================================
int main(int argc, char** argv)
{
   Graph myGraph = readIn();
   printOut(myGraph);
   return 0;
}

Answer 1

你的代码有很多错误。第一件事，可能是最明显的是:

myGraph.vertexInfo[p1].adjacency = new ListCell 
   (p2,edge,myGraph.vertexInfo[p1].adjacency);

在输入循环中调用。看看你输入的第一个顶点(1)。你输入两次，一次是"12 9.0"，另一次是"1 3 12.0"。变量p1没有改变(它保持为1)，但是您用第二个输入覆盖了第一个输入。

所以你不仅在输入中有一个错误，你有一个内存泄漏，因为你动态创建一个ListCell，并覆盖之前动态分配的ListCell。

也许数组不是你应该使用的vertexInfo。也许它应该是一个顶点到顶点/距离的映射:

std::map<int, std::vector<std::pair<int,double>>>

，其中键是顶点，内部向量是所有相邻顶点和距离的向量(每一个都表示为一对)。