数据结构之---C++语言实现图的十字链表存储表示

近期一直忙着考研复习，非常久都没有更新博客了。今天写一篇数据结构的存储。

//有向图的十字链表存储表示

//杨鑫

#include <iostream>

#include <cstdio>

#include <stdlib.h>

#include <cstring>

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("请输入有向图的顶点数以及弧数:\n");

	scanf("%d%d",&G.vexnum, &G.arcnum);

	printf("请输入%d个顶点的值，之间有空格隔开:\n",G.vexnum);

	for(i=0; i<G.vexnum; ++i) //构造表头向量

	{

		getchar();

		scanf("%s",G.xlist[i].data);  //输入顶点值

		G.xlist[i].firstin = NULL;

		G.xlist[i].firstout = NULL;

	}

	VertexType v1,v2;

	ArcBox *p;

	printf("请依次输入%d条弧各自依附的两个顶点（输入格式:v1 v2）\n",G.arcnum);

	for(k=0; k < G.arcnum; ++k)  //输入各弧并构造十字链表

	{

		getchar();

		scanf("%s%s",v1,v2);

		i=LocateVex(G,v1);

		j=LocateVex(G,v2);

		p = (ArcBox *)malloc(sizeof(ArcBox));

		if(!p)

			exit(OVERFLOW);

		p->tailvex = 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("\n");

}

//顶点的度：入度+出度

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("=========================================\n");

	printf("该有向图的弧例如以下:\n");

	DisplayArc(G);

	VertexType v;

	printf("\n=========================================\n");

	while(1)

	{

		if(flag == 0)

				break;

		printf("请输入随意顶点,将输出该顶点度的值:");

		scanf("%s",v);

		getchar();

		printf("顶点 %s 的度为 :%d\n",v,VexDegree(G,v));

		printf("结束请输入 0 以回车键结束\n\n");

		cin>>flag;

	}

	printf("=========================================\n");

	return 0;

}

结果：