图的存储结构2 （邻接表）

目录

无向图：

有向图 

代码实现如下：

注释：

        在无向图中称之为边，有向图中为弧

无向图：

1.无向图需要的存储空间为 n+2e

2.为什么有e条边却需要2e个表结点呢？是因为在无向图中 （v1,v2）与（v2,v1）会在邻接表中行成两个表结点。

3.每一条边链中，表结点的位置都是可以置换的。

无向图的度：

        vi顶点后表结点的数量      例：v1的度为2

有向图 

有向图的度：

       出度：vi顶点后表结点的个数。

       入度：整个单链表中临结点域值为i-1的结点个数。

当我们以入度的方式形成邻接表时：

即逆邻接表

其入度出度与普通邻接表相反

代码实现如下：

#include 
#include 
#include 
#include 
#define MAX_NUM 100
typedef bool Status;
typedef char VerTexType;
typedef char Otherlnfo;

typedef struct arcnode{//边结点 
	int adjvex;//该边所指向的顶点的位置 
	struct arcnode *nextarc;//指向下一条边的指针 
	Otherlnfo info;//和边结点相关的信息 
}ArcNode;

typedef struct vnode{
	VerTexType data;//顶点信息 
	ArcNode *firstarc;//指向第一条依附于该顶点边的指针 
}VNode,AdjList[MAX_NUM];

typedef struct {//无向图结构的定义 
	AdjList vertices;
	int vexnum,arcnum;// 顶点数和边（弧）数 
}ALGraph;


int Location(ALGraph G,char v){
	int i;
	for(i = 0;ivexnum,&G->arcnum);
	getchar();//干掉scanf中的回车符，以下都是此行为 
	
	for(i = 0;ivexnum;i++){
		printf("请输入第%d个顶点：",i+1);
		scanf("%c",&G->vertices[i].data);
		getchar();
		G->vertices[i].firstarc = NULL;//初始化 
	}
	
	for(k = 0;karcnum;k++){           //输入各边构造邻接点 
		printf("请输入第%d条边：",k+1);
		scanf("%c %c",&v1,&v2);
		getchar();
		i = Location(*G,v1);// 返回v1，v2在顶点字符数组中的位置 
		j = Location(*G,v2);
		
		ArcNode *pNew = (ArcNode *)malloc(sizeof(ArcNode));
		if(!pNew) exit(-1);
		pNew->adjvex = i;
		pNew->nextarc = G->vertices[i].firstarc;
		G->vertices[j].firstarc = pNew;
		//由于是无向图，所以此处需要建两个表结点（两结点依附同一条边） 
		ArcNode *tNew = (ArcNode *)malloc(sizeof(ArcNode));
		if(!tNew) exit(-1);
		tNew->adjvex = j;
		tNew->nextarc = G->vertices[i].firstarc;
		G->vertices[i].firstarc = tNew;
	}
	
}

int main()
{
	ALGraph G;
	
	CreateUDE(&G);
	
}