问邻接表从零开始

EN

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>


 /*a single node of an adjacency list*/
typedef struct adjList{

    int dest;
    struct adjList *next;

} adjList;


/*Image of a graph...*/

typedef struct Image{

    int source;
    adjList *head;

} Image;



void initialize_graph(Image *graph, int vertices);

void print_graph(Image graph[], int vertices);

void add_adj_node(Image *graph, int source, int destiny, bool directed);

void free_graph(Image graph[], int vertices);



int main() {

    int vertices;
    scanf("%d", &vertices);


    Image graph[vertices];

    printf("size of graph: %d bytes\n", sizeof graph);


    initialize_graph(graph, vertices);

    printf("initialized image of graph\n");

    print_graph(graph, vertices);

    printf("                          \n");
    //is the graph directed ? ans: false

    add_adj_node(graph, 1, 7, false);
    add_adj_node(graph, 1, 3, false);
    add_adj_node(graph, 4, 6, false);
    add_adj_node(graph, 4, 1, false);
    add_adj_node(graph, 5, 2, false);
    add_adj_node(graph, 1, 5, false);
    add_adj_node(graph, 1, 2, false);

    print_graph(graph, vertices);

    free_graph(graph, vertices);

    /*if this print produces segmentation fault then the memory is fully freed*/
    printf("graph[1].head->dest%d\n", graph[1].head->dest);


    return 0;
}




void initialize_graph(Image graph[], int vertices) {


        for(int i = 1; i<= vertices; i++){
                graph[i].source = i;
                graph[i].head = NULL;
        }

        return;
}



void add_adj_node(Image *graph, int src, int dest, bool directed){

    adjList *cache = malloc(sizeof(adjList));
    /*create a single node*/
    cache->dest = dest;
    cache->next = NULL;


    if(graph[src].head == NULL){
            graph[src].head = cache;

    }


    else{
            /*put the head address on the crawler*/
            adjList *crawler = graph[src].head;

            while( crawler->next != NULL){
                crawler = crawler->next;
            }

            /*update head value and address. head will point to new adj node
             this will also link src -> dest*/

            crawler->next = cache;
    }




    if (directed == false) {
          directed = true; 

          /*notice we've changed the sequence. dest and src*/
          add_adj_node( graph, dest, src, directed);
    }

    return;
}



void print_graph(Image *graph, int vertices){

    for(int i = 1; i<= vertices; i++){

                adjList *crawl = graph[i].head;
                printf("node: %d    ", graph[i].source);

                while(crawl){

                      printf("%d ", crawl->dest);
                      crawl = crawl->next;
                }

                printf("\n");
        }

    return;
}


/*just a reverse version of crawling a graph*/

void free_graph(Image *graph, int vertices){

    for(int i = 1; i<= vertices; i++){

                adjList *cache;
                printf("releasing elements of node: %d    ", graph[i].source);

                while(graph[i].head){

                      /*put the next adjacency node in the cache*/
                      cache = graph[i].head->next;
                      /*free the present adjacencey node*/
                      free(graph[i].head);
                      graph[i].head = cache;
                }

                printf("\n");
        }

    return;
}