4-7.c

《C程序员成长攻略》-黎陡-源代码,书中所有源码

#include"stdio.h"
#include"alloc.h"
#define MAX_VERTEX_NUM 20
typedef enum{FALSE,TRUE} Boolean;
Boolean visited[MAX_VERTEX_NUM];
typedef struct ArcNode{
    char adjvex;
    struct ArcNode *next;
    char *info;
}ArcNode;

typedef struct VNode{
    char v;
    ArcNode *firstarc;
}AdjList[MAX_VERTEX_NUM];

typedef struct{
    AdjList vertices;
    int vexnum,arcnum;
}ALGraph;

typedef struct{
    int v1,v2;
}ArcVex;

int Q[MAX_VERTEX_NUM]; /*队列数组*/
int tail; /*指示队尾的变量*/

void InitQueue() /*初始化队列*/
{
    int i;
    tail=-1;  /*队尾变量初始化为-1，表示队列为空*/
    for(i=0;i<MAX_VERTEX_NUM;i++)
        Q[i]=-1; /*数组各元素值先置为-1*/
}

void EnQueue(char v) /*进队操作*/
{
    Q[++tail]=v; /*将新成员添加到队列尾端*/
}

char DeQueue()  /*出队操作*/
{
    int i;
    char v;
    v=Q[0];   /*首先获得队列头结点的值*/
    for(i=0;i<tail;i++) /*然后将随后的队列各结点依次往前移一个位置*/
        Q[i]=Q[i+1];
    Q[tail--]=-1; /*原本队列尾端的位置此时要置-1，表示此位置为空。且队尾指示变量值减1*/
    return v; /*函数返回队头元素值*/
}

Boolean QueueEmpty() /*判断队列是否为空*/
{
    if(tail==-1)    /*如果tail为-1，则表示队空，否则队列不为空*/
        return TRUE;  /*利用程序自定义的FASLE和TRUE值，使函数返回1或0值*/
     return  FALSE;
}

void CreateALGraph(ALGraph *G)
{
    int i,j,k;
    ArcNode *s,*p;
    ArcVex a[9]={{0,1},{0,2},{1,3},{1,4},{3,7},{4,7},{2,5},{2,6},{5,6}};
    G->vexnum=8; G->arcnum=9;
    for(i=0;i<G->vexnum;i++)
	{
        G->vertices[i].v='A'+i;
        G->vertices[i].firstarc=NULL;
	}
    for(k=G->arcnum-1;k>=0;k--)
	{
        i=a[k].v1; j=a[k].v2;

        s=(ArcNode *)malloc(sizeof(ArcNode));
        s->adjvex='A'+j;
        s->next=G->vertices[i].firstarc;
        G->vertices[i].firstarc=s;

        s=(ArcNode *)malloc(sizeof(ArcNode));
        s->adjvex='A'+i;
        s->next=G->vertices[j].firstarc;
        G->vertices[j].firstarc=s;
	}
}

void ShowAdjList(ALGraph *G)
{
    int i;
    ArcNode *p;
    for(i=0;i<G->vexnum;i++)
	{
        printf("%c-->",G->vertices[i].v);
        p=G->vertices[i].firstarc;
        while(p!=NULL)
		{
            if(p->next==NULL)
	            printf("%c",p->adjvex);
            else
	            printf("%c-->",p->adjvex);
            p=p->next;
		}
        printf("\n\n");
    }
}

int FindVex(ALGraph *G,char v)
{
    int i;
    for(i=0;i<G->vexnum;i++)
        if(G->vertices[i].v==v)
	return i;
}

void DFS(ALGraph *G,char v)
{
    int i,j;
    ArcNode *p;
    for(i=0;i<G->vexnum;i++)
        if(G->vertices[i].v==v)
	        break;
    visited[i]=TRUE;
    printf("%5c",v);
    p=G->vertices[i].firstarc;
    for(;p!=NULL;p=p->next)
	{
        j=FindVex(G,p->adjvex);
        if(!visited[j])
	        DFS(G,G->vertices[j].v);
	}
}

void BFS(ALGraph *G,char v)/*按广度优先非递归遍历图，从顶点v开始*/
{ 
    int i,j,k;

    ArcNode *p;
    InitQueue(Q);  /*队列初始化*/
    k=FindVex(G,v); /*找到v在图中的位置，即为k*/
    printf("%5c",G->vertices[k].v); /*首先访问v这个顶点*/
    visited[k]=TRUE;  /*置v的访问标识为TRUE*/
    EnQueue(v);   /*顶点v入队列*/
    while(!QueueEmpty())  /*队列不空，则循环*/
	{
        i=FindVex(G,DeQueue()); /*队头顶点出队列，并将该顶点的标识赋给变量i*/
        p=G->vertices[i].firstarc;
        for(;p!=NULL;p=p->next)
		{
            j=FindVex(G,p->adjvex); /*找到当前弧p所关联的顶点在图中的位置*/
            if(!visited[j])
			{
                printf("%5c",p->adjvex); /*访问这个顶点*/
	            visited[j]=TRUE;  /*相应标识置为TRUE*/
                EnQueue(p->adjvex);  /*将这个顶点入队列*/
			}
		}
	}
}

main()
{
    ALGraph G;
    clrscr();
    CreateALGraph(&G);
    ShowAdjList(&G);
    printf("\nVisit a AdjList expressed Graph in BFSTraverse:\n\n");
    BFS(&G,'A');
    getch();
}