c - C：变量的值改变而不重新赋值

Question

我正在实施 Kruskal 的算法。

在下面的代码中调用 graph() 后，节点的值发生了变化。我不太清楚为什么——如果有人能澄清这一点，我将不胜感激。我没有从图中访问节点的值，并且正在访问的数组的节点和边都分配在堆栈之外！

struct node {
  int parent, rank;
};
typedef struct node node;

struct edge {
  int fromvertex, tovertex;
  float weight;
};
typedef struct edge edge;

node* nodes;
edge* edges;

typedef enum {Unvisited, Visited} vertexstate;

int main (int argc, char const *argv[])
{
  void getcount(int*, int*);
  void graph(int, int);
  void makeset(int);
  int hasspantree(int, int, int);
  void kruskal(int, int);
  int printmcst(int);
  int nodecount, edgecount, i, totalcost=0;
  getcount(&nodecount, &edgecount);
  for (i = 1; i <= nodecount; i++)
    makeset(i);
  printf("%d \t %d\n", nodes[6].parent, nodes[6].rank );
  graph(nodecount, edgecount);
  printf("%d \t %d\n", nodes[6].parent, nodes[6].rank );
  printf("Has a spanning tree?");
  if(hasspantree(1, nodecount, edgecount)) {
    printf("\t Yes.\n");
    kruskal(nodecount, edgecount);
    printf("MCST found:\n\n");
    totalcost = printmcst(nodecount);
    printf("\nCost: %d", totalcost);
  }
  else {
    printf("No.");
    exit(0);
  }
  return 0;
}

void graph(int nodecount, int edgecount)
{
  for (int i = 0; i < edgecount; i++) {
    scanf("%d", &edges[i].fromvertex);
    scanf("%d", &edges[i].tovertex);
    scanf("%f", &edges[i].weight);
  }
}

void getcount(int *nodecount, int *edgecount)
{
  scanf("%d", nodecount);
  scanf("%d", edgecount);
  nodes = malloc(*nodecount * sizeof(node));
  edges = malloc(*edgecount * sizeof(edge));
}

void makeset(int x)
{
  nodes[x].parent = x;
  nodes[x].rank = 0;
}

Answer 1

一个明显的错误是访问从索引 1 而不是 0 开始的节点数组，这会在您访问最后一个元素时导致缓冲区溢出

 for (i = 1; i <= nodecount; i++)  <-- here i should start at 0 and access only up to nodecount-1
    makeset(i);