数据结构_图_建立十字链表求有向图中每个顶点的入度出度并输出和它相关的弧_C++实现

示例输入：

a b c d //每个顶点的名字 char型

(CTRL+Z) //标示输入结束

7 //有向图中弧的个数

0 1 //该数对代表从编号为0的顶点到编号为1的顶点之间有一条弧 0->1 下同

0 2 //a、b、c、d编号分别为0、1、2、3

2 0

2 3

3 0

3 1

3 2

示例输出：

有向图示例

"head.h"

#include<iostream>
#define MAX_VERTEX_NUM 20
using namespace std;

class ArcBox//弧
{
public:
	ArcBox();
	int tailvex,headvex;
	ArcBox * hlink,* tlink;
	char info;
};

ArcBox::ArcBox()
{
	tailvex=headvex=0;
	hlink=tlink=NULL;
}

class VexNode//顶点
{
public:
	VexNode();
	char data;
	ArcBox *firstin,*firstout;
};

VexNode::VexNode()
{
	firstin=firstout=NULL;
}

class OlGraphMessage//十字链表相关
{
public:
	 OlGraphMessage();
	VexNode xlist[MAX_VERTEX_NUM];
	int vexnum,arcnum;
};

OlGraphMessage::OlGraphMessage()
{
	vexnum=arcnum=0;
}

class OLGRAPH
{
public:
	void OlGraphConstructor();//建立十字链表
private:
	void GetVertex();//得到顶点信息
	void GetArcNum();//得到弧度数
	void CreatOl();//根据顶点信息建立十字链表
	void OlPrinter();//输出顶点信息
	OlGraphMessage ol;
};

void OLGRAPH::OlGraphConstructor()
{
	cout<<"OlGraphConstructor Called !"<<endl<<endl;
	GetVertex();//得到顶点信息
	GetArcNum();//得到弧度数
	CreatOl();//根据顶点信息建立十字链表
	OlPrinter();//输出顶点信息
}

void OLGRAPH::GetVertex()//得到顶点信息
{
	cout<<"GetVertex Called !"<<endl<<endl;
	cout<<"Please Enter The Vertex"<<endl<<endl;
	while(cin>>ol.xlist[ol.vexnum].data)
		ol.vexnum++;
	cin.clear();
}

void OLGRAPH::GetArcNum()//得到弧度数
{
	cout<<"GetArcNum Called !"<<endl<<endl;
	cout<<"Please Enter The Number Of The Arc"<<endl<<endl;
	cin>>ol.arcnum;
}
void OLGRAPH::CreatOl()//根据顶点信息建立十字链表
{
	cout<<"CreatOl Called !"<<endl<<endl;
	cout<<"Please Input The ArcMessage :"<<endl<<endl;
	int a,b;
	ArcBox *insert,*p;
	while(ol.arcnum--)
	{
		cin>>a>>b;
		insert=new ArcBox;
		insert->headvex=a;
		insert->tailvex=b;
		p=ol.xlist[a].firstout;
		if(p==NULL)
		{
			ol.xlist[a].firstout=insert;
		}
		else
		{
			while(p->tlink!=NULL)
				p=p->tlink;
			p->tlink=insert;
		}
		p=ol.xlist[b].firstin;
		if(p==NULL)
		{
			ol.xlist[b].firstin=insert;
		}
		else
		{
			while(p->hlink!=NULL)
				p=p->hlink;
			p->hlink=insert;
		}
	}
	cout<<"CreatOl Succeed !"<<endl<<endl;
}

void OLGRAPH::OlPrinter()//输出顶点信息
{
	cout<<"OlPrinter Called !"<<endl<<endl;
	ArcBox * p;
	int od,id;
	for(int i=0;i<ol.vexnum;i++)
	{
		cout<<ol.xlist[i].data<<" : "<<endl;//输出顶点
		od=id=0;//初始化出度和入度
		//求以该顶点为弧尾的弧
		p=ol.xlist[i].firstout;
		while(p!=NULL)
		{
			cout<<ol.xlist[p->headvex].data<<"->"<<ol.xlist[p->tailvex].data<<endl;
			p=p->tlink;
			od++;
		}
		cout<<"OutDegree = "<<od<<endl;
		//求以该顶点为弧头的弧
		p=ol.xlist[i].firstin;
		while(p!=NULL)
		{
			cout<<ol.xlist[p->tailvex].data<<"<-"<<ol.xlist[p->headvex].data<<endl;
			p=p->hlink;
			id++;
		}
		cout<<"InDegree = "<<id<<endl;
	}
}

"main.cpp"

#include"head.h"
int main()
{
	OLGRAPH ol;
	ol.OlGraphConstructor();
	system("pause");
}