printf("Output the message of VNode:\n"); for(i=0;i<G->vexnum;++i) printf("v%d\n",G->vertices[i].data); for(k=0;k<G->arcnum;++k) { printf("Please input the %d edge beginpoint and endpoint: ",k+1); scanf("%d%d",&v1,&v2); i=LocateVex(G,v1); j=LocateVex(G,v2); if(i>=0&&j>=0) { ++flag; p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=_______; p->nextarc=NULL; if(!G->vertices[i].firstarc) G->vertices[i].firstarc=p; else { for(p1=G->vertices[i].firstarc;p1->nextarc;p1=p1->nextarc); ______________; } q=(ArcNode *)malloc(sizeof(ArcNode)); q->adjvex=i; q->nextarc=NULL; if(!G->vertices[j].firstarc) G->vertices[j].firstarc=q; else { for(q1=G->vertices[j].firstarc;q1->nextarc;q1=q1->nextarc); q1->nextarc=q; } } else { printf("Not hava this edge!\n"); k=flag; } }

在这段代码中，第一个空的位置应该填写的是 j，即：

p->adjvex = j;

而第二个空的位置应该填写的是：

p1->nextarc = p;

相关问题

调试这段代码：#include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX_VERTEX_NUM 20 struct ArcNode{ int adjvex; ArcNode *nextarc; int *info; };//表结点 typedef struct{ char data; ArcNode *firstarc; }VNode,AdjList[MAX_VERTEX_NUM];//头结点 struct ALGraph{ AdjList vertices; int vexnum; }; void CreateGraph(ALGraph *G) {scanf("%d",&G->vexnum); int i; for(i=0;i<G->vexnum;i++) {G->vertices[i].data=getchar(); G->vertices[i].firstarc=NULL; getchar(); } char num[20]; for(i=0;i<G->vexnum;i++) {char *token; int con[20];//存分割后的整型数 scanf("%s",num); token=strtok(num," "); int j=1; while(token!=NULL)//分割num，依次存入con {con[j]=atoi(token); j++; token=strtok(NULL," "); } int k; ArcNode *q; q=NULL; G->vertices[i].firstarc->nextarc=NULL; for(k=1;k<j;k+=2) {q=(ArcNode*)malloc(sizeof(ArcNode)); q->adjvex=con[k]; q->nextarc=G->vertices[i].firstarc; G->vertices[i].firstarc=q; q->info=(int*)malloc(sizeof(int)); *(q->info)=con[k+1]; } } } int main() {ALGraph *G0=(ALGraph*)malloc(sizeof(ALGraph));//一开始没写这一条，导致运行到Create函数中scanf(G->vexnum)是出现内存无效引用 CreateGraph(G0); int i; for(i=0;i<G0->vexnum;i++) {printf("%c ",G0->vertices[i].data); ArcNode *p; p=G0->vertices[i].firstarc; while(p) {printf("(%d,%d)%d ",i,p->adjvex,*(p->info)); p=p->nextarc; } printf("\n"); } free(G0); return 0; }

这段代码存在一些问题，需要进行调试：

1. 在 CreateGraph 函数中，每个顶点的邻接表首先应该被初始化为 NULL，而不是直接赋值为 G->vertices[i].firstarc。因此，应该将 G->vertices[i].firstarc=NULL 放到 G->vertices[i].data=getchar() 和 getchar() 之间。

2. 在为每个邻接点分配内存时，应该先判断该顶点是否有邻接点。如果没有，那么该邻接点应该是该顶点的第一个邻接点，此时应该将 G->vertices[i].firstarc 指向该邻接点；否则，应该将该邻接点接到邻接表的最后。因此，应该将 G->vertices[i].firstarc->nextarc=NULL 放到与上述判断语句相同的 if 语句中。

以下是修改后的代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_VERTEX_NUM 20

struct ArcNode {
    int adjvex;
    ArcNode* nextarc;
    int* info;
}; // 表结点

typedef struct {
    char data;
    ArcNode* firstarc;
} VNode, AdjList[MAX_VERTEX_NUM]; // 头结点

struct ALGraph {
    AdjList vertices;
    int vexnum;
};

void CreateGraph(ALGraph* G) {
    scanf("%d", &G->vexnum);
    int i;
    for (i = 0; i < G->vexnum; i++) {
        G->vertices[i].data = getchar();
        G->vertices[i].firstarc = NULL;
        getchar();
    }
    char num[20];
    for (i = 0; i < G->vexnum; i++) {
        char* token;
        int con[20]; // 存分割后的整型数
        scanf("%s", num);
        token = strtok(num, " ");
        int j = 1;
        while (token != NULL) // 分割 num，依次存入 con
        {
            con[j] = atoi(token);
            j++;
            token = strtok(NULL, " ");
        }
        int k;
        ArcNode *q, *p;
        q = NULL;
        for (k = 1; k < j; k += 2) {
            q = (ArcNode*)malloc(sizeof(ArcNode));
            q->adjvex = con[k];
            q->nextarc = NULL;
            q->info = (int*)malloc(sizeof(int));
            *(q->info) = con[k + 1];
            if (G->vertices[i].firstarc == NULL) {
                G->vertices[i].firstarc = q;
            }
            else {
                p = G->vertices[i].firstarc;
                while (p->nextarc != NULL) {
                    p = p->nextarc;
                }
                p->nextarc = q;
            }
        }
    }
}

