图-邻接表.cpp

这个是有关数据结构中有关图的存储问题,包含了邻接表,和邻接巨阵的存储代码

#include <iostream>
using namespace std;

#define VNUM 20
#define OK 1
#define ERROR 0
#define NULL 0
#define OVERFLOW -2
#define TRUE 1
#define FALSE 0

typedef int Status;
typedef int ElemType;

typedef struct ArcNode
{
	int Adjvex;
	struct ArcNode *nextarc;
}ArcNode;
             
typedef struct VexNode
{
	int Vertex;
	ArcNode *firstarc;
}Adjlist[VNUM]; 
            
typedef struct Graphs
{
	Adjlist Adjlist;
	int vexnum,arcnum;
}Graph;

Status Create(Graph *g)
{
	int n, e, i, j, k;
	int lasti[VNUM], lastj[VNUM], flag;
	ArcNode *p;
	cout << "创建一个有向图:" << endl;
	cout << "请输入要建立的图的顶点数n=";
	cin >> n;
	cout << "请输入要建立的图的边数e=";
	cin >> e;
	g->vexnum = n;
	g->arcnum = e;
	for(i=0;i<n;i++)
	{
		g->Adjlist[i].Vertex=i;
		g->Adjlist[i].firstarc=NULL;
	}
	for(k=1;k<=e;k++)
	{
		cout << "请输入第" << k << "条边的起点:";
		cin >>i;
		cout << "请输入第" << k << "条边的终点:";
		cin >>j;
		for (int ks=k;ks>0;ks--)
		{
			if (lasti[ks]==i && lastj[ks]==j)
			{
				flag = 1;
			}
		}
		if (i>n || j>n || i==j)
		{
			flag = 1;
		}
		if (flag ==1)
		{
			cout << "您输入的数据有误！" << endl;
			k--;
			flag = 0;
			continue;
		}
		lasti[k] = i;
		lastj[k] = j;
		p = (ArcNode *)malloc(sizeof(ArcNode));
		p->Adjvex = j;
		p->nextarc = g->Adjlist[i].firstarc;
		g->Adjlist[i].firstarc = p;
	}
	return OK;
}

int OutDegree(Graph g, int v)
{
	ArcNode *p;
	int n=0;
	p = g.Adjlist[v].firstarc;
	while (p!=NULL)
	{
		n++;
		p = p->nextarc;
	}
	return n;
}

Status Inverse(Graph g, Graph &h)
{
	int i, w;
	ArcNode *p, *q;
	h.vexnum = g.vexnum;
	h.arcnum = g.arcnum;
	for(i=0;i<g.vexnum;i++)
	{
		h.Adjlist[i].Vertex = g.Adjlist[i].Vertex;
		h.Adjlist[i].firstarc = NULL;
	}
	for(i=0;i<g.vexnum;i++)
	{
		p = g.Adjlist[i].firstarc;
		while (p!=NULL)
		{
			w = p->Adjvex;
			q = (ArcNode *)malloc(sizeof(ArcNode));
			q->Adjvex = i;
			q->nextarc = h.Adjlist[w].firstarc;
			h.Adjlist[w].firstarc = q;
			p = p->nextarc;
		}
	}
	return OK;
}

Status DisInDegree(Graph g, Graph h)
{
	int i;
	Inverse(g, h);
	cout << "各顶点的入度:" << endl;
	for (i=0;i<h.vexnum;i++)
	{
		cout << i+1 << ":" << OutDegree(h, i) << endl;
	}
	return OK;
}

Status DisOutDegree(Graph g)
{
	int i;
	cout << "各顶点的出度:" << endl;
	for (i=0;i<g.vexnum;i++)
	{
		cout << i+1 << ":" << OutDegree(g, i) << endl;
	}
	return OK;
}

Status Display(Graph *g)
{
	int i, have;
	ArcNode *p;
	cout << "输出图：" << endl;
	for (i=0;i<g->vexnum;i++)
	{
		p = g->Adjlist[i].firstarc;
		have = 0;
		while(p!=NULL)
		{
			cout << "(" << i << "," << p->Adjvex << ")";
			p = p->nextarc;
			have = 1;
		}
		if (have==1)
		{
			cout << endl;
		}
	}
	return OK;
}

void main(void)
{
	Graph Ga, h;
	int visited[VNUM], i;
	int select;
	do
	{
		cout << "***********图程序功能选择菜单***********\n";
		cout << "* 1.有向图的建立                       *\n";
		cout << "* 2.有向图的输出                       *\n";
	    cout << "* 0.结束程序                           *\n";
		cout << "****************************************\n";
		
		cout << endl << "\n请输入您的选择：" << endl;
		cin >> select;
		switch (select)
		{
		case 0:
			cout << "操作结束，跳出程序！" << endl;
			break;
		case 1:
			for(i=0;i<VNUM;i++)
			{
				visited[i]=0;
			}
			if (Create(&Ga)==ERROR)
			{
				cout << endl << "创建失败！" << endl;
			}
			else 
			{
				cout << endl << "已创建有向图！" << endl;
			}
	    	break;
		case 2:
			if (Display(&Ga)==ERROR || DisOutDegree(Ga)==ERROR || DisInDegree(Ga, h)==ERROR) 
			{
				cout << endl << "输出失败！" << endl;
			}
			else 
			{
				cout << endl << "输出成功！" << endl;
			}
			break;	
		default:
			cout << "输入的数字是无效的！\n" << endl;
			break;
		}
        cout << endl << endl;
	}while (select!=0);
}