我参考《算法精解》中用单链表实现算法的代码，但在编写 main 函数时，运行出来会遇到图顶点插入出错，第一个顶点插入时会成功，但是第二个顶点之后似乎没有被插入图中，希望大神指教：

这里是 main 函数：

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

#include "list.h"
#include "set.h"
#include "graph.h"
#include "example.h"
#include "graphalg.h"

#define DBL_MAX 20

int _match(const void *key1, const void *key2)
{
    if(key1 == key2)
        return 0;
    else
        return 1;
}

void _destroy(void *data)
{
    free(data);
}


int main()
{
    example();
    return 0;
}

#ifndef EXAMPLE_H
#define EXAMPLE_H

#include <stdio.h>

int _match(const void *key1, const void *key2);
void _destroy(void *data);
int example();

#endif

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

#include "list.h"
#include "set.h"
#include "graph.h"
#include "graphalg.h"
#include "example.h"
    
int example()
{
    Graph _graph;
    Graph *graph = &_graph;
    List _list,
         *list = &_list;
    PathVertex pvertex1, pvertex2,
               *pathvertex1 = &pvertex1, *pathvertex2 = &pvertex2;
    int i = 0;
    void *data;
    ListElmt *element;
    char _city[6] = {'a','b','c','d','e','f'},
         (*city)[6] = &_city;

    double A_B = 8,
           A_C = 4,
           B_C = 6,
           B_D = 2,
           C_F = 1,
           C_E = 4,
           F_B = 2,
           F_D = 7,
           F_E = 4;


    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);

    /*Match and destroy function. Use void pointer to realize.*/
    match = &_match;
    destroy = &_destroy;

    graph_init(graph, match, destroy);
    for(i; i < 6; ++i)
    {
        pathvertex1 -> data = &_city[i];
        graph_ins_vertex(graph, (const PathVertex *)pathvertex1;
    }
//        printf("%c\n", *(char *)pathvertex_data(pathvertex1));
//    }
//    for(element = list_head(&graph -> adjlists); element != NULL; element = list_next(element)
//    {
//            data = ((AdjList *)list_data(element)) -> vertex;
//            pathvertex1 = (PathVertex *)data;
//            printf("%c\n", *(char *)(pathvertex_data(pathvertex1)));
//}
//    pathvertex1 -> data = &_city[0];
//    pathvertex2 -> data = &_city[1];
//    graph_ins_edge(graph, (const PathVertex *)pathvertex1, (const PathVertex *)pathvertex2, A_B);


//    pathvertex1 -> data = &_city[0];
//    shortest(graph, pathvertex1, list, match);

    return 0;
}

下面是最短路径完整算法：

/*list.h*/

#ifndef LIST_H
#define LIST_H

#include <stdlib.h>


 
typedef struct ListElmt_
{
    void *data;
    struct ListElmt_ *next;
} ListElmt;


 
typedef struct List_
{
    int size;
    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    ListElmt *head;
    ListElmt *tail;
} List;


 
void list_init(List *list, void (*destroy)(void *data));
void list_destroy(List *list);
int list_ins_next(List *list, ListElmt *element, const void *data);
int list_rem_next(List *list, ListElmt *element, void **data);
#define list_size(list) ((list) -> size)

#define list_head(list) ((list) -> head)
#define list_tail(list) ((list) -> tail)
#define list_is_head(list, element) ((element) == (list) -> head ? 1 : 0)
#define list_is_tail(list, element) ((element) -> next == NULL ? 1 : 0)
#define list_data(element) ((element) -> data)
#define list_next(element) ((element) -> next)

#endif

#include"list.h"
#include "graph.h"
#include "graphalg.h"
#include "list.h"
#include "set.h"

