邻接表表示图的各结点的度数(无向图)出度(有向图)

#include<iostream>
#include<string.h>

using namespace std;

#define MAX_VERTEX_NUM 50               //定义最大的结点数

typedef enum{DG,UDG}GraphKind;         //定义图的种类DG(有向图) UDG(无向图)

typedef char VertexData;                         //定义结点信息的数据类型

//定义弧结点
typedef struct EdgeNode
{
  int adjvex;    //该弧指向顶点的位置
  VertexData data;
  EdgeNode *next;
}EdgeNode;

//定义表头结点
typedef struct VetexNode
{
  VertexData data;
  EdgeNode *link;
}VetexNode;

//定义基于邻接表的图
typedef struct AdjList
{
  int vexNun,arcNun; //定义邻接表的顶点数，弧数
  VetexNode vertex[MAX_VERTEX_NUM];
  GraphKind kind;
}AdjList;

// 创建图，输入信息包括（图的定点数，边数，图的种类，及每条边的起始，结束位置）

void CreateGraph(AdjList *adj,int *n)
{
  int e,s,d;
  char str;
  cout<<"输入顶点数(n)和边数(e)\n";
  cin>>*n>>e;
  adj->arcNun=*n;
  adj->vexNun=e;
  cout<<"选择图的类型有向图(D)无向图(U)\n";
  cin>>str;
  //判断图的类型
  switch(str)
  {
    case 'D': adj->kind=DG;
    break;
    case 'U': adj->kind=UDG;
    break;
    default :
    cout<<"没有此类型的图\n";
    break;
  }
  EdgeNode *q=NULL;
  //初始化n个表头结点
  for(int i=1;i<=*n;i++)
  {
     cout<<"输入第"<<i<<"个结点的信息\n";
     cin>>adj->vertex[i].data;
     adj->vertex[i].link=NULL;
  }
  for(i=1;i<=e;i++)
  {
     cout<<"请输入边的起始与目的位置\n";
     cin>>s>>d;
     cout<<"请输入目的结点的信息\n";
     q=(EdgeNode *)malloc(sizeof(EdgeNode));
     if(q==NULL) return;
     q->adjvex=d;
     cin>>q->data;
     q->next=adj->vertex[s].link;
     adj->vertex[s].link=q;
  }
}

//显示图的每条边

void DispGraph(AdjList *adj)
{  
  int n=adj->arcNun;
  cout<<"所有的边为:\n";
  EdgeNode *q=NULL;
  for(int i=1;i<=n;i++)
  {
     q=adj->vertex[i].link;
     if(q==NULL)
    {
       cout<<"没有从"<<adj->vertex[i].data<<"出发的结点\n";
     }
     else
     {
        cout<<"从结点"<<adj->vertex[i].data<<"出发的"<<"边是\n";
        while(q!=NULL)
        {
          cout<<adj->vertex[i].data<<"->"<<q->data<<"\n";
          q=q->next;
        }
     }
  }
}

//如果是有向图求得每个结点的出度，无向图求得每个结点的度数
void GetNodeDu(AdjList *adj)
{
  int countDu;
  EdgeNode *q=NULL;
  for(int i=1;i<=adj->arcNun;i++)
  {
     countDu=0;
     q=adj->vertex[i].link;
     while(q!=NULL)
     {
       countDu++;
       q=q->next;
     }
     if(adj->kind==DG)
        cout<<"结点"<<adj->vertex[i].data<<"的出度为"<<countDu<<"\n";
     else if(adj->kind==UDG)
        cout<<"结点"<<adj->vertex[i].data<<"的度数为"<<countDu<<"\n";
  }
}

int main()
{
  int n;
  AdjList * adj=(AdjList *)malloc(sizeof(AdjList));
  CreateGraph(adj,&n);
  DispGraph(adj);
  GetNodeDu(adj);
  return 0;
}