邻接表的逆邻接表

欢迎加qq群：453398542 学习讨论，会定期分享资料课程，解答问题。

/*已知有向图采用邻接表存储，设计算法，求其逆邻接表。*/
#include<stdio.h>
#include<stdlib.h>
#define max 20
typedef struct ArcNode{
	int adjvex; //该弧所指向的顶点的位置
	struct ArcNode *nextarc; //指向下一条弧的指针 
}ArcNode;
typedef struct VNode{
	char data;  //顶点信息
	ArcNode *firstarc; //指向第一条依附该顶点的弧的指针  
}VNode,AdjList[max];
typedef struct{
	AdjList vertices;
	int vexnum,arcnum;
}ALGraph;
void CreatGraph(ALGraph &G){
	int i,s,e;
	ArcNode *p;
	printf("输入结点数目和边数：");
	scanf("%d%d",&G.vexnum,&G.arcnum);
	getchar();
	printf("输入顶点信息：\n");
	for(i=1;i<=G.vexnum;i++){
		scanf("%c",&G.vertices[i].data);
		G.vertices[i].firstarc=NULL;
	} 
	getchar();
	printf("输入一条边依附的起点序号和终点序号：\n");
	for(i=1;i<=G.arcnum;i++){
		scanf("%d%d",&s,&e);
		getchar();
		p=(ArcNode *)malloc(sizeof(ArcNode));
		p->adjvex=e;
		p->nextarc=G.vertices[s].firstarc;
		G.vertices[s].firstarc=p;
	}
}
void PrintGraph(ALGraph G){
	int i;
	printf("打印有向图：\n");
	for(i=1;i<=G.vexnum;i++){
		printf("%3c",G.vertices[i].data);
		if(G.vertices[i].firstarc==NULL){
			printf("\n");
			continue;
		}
		while(G.vertices[i].firstarc){
			printf("%3d",G.vertices[i].firstarc->adjvex);
			G.vertices[i].firstarc=G.vertices[i].firstarc->nextarc;
		}
		printf("\n");
	}
}
void Reverse(ALGraph A,ALGraph &B){
	//逆邻接表
	int i,k;
	ArcNode *p1,*p2;
	B.vexnum=A.vexnum;
	B.arcnum=A.arcnum;
	for(i=1;i<=A.vexnum;i++){
		scanf("%c",&B.vertices[i].data);
		B.vertices[i].firstarc=NULL;
	} 
	for(i=1;i<=A.arcnum;i++){
		p1=A.vertices[i].firstarc;
		while(p1){
			k=p1->adjvex;
			p2=(ArcNode *)malloc(sizeof(ArcNode));
			p2->adjvex=i;
			p2->nextarc=B.vertices[k].firstarc;
			B.vertices[k].firstarc=p2;
			p1=p1->nextarc;
		}
	}
	
}
int main(){
	ALGraph G,B;
	CreatGraph(G);
	PrintGraph(G);
	Reverse(G,B);
    PrintGraph(B);
	return 0;
}