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*/