链表到矩阵.cpp

来自「数据结构中关于图的操作,含多种操作方法例子」· C++ 代码 · 共 86 行

#include"jb.h"

void travgraph(adjlist g,int n);
void btoj(adjlist g,int n);

void main()
{
	adjlist g;
	int e,i,s,d,n;
	struct edgenode *p,*q;
	printf("输入结点数(n)和边数(e):  ");
	scanf("%d%d",&n,&e);
	for(i=1;i<=n;i++)
	{
		getchar();
		printf("第%d个结点信息:",i);
		scanf("%c",&g[i].data1);
		g[i].link=NULL;
	}
	for(i=1;i<=e;i++)
	{
		printf("第%d条边的起点序号,终点序号:",i);
		scanf("%d%d",&s,&d);
		p=(struct edgenode*)malloc(sizeof(struct edgenode));
		q=(struct edgenode*)malloc(sizeof(struct edgenode));
		p->adjvex=d;
		p->info=g[d].data1;
		q->adjvex=s;
		q->info=g[s].data1;
		p->next=g[s].link;			//p插入顶点s是邻接表中
		g[s].link=p;
		q->next=g[d].link;			//q插入顶点d的邻接表中
		g[d].link=q;
	}
	travgraph(g,n);
	btoj(g,n);
}

//遍历邻接表表示的一个图
void travgraph(adjlist g,int n)
{
	int i;
	struct edgenode *p;
	printf("建立的邻接表如下:\n");
	for(i=1;i<=n;i++)
	{
		printf("[%d,%c]=>",i,g[i].data1);
		p=g[i].link;
		while(p!=NULL)
		{
			printf("(%d,%c)-->",p->adjvex,p->info);
			p=p->next;
		}
		printf("\n");
	}
}

void btoj(adjlist g,int n)
{
	adjmax adj;
	struct edgenode *p;
	int i,j,k;
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			adj.edges[i][j]=0;
	for(i=1;i<=n;i++)
	{
		adj.vexs[i].data=g[i].data1;	
		for(p=g[i].link;p!=NULL;p=p->next)
		{
			k=p->adjvex;
			adj.edges[i][k]=adj.edges[k][i]=1;
		}
	}
	printf("上述链表转化的矩阵为:\n");
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			printf("%4d",adj.edges[i][j]);
		printf("\n");
	}
}