#define TU_H
#include <string>
#define ERROR -1
#define OK 1
#define FALSE 0
typedef int status;
typedef int InfoType;
typedef string VertexType;
#define MAX_VERTEX_NUM 10
typedef enum{DG,AG}GraphKind;
int visited[MAX_VERTEX_NUM];
typedef struct ArcNode //弧的结构
{
int adjvex;
struct ArcNode *nextarc;
InfoType *info;
}ArcNode;
typedef struct //顶点结构
{
int degree,indegree;//顶点的（出）度，入度
VertexType data;
ArcNode *firstarc;
}VNode,AdjList[MAX_VERTEX_NUM];
typedef struct //图的结构
{
AdjList vertices;
int vexnum,arcnum;
//int kind;
}ALGraph;
int LocateVex(ALGraph G,VertexType u)
{
int i=0;
for(i=0;i<G.vexnum;++i)
//if(strcmp(u,G.vertices[i].data)==0)
if(u == G.vertices[i].data)
return i;
return -1;
}
status CreateGraph(ALGraph &G)
{
int i=0,j=0,k;
VertexType va,vb;
ArcNode *p;
cout<<"请输入图的顶点数,边数: "<<endl;
cin>>G.vexnum>>G.arcnum;
printf("请输入%d个顶点的值:\n",G.vexnum);
for(i=0;i<G.vexnum;++i)
{
cin>>G.vertices[i].data;
G.vertices[i].firstarc=NULL;
G.vertices[i].degree = G.vertices[i].indegree = 0;
}
for(i=0;i<G.vexnum;i++)
cout<<G.vertices[i].data<<endl;
printf("请顺序输入每条弧(边)的弧尾和弧头(以空格作为间隔):\n");
for(k=0;k<G.arcnum; k++)
{
cin>>va>>vb;
i=LocateVex(G,va);
j=LocateVex(G,vb);
if ( i != -1 && j != -1 )
{
p=(ArcNode*)malloc(sizeof(ArcNode));
p->adjvex=j;
//p->info=NULL;
p->nextarc=G.vertices[i].firstarc;
G.vertices[i].firstarc=p;
++G.vertices[i].degree;
++G.vertices[j].indegree;
//++k;
}
}
return OK;
}
void Display(ALGraph G)
{
int i=0;
ArcNode *p;/
ArcNode *p;
int v1;
v1=LocateVex(G,v);
p=G.vertices[v1].firstarc;
if(p)
return p->adjvex;
else
return -1;
}
int NextAdjVex(ALGraph G,VertexType v,VertexType w)
{
ArcNode *p;
int v1,w1;
v1=LocateVex(G,v);
w1=LocateVex(G,w);
p=G.vertices[v1].firstarc;
while(p&&p->adjvex!=w1)
p=p->nextarc;
if(!p||!p->nextarc)
return -1;
else
return p->nextarc->adjvex;
}
VertexType GetVex(ALGraph G,int v)
{
if(v>=G.vexnum||v<0)
exit(ERROR);
return G.vertices[v].data;
}
void print(string v)
{
cout<<v<<" ";
}
#include <iostream>
using namespace std;
int main()
{
int choose=0;
ALGraph MyGraph;
CreateGraph(MyGraph);
char select;
while (1)
{
cout<<"请选择功能：\n1、输出该图的邻接表\n2、求每个节点的度"<<endl;
cin>>choose;
switch (choose)
{
case 1:
Display(MyGraph);
break;
case 2:
out_in_degree(MyGraph);
break;
}
cout<<"是否继续选择功能(Y/N)？"<<endl;
cin>>select;
if( select == 'n' || select == 'N' )
break;
}
return 0;
}