自己搞到答案啦给大家分享一下
# include <stdio.h>
# include <stdlib.h>
typedef int vextype;
typedef int infotype;
typedef int status;
# define max_vex_num 15//顶点字符串最大长度
# define FALSE 0
# define TRUE 1
# define OVERFLOW -2
typedef struct arcbox
{
int tailvex,headvex;//弧头弧尾的位置
struct arcbox *hlink,*tlink;//分别为弧头相同和弧尾相同的链域
infotype * info;//指针信息
}arcbox;
typedef struct vexnode
{
vextype data;
arcbox *firstin,*firstout;//分别指向顶点的第一条入弧和出弧
}vexnode;
typedef struct
{
vexnode xlist[max_vex_num];//表头向量
int vexnum,arcnum;//顶点数弧数
}OLgraph;
int Locatevex(OLgraph G,int d)
{
int k;
for(k=0;k<G.vexnum;++k)
{
if(G.xlist[k].data==d)
return k;
}
}
status creat_DG(OLgraph &G)
{
int a,k,incinfo,i,j;
vextype tailnum,headnum;
arcbox *p;
printf("输入结点个数:");
scanf("%d",&G.vexnum);
printf("输入弧的条数:");
scanf("%d",&G.arcnum);
printf("输入有无权值判定符(0表示没有,1表示有):");
scanf("%d",&incinfo);
printf("输入所有弧结点数据:");
for(a=0;a<G.vexnum;++a)//构造表头向量
{
scanf("%d",&G.xlist[a].data);
G.xlist[a].firstin=NULL;
G.xlist[a].firstout=NULL;
}
for(k=0;k<G.arcnum;++k)
{
printf("输入弧头结点和弧尾结点的数据:");
scanf("%d,%d",&tailnum,&headnum);
i=Locatevex(G,tailnum);//确定头尾指针在弧中的位置
j=Locatevex(G,headnum);
p=(arcbox*)malloc(sizeof(arcbox));//产生弧结点
p->tailvex=i;//对结点赋值
p->headvex=j;
p->hlink=G.xlist[j].firstin;//完成在入弧和出弧链表的表头插入
p->tlink=G.xlist[i].firstout;
//p->info=NULL;
G.xlist[j].firstin=G.xlist[i].firstout=p;
if(incinfo)
{
printf("输入权值:");
scanf("%d",p->info);
}
}
return TRUE;
}//creat_DG
typedef int boolen;
boolen visited[max_vex_num ];
int finished[max_vex_num ];
int number;
void DFS_1(OLgraph G,int v)
{
arcbox *p;
visited[v]=TRUE;//访问标志
p=G.xlist[v].firstout;//P指向第V个顶点的出度
while(p)
{
if(!visited[p->headvex])//该弧的头顶点没被访问
{
DFS_1(G,p->headvex);
}
p=p->tlink;//查找下一个结点
}
finished[number]=v;
number=number+1;
}
void DFStraverse_1(OLgraph G)
{
int v;
for(v=0;v<G.vexnum;++v)
visited[v]=FALSE;//未被访问
for(v=0;v<G.vexnum;++v)//由序号0开始继续查找未被访问的顶点
{
if(!visited[v])
DFS_1(G,v);
}
}
void DFS_2(OLgraph G,int v)
{
arcbox *p;
visited[v]=TRUE;
printf("%3d",G.xlist[v].data);
p=G.xlist[v].firstin;//p指向第V个顶点的入度
while(p)
{
if(!visited[p->tailvex])//如果该图的尾顶点未被访问
DFS_2(G,p->tailvex);
p=p->hlink;//查找下一个结点
}
}
void DFStraverse_2(OLgraph G)
{
int v,m=1;
for(v=0;v<G.vexnum;v++)
visited[v]=FALSE;
for(v=G.vexnum-1;v>=0;v--)
{
if(!visited[finished[v]])
{
printf("\n");
printf("\n");
printf("第%d个连通分量的顶点集:",m);
m=m+1;
DFS_2(G,finished[v]);
}
}
}
void main()
{
OLgraph G;
printf("====================================================\n");
printf("使用说明:本程序实现十字链表算法创建有向图\n");
printf("====================================================\n\n\n\n");
printf("===================@输入模块@=======================\n");
creat_DG(G);
printf("====================================================\n\n\n\n");
printf("===================@输出模块@=======================");
DFStraverse_1(G);
DFStraverse_2(G);
printf("\n\n");
printf("====================================================\n");
printf("\n");
}