学步园

十字链表是有向图的一种存储方式,它可以看做将有向图的邻接表和逆邻接表结合起来的一种链表.其弧节点及顶点节点结构示意图如下:

C语言结构话形式定义:

#define MAX_VERTEX_NUM 20							//最多顶点个数
typedef enum{DG,DN,UDG,UDN} GraphKing;				//图的种类
typedef int VertexData;								//顶点数据类型,根据实际需要更改
typedef struct ArcNode{								//弧的信息
	int tailvex;
	int headvex;
	struct ArcNode * hlink;
	struct ArcNode * tlink;
}ArcNode;
typedef struct VertexNode{							//顶点信息
	VertexData data;
	ArcNode *firstin;
	ArcNode *firstout;
}VertexNode;
typedef struct {
	VertexNode vertex[MAX_VERTEX_NUM];				//顶点数组
	int vexnum,arcnum;								//图的顶点数目和弧的数目
	GraphKing king;									//图的种类
}OrthList;											//图的十字链表表示法(Orthogonal List)

测试代码:

#include<stdio.h>
#include<stdlib.h>
#define MAX_VERTEX_NUM 20							//最多顶点个数
typedef enum{DG,DN,UDG,UDN} GraphKing;				//图的种类
typedef int VertexData;								//顶点数据类型,根据实际需要更改
typedef struct ArcNode{								//弧的信息
	int tailvex;
	int headvex;
	struct ArcNode * hlink;
	struct ArcNode * tlink;
}ArcNode;
typedef struct VertexNode{							//顶点信息
	VertexData data;
	ArcNode *firstin;
	ArcNode *firstout;
}VertexNode;
typedef struct {
	VertexNode vertex[MAX_VERTEX_NUM];				//顶点数组
	int vexnum,arcnum;								//图的顶点数目和弧的数目
	GraphKing king;									//图的种类
}OrthList;											//图的十字链表表示法(Orthogonal List)

int Locate(OrthList *G,int v)
{
	int i,j;
	for(i=1;i<=G->vexnum;i++){
		if(G->vertex[i].data == v){
			j = i;
			break;
		}
	}
	return j;
}
void CrtOrthList(OrthList *G)
{
	int vt,vh;
	int i,j,k;
	ArcNode *p;

	printf("输入图的顶点个数及弧的个数:\n");
	scanf("%d%d",&(G->vexnum),&(G->arcnum));

	printf("输入各个顶点:\n");
	for(k=1;k<=G->vexnum;k++){
		scanf("%d",&(G->vertex[k].data));
		G->vertex[k].firstin=G->vertex[k].firstout = NULL;//初始化顶点指针
	}

	for(k=1;k<=G->arcnum; k++){
		printf("输入第%d条弧的弧尾和弧头:\n",k);
		scanf("%d%d",&vt,&vh);
		i = Locate(G,vt);//寻找弧尾在顶点数组中的位置
		j = Locate(G,vh);//寻找弧头在顶点数组中的位置

		p = (ArcNode*)malloc(sizeof(ArcNode));
		p->tailvex = i; p->headvex = j;

		p->tlink = G->vertex[i].firstout;
		G->vertex[i].firstout = p;

		p->hlink = G->vertex[i].firstin;
		G->vertex[i].firstin = p;
	}
}
void Print(OrthList *G)
{
	int i;
	ArcNode*p;
	for(i=1;i<=G->vexnum;i++){
		p=G->vertex[i].firstout;
		if(p){
			printf("以 %d 为尾节点的弧有: ",i);
			while(p){
				printf("%d->%d  ",p->tailvex,p->headvex);
				p=p->tlink;
			}
			printf("\n");
		}
		else printf("没有以 %d 为尾节点的弧!\n",i);
	}
}
int main()
{
	OrthList G;
	CrtOrthList(&G);
	Print(&G);
	return 0;
}