图的实现--邻接表(求出各顶点的出度和入度)

#include<iostream>
using namespace std;
#include<stdio.h>
#define MAX 100
struct ArcNode{//边结点

	int adjvex;//有向边的另一个邻接点的序号
	ArcNode *nextarc;//指向下一个边结点的指针
};
struct VNode{

	int data;
	ArcNode *head1;
	ArcNode *head2;

};
struct LGraph{
	VNode vertexs[MAX];
   int vernum,arcnum;	
};
LGraph lg;
void CreateLG(LGraph *lg)
{

	int i=0;
	ArcNode *pi;
	int v1,v2;
	//lg->vernum=lg->arcnum=0;
	//scanf("%d%d",&lg->vernum,&lg->arcnum);
	for(i=0;i<lg->vernum;i++)
		lg->vertexs[i].head1=lg->vertexs[i].head2=NULL;
	for(i=0;i<lg->arcnum;i++)
	{
		scanf("%d%d",&v1,&v2);
		v1--;v2--;
		pi=new ArcNode;
		pi->adjvex=v2;
		pi->nextarc=lg->vertexs[v1].head1;
		lg->vertexs[v1].head1=pi;
		pi=new ArcNode;
		pi->adjvex=v1;
		pi->nextarc=lg->vertexs[v2].head2;
		lg->vertexs[v2].head2=pi;
	}
}
void DeleteLG(LGraph *lg)
{

	int i;
	ArcNode *pi;
	for(i=0;i<lg->vernum;i++)
	{
		pi=lg->vertexs[i].head1;
		while(pi!=NULL)
		{

			lg->vertexs[i].head1=pi->nextarc;
			delete pi;
			pi=lg->vertexs[i].head1;
		}
        pi=lg->vertexs[i].head2;
		while(pi!=NULL)
		{

			lg->vertexs[i].head2=pi->nextarc;
			delete pi;
			pi=lg->vertexs[i].head2;

		}

	}
}
int main()
{
//	CreateLG(&lg);
	int i;
	int id,od;
	ArcNode *pi;
	while(1)
	{

		lg.vernum=lg.arcnum=0;
		scanf("%d%d",&lg.vernum,&lg.arcnum);
		if(lg.vernum==0) break;
		
	    CreateLG(&lg);
		for(i=0;i<lg.vernum;i++)//求出度
		{

			od=0;
			pi=lg.vertexs[i].head1;
			while(pi!=NULL)
			{

				od++;
				pi=pi->nextarc;

			}
			if(i==0)
				printf("%d",od);//输出出度
			else
				printf(" %d",od);

		}
		printf("\n");
		for(i=0;i<lg.vernum;i++)//求入度
		{

			id=0;
			pi=lg.vertexs[i].head2;
			while(pi!=NULL)
			{
			pi=pi->nextarc;
            id++;

		    }
			if(i==0)
				printf("%d",id);//输出入度
			else 
				printf(" %d",id);

	    }
		printf("\n");
               DeleteLG(&lg);
	}
	return 0;
}//测试数据如下:
//4 7  分别代表定点数和边数 
//1 4//弧尾和弧头
//2 1
//2 2
//2 3 
//2 3
//4 2
//4 3

图的实现--邻接表(求出各顶点的出度和入度)

上一篇:开源代码生成器MyGeneration使用(四) 综合示例


下一篇:Freehand新手入门:Freehand9工具箱中各种绘图工具的使用方法