【データ構造】キーパス
キーパス
データ構造の中で肝心な経路を求めて、以前書いたコード、みんなに伝えて見せます!
データ構造の中で肝心な経路を求めて、以前書いたコード、みんなに伝えて見せます!
/*
：
： C
：VC++ 6.0
：2014-3-25
*/
#include <stdio.h>
#include <limits.h>
#include <malloc.h>
#include<cstdlib>
#include <string.h>
// 。 7.13、7.14
//
#define MAX_NAME 3 // +1
#define MAX_VERTEX_NUM 20
typedef int InfoType; //
typedef char VertexType[MAX_NAME]; //
typedef enum{DG,DN,AG,AN}GraphKind; // { , , , }
typedef struct ArcNode
{
int adjvex; //
struct ArcNode *nextarc; //
InfoType *info; // ）
}ArcNode; //
typedef struct VNode
{
VertexType data; //
ArcNode *firstarc; // ,
}VNode,AdjList[MAX_VERTEX_NUM];//
typedef struct
{
AdjList vertices;
int vexnum,arcnum; //
int kind; //
}ALGraph;
int ve[MAX_VERTEX_NUM]; // ( 7.13 7.14)
// G u, ; -1。
int LocateVex(ALGraph G,VertexType u)
{
int i;
for(i=0;i<G.vexnum;++i)
if(strcmp(u,G.vertices[i].data)==0)
return i;
return -1;
}
// , G( 4 )。
int CreateGraph(ALGraph *G)
{
int i,j,k;
int w; //
VertexType va,vb;
ArcNode *p;
printf(" ( :0, :1, :2, :3): ");
scanf("%d",&(*G).kind);
printf(" :（ ）
");
scanf("%d%d", &(*G).vexnum, &(*G).arcnum);
printf(" %d (<%d ):
",(*G).vexnum,MAX_NAME);
for(i = 0; i < (*G).vexnum; ++i) //
{
scanf("%s", (*G).vertices[i].data);
(*G).vertices[i].firstarc = NULL;
}
if((*G).kind == 1 || (*G).kind == 3) //
printf(" ( ) 、 ( ):
");
else //
printf(" ( ) ( ):
");
for(k = 0;k < (*G).arcnum; ++k) //
{
if((*G).kind==1||(*G).kind==3) //
scanf("%d%s%s",&w,va,vb);
else //
scanf("%s%s",va,vb);
i = LocateVex(*G,va); //
j = LocateVex(*G,vb); //
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = j;
if((*G).kind == 1 || (*G).kind == 3) //
{
p->info = (int *)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; //
p->nextarc = (*G).vertices[i].firstarc; //
(*G).vertices[i].firstarc = p;
if((*G).kind >= 2) // ,
{
p = (ArcNode*)malloc(sizeof(ArcNode));
p->adjvex = i;
if((*G).kind == 3) //
{
p->info = (int*)malloc(sizeof(int));
*(p->info) = w;
}
else
p->info = NULL; //
p->nextarc = (*G).vertices[j].firstarc; //
(*G).vertices[j].firstarc = p;
}
}
return 1;
}
// G。
void Display(ALGraph G)
{
int i;
ArcNode *p;
switch(G.kind)
{
case DG: printf("
");
break;
case DN: printf("
");
break;
case AG: printf("
");
break;
case AN: printf("
");
}
printf("%d ：
",G.vexnum);
for(i = 0; i < G.vexnum; ++i)
printf("%s ",G.vertices[i].data);
printf("
%d ( ):
", G.arcnum);
for(i = 0; i < G.vexnum; i++)
{
p = G.vertices[i].firstarc;
while(p)
{
if(G.kind <= 1) //
{
printf("%s→%s ",G.vertices[i].data,
G.vertices[p->adjvex].data);
if(G.kind == DN) //
printf(":%d ", *(p->info));
}
else // ( )
{
if(i < p->adjvex)
{
printf("%s－%s ",G.vertices[i].data,
G.vertices[p->adjvex].data);
if(G.kind == AN) //
printf(":%d ",*(p->info));
}
}
p=p->nextarc;
}
printf("
");
}
}
// ， 7.12、7.13
void FindInDegree(ALGraph G,int indegree[])
{
int i;
ArcNode *p;
for(i=0;i<G.vexnum;i++)
indegree[i]=0; //
for(i=0;i<G.vexnum;i++)
{
p=G.vertices[i].firstarc;
while(p)
{
indegree[p->adjvex]++;
p=p->nextarc;
}
}
}
typedef int SElemType; //
#define STACK_INIT_SIZE 10 //
#define STACKINCREMENT 2 //
// P46
typedef struct SqStack
{
SElemType *base; // ，base NULL
SElemType *top; //
int stacksize; // ，
}SqStack; //
// S。
int InitStack(SqStack *S)
{
//
(*S).base = (SElemType *)malloc(STACK_INIT_SIZE*sizeof(SElemType));
if( !(*S).base )
exit(0); //
(*S).top = (*S).base; //
(*S).stacksize = STACK_INIT_SIZE;
return 1;
}
// S （ ）， 1， 0。
int StackEmpty(SqStack S)
{
if(S.top == S.base)
return 1;
else
return 0;
}
// e 。
int Push(SqStack *S, SElemType e)
{
if((*S).top - (*S).base >= (*S).stacksize) // ，
{
(*S).base = (SElemType *)realloc((*S).base,
((*S).stacksize + STACKINCREMENT) * sizeof(SElemType));
if( !(*S).base )
exit(0); //
(*S).top = (*S).base+(*S).stacksize;
(*S).stacksize += STACKINCREMENT;
}
*((*S).top)++=e;
// ++ * ， ，
return 1;
}
// ， S ， e ， 1； 0。
int Pop(SqStack *S,SElemType *e)
{
if((*S).top == (*S).base)
return 0;
*e = *--(*S).top;
// ++ * ， ，
return 1;
}
// 7.13 P185
// G , ve ( )。
// T ,S 。 G , T G
// , 1, 0
int TopologicalOrder(ALGraph G,SqStack *T)
{
int j,k,count,indegree[MAX_VERTEX_NUM];
SqStack S;
ArcNode *p;
FindInDegree(G,indegree);// indegree[0..vernum-1]
InitStack(&S); //
for(j=0;j<G.vexnum;++j) // S
if(!indegree[j])
Push(&S,j); // 0
InitStack(T); //
count=0; //
for(j=0;j<G.vexnum;++j) // ve[]=0 ( )
ve[j]=0;
while(!StackEmpty(S))
{
//
Pop(&S,&j);
Push(T,j); // j T
++count;
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{
// j 1
k=p->adjvex;
if(--indegree[k]==0) // 0,
Push(&S,k);
if(ve[j]+*(p->info)>ve[k])
ve[k]=ve[j]+*(p->info);
}
}
if(count<G.vexnum)
{
printf("
");
return 0;
}
else
return 1;
}
// 7.14 P185
// G , G
int CriticalPath(ALGraph G)
{
int vl[MAX_VERTEX_NUM];
SqStack T;
int i,j,k,ee,el;
ArcNode *p;
char dut,tag;
if(!TopologicalOrder(G,&T)) //
return 0;
j=ve[0];
for(i=1;i<G.vexnum;i++) // j=Max(ve[])
if(ve[i]>j)
j=ve[i];
for(i=0;i<G.vexnum;i++) // ( )
vl[i]=j; //
while(!StackEmpty(T)) // vl
for(Pop(&T,&j),p=G.vertices[j].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
dut=*(p->info); // dut<j,k>
if(vl[k]-dut<vl[j])
vl[j]=vl[k]-dut;
}
printf(" j k dut ee el tag
");
for(j=0;j<G.vexnum;++j) // ee,el
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
dut=*(p->info);
ee=ve[j];
el=vl[k]-dut;
tag=(ee==el)?'*':' ';
//
printf("%2d %2d %3d %3d %3d %c
",j,k,dut,ee,el,tag);
}
printf(" :
");
for(j=0;j<G.vexnum;++j) //
for(p=G.vertices[j].firstarc;p;p=p->nextarc)
{
k=p->adjvex;
dut=*(p->info);
if(ve[j]==vl[k]-dut)
//
printf("%s→%s
",G.vertices[j].data,G.vertices[k].data);
}
return 1;
}
int main()
{
ALGraph h;
printf("
");
CreateGraph(&h);
Display(h);
CriticalPath(h);
system("pause");
return 0;
}
/*
：
( :0, :1, :2, :3): 1
:（ ）
6 8
6 (<3 ):
v1
v2
v3
v4
v5
v6
( ) 、 ( ):
3 v1 v2
2 v1 v3
2 v2 v4
3 v2 v5
4 v3 v4
3 v3 v6
2 v4 v6
1 v5 v6
6 ：
v1 v2 v3 v4 v5 v6
8 ( ):
v1→v3 :2 v1→v2 :3
v2→v5 :3 v2→v4 :2
v3→v6 :3 v3→v4 :4
v4→v6 :2
v5→v6 :1
j k dut ee el tag
0 2 2 0 0 *
0 1 3 0 1
1 4 3 3 4
1 3 2 3 4
2 5 3 2 5
2 3 4 2 2 *
3 5 2 6 6 *
4 5 1 6 7
:
v1→v3
v3→v4
v4→v6
. . .
*/