数据结构基本算法：图的存储（以邻接链表为例）

数据结构的图的建立方法，简单的邻接链表形式代码：

可运行。

对于其他各种的存储方式，等会有一帖。（发现了好东西。。）

代码如下：有链表和顺序数组组成。链表用来存储边的信息，数组用来用存储顶点的数据信息。

图的示例结构如下：

/***** 图的建立********/

/******** written by C_Shit_Hu ************/

//////////////数据结构///////////////

/****************************************************************************/
/* 
图的存储方式常见的有两种--邻接矩阵存储方法和邻接链表存储方法
···邻接矩阵核心思想：利用两个数组存储一个图，一个数组是一个一维数组用于存储顶点信息，一个是一个二维数组用于存储顶点的边的信息
···缺点：不适用于存储稀疏图
利用邻接表建立图，弥补邻接矩阵的不足的方法。有链表和顺序数组组成。链表用来存储边的信息，数组用来用存储顶点的数据信息。

-----具体见博客说明：
*/
/****************************************************************************/

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

//定义单链表中的结点的类型
typedef struct ArcNode{

	int  adjvex;                  // 该边指向的顶点在顺序表中的位置
	struct ArcNode  *next;        // 下一条边*/
}ArcNode;

// 顶点类型
typedef struct VNode{

	int  data;                    // 顶点中的数据信息
	ArcNode  *firstarc;           // 指向单链表，即指向第一条边
}VNode;

void CreatGraph(int n , VNode G[] )
{
	int i,e;
	ArcNode *p , *q;
	printf("Input the information of the vertex\n");
	for(i=0;i<n;i++){
		scanf("%d",&G[i]);
		G[i].firstarc = NULL;                        // 初始化第一条边为空
	}
	for(i=0;i<n;i++)
	{
		printf("Creat the edges for the %dth vertex\n",i) ;
		scanf("%d",&e);
		while(e!=-1){
			p = (ArcNode *)malloc(sizeof(ArcNode));            // 创建一条边
			p->next = NULL;
			p->adjvex = e;
			if(G[i].firstarc == NULL) G[i].firstarc = p;        // i结点的第一条边
			else q->next = p;                            // 下一条边
			q = p;
			scanf("%d",&e);
		}
	}
}

int main()
{
    VNode G[5];
    CreatGraph(5,G);
    getchar();
    return 0 ;
}

运行结果如下：

稍后转一贴集合版的数据结构的图的存储方式贴。