図面へのクロスチェーンテーブルストレージ
52042 ワード
/* c7-3.h */
#define MAX_VERTEX_NUM 20
typedef struct ArcBox
{
int tailvex,headvex; /* */
struct ArcBox *hlink,*tlink; /* */
InfoType *info; /* ( ) */
}ArcBox; /* */
typedef struct
{
VertexType data;
ArcBox *firstin,*firstout; /* */
}VexNode; /* */
typedef struct
{
VexNode xlist[MAX_VERTEX_NUM]; /* ( ) */
int vexnum,arcnum; /* */
}OLGraph; /* bo7-3.c ( c7-3.h ) (15 ) */
int LocateVex(OLGraph G,VertexType u)
{ /* u G ( ), -1 */
int i;
for(i=0;i/* */
if(!strcmp(G.xlist[i].data,u))
return i;
return -1;
}
Status CreateDG(OLGraph *G)
{ /* , G。 7.3 */
int i,j,k;
int IncInfo;
char str[MAX_Info];
ArcBox *p;
VertexType v1,v2;
printf(" , , ( :1， :0): ");
scanf("%d,%d,%d",&(*G).vexnum,&(*G).arcnum,&IncInfo);
printf(" %d (",(*G).vexnum,MAX_VERTEX_NAME);
for(i=0;ii)
{ /* */
scanf("%s",&(*G).xlist[i].data); /* */
(*G).xlist[i].firstin=NULL; /* */
(*G).xlist[i].firstout=NULL;
}
printf(" %d ( ):
",(*G).arcnum);
for(k=0;kk)
{ /* */
scanf("%s%s",&v1,&v2);
i=LocateVex(*G,v1); /* v1 v2 G */
j=LocateVex(*G,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;
if(IncInfo)
{ /* ， */
printf(" (",MAX_Info);
scanf("%s",str);
p->info=(InfoType *)malloc((strlen(str)+1)*sizeof(InfoType));
strcpy(p->info,str);
}
else /* */
p->info=NULL;
}
return OK;
}
void DestroyGraph(OLGraph *G)
{ /* : G */
/* : G */
int j;
ArcBox *p,*q;
for(j=0;j/* */
{
p=(*G).xlist[j].firstout; /* */
while(p)
{
q=p;
p=p->tlink;
if(q->info)
free(q->info);
free(q);
}
}
(*G).arcnum=0;
(*G).vexnum=0;
}
VertexType* GetVex(OLGraph G,int v)
{ /* : G ,v G 。 : v */
if(v>=G.vexnum||v<0)
exit(ERROR);
return &G.xlist[v].data;
}
Status PutVex(OLGraph *G,VertexType v,VertexType value)
{ /* : G ,v G */
/* : v value */
int i;
i=LocateVex(*G,v);
if(i<0) /* v G */
return ERROR;
strcpy((*G).xlist[i].data,value);
return OK;
}
int FirstAdjVex(OLGraph G,VertexType v)
{ /* : G ,v G */
/* : v 。 G , -1 */
int i;
ArcBox *p;
i=LocateVex(G,v);
p=G.xlist[i].firstout; /* p v 1 */
if(p)
return p->headvex;
else
return -1;
}
int NextAdjVex(OLGraph G,VertexType v,VertexType w)
{ /* : G ,v G ,w v */
/* : v ( w ) , */
/* w v , -1 */
int i,j;
ArcBox *p;
i=LocateVex(G,v); /* i v */
j=LocateVex(G,w); /* j w */
p=G.xlist[i].firstout; /* p v 1 */
while(p&&p->headvex!=j)
p=p->tlink;
if(p) /* w v */
p=p->tlink; /* p w */
if(p) /* */
return p->headvex;
else
return -1;
}
void InsertVex(OLGraph *G,VertexType v)
{ /* : G ,v G */
/* : G v( , InsertArc() ) */
strcpy((*G). xlist[(*G). vexnum].data,v);
(*G). xlist[(*G). vexnum].firstin=(*G). xlist[(*G). vexnum].firstout=NULL;
(*G). vexnum++;
}
Status DeleteVex(OLGraph *G,VertexType v)
{ /* : G ,v G */
/* : G v */
int j,k;
ArcBox *p,*q;
k=LocateVex(*G,v); /* k v */
if(k<0) /* v G */
return ERROR;
/* v */
for(j=0;j/* v */
{
if(j==k)
continue;
p=(*G). xlist[j].firstin; /* v */
while(p)
if(p->tailvex==k&&p==(*G). xlist[j].firstin) /* */
{
(*G). xlist[j].firstin=p->hlink;
break;
}
else if(p->tailvex!=k) /* */
{
q=p;
p=p->hlink;
}
else /* */
{
q->hlink=p->hlink;
break;
}
}
p=(*G). xlist[k].firstout; /* v */
while(p)
{
q=p->tlink; /* q p */
if(p->info) /* p */
free(p->info);
free(p);
(*G). arcnum--;
p=q;
}
/* v */
for(j=0;j/* v */
{
if(j==k)
continue;
p=(*G). xlist[j].firstout; /* v */
while(p)
if(p->headvex==k&&p==(*G). xlist[j].firstout) /* */
{
(*G). xlist[j].firstout=p->tlink;
break;
}
else if(p->headvex!=k) /* */
{
q=p;
p=p->tlink;
}
else /* */
{
q->tlink=p->tlink;
break;
}
}
p=(*G). xlist[k].firstin; /* v */
while(p)
{
q=p->hlink; /* q p */
if(p->info) /* p */
free(p->info);
free(p);
(*G). arcnum--;
p=q;
}
for(j=k+1;j/* >k */
(*G). xlist[j-1]=(*G). xlist[j];
(*G). vexnum--; /* 1 */
for(j=0;j/* >k 1 */
{
p=(*G). xlist[j].firstout; /* */
while(p)
{
if(p->tailvex>k)
p->tailvex--; /* -1 */
if(p->headvex>k)
p->headvex--; /* -1 */
p=p->tlink;
}
}
return OK;
}
Status InsertArc(OLGraph *G,VertexType v,VertexType w)
{ /* : G ,v w G */
/* : G */
int i,j;
int IncInfo;
char str[MAX_Info];
ArcBox *p;
i=LocateVex(*G,v); /* */
j=LocateVex(*G,w); /* */
if(i<0||j<0)
return ERROR;
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;
(*G). arcnum++; /* 1 */
printf(" ( : 1, : 0): ");
scanf("%d",&IncInfo);
if(IncInfo)
{
printf(" (",MAX_Info);
scanf("%s",str);
p->info=(InfoType *)malloc((strlen(str)+1)*sizeof(InfoType));
strcpy(p->info,str);
}
else
p->info=NULL;
return OK;
}
Status DeleteArc(OLGraph *G,VertexType v,VertexType w)
{ /* : G ,v w G */
/* : G */
int i,j;
ArcBox *p1,*p2;
i=LocateVex(*G,v); /* */
j=LocateVex(*G,w); /* */
if(i<0||j<0||i==j)
return ERROR;
p2=(*G). xlist[i].firstout; /* */
if(p2&&p2->headvex==j) /* 1 */
(*G). xlist[i].firstout=p2->tlink;
else
{
while(p2&&p2->headvex!=j) /* */
{
p1=p2;
p2=p2->tlink;
}
if(p2) /* */
p1->tlink=p2->tlink;
}
p2=(*G). xlist[j].firstin; /* */
if(p2&&p2->tailvex==i)
(*G). xlist[j].firstin=p2->hlink;
else
{
while(p2&&p2->tailvex!=i)
{
p1=p2;
p2=p2->hlink;
}
if(p2) /* */
p1->hlink=p2->hlink;
}
if(p2->info) /* */
free(p2->info);
free(p2);
(*G). arcnum--; /* 1 */
return OK;
}
Boolean visited[MAX_VERTEX_NUM]; /* */
Status(*VisitFunc)(VertexType); /* */
void DFS(OLGraph G,int i) /* DFSTraverse() */
{
ArcBox *p;
visited[i]=TRUE; /* 1( ) */
VisitFunc(G.xlist[i].data); /* i */
p=G.xlist[i].firstout; /* p i */
while(p&&visited[p->headvex]) /* p */
p=p->tlink; /* */
if(p&&!visited[p->headvex]) /* */
DFS(G,p->headvex); /* DFS() */
}
void DFSTraverse(OLGraph G,Status(*Visit)(VertexType))
{ /* : G ,v G ,Visit */
/* : 1 , G, */
/* Visit 。 Visit() , */
int i;
for(i=0;i)
visited[i] =FALSE; /* ( ) */
VisitFunc=Visit;
for(i=0;i/* 0 , */
if(!visited[i])
DFS(G,i);
printf("
");
}
typedef int QElemType;
#include"c3-3.h"
#include"bo3-3.c"
void BFSTraverse(OLGraph G,Status(*Visit)(VertexType))
{ /* : G ,Visit 。 7.6 */
/* : 1 , G, */
/* Visit 。 Visit() , 。 */
/* Q visited */
int v,u,w;
VertexType u1,w1;
SqQueue Q;
for(v=0;v)
visited[v]=FALSE;
InitQueue(&Q);
for(v=0;v)
if(!visited[v])
{
visited[v]=TRUE;
Visit(G.xlist[v].data);
EnQueue(&Q,v);
while(!QueueEmpty(Q))
{
DeQueue(&Q,&u);
strcpy(u1,*GetVex(G,u));
for(w=FirstAdjVex(G,u1);w>=0;w=NextAdjVex(G,u1,strcpy(w1,*GetVex(G,w))))
if(!visited[w]) /* w u */
{
visited[w]=TRUE;
Visit(G.xlist[w].data);
EnQueue(&Q,w);
}
}
}
printf("
");
}
void Display(OLGraph G)
{ /* G */
int i;
ArcBox *p;
printf(" %d ,%d :
",G.vexnum,G.arcnum);
for(i=0;i)
{
printf(" %s: : ",G.xlist[i].data);
p=G.xlist[i].firstin;
while(p)
{
printf("%s ",G.xlist[p->tailvex].data);
p=p->hlink;
}
printf(" : ");
p=G.xlist[i].firstout;
while(p)
{
printf("%s ",G.xlist[p->headvex].data);
if(p->info) /* */
printf(" : %s ",p->info);
p=p->tlink;
}
printf("
");
}
} /* algo7-3.c 7.10、7.11 */
#include"c1.h"
#define MAX_NAME 2 /* +1 */
typedef int InfoType;
typedef char VertexType[MAX_NAME]; /* */
#include"c7-2.h"
#include"bo7-2.c"
int count; /* count */
int low[MAX_VERTEX_NUM];
void DFSArticul(ALGraph G,int v0)
{ /* v0 G， 。 7.11 */
int min,w;
ArcNode *p;
visited[v0]=min=++count; /* v0 count */
for(p=G.vertices[v0].firstarc;p;p=p->nextarc) /* v0 */
{
w=p->adjvex; /* w v0 */
if(visited[w]==0) /* w ， v0 */
{
DFSArticul(G,w); /* low[w] */
if(low[w]<min)
min=low[w];
if(low[w]>=visited[v0])
printf("%d %s
",v0,G.vertices[v0].data); /* */
}
else if(visited[w]<min)
min=visited[w]; /* w ，w v0 */
}
low[v0]=min;
}
void FindArticul(ALGraph G)
{ /* G ， G 。 7.10 */
/* count 。 */
int i,v;
ArcNode *p;
count=1;
low[0]=visited[0]=1; /* 0 */
for(i=1;ii)
visited[i]=0; /* */
p=G.vertices[0].firstarc;
v=p->adjvex;
DFSArticul(G,v); /* v */
if(count/* */
{
printf("%d %s
",0,G.vertices[0].data); /* ， */
while(p->nextarc)
{
p=p->nextarc;
v=p->adjvex;
if(visited[v]==0)
DFSArticul(G,v);
}
}
}
void main()
{
int i;
ALGraph g;
printf("
");
CreateGraph(&g);
printf(" ：
");
FindArticul(g);
printf(" i G.vertices[i].data visited[i] low[i]
");
for(i=0;ii)
printf("%2d %9s %14d %8d
",i,g.vertices[i].data,visited[i],low[i]);
} /* main7-3.c bo7-3.c */
#include"c1.h"
typedef char InfoType;
#define MAX_Info 80 /* +1 */
#define MAX_VERTEX_NAME 3 /* +1 */
typedef char VertexType[MAX_VERTEX_NAME];
#include"c7-3.h"
#include"bo7-3.c"
Status visit(VertexType v)
{
printf("%s ",v);
return OK;
}
void main()
{
int j,k,n;
OLGraph g;
VertexType v1,v2;
CreateDG(&g);
Display(g);
printf(" ， : ");
scanf("%s%s",v1,v2);
PutVex(&g,v1,v2);
printf(" ， : ");
scanf("%s",v1);
InsertVex(&g,v1);
printf(" ， : ");
scanf("%d",&n);
for(k=0;k)
{
printf(" (0: 1: ): ");
scanf("%s%d",v2,&j);
if(j)
InsertArc(&g,v2,v1);
else
InsertArc(&g,v1,v2);
}
Display(g);
printf(" ， ：");
scanf("%s%s",v1,v2);
DeleteArc(&g,v1,v2);
Display(g);
printf(" ， : ");
scanf("%s",v1);
DeleteVex(&g,v1);
Display(g);
printf(" :
");
DFSTraverse(g,visit);
printf(" :
");
BFSTraverse(g,visit);
DestroyGraph(&g);
} 転載先:https://www.cnblogs.com/cpoint/p/3480214.html