图的邻接表实现及操作.多文件链接,makefile

adjlist.c

/*
 * =========================================================
 *       Filename:  adjlist.c
 *    Description:  图的邻接表表示及各种操作
 *
 * =========================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include "queue.h"

//定义邻接表
typedef struct arcnode{
    int arc ;//邻接顶点值
    struct arcnode *next ; //指向下一个邻接顶点
}ArcNode ,*AdjList ;

typedef struct graph{
    AdjList ver ; //ver是 arcnode类型数组，存储顶点及邻接信息
    int vernum ; //顶点个数
}Graph;

//根据图创建对应的邻接表,输入arc对(v , w)
ArcNode *newArc(int v);
void InitialGraph(Graph *g ,int vnum); //也就是类中的Constructor
void addEdge(Graph *g , int v , int w);

void DFSUtil(Graph *g , int v , bool visited[]); //DFS v的可达顶点
void DFS(Graph *g ,int v );//DFS 遍历全图
void BFS(Graph *g);//BFS 遍历全图
int main(){
    Graph gra ;
    InitialGraph( &gra , 4);
    addEdge(&gra , 0 ,3);
    addEdge(&gra , 0 ,2);
    addEdge(&gra , 3 ,2);
    addEdge(&gra , 2 ,0);
    addEdge(&gra , 2 ,1);
    addEdge(&gra , 1 ,1);
    DFS(&gra , 3);
    BFS(&gra);
    return 0;
}

ArcNode *newArc(int v){
    ArcNode *n = malloc(sizeof(ArcNode));
    n->arc = v;
    n->next = NULL;
    return n;
}
void InitialGraph( Graph *g ,int vnum){
    g->vernum = vnum;
    g->ver = malloc(vnum * sizeof(ArcNode));
}
void addEdge(Graph *g , int v , int w){ //脑子里有清晰的创建过程
//    ArcNode vertex = g->ver[v];
    ArcNode *n = newArc(w);
//    ArcNode *p = &vertex ;
    ArcNode *p = g->ver + v;
    while ( p->next )
        p = p->next;
    p->next = n;

}
void DFSUtil(Graph *g , int v , bool visited[]){
    visited[v] = true;
    printf("%d ",v);

    ArcNode *p = g->ver[v].next;
    while (p){
        if (!visited[p->arc])
            DFSUtil(g ,p->arc ,visited);
        p = p->next;
    }
}
void DFS(Graph *g , int v){
    bool *visited = malloc(g->vernum * sizeof(bool));
    for (int i=0 ; i< g->vernum ;i++)
        visited[i] = false;

    DFSUtil(g , v ,visited);
    for (int i=0 ; i< g->vernum ;i++){
        if (!visited[i])
            DFSUtil(g , i , visited);
    }

}
void BFS(Graph *g){
    bool *visited = malloc(g->vernum * sizeof(bool));
    for(int i = 0; i < g->vernum ; i++)
        visited[i] = false ;

    Queue q;
    InitQueue(&q ,(unsigned)g->vernum);

    for(int i = 0; i < g->vernum ;i++){
        if (!visited[i]){ //遍历i的可达顶点
            printf("%d ",i);
            visited[i] = true;
            InQueue(&q , i);

            while(!IsEmpty(&q)){
                int v = DeQueue(&q);
                ArcNode *p = (g->ver + v)->next;
                while(p){
                    if (!visited[p->arc]){
                        printf("%d ",p->arc);
                        visited[p->arc] = true;
                        InQueue(&q , p->arc);
                    }
                    p = p->next;
                }
            }
        }
    }
}

/*
 * =====================================================================================
 *
 *       Filename:  queue.h
 *
 *    Description:  整数循环队列头文件说明
 *
 *        Version:  1.0
 *        Created:  2014/04/17 14时46分22秒
 *       Revision:  none
 *       Compiler:  gcc
 *
 *         Author:  YOUR NAME (), 
 *   Organization:  
 *
 * =====================================================================================
 */

typedef struct queue{
    int *array;
    unsigned size;
    int head,tail;
}Queue;

extern void InitQueue(Queue *q , unsigned qsize);
extern bool IsEmpty(Queue *q);
extern bool IsFull(Queue *q);
extern void InQueue(Queue *q , int elem);
extern int DeQueue(Queue *q);

/*
 * =========================================================
 *       Filename:  queue.c
 *    Description:  整数循环队列操作的实现
 *
 * =========================================================
 */
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <assert.h>
#include "queue.h"

void InitQueue(Queue *q , unsigned qsize){
    q->size = qsize;
    q->array = malloc(qsize * sizeof(int));
    q->head = q->tail = 0;
}

bool IsEmpty(Queue *q){
    return (q->head == q->tail)?true:false;
}

bool IsFull(Queue *q){
    return ((q->tail + 1) % q->size == q->head)?true:false;
}

void InQueue(Queue *q , int elem){
    assert(!IsFull(q));
    q->array[q->tail] = elem;
    q->tail = (q->tail + 1) % q->size;
}

int DeQueue(Queue *q){
    assert(!IsEmpty(q));
    int e = q->array[q->head];
    q->head = (q->head + 1) % q->size;
    return e;
}

/*makefile. make -f makefile*/
adjlist: adjlist.o queue.o
	clang adjlist.o queue.o -o adjlist
adjlist.o: adjlist.c queue.h
	clang -c adjlist.c
queue.o: queue.c queue.h
	clang -c queue.c