/*list_init*/
void list_init(List *list,void (*destroy)(void *data)) {
     
    list -> size = 0;
    list -> destroy = destroy;
    list -> head = NULL;
    list -> tail = NULL;

    return;
}


 
void list_destroy(List *list) {
    void *data;
     
    while (list_size(list) > 0) {
        if (list_rem_next(list, NULL, (void **)&data) == 0 && list -> destroy != NULL) {
             

            list -> destroy(data);
        }
    }

     
    memset(list, 0, sizeof(List));
    return;
}


 
int list_ins_next(List *list, ListElmt *element, const void *data) {
    ListElmt      *new_element;

    if ((new_element = (ListElmt *)malloc(sizeof(ListElmt))) == NULL)
        return -1;

    new_element -> data = (void *)data;
    if(element == NULL) {
               if (list_size(list) == 0)
            list -> tail = new_element;

        new_element -> next = list -> head;
        list -> head = new_element;
    }
    else {

        if (element -> next == NULL)
            list -> tail = new_element;

        new_element -> next = element -> next;
        element -> next = new_element;
    }
     
    list -> size++;

    return 0;
}


 
int list_rem_next(List *list, ListElmt *element, void **data) {
    ListElmt       *old_element;

     
    if (list_size(list) == 0)
        return -1;

     
    if (element == NULL)
    {

         
        *data = list -> head -> data;
        old_element = list -> head;
        list -> head = list -> head -> next;

        if (list_size(list) == 1)
        list -> tail = NULL;
    }

    else
    {
         
        if (element -> next == NULL)
            return -1;
        *data = element -> next -> data;
        old_element = element -> next;
        element -> next = element -> next -> next;

        if (element -> next == NULL)
        list -> tail = element;
    }

     
    free(old_element);

     
    list -> size--;
    return 0;
}

/* set.h */
#ifndef SET_H
#define SET_H

#include <stdlib.h>
#include "list.h"


 

typedef List Set;

  

void set_init(Set *set, int (*match)(const void *key1, const void *key2), void (*destroy)(void *data));

#define set_destroy list_destroy
int set_insert(Set *set, const void *data);
int set_remove(Set *set, void **data);
int set_union(Set *setu, const Set *set1, const Set *set2);
int set_intersection(Set *seti, const Set *set1, const Set *set2);
int set_difference(Set *setd, const Set *set1, const Set *set2);
int set_is_member(const Set *set, const void *data);
int set_is_subset(const Set *set1, const Set *set2);
int set_is_equal(const Set *set1, const Set *set2);
#define set_size(set) ((set) -> size)

#endif

/* set.c */
#include <stdlib.h>
#include <string.h>
#include "list.h"
#include "set.h"


 
void set_init(Set *set, int (*match)(const void *key1, const void *key2),
              void (*destroy)(void *data))
{
     
    list_init(set, destroy);
    set -> match = match;

    return;
}


 
int set_insert(Set *set, const void *data)
{
     
    if (set_is_member(set, data))
    return 1;
    
     
    return list_ins_next(set, list_tail(set), data);
}

 
int set_remove(Set *set, void **data)
{
    ListElmt *member, *prev;

     
    prev = NULL;

    for(member = list_head(set); member != NULL; member = list_next(member))
    {
    if(set -> match(*data, list_data(member)))
        break;
    prev = member;
    }


    if (member == NULL)
        return -1;
    

    return list_rem_next(set, prev, data);
}


 
int set_union(Set *setu, const Set *set1, const Set *set2)
{
    ListElmt *member;
    void     *data;


    set_init(setu, set1 -> match, NULL);

    for (member = list_head(set1); member != NULL; member = list_next(member))
    {
    data = list_data(member);
    if(list_ins_next(setu, list_tail(setu), data) != 0)
    {
        set_destroy(setu);
        return -1;
    }
    }

     
    for (member = list_head(set2); member != NULL; member = list_next(member))
    {
    if(set_is_member(set1, list_data(member)))
    {
        continue;
    }
    else
    {
        data = list_data(member);
        if(list_ins_next(setu, list_tail(setu), data) != 0)
        {
            set_destroy(setu);
            return -1;
        }
    }
    }
    return 0;
}


 
int set_intersection(Set *seti, const Set *set1, const Set *set2)
{
    ListElmt *member;
    void *data;


    set_init(seti, set1 -> match, NULL);


 
    for (member = list_head(set1); member != NULL; member = list_next(member))
    {
    if(set_is_member(set2, list_data(member)))
    {
        data = list_data(member);
        if(list_ins_next(seti, list_tail(seti), data) != 0)
        {
            set_destroy(seti);
            return -1;
        }
    }
    }
    return 0;
}


 
int set_difference(Set *setd, const Set *set1, const Set *set2)
{
    ListElmt *member;
    void     *data;


 
    set_init(setd, set1 -> match, NULL);


 
    for(member = list_head(set1); member != NULL; member = list_next(member))
    {
    if (!set_is_member(set2, list_data(member)))
    {
        data = list_data(member);

        if(list_ins_next(setd, list_tail(setd), data) != 0)
        {
            set_destroy(setd);
            return -1;
        }
    }
    }
    return 0;
}


 
int set_is_member(const Set *set, const void *data)
{
    ListElmt *member;


 
    for(member = list_head(set); member != NULL; member = list_next(member))
    {
    if(set->match(data,list_data(member)))
        return 1;
    }
    return 0;
}
    

 
int set_is_subset(const Set *set1, const Set *set2)
{
    ListElmt *member;


 
    if(set_size(set1) > set_size(set2))
        return 0;


 
    for(member = list_head(set1); member != NULL; member = list_next(member))
    {
    if (!set_is_member(set2,list_data(member)))
        return 0;
    }
    return 1;
}


 
int set_is_equal(const Set *set1, const Set *set2)
{

 
    if(set_size(set1) != set_size(set2))
    return 0;


 
    return set_is_subset(set1, set2);
}

