插入邻接表的问题
Issue with insertion in an adjacency list
我正在尝试在无向图中插入节点,在第一次插入时代码运行良好,但在第二次插入时代码不再起作用,我不明白为什么。有人可以帮我解决这个问题吗?
我已经尝试在 Dev-c++ 中进行编译,有时代码 运行 和其他代码不能,但是在 CodeBlocks 和 CMD(Windows) 中就不起作用。
这是我的代码:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
typedef struct tedge {
int vdest; //destiny vertex
double weight;
struct tedge* next;
}TypeEdge;
typedef TypeEdge* TypePointer;
typedef struct {
TypePointer* listAdj;
int numVertex;
int numEdges;
}TypeGraph;
//initialize the graph
bool initializeGraph(int nv, TypeGraph* graph) {
if(nv <= 0) return false;
int i;
if(graph->listAdj = (TypePointer*)malloc(nv*sizeof(TypePointer))) {
graph->numEdges = 0;
graph->numVertex = nv;
for(i = 0; i < nv; i++)
graph->listAdj[i] = NULL;
return true;
}
return false;
}
//insertion
bool insertEdge(int v1, int v2, double weight, TypeGraph *graph) {
if(!graph) return false;
if((v1 < 0) || (v1 >= graph->numVertex)) return false;
if((v2 < 0) || (v2 >= graph->numVertex)) return false;
TypePointer new = (TypePointer)malloc(sizeof(TypePointer));
new->vdest = v2;
new->weight = weight;
new->next = graph->listAdj[v1];
graph->listAdj[v1] = new;
TypePointer simetry = (TypePointer)malloc(sizeof(TypePointer));
simetry->vdest = v1;
simetry->weight = weight;
simetry->next = graph->listAdj[v2];
graph->listAdj[v2] = simetry;
graph->numEdges++;
return true;
}
void printGraph(TypeGraph* graph) {
int i;
for(i = 0; i < graph->numVertex; i++) {
TypePointer actual = graph->listAdj[i];
printf("v %i: ", i);
while(actual != NULL) {
printf("(adj %i, weight %g); ", actual->vdest, actual->weight);
actual = actual->next;
}
printf("\n");
}
}
int main() {
TypeGraph graph;
initializeGraph(9, &graph);
insertEdge(0, 1, 8, &graph);
insertEdge(0, 3, 4, &graph);
insertEdge(0, 6, 11, &graph);
insertEdge(1, 2, 7, &graph);
insertEdge(1, 4, 2, &graph);
insertEdge(1, 8, 4, &graph);
insertEdge(2, 5, 9, &graph);
insertEdge(2, 8, 14, &graph);
insertEdge(3, 6, 8, &graph);
insertEdge(4, 6, 7, &graph);
insertEdge(5, 8, 10, &graph);
insertEdge(6, 7, 1, &graph);
insertEdge(7, 8, 2, &graph);
printGraph(&graph);
return 0;
}
如果有人可以帮助我,我接受任何建议。谢谢
看到指针的 typedef 中的危险
TypePointer new = (TypePointer)malloc(sizeof(TypePointer));
new->vdest = v2;
new->weight = weight;
new->next = graph->listAdj[v1];
只为指针分配足够的内存。我建议
TypePointer new = malloc(sizeof(*new));
也在这里
TypePointer simetry = (TypePointer)malloc(sizeof(TypePointer));
应该是
TypePointer simetry = malloc(sizeof(*simetry));
进行这些更正后,程序报告:
v 0: (adj 6, weight 11); (adj 3, weight 4); (adj 1, weight 8);
v 1: (adj 8, weight 4); (adj 4, weight 2); (adj 2, weight 7); (adj 0, weight 8);
v 2: (adj 8, weight 14); (adj 5, weight 9); (adj 1, weight 7);
v 3: (adj 6, weight 8); (adj 0, weight 4);
v 4: (adj 6, weight 7); (adj 1, weight 2);
v 5: (adj 8, weight 10); (adj 2, weight 9);
v 6: (adj 7, weight 1); (adj 4, weight 7); (adj 3, weight 8); (adj 0, weight 11);
v 7: (adj 8, weight 2); (adj 6, weight 1);
v 8: (adj 7, weight 2); (adj 5, weight 10); (adj 2, weight 14); (adj 1, weight 4);
我也注意到函数 return 一个状态,它被忽略了,虽然这并没有导致这里的崩溃。
我正在尝试在无向图中插入节点,在第一次插入时代码运行良好,但在第二次插入时代码不再起作用,我不明白为什么。有人可以帮我解决这个问题吗?
我已经尝试在 Dev-c++ 中进行编译,有时代码 运行 和其他代码不能,但是在 CodeBlocks 和 CMD(Windows) 中就不起作用。
这是我的代码:
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <malloc.h>
typedef struct tedge {
int vdest; //destiny vertex
double weight;
struct tedge* next;
}TypeEdge;
typedef TypeEdge* TypePointer;
typedef struct {
TypePointer* listAdj;
int numVertex;
int numEdges;
}TypeGraph;
//initialize the graph
bool initializeGraph(int nv, TypeGraph* graph) {
if(nv <= 0) return false;
int i;
if(graph->listAdj = (TypePointer*)malloc(nv*sizeof(TypePointer))) {
graph->numEdges = 0;
graph->numVertex = nv;
for(i = 0; i < nv; i++)
graph->listAdj[i] = NULL;
return true;
}
return false;
}
//insertion
bool insertEdge(int v1, int v2, double weight, TypeGraph *graph) {
if(!graph) return false;
if((v1 < 0) || (v1 >= graph->numVertex)) return false;
if((v2 < 0) || (v2 >= graph->numVertex)) return false;
TypePointer new = (TypePointer)malloc(sizeof(TypePointer));
new->vdest = v2;
new->weight = weight;
new->next = graph->listAdj[v1];
graph->listAdj[v1] = new;
TypePointer simetry = (TypePointer)malloc(sizeof(TypePointer));
simetry->vdest = v1;
simetry->weight = weight;
simetry->next = graph->listAdj[v2];
graph->listAdj[v2] = simetry;
graph->numEdges++;
return true;
}
void printGraph(TypeGraph* graph) {
int i;
for(i = 0; i < graph->numVertex; i++) {
TypePointer actual = graph->listAdj[i];
printf("v %i: ", i);
while(actual != NULL) {
printf("(adj %i, weight %g); ", actual->vdest, actual->weight);
actual = actual->next;
}
printf("\n");
}
}
int main() {
TypeGraph graph;
initializeGraph(9, &graph);
insertEdge(0, 1, 8, &graph);
insertEdge(0, 3, 4, &graph);
insertEdge(0, 6, 11, &graph);
insertEdge(1, 2, 7, &graph);
insertEdge(1, 4, 2, &graph);
insertEdge(1, 8, 4, &graph);
insertEdge(2, 5, 9, &graph);
insertEdge(2, 8, 14, &graph);
insertEdge(3, 6, 8, &graph);
insertEdge(4, 6, 7, &graph);
insertEdge(5, 8, 10, &graph);
insertEdge(6, 7, 1, &graph);
insertEdge(7, 8, 2, &graph);
printGraph(&graph);
return 0;
}
如果有人可以帮助我,我接受任何建议。谢谢
看到指针的 typedef 中的危险
TypePointer new = (TypePointer)malloc(sizeof(TypePointer));
new->vdest = v2;
new->weight = weight;
new->next = graph->listAdj[v1];
只为指针分配足够的内存。我建议
TypePointer new = malloc(sizeof(*new));
也在这里
TypePointer simetry = (TypePointer)malloc(sizeof(TypePointer));
应该是
TypePointer simetry = malloc(sizeof(*simetry));
进行这些更正后,程序报告:
v 0: (adj 6, weight 11); (adj 3, weight 4); (adj 1, weight 8); v 1: (adj 8, weight 4); (adj 4, weight 2); (adj 2, weight 7); (adj 0, weight 8); v 2: (adj 8, weight 14); (adj 5, weight 9); (adj 1, weight 7); v 3: (adj 6, weight 8); (adj 0, weight 4); v 4: (adj 6, weight 7); (adj 1, weight 2); v 5: (adj 8, weight 10); (adj 2, weight 9); v 6: (adj 7, weight 1); (adj 4, weight 7); (adj 3, weight 8); (adj 0, weight 11); v 7: (adj 8, weight 2); (adj 6, weight 1); v 8: (adj 7, weight 2); (adj 5, weight 10); (adj 2, weight 14); (adj 1, weight 4);
我也注意到函数 return 一个状态,它被忽略了,虽然这并没有导致这里的崩溃。