Question

求个有向图的邻接表（C语言）

Answer 1

#include <stdio.h>
#include<stdlib.h>
typedef struct ArcNode {
int adjvex; // 该弧所指向的顶点的位置
struct ArcNode *nextarc; // 指向下一条弧的指针
int *info; // 该弧相关信息的指针
}ArcNode;
typedef struct VNode {
int data; // 顶点信息
ArcNode *firstarc; // 指向第一条依附该顶点的弧
}VNode, AdjList[50];
typedef struct {
AdjList vertices;
int vexnum, arcnum; // 图的当前顶点数和弧数
}ALGraph;

int locateALG(ALGraph g,int v){
for(int i=0;i<g.vexnum;i++){
if(g.vertices[i].data==v)
return i;
}
return -1;
}

int CreateADG(ALGraph &g){
int i,j,k,l;
ArcNode *p;
int v1,v2;
int c;
printf("请输入有向图的顶点数:");
scanf("%d",&g.vexnum);
while(g.vexnum>50){

printf("\n请输入有向图的顶点数：");
scanf("%d",&g.vexnum);
}
i=g.vexnum*(g.vexnum-1);
printf("请输入有向图的边数:");
scanf("%d",&g.arcnum);
while(g.arcnum>i){

printf("\n请输入有向图的边数：");
scanf("%d",&g.arcnum);
}
getchar();
printf("请依次输入有向图的各个顶点族扮:");
for(i=0;i<g.vexnum;i++){//输入顶点信息

scanf("%d"启闭,&c);
l=locateALG(g,c);
if(l>=0){
printf("输入的顶点重复，请重新输入\n");
i--;
continue;
}
g.vertices[i].data=c;
g.vertices[i].firstarc=NULL;
}
for(k=0;k<g.arcnum;k++){//输入边的信息

printf("请输入第%d条弧的起点与终点(用逗号分隔)：",k+1);
scanf("%d,%d",&v1,&v2);
i=locateALG(g,v1);
j=locateALG(g,v2);
if(i<0||j<0||i==j||(g.vexnum<0)){

k--;
continue;
}
p=(ArcNode*)malloc(sizeof(ArcNode));//建立结点
if(!p) return -1;

p->adjvex=j;
p->nextarc=g.vertices[i].firstarc;//顶点i的链表
g.vertices[i].firstarc=p;//添加到最左边

}
printf("有向图的邻接表创建成功\n");
return 1;
}

void printGra(ALGraph G){
ArcNode *p;
int i;
printf("图中有悄穗裂%d个顶点，%d条弧：\n",G.vexnum,G.arcnum);
for(i=0;i<G.vexnum;i++){
p=G.vertices[i].firstarc;
printf("%d\t",G.vertices[i].data);
while(p){
printf("<%d,%d>",G.vertices[i].data,G.vertices[p->adjvex].data);
p=p->nextarc;
}
printf("\n");
}
}
int main(void)
{
ALGraph g;
CreateADG(g);
printGra(g);
return 0;
}