建立十字鏈表求有向圖中每個頂點的入度出度並輸出和它相關的弧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");
}

 作者“Dreamer Thinker Doer”