C 十字链表

C 的十字链表实现

#include<stdio.h>
#include<stdlib.h>
#include<conio.h>
#include<string.h>

#define MAX 20/*顶点的个数*/

typedef struct ArcBox{
	int tailvex,headvex;/*弧的尾和头顶点位置*/
	struct ArcBox *hlink,*tlink;/*分别为弧头相同弧尾相同的弧的链域*/
}ArcBox;

typedef struct type{
	char r[3];/*顶点值*/
}VertexType;

typedef struct VexNode{
	VertexType data;
	ArcBox *firstin,*firstout;/*分别指向该顶点第一条入弧和出弧*/
}VexNode;

typedef struct{
	VexNode xlist[MAX];/*表头向量*/
	int vexnum,arcnum;/*有向图的当前顶点数和弧数*/
}OLGraph;

int Locate(OLGraph G,VertexType v1)/*确定v1在图顶点中的位置*/
{
	int i;
	for(i=0;i<G.vexnum;i++)
		if(strcmp(v1.r,G.xlist[i].data.r)==0) return i;
		return -1;
}

int CreateDG(OLGraph *G)
{
	int i,k,j;
	VertexType v1,v2;
	ArcBox *p;
	printf("分别输入顶点和弧的个数：");
	scanf("%d%d",&G->vexnum,&G->arcnum);
	printf("输入顶点的值: ");

	for(i=0;i<G->vexnum;i++)/*构造表头向量*/
	{
		scanf("%s",&G->xlist[i].data);
		G->xlist[i].firstin=NULL;G->xlist[i].firstout=NULL;/*初始化指针*/
	}

	for(k=0;k<G->arcnum;++k)/*输入各弧并构造十字链表*/
	{
		printf("输入第 %d 的两个点（方向） ：",k+1);
		scanf("%s%s",v1.r,v2.r);
		i=Locate(*G,v1);j=Locate(*G,v2);/* v1和v2 的位置*/
		p=(ArcBox *)malloc(sizeof(ArcBox));/*申请弧空间*/
		p->tailvex=i;p->headvex=j;/*对弧结点赋值*/
		p->hlink=G->xlist[j].firstin;
		p->tlink=G->xlist[i].firstout;
		G->xlist[j].firstin=G->xlist[i].firstout=p;/*完成在入弧和出弧链头的插入*/
	}
	return 1;
}
void main()
{
	OLGraph G;
	int i;
	ArcBox *q;
	CreateDG(&G);
	printf("十字邻接表为：\n");

	for(i=0;i<G.vexnum;i++)/*输出邻接表*/
	{
		printf(" *%s* ",G.xlist[i].data.r);
		q=G.xlist[i].firstout;

		while(q)
		{
			printf(" *%s %s*",G.xlist[q->headvex].data.r,G.xlist[q->tailvex].data.r);
			q=q->tlink;
		}

		printf("\n     ");
		q=G.xlist[i].firstin;

		while(q)
		{
			printf(" *%s %s*",G.xlist[q->headvex].data.r,G.xlist[q->tailvex].data.r);
			q=q->hlink;
		}
		printf("\n");
	}
}
/*书第165页*/
/*可输入4 7
1 2 3 4
1 3
1 2
3 1
3 4
4 1
4 2
4 3*/