参考：http://ahalei.blog.51cto.com/4767671/1391988
自己实现的链接表，遇到了segment fault问题， 主要是不知道怎么初始化指针数组。不能sizeof(AdjList*)*20，而是要把整个数组进行sizeof求值。整个数组sizeof(AdjList(*)[20])的sizeof值只有8.和sizeof(AdjList(*)) 一样，证明只需要求得数组的头指针值。
AdjList (*list)[20] = (AdjList(*)[20])malloc(sizeof(AdjList(*)[20]));
#include
#include
typedef struct _edge
{
int src,dst,dist;
struct _edge *next;
}Edge;
typedef struct _head
{
struct _edge *head;
struct _edge *tail;
}AdjList;
//virtual head,real tail
void list_add(AdjList *list,Edge *edge)
{
// printf("list=%p\n",list);
// printf("list->head=%p\n",list->head);
if(list->head->next == NULL)
{
list->tail = edge;
list->head->next = edge;
// printf("insert a new tail.src=%d|dst=%d|dist=%d|tail_next=%p\n",
// list->head->src,
// edge->dst,
// edge->dist,
// edge->next);
}
else
{
list->tail->next = edge;
list->tail = edge;
// printf("add to old tail.src=%d|dst=%d|dist=%d|tail_next=%p\n",
// list->head->src,
// edge->dst,
// edge->dist,
// edge->next);
}
}
void list_travel(AdjList *list)
{
Edge *temp = (Edge*)malloc(sizeof(Edge));
temp = list->head->next;
printf("adjacency node:%2d | ",list->head->src);
while(temp != NULL)
{
printf("%2d->%2d=%2d ",list->head->src,temp->dst,temp->dist);
temp = temp->next;
}
printf("\n");
}
void main()
{
//vertext array
//printf("edge_size = %d;Adj_size=%d\n",(int)sizeof(Edge),(int)sizeof(AdjList(*)[20]));
AdjList (*list)[20] = (AdjList(*)[20])malloc(sizeof(AdjList(*)[20]));
int i,j,k,vNum,eNum,dist;
printf("Please input num of vertex and edge\n");
scanf("%d %d",&vNum,&eNum);
//init Edge,start from 1
for(i=1;i<=vNum;i++)
{
list[i]->head = (Edge*)malloc(sizeof(Edge));
list[i]->tail = (Edge*)malloc(sizeof(Edge));
list[i]->head->src = i;
list[i]->head->next = list[i]->tail = NULL;
}
printf("Please input edge info:i j dist\n");
for(k=1;k<=eNum;k++)
{
Edge *edge = (Edge*)malloc(sizeof(Edge));
scanf("%d %d %d",&i,&j,&dist);
edge->dst = j;
edge->dist = dist;
edge->next = (Edge*)malloc(sizeof(Edge));
edge->next = NULL;
list_add(list[i],edge);
}
//travel the list
printf("******************************\n");
printf("adjacency matrix is like this:\n");
for(k=1;k<=vNum;k++)
{
list_travel(list[k]);
}
}
运行结果 [email protected]:~/learning/sample code/algrithm/map/adjacency_list$ ./adjacency.o edge_size = 24;Adj_size=8 Please input num of vertex and edge 5 10 Please input edge info:i j dist 1 2 10 2 3 20 3 4 5 4 5 15 5 1 20 5 2 13 1 5 8 2 4 9 3 5 7 4 2 3 ****************************** adjacency matrix is like this: adjacency node: 1 | 1-> 2=10 1-> 5= 8 adjacency node: 2 | 2-> 3=20 2-> 4= 9 adjacency node: 3 | 3-> 4= 5 3-> 5= 7 adjacency node: 4 | 4-> 5=15 4-> 2= 3 adjacency node: 5 | 5-> 1=20 5-> 2=13