86
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*/
最后更新：2017-04-03 05:39:11