/* graph.h */
#ifndef GRAPH_H
#define GRAPH_H
#include <stdlib.h>
#include "list.h"
#include "set.h"

 
typedef struct AdjList_
{
    void *vertex;
    Set adjacent;
}AdjList;

 
typedef struct Graph_
{
    int vcount;
    int ecount;
    int (*match)(const void *key1, const void *key2);
    void (*destroy)(void *data);
    List adjlists;
}Graph;

 
typedef enum VertexColor_{white, black}VertexColor;

 
void graph_init(Graph *graph, int (*match)(const void *key1, const void *key2),void (*destroy)(void *data));
void graph_destroy(Graph *graph);
int graph_ins_vertex(Graph *graph, const void *data);
int graph_ins_edge(Graph *graph, const void *data1, const void *data2, double data3);
int graph_rem_vertex(Graph *graph, void **data);
int graph_rem_edge(Graph *graph, void *data1, void **data2);
int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist);
int graph_is_adjacent(const Graph *graph, const void *data1, const void *data2);
#define graph_adjlists(graph) ((graph) -> adjlists)
#define graph_vcount(graph) ((graph) -> vcount)
#define graph_ecount(graph) ((graph) -> ecount)
#endif

#include <stdlib.h>
#include <string.h>

#include "graph.h"
#include "graphalg.h"
#include "list.h"
#include "set.h"

//graph_init
void graph_init(Graph *graph, int (*match)(const void *key1, const void *key2), void(*destroy)(void *data))
{
    graph -> vcount = 0;
    graph -> ecount = 0;
    graph -> match = match;
    graph -> destroy = destroy;

    list_init(&graph -> adjlists, NULL);

    return;
}

