|
#2
yuccn2014-01-02 08:24
|
这里是 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;
}