int main() {
    ALGraph* G0 = (ALGraph*)malloc(sizeof(ALGraph));
    CreateGraph(G0);
    int i;
    for (i = 0; i < G0->vexnum; i++) {
        printf("%c  ", G0->vertices[i].data);
        ArcNode* p;
        p = G0->vertices[i].firstarc;
        while (p) {
            printf("(%d,%d)%d  ", i, p->adjvex, *(p->info));
            p = p->nextarc;
        }
        printf("\n");
    }
    free(G0);
    return 0;
}

完善代码：#include <stdio.h> #include <stdlib.h> #define INF 50 typedef struct ArcNode{ int adjvex;//该弧所指向的顶点位置 struct ArcNode *nextarc;//下一个临接点 int weight;//弧的权重 }ArcNode;//表结点 typedef struct VNode{ char data; //顶点信息 ArcNode *firstarc;//指向下一个结点. }VNode,AdjList[6]; typedef struct{ AdjList LH;//创建头结点数组 int vexnum;//图的点的个数 int arcnum;//图的边的个数 }Graph; typedef struct{ char nextvex; int lowcost; int know; }Auxiliary_array;//辅助数组结构体 voidmain (void){ void buildtu (Graph*); void printgraph(Graph*); void prim( Graph *G, char u); char u; Graph UDG; Graph *G = &UDG; buildtu(G); printgraph(G);//打印图 printf("请输入起始顶点: \n"); while(getchar()!=')n'); u = getchar(); prim(G,u); } void buildtu (Graph*G) { //建图 int search(Graph *G,char a); int i,n1,n2,w;char a,b; ArcNode *p, *q; printf("请输入顶点个数和边的条数: \n"); scanf("%d %d",&G->vexnum,&G->arcnum); printf("请输入顶点信息\n"); for (i= 0;i< G->vexnum; ++i){ while (getchar()!='\n'); scanf("%c" ,&G->LH[i].data); G->LH[i].firstarc = NULL; } printf(" 请输入有关系的结点和该边的权重:\n");for(i=0;i<G->arcnum;++i){ while (getchar()!='\n'); scanf("%c %c %d",&a,&b,&w); n1=search(G,a); n2=search(G,b); p=G->LH[n1].firstarc; if(p == NULL){ p=G->LH[n1].firstarc=(ArcNode *) malloc (sizeof(ArcNode)); } else{ while(p->nextarc!=NULL){ p=p->nextarc; } p=p->nextarc=(ArcNode*)malloc(sizeof(ArcNode)); }

p->adjvex=n2;//弧指向的结点位置
p->weight=w;//弧的权重
p->nextarc=NULL;//下一个临接点为空
q=G->LH[n2].firstarc;
if(q == NULL){
q=G->LH[n2].firstarc=(ArcNode *) malloc (sizeof(ArcNode));
}
else{
while(q->nextarc!=NULL){
q=q->nextarc;
}
q=q->nextarc=(ArcNode*)malloc(sizeof(ArcNode));
}
q->adjvex=n1;//弧指向的结点位置
q->weight=w;//弧的权重
q->nextarc=NULL;//下一个临接点为空
}
}

int search(Graph *G,char a){//查找结点位置
int i;
for(i=0;i<G->vexnum;++i){
if(G->LH[i].data==a){
return i;
}
}
return -1;
}

void printgraph(Graph*G){//打印图
int i;
ArcNode *p;
printf("图的邻接表为：\n");
for(i=0;i<G->vexnum;++i){
printf("%c -> ",G->LH[i].data);
p=G->LH[i].firstarc;
while(p!=NULL){
printf("%c(%d) ",G->LH[p->adjvex].data,p->weight);
p=p->nextarc;
}
printf("\n");
}
}

void prim( Graph *G, char u){//prim算法
int i,j,k;
Auxiliary_array *D;
ArcNode *p;
int min;
k=search(G,u);
D=(Auxiliary_array*)malloc(sizeof(Auxiliary_array)*G->vexnum);
for(i=0;i<G->vexnum;++i){
if(i!=k){
D[i].nextvex=u;
D[i].lowcost=INF;
D[i].know=0;
}
}
p=G->LH[k].firstarc;
while(p!=NULL){
i=p->adjvex;
D[i].nextvex=u;
D[i].lowcost=p->weight;
D[i].know=1;
p=p->nextarc;
}
D[k].know=1;
D[k].lowcost=0;
for(i=1;i<G->vexnum;++i){
min=INF;
for(j=0;j<G->vexnum;++j){
if(D[j].know==0 && D[j].lowcost<min){
min=D[j].lowcost;
k=j;
}
}
D[k].know=1;
p=G->LH[k].firstarc;
while(p!=NULL){
j=p->adjvex;
if(D[j].know==0 && p->weight<D[j].lowcost){
D[j].lowcost=p->weight;
D[j].nextvex=G->LH[k].data;
}
p=p->nextarc;
}
}
printf("最小生成树为：\n");
for(i=0;i<G->vexnum;++i){
if(i!=k){
printf("(%c,%c)\n",D[i].nextvex,G->LH[i].data);
}
}
}