建立十字链表求有向图中每个顶点的入度出度并输出和它相关的弧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
#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 !"< GetVertex();//得到顶点信息
GetArcNum();//得到弧度数
CreatOl();//根据顶点信息建立十字链表
OlPrinter();//输出顶点信息
}

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

void OLGRAPH::GetArcNum()//得到弧度数
{
cout<<"GetArcNum Called !"< cout<<"Please Enter The Number Of The Arc"< cin>>ol.arcnum;
}
void OLGRAPH::CreatOl()//根据顶点信息建立十字链表
{
cout<<"CreatOl Called !"< cout<<"Please Input The ArcMessage :"< 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 !"< }

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

"main.cpp"

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

作者“Dreamer Thinker Doer”