C语言 使用邻接矩阵创建图形

Question

这是我的结构

struct node{
int V,E;
int **adj;
};

这是我创建图形的代码：

struct node* create()
{
int i,j,x,y;
struct node *G=malloc(sizeof(struct node));
printf("Write the number of vertex and edgesn");
scanf("%d%d",&G->V,&G->E);
G->adj=malloc(sizeof(int)*(G->V * G->V));
if(!G->adj){
printf("Out of memoryn");
return;
}
for(i=0;i<G->V;i++)
for(j=0;j<G->V;j++)
G->adj[i][j]=0;
printf("nWrite the source node and destination: ");
for(i=0;i<G->E;i++){
scanf("%d%d",&x,&y);
G->adj[x][y]=1;
G->adj[y][x]=1;
}
return(G);
}

我将这个函数返回的指针存储在另一个指针中，如下所示：

int main()
{
struct node *G=create();
}

当我编译程序时，我被要求输入顶点和边的数量，但一旦我输入值，我的程序就会崩溃。我想知道原因。这是因为内存分配失败吗？

Answer 1

C99 样式的可变长度数组仅适用于局部变量或参数。因此，您可以使用两种经典的 C 方法来实现 2D 数组。

1. 指针数组：

这就是您的结构的样子。 这样，您需要为指针数组和数据单独分配：

G->adj = calloc(G->V, sizeof (int*));
assert(G->adj != NULL); /* need assert.h for this */
for (i=0; i<G-V; ++i)
{
G->adj[i] = calloc(G->V, sizeof (int));
assert(G->adj[i] != NULL);
}

在内存上对数组数据进行一次批量分配，然后使用指针算法来设置G->adj[]指针会更容易一些，但上面给出了一个想法，就 C 而言，每一行都是一个单独的数组。

2. 只有一个批量数组，每次访问时都会完成明确的单元格位置计算。 这就是 C 在内部对嵌套数组所做的。

将adj类型更改为仅int*，然后：

G->adj = calloc(G->V * G->V, sizeof (int));
assert(G->adj != NULL);

就是这样。 现在，当您访问元素时，请使用G->adj[i*G->V + j]，而不是G->adj[i][j]。 宏可能有助于提高可读性。