创建有向图邻接矩阵 转换成邻接表 单链表存储顶点

xiaoxiao2021-02-28  10

//数值类型 整型 //创建有向图邻接矩阵 //把邻接矩阵转换成临界表 //把值大于50的顶点保存在单链表中

//输出邻接矩阵,临界表,大于50的结点

#include<stdio.h>#include<malloc.h>#define VNUM 20#define max 20//定义邻接矩阵typedef struct{ int vexs[VNUM]; int arcs[VNUM][VNUM]; int vexNum,arcNum;}MGraph;//定义临界表边结点typedef struct ArcNode{ int adjvex; struct ArcNode * nextArc;}ArcNode;//定义临界表表头结点typedef struct VertexNode{ int vertex; ArcNode *FirstArc;}VertexNode;//定义图的临接表类型typedef struct ALGraph{ VertexNode adjlist[max];}ALGraph;//定义单链表结点typedef struct Lnode{ int data; struct Lnode *next;}Lnode,*LinkList;void CreateGraph(MGraph *G,int v,int a,LinkList *L);void CreateAdjlist(ALGraph *G,int v,MGraph *M);void initLinkList(LinkList *L);void displayALGraph(ALGraph *A,int v);void displayLinkList(LinkList L);void displayMGraph(MGraph *G,int v,int a);void initLinkList(LinkList *L){ *L=(LinkList)malloc(sizeof(Lnode)); if(*L==NULL) return 0; (*L)->next=NULL; return 1;}void CreateGraph(MGraph *G,int v,int a,LinkList *L){ int i,j,k; LinkList s; for(i=0;i<v;i++) { printf("请输入第%d个顶点的值\n",i+1); scanf("%d",&G->vexs[i]); if(G->vexs[i]>50) { s=(LinkList)malloc(sizeof(Lnode)); s->data=G->vexs[i]; s->next=(*L)->next; (*L)->next=s; } } for(i=0;i<v;i++) for(j=0;j<v;j++) G->arcs[i][j]=0; for(k=0;k<a;k++) { printf("请读入第%d条边邻接的两个从1开始的序号\n",k+1); scanf("%d%d",&i,&j); G->arcs[i-1][j-1]=1; }}void CreateAdjlist(ALGraph *G,int v,MGraph *M){ int i,m,n; ArcNode *p; for(i=0;i<v;i++) { G->adjlist[i].vertex=M->vexs[i]; G->adjlist[i].FirstArc=NULL; } for(m=0;m<v;m++) for(n=0;n<v;n++) { if(M->arcs[m][n]==1) { p=(ArcNode *)malloc(sizeof(ArcNode)); p->adjvex=n; p->nextArc=G->adjlist[m].FirstArc; G->adjlist[m].FirstArc=p; } } }//输出邻接矩阵void displayMGraph(MGraph *G,int v,int a){ int i,j; for(i=0;i<v;i++) { for(j=0;j<v;j++) { printf("%d ",G->arcs[i][j]); } printf("\n"); }}//输出单链表void displayLinkList(LinkList L){ LinkList p=L->next; if(p==NULL) printf("没有大于50的顶点\n"); while(p) { printf("%d \n",p->data); p=p->next; }}//输出临接表void displayALGraph(ALGraph *A,int v){ int i; ALGraph *p=A; for(i=0;i<v;i++) { printf("%d %d->",i,p->adjlist[i].vertex); while(p->adjlist[i].FirstArc) { printf("%d->",p->adjlist[i].FirstArc->adjvex); p->adjlist[i].FirstArc=p->adjlist[i].FirstArc->nextArc; } printf("\n"); } printf("\n");}void main(){ int v,a;//定点数和边数 MGraph G; ALGraph A; LinkList L; initLinkList(&L); printf("请输入顶点数和边数\n"); scanf("%d%d",&v,&a); printf("创建邻接矩阵\n"); CreateGraph(&G,v,a,&L); printf("创建邻接表\n");    CreateAdjlist(&A,v,&G); printf("输出邻接矩阵\n"); displayMGraph(&G,v,a); printf("输出邻接表\n"); displayALGraph(&A,v); printf("输出顶点大于50的单链表\n"); displayLinkList(L);}

转载请注明原文地址: https://www.6miu.com/read-2799963.html

最新回复(0)