一道C数据结构试题

//图的邻接矩阵转换为邻接表;
Status DMG2DLG(DMGraph DMG,DLGraph*DLG)
{
int i,j ;
ArcType*p=NULL ;
DLG->VexNums=DMG.VexNums ;
if(!(DLG->Vex=(VexType*)malloc((DLG->VexNums+1)*sizeof(VexType))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(DLG->FirstArc=(ArcType**)malloc((DLG->VexNums+1)*sizeof(ArcType*))))
{
printf("\n内存溢出。");
return 1 ;
}
for(i=1;i<=DLG->VexNums;i++)
{
DLG->Vex.VNode=DMG.Vex;
DLG->FirstArc=NULL ;
DLG->Vex.indgree=0 ;
for(j=1;j<=DMG.VexNums;j++)
{
if(DMG.Arc[j]{
if(!(p=(ArcType*)malloc(sizeof(ArcType))))
{
printf("\n内存溢出。");
return 1 ;
}
p->Adj.VNode=DMG.Vex[j];
p->Weight=DMG.Arc[j];
p->NextArc=DLG->FirstArc;
DLG->FirstArc=p ;
}
}
for(j=1;j<=DMG.VexNums;j++)
{
if(DMG.Arc[j]++DLG->Vex.indgree ;
}
}
return 0 ;
}
//========================================================================================
//邻接矩阵的遍历;
Status DMG_Traver(DMGraph DMG)
{
int i,*Visited ;
if(!(Visited=(int*)malloc((DMG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
printf("\n 图的深度优先搜索：\n递 归：");
for(i=1;i<=DMG.VexNums;i++)
Visited=0 ;
for(i=1;i<=DMG.VexNums;i++)
if(Visited==0)
DMG_DFS(DMG,i,Visited);
printf("#");
printf("\n非递归：");
for(i=1;i<=DMG.VexNums;i++)
Visited=0 ;
for(i=1;i<=DMG.VexNums;i++)
if(Visited==0)
DMG_DFS_Uni(DMG,i,Visited);
printf("#");
return 0 ;
}
//========================================================================================
//邻 接 表的广度优先遍历;
Status DLG_Traver(DLGraph DLG)
{
int i,*Visited ;
if(!(Visited=(int*)malloc((DLG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
printf("\n\n 图的广度遍历：\n\t");
for(i=1;i<=DLG.VexNums;i++)
Visited=0 ;
for(i=1;i<=DLG.VexNums;i++)
if(Visited==0)
DLG_BFS(DLG,i,Visited);
return 0 ;
}
//========================================================================================
//邻接矩阵深度遍历(递 归);
Status DMG_DFS(DMGraph DMG,int v,int*Visited)
{
int i ;
Visited[v]=1 ;
printf("%2d-->",v);
for(i=1;i<=DMG.VexNums;i++)
if(Visited==0&&DMG.Arc[v]DMG_DFS(DMG,i,Visited);
return 0 ;
}
//========================================================================================
//邻接矩阵深度遍历(非递归);
Status DMG_DFS_Uni(DMGraph DMG,int v,int*Visited)
{
int i,*Stack,top=-1 ;
if(!(Stack=(int*)malloc((DMG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
Visited[v]=1 ;
printf("%2d-->",v);
Stack[++top]=v ;
while(top!=-1)
{
for(i=1;i<=DMG.VexNums;i++)
if(Visited==0&&DMG.Arc[Stack[top]]{
Visited=1 ;
printf("%2d-->",i);
Stack[++top]=i ;
break ;
}
if(i==DMG.VexNums+1)
--top ;
}
return 0 ;
}
//========================================================================================
//邻 接 表广度遍历;
Status DLG_BFS(DLGraph DLG,int v,int*Visited)
{
ArcType*p=NULL ;
int*Queue,rear,front ;
if(!(Queue=(int*)malloc((DLG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
rear=fr ;
Visited[v]=1 ;
printf("%2d -->",v);
rear=(rear+1)%DLG.VexNums ;
Queue[rear]=v ;
while(rear!=front)
{
front=(front+1)%DLG.VexNums ;
p=DLG.FirstArc[Queue[front]];
while(p!=NULL)
{
if(Visited[p->Adj.VNode]==0)
{
Visited[p->Adj.VNode]=1 ;
printf("%2d-->",p->Adj);
rear=(rear+1)%DLG.VexNums ;
Queue[rear]=p->Adj.VNode ;
}
p=p->NextArc ;
}
}
return 0 ;
}
//========================================================================================
//邻接表有向图的Topsort拓扑排序;
Status Topsort(DLGraph DLG,ElemType**ts)
{
int i,j,k,m=0,top=-1 ;
ArcType*tp,*p ;
if(!(*ts=(ElemType*)malloc((DLG.VexNums+1)*sizeof(ElemType))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(tp=(ArcType*)malloc((DLG.VexNums+1)*sizeof(ArcType))))
{
printf("\n内存溢出。");
return 1 ;
}
printf(" Topsort：\n\n ");
//初始化tp;
for(i=1;i<=DLG.VexNums;i++)
{
tp.Adj.VNode=DLG.Vex.VNode ;
tp.NextArc=DLG.FirstArc;
tp.Adj.indgree=DLG.Vex.indgree ;
if(DLG.Vex.indgree==0)
{
tp.Adj.indgree=top ;
top=i ;
}
}
while(top!=-1)
{
j=top ;
top=tp[top].Adj.indgree ;
printf("%2d ,",tp[j].Adj.VNode);
++m ;
p=tp[j].NextArc ;
while(p!=NULL)
{
k=p->Adj.VNode ;
--tp[k].Adj.indgree ;
if(tp[k].Adj.indgree==0)
{
tp[k].Adj.indgree=top ;
top=k ;
}
p=p->NextArc ;
}
}
if(mprintf("\n\t\t不能拓扑!\n");
return 0 ;
}
//========================================================================================
//输出Dijkstra最短路径;
Status PRN_DK(DMGraph DMG,unsigned int***dis)
{
int i,j,flag ;
unsigned int**dist ;
if(!(dist=(unsigned int**)malloc((DMG.VexNums+1)*sizeof(unsigned int*))))
{
printf("\n内存溢出。");
return 1 ;
}
*dis=dist ;
for(i=1;i<=DMG.VexNums;i++)
{
if(!(dist=(unsigned int*)malloc((DMG.VexNums+1)*sizeof(unsigned int))))
{
printf("\n内存溢出。");
return 1 ;
}
Dijkstra(DMG,i,dist);
//Dijkstra最短路径;
}
for(i=1;i<=DMG.VexNums;i++)
{
flag=0 ;
printf("\n从%d出发的最短路径：",i);
for(j=1;j<=DMG.VexNums;j++)
{
if(j!=i&&dist[j]{
printf("\n\t自%d ==>%d点,路径长:%d",i,j,dist[j]);
flag=1 ;
}
}
if(flag==0)
printf("\n\t没有任何路径...");
}
return 0 ;
}
//========================================================================================
//最短路径Dijkstra(迪杰斯特拉);
Status Dijkstra(DMGraph DMG,ElemType v,unsigned int*dist)
{
int i,j,t ;
ElemType*flag ;
unsigned int min ;
if(!(flag=(ElemType*)malloc((DMG.VexNums+1)*sizeof(ElemType))))
{
printf("\n内存溢出。");
return 1 ;
}
//初始化,置U={v}到V-U到各点最短路径;
for(i=1;i<=DMG.VexNums;i++)
{
flag=0 ;
dist=DMG.Arc[v];
}
flag[v]=1 ;
//v并入U;
for(i=1;i<=DMG.VexNums;i++)
{
min=INT_MAX ;
t=i ;
//找到U到V-U最小路径(最短路径);
for(j=1;j<=DMG.VexNums;j++)
{
if(flag[j]==0&&min>dist[j])
{
min=dist[j];
t=j ;
}
}
flag[t]=1 ;
//t并入U;
//重置U到V-U各点最短路径;
for(j=1;j<=DMG.VexNums;j++)
{
if(flag[j]==0&&dist[t]+DMG.Arc[t][j]{
dist[j]=dist[t]+DMG.Arc[t][j];
}
}
}
return 0 ;
}
//========================================================================================
//Floyd(弗洛伊德)最短路径;
Status Floyd(DMGraph DMG,unsigned int***flyd)
{
int i,j,k,**Path=NULL ;
unsigned int**Weight=NULL ;
if(!(Path=(int**)malloc((DMG.VexNums+1)*sizeof(int*))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(Weight=(unsigned int**)malloc((DMG.VexNums+1)*sizeof(unsigned int*))))
{
printf("\n内存溢出。");
return 1 ;
}
*flyd=Weight ;
//初始化;
for(i=1;i<=DMG.VexNums;i++)
{
if(!(Path=(int*)malloc((DMG.VexNums+1)*sizeof(int))))
{
printf("\n内存溢出。");
return 1 ;
}
if(!(Weight=(unsigned int*)malloc((DMG.VexNums+1)*sizeof(unsigned int))))
{
printf("\n内存溢出。");
return 1 ;
}
for(j=1;j<=DMG.VexNums;j++)
{
Weight[j]=DMG.Arc[j];
Path[j]=0 ;
}
}
//Floyd迭代算法;
for(k=1;k<=DMG.VexNums;k++)
for(i=1;i<=DMG.VexNums;i++)
for(j=1;j<=DMG.VexNums;j++)
if(Weight[j]>(Weight[k]+Weight[k][j]))
{
Weight[j]=Weight[k]+Weight[k][j];
Path[j]=k ;
}
//输出;
for(i=1;i<=DMG.VexNums;i++)
{
printf("\n从%d出发的最短路径：",i);
for(j=1;j<=DMG.VexNums;j++)
{
if(j!=i&&Weight[j]printf("\n\t自%d ==>%d点,路径:%4d",i,j,Weight[j]);
}
}
return 0 ;
}
//========================================================================================
//输出邻接矩阵;
Status PRN_DMGraph(DMGraph DMG)
{
int i,j ;
for(i=1;i<=DMG.VexNums;i++)
{
printf("\n\t");
for(j=1;j<=DMG.VexNums;j++)
{
if(DMG.Arc[j]printf(" %3d ",DMG.Arc[j]);
else
printf(" ∞ ");
}
printf("\n");
}
return 0 ;
}
//========================================================================================
//输出邻接表;
Status PRN_DLGraph(DLGraph DLG)
{
int i ;
ArcType*p=NULL ;
for(i=1;i<=DLG.VexNums;i++)
{
printf("\n %2d(入度%d) ==>",i,DLG.Vex.indgree);
p=DLG.FirstArc;
while(p!=NULL)
{
if(p->NextArc)
printf("%d(%d)-->",p->Adj.VNode,p->Weight);
else printf("%d(%d)",p->Adj.VNode,p->Weight);
p=p->NextArc ;
}
}
return 0 ;
}