图的邻接表的基本操作及显示实例

// 图的邻接表.cpp : 定义控制台应用程序的入口点。
//
#include<iostream>
using namespace std;
#include "stdafx.h"
#define Max_Vertex_Num 20
/*邻结点的信息*/
struct ListNode{
int position;//位置信息
ListNode *next;//后继结点信息
};
typedef ListNode *position;
/*表头结点的信息*/
struct FirstNode{
 char data;
 ListNode *FirstArc;
};
typedef FirstNode AdList[Max_Vertex_Num];//表头结点的数组
struct AdGraph{
AdList vertices;
int Vexnum,Arcnum;
};
/*G用邻接表表示，从键盘输入图的顶点序列和边集，构造图G*/
void CreateGraph(AdGraph &G)
{
    cout<<"G用邻接表表示，从键盘输入图的顶点序列和边集，构造图G"<<endl;
 cin>>G.Arcnum>>G.Vexnum;
 for(int i=0;i<G.Vexnum;i++)
 {
  cin>>G.vertices[i].data;//输入顶点的信息
  G.vertices[i].FirstArc=NULL;//边链头指针置空
 }
 for(int j=0;j<G.Arcnum;j++)
 {
  int m,n;
  char vi,vj;
  cin>>vi>>vj;
  m=Locate(vi,G);//获取对应点名称的位置下标
  n=Locate(vj,G);
  /*单链表形式在每个表头结点后面插入结点*/
  position p=new ListNode;
  p->position=n;
  p->next=G.vertices[m].FirstArc;
  G.vertices[m].FirstArc=p;
  /*无向图需要倒置信息,此处默认用户输入的是无向图的结点信息*/
  p->position=m;
  p->next=G.vertices[n].FirstArc;
  G.vertices[n].FirstArc=p;
  /*至此邻接表创建完毕*/
 }
}
/*查找顶点信息为v的位置下标*/
int Locate(char v,AdGraph &G)
{
 for(int i=0;i<G.Vexnum;i++)
 {
  if(G.vertices[i].data==v)
   return i;
 }
 return -1;
}
/*在邻接表中插入边的操作*/
void insertArc(AdGraph G,char vi,char vj){
     int m,n;
        cin>>vi>>vj;
  m=Locate(vi,G);//获取对应点名称的位置下标
  n=Locate(vj,G);
  /*单链表形式在每个表头结点后面插入结点*/
  position p=new ListNode;
  p->position=n;
  p->next=G.vertices[m].FirstArc;
  G.vertices[m].FirstArc=p;
  /*无向图需要倒置信息,此处默认用户输入的是无向图的结点信息*/
  p->position=m;
  p->next=G.vertices[n].FirstArc;
  G.vertices[n].FirstArc=p;
  /*至此邻接表创建完毕*/
}
/*返回结点位置为v的第一个邻接点*/
int FirstNo(AdGraph G,int v)
{
 if(G.vertices[v].FirstArc)
   return G.vertices[v].FirstArc->position;
 else
  return -1;
}
/*输出邻接表的信息*/
void prtAdGraph(AdGraph G)
{
 for(int i=0;i<G.Vexnum;i++)
 {
  position p=G.vertices[i].FirstArc;
  cout<<G.vertices[i].data;
  while(p)
  {
   cout<<" "<<p->position;
   p=p->next;
  }
  cout<<endl;
 }
}
void main()
{
 AdGraph G;
 CreateGraph(G);
 prtAdGraph(G);
 system("pause");
}