數據結構之---C++語言實現圖的十字鏈表存儲表示

數據結構之---C++語言實現圖的十字鏈表存儲表示

最近一直忙著考研復習，很久都沒有更新博客了，今天寫一篇數據結構的存儲。

//有向圖的十字鏈表存儲表示
//楊鑫
#include 
#include 
#include 
#include 
using namespace std;
#define MAX_VERTEX_NUM 20
#define OVERFLOW -2
#define OK 1
typedef int Status;
typedef char VertexType[MAX_VERTEX_NUM];
typedef char InfoType;
//弧（邊）的結構體
typedef struct ArcBox
{
	int tailvex,headvex;  						//該弧的尾和頭頂點的位置
	struct ArcBox *hlink, *tlink;  				//分別為弧頭相同和弧尾相同的弧的鏈域
	InfoType *info;  							//該弧的相關信息的指針
}ArcBox;

//頂點的結構體
typedef struct VexNode
{
	VertexType data;
	ArcBox *firstin, *firstout;  //分別指向該頂點的第一條入弧和出弧
}VexNode;

//有向圖的結構體
typedef struct  
{
	VexNode xlist[MAX_VERTEX_NUM];  	//表頭向量
	int vexnum, arcnum;  				//有向圖的當前頂點數和弧數
}OLGraph;

int LocateVex(OLGraph &G, VertexType u)
{
	for(int i = 0; i < G.vexnum; ++i)
		if(strcmp(G.xlist[i].data, u) == 0)
			return i;
	return -1;
}

//構造有向圖G;
Status CreateDG(OLGraph &G)
{
	
	int i,j,k;
	printf(請輸入有向圖的頂點數以及弧數:
);
	scanf(%d%d,&G.vexnum, &G.arcnum);
	printf(請輸入%d個頂點的值，之間有空格隔開:
,G.vexnum);
	for(i=0; itailvex = i;
		p->headvex = j;
		p->hlink = G.xlist[j].firstin;
		p->tlink = G.xlist[i].firstout;
		p->info = NULL;
		G.xlist[j].firstin = G.xlist[i].firstout = p;  //完成在入弧和出弧鏈頭的插入
	}
	getchar();
	return OK;
}

void DisplayArc(OLGraph &G)
{
	ArcBox *p;
	for(int i=0; i < G.vexnum; ++i)
	{
		p=G.xlist[i].firstout;
		while(p)
		{
			printf(<%s,%s> ,G.xlist[p->tailvex].data, G.xlist[p->headvex].data);
			p = p->tlink;
		}
	}
	printf(
);
}


//頂點的度：入度+出度
int VexDegree(OLGraph &G, VertexType v)
{
	
	int k = LocateVex(G,v);
	if(k<0)
		exit(OVERFLOW);
	int id=0,od=0;  //入度，出度

	ArcBox *pin = G.xlist[k].firstin;
	ArcBox *pout = G.xlist[k].firstout;
	while(pin)  //求入度
	{
		++id;
		pin = pin->hlink;
	}

	while(pout)  //求出度
	{
		++od;
		pout = pout->tlink;
	}

	return id+od; //頂點的度
}

int main()
{
	int flag = 1;
	OLGraph G;
	CreateDG(G);
	printf(=========================================
);
	printf(該有向圖的弧如下:
);
	DisplayArc(G);
	VertexType v;
	printf(
=========================================
);
	while(1)
	{
		if(flag == 0)
				break;
		printf(請輸入任意頂點,將輸出該頂點度的值:);
		scanf(%s,v);
		getchar();
		printf(頂點 %s 的度為 :%d
,v,VexDegree(G,v));
		printf(結束請輸入 0 以回車鍵結束

);
		cin>>flag;
	}
	printf(=========================================
);
	return 0;
}

結果：