红联Linux门户
Linux帮助

算法--数据结构--图的邻接链表表示法

发布时间:2005-10-23 16:20:51来源:红联作者:frog
/*********************************************************
Title : graph-adjacentlist.c
Author :
Time :
Purpose : 图的邻接链表表示法
Thread :
Comment :
Usage :
**********************************************************/
#include "stdio.h"
#include "stdlib.h"





/*=====================变量声明--variable declaration=================*/
typedef struct _graphnode { /* 图形顶点结构宣告 */
int vertex; /* 顶点资料 */
struct _graphnode *nextnode; /* 指下一顶点的指标 */
} graphnode;

typedef struct _graph { /* 图形的结构新型态 */
struct _graphnode *firstnode;
} graph;


struct _graphnode head[6]; /* 图形顶点结构数组 */




/*=====================函数声明--function declaration=================*/
void creategraph(int *node,int num);




/*====================函数实现--function implementation================*/
/* --------------------------------------------------
Function : creategraph()
Purpose : 建立图形
Arguments :
Returns :
------------------------------------------------- */
void creategraph(int *node,int num)
{
graphnode *newnode; /* 新顶点指标 */
graph ptr;
int from; /* 边线的起点 */
int to; /* 边线的终点 */
int i;

for ( i = 0; i < num; i++ ) { /* 读取边线的回路 */
from = node[i*2]; /* 边线的起点 */
to = node[i*2+1]; /* 边线的终点 */
/* 建立新顶点记忆体 */
newnode = ( graphnode *) malloc(sizeof(struct _graphnode));
newnode->vertex = to; /* 建立顶点内容 */
newnode->nextnode = NULL; /* 设定指标初值 */
ptr.firstnode = &(head[from]); /* 顶点位置 */
while ( ptr.firstnode->nextnode != NULL ) /* 遍历至链表尾 */
ptr.firstnode = ptr.firstnode->nextnode; /* 下一个顶点 */
ptr.firstnode->nextnode = newnode; /* 插入结尾 */
}
}



/*=========主函数: 建立图形后,将邻接链表印出==========*/
int main(int argc, char *argv[])
{
graph ptr;
int node[12][2] = { {1, 2}, {2, 1}, /* 边线数组 */
{1, 3}, {3, 1},
{2, 3}, {3, 2},
{2, 4}, {4, 2},
{3, 5}, {5, 3},
{4, 5}, {5, 4} };
int i;

for ( i = 1; i <= 5; i++ ) {
head[i].vertex = i; /* 设定顶点值 */
head[i].nextnode = NULL; /* 清除图形指标 */
}
creategraph(node,12); /* 建立图形 */
printf("图形的邻接链表内容:\n");
for ( i = 1; i <= 5; i++ ) {
printf("顶点%d =>",head[i].vertex);/* 顶点值 */
ptr.firstnode = head[i].nextnode; /* 顶点位置 */
while ( ptr.firstnode != NULL ) { /* 遍历至链表尾 */
printf(" %d ",ptr.firstnode->vertex); /* 印出顶点内容 */
ptr.firstnode = ptr.firstnode->nextnode; /* 下一个顶点 */
}
printf("\n"); /* 换行 */
}

return 1;
}
文章评论

共有 2 条评论

  1. jemney 于 2005-10-26 22:51:17发表:

  2. reing 于 2005-10-25 00:31:03发表:

    不错