矩阵到链表.cpp

数据结构中关于图的操作,含多种操作方法例子

#include"jb.h"

void travgraph(adjlist g,int n);
void jtol(adjmax adj,int n);

void main()
{
	int i,j,k,n,e;
	char b,t;
	adjmax adj;
	printf("输入顶点数(n)和边数(e):  ");
	scanf("%d%d",&n,&e);
	for(i=1;i<=n;i++)
	{
		getchar();
		printf("  第%d个顶点的信息:  ",i);
		scanf("%c",&adj.vexs[i].data);
	//	adj.vexs[i].num=i;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			adj.edges[i][j]=0;
	for(k=1;k<=e;k++)
	{
		getchar();
		printf("第%d条边=>起点:  ",k);
		b=getchar();
		getchar();
		for(i=1;i<=n&&adj.vexs[i].data!=b;i++)  
			;	
		if(i>n)
		{
			printf("输入的起点不存在!\n");
			exit(0);
		}
		printf("  \t 终点:  ");
		t=getchar();
	//	getchar();
		for(j=1;j<=n&&adj.vexs[j].data!=t;j++)  
			;
		if(j>n)
		{
			printf("输入的终点不存在!\n");
			exit(0);
		}
	//	printf(" \t 权值:  ");
	//	scanf("%d",&w);
		adj.edges[i][j]=adj.edges[j][i]=1;
	}
	printf("该图对应的邻接矩阵为:\n");			//输出该邻接矩阵
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=n;j++)
			printf("%4d",adj.edges[i][j]);
		printf("\n");
	}
	jtol(adj,n);
}

//链接矩阵和链接图的转换
void jtol(adjmax adj,int n)
{
	adjlist g;
	struct edgenode *p,*q;
	int i,j;
	for(i=1;i<=n;i++)
	{
		g[i].data1=adj.vexs[i].data;
		g[i].link=NULL;
	}
	for(i=1;i<=n;i++)
		for(j=1;j<=i;j++)
			if(adj.edges[i][j]!=0)
			{
				p=(struct edgenode*)malloc(sizeof(struct edgenode));
				q=(struct edgenode*)malloc(sizeof(struct edgenode));
				p->adjvex=j;
				p->info=g[j].data1;
				q->adjvex=i;
				q->info=g[i].data1;
				p->next=g[i].link;			//p插入顶点s是邻接表中
				g[i].link=p;
				q->next=g[j].link;			//q插入顶点d的邻接表中
				g[j].link=q;
			}
	travgraph(g,n);
	printf("\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");
	}
}