void graph_destroy(Graph *graph)
{
    AdjList *adjlist;

    while(list_size(&graph -> adjlists) > 0)
    {
        if(list_rem_next(&graph -> adjlists, NULL, (void **)&adjlist) == 0)
        {
            set_destroy(&adjlist -> adjacent);
            if(graph -> destroy != NULL)
                graph -> destroy(adjlist -> vertex);
                free(adjlist);
        }
    }
    list_destroy(&graph -> adjlists);

 
    memset(graph, 0, sizeof(Graph));
    return;
}

 
int graph_ins_vertex(Graph *graph, const void *data)
{
    ListElmt *element;
    AdjList *adjlist;
    int retval;

    for(element = list_head(&graph -> adjlists); element != NULL; element = list_next(element))
    {
        if(graph -> match(data, ((AdjList *)list_data(element)) -> vertex))
            return 1;
    }

    if((adjlist = (AdjList *)malloc(sizeof(AdjList))) == NULL)
        return -1;


      adjlist -> vertex = (void *)data;
      set_init(&adjlist -> adjacent, graph -> match, NULL);
      if((retval = list_ins_next(&graph -> adjlists, list_tail(&graph -> adjlists), adjlist)) != 0) 
      {
       return retval;
      }
    graph -> vcount++;
    return 0;
}

 
int graph_ins_edge(Graph *graph, const void *data1, const void *data2, double data3)
{
    ListElmt *element;
    int retval;

    for(element = list_head(&graph -> adjlists); element != NULL; element = list_next(element))
    {
        
    if(graph -> match(data2, ((AdjList *)list_data(element)) -> vertex))
    {
                data = ((AdjList *)list_data(element)) -> vertex;
                pathvertex = (PathVertex *)data;
                pathvertex -> weight = data3;
                break;
        }
    }
    if(element == NULL)
    return -1;

    for(element = list_head(&graph -> adjlists); element != NULL; element = list_next(element))
    {
    if(graph -> match(data1, ((AdjList*)list_data(element)) -> vertex))
        break;
    }
    if(element == NULL)
        return -1;
     
    if((retval = set_insert(&((AdjList *)list_data(element)) -> adjacent, data2)) != 0)
    {
    return retval;
    }
     

    graph -> ecount++;
    return 0;
}

 
int graph_rem_vertex(Graph *graph, void **data)
{
  ListElmt *element, *temp, *prev;
  AdjList  *adjlist;
  int found;
   
  prev = NULL;
  found = 0;
  
  for(element = list_head(&graph -> adjlists); element != NULL; element = list_next(element))
  {
     if(set_is_member(&((AdjList *)list_data(element)) -> adjacent, *data))
        return -1;
      
    if(graph -> match(*data, ((AdjList *)list_data(element)) -> vertex))
    {
    temp = element;
    found = 1;
    }
   
     
   if(!found)
     prev = element;
  }
    
   if(!found)
      return -1;
    
   if(set_size(&((AdjList *)list_data(temp)) -> adjacent) > 0)
     return -1;
    
   if(list_rem_next(&graph -> adjlists, prev,(void **)&adjlist) != 0)
      return -1;
     
   *data = adjlist -> vertex;
   free(adjlist);
    
   graph -> vcount--;
   return  0;
}
   
int graph_rem_edge(Graph *graph, void *data1, void **data2)
{
   ListElmt  *element;
      
   for(element = list_head(&graph -> adjlists); element != NULL; element = list_next(element))
   {
       if(graph -> match(data1, ((AdjList *)list_data(element)) -> vertex))
          break;
   }
   if(element == NULL)
      return -1;
   
   if(set_remove(&((AdjList *)list_data(element)) -> adjacent, data2) != 0)
       return -1;
   
   graph -> ecount--;
   return 0;
}
  
int graph_adjlist(const Graph *graph, const void *data, AdjList **adjlist)
{
   ListElmt  *element, *prev;
    
   prev = NULL;
   for(element = list_head(&graph -> adjlists); element != NULL; element = list_next(element))
   {
       if(graph -> match(data, ((AdjList *)list_data(element)) -> vertex))
           break;
       prev = element;
   }
   
   if(prev == NULL)
      return -1;
   
   *adjlist = list_data(element);
   return 0;
}
   
int graph_is_adjacent(const Graph  *graph, const void *data1, const void *data2)
{
  ListElmt  *element,*prev;
    
  prev = NULL;
  for(element = list_head(&graph -> adjlists); element != NULL; element=list_next(element))
  {
      if(graph -> match(data1, ((AdjList *)list_data(element)) -> vertex))
         break;
      prev = element;
  }
    
  if(prev == NULL)
     return 0;
   
  return set_is_member(&((AdjList *)list_data(element)) -> adjacent, data2);
}       
    

/*graphalg.h*/
#ifndef GRAPHALG_H
#define GRAPHALG_H

#include <stdio.h>

#include "graph.h"
#include "list.h"

/*Define a structure for vertices in shortest-path problems.*/
typedef struct PathVertex_
{
    void *data;
    double weight;

    VertexColor color;
    double  d;

    struct PathVertex_ *parent;
}PathVertex;



