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