/*Public Interface*/
int shortest(Graph *graph, PathVertex *start, List *paths , int (*match)(const void *key1, const void *key2));
#define pathvertex_data(element) ((element) -> data)

#endif

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

#include "graph.h"
#include "graphalg.h"
#include "list.h"
#include "set.h"

/*relax*/
static void relax(PathVertex *u, PathVertex *v, double weight)
{
    /*relax an edge between two vertices u and v.*/
    if (v -> d > u -> d + weight)
    {
        v -> d = u -> d + weight;
        printf("%lf\n", v -> d);
        v -> parent = u;
    }
    return;
}

/*shortest*/
int shortest(Graph *graph, PathVertex *start, List *paths, int (*match)(const void *key1, const void *key2))
{
    AdjList *adjlist;
    PathVertex *pth_vertex,
               *adj_vertex,
               *pathvertex;
    ListElmt *element,
             *member;
    double minimum;
    int found,
        i;
    FILE *fp;
    void *data;


    /*initialize all of the vertices in the graph.*/
    found = 0;

    for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
    {
        pth_vertex = ((AdjList *)list_data(element)) -> vertex;
        if (match(pth_vertex, start))
        {
            /*initialize the start vertex.*/
            pth_vertex -> color = white;
            pth_vertex -> d = 0;
            pth_vertex -> parent = NULL;
            found = 1;
        }
        else
        {
            /* initialize vertices other than the start vertex.*/
            pth_vertex -> color = white;
            pth_vertex -> d = DBL_MAX;
            pth_vertex -> parent = NULL;
        }
    }

    /* return if the start vertex was not found.*/
    if(!found)
        return -1;

    /*use Dijkstra's algorithm to compute shortest paths from the start vertex.*/
    i = 0;

    while (i < graph_vcount(graph))
    {
        /*Select the white vertex with the smallest shortest-path estimate.*/
        minimum = DBL_MAX;

        for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
        {
            pth_vertex = ((AdjList *)list_data(element)) -> vertex;

            if(pth_vertex -> color == white && pth_vertex -> d < minimum)
            {
                minimum = pth_vertex -> d;
                adjlist = list_data(element);
            }
        }

        /*color the selected vertex black.*/
        ((PathVertex *)adjlist -> vertex) -> color = black;

        /*traverse each vertex adjacent to the selected vertex.*/
        for(member = list_head(&adjlist -> adjacent); member != NULL; member = list_next(member))
        {
            adj_vertex = list_data(member);

            /*find the adjacent vertex in the list of adjacency-list structures.*/
            for (element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
            {
                pth_vertex = ((AdjList *)list_data(element)) -> vertex;

                if(match(pth_vertex, adj_vertex))
                {
                    /*relax the adjacent vertex in the list of adjacency-list structures.*/
                    relax(adjlist -> vertex, pth_vertex, adj_vertex -> weight);
                }
            }
        }

        /*prepare to select the next vertex.*/
        ++i;
    }

//    fp = fopen("example_map", "a+");
//    fprintf(fp, "起始城市 到达城市 最短距离\n");
//    fclose(fp);

    /* load the vertices with their path information into a list.*/
    list_init(paths, NULL);

    for(element = list_head(&graph_adjlists(graph)); element != NULL; element = list_next(element))
    {
        /*load each black vertex from the list of adjacency-list structures.*/
        pth_vertex = ((AdjList *)list_data(element)) -> vertex;

        if(pth_vertex -> color == black)
        {
            if(list_ins_next(paths, list_tail(paths), pth_vertex) != 0)
            {
                list_destroy(paths);
                return -1;
            }
//            else
//            {
//            pathvertex = (PathVertex *)pth_vertex;
//            printf("%c\n", *(char *)(pathvertex_data(pathvertex)));
//            fp = fopen("example_map", "a+");
//            fprintf(fp, "%c         %c         %lf\n", *(char )pathvertex_data(start), *(char)pathvertex_data(pathvertex), pth_vertex -> d);
//            fclose(fp);
//            }
        }

    }
    return 0;
    
    
}

调试一下~