PS：邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。图的邻接表储存方式相对于邻接矩阵比较节约空间，对于邻接矩阵需要分别把顶点和边（顶点之间的关系）用一维数组和二维数组储存起来。而邻接表则是把顶点按照顺序储存到一维数组中，然后再通过链式方式，把有关系的顶点下标链接到后方，咱们先不考虑权重问题，结构体定义简单一点，当然加上权值也不难。下方看图解释。邻接表有向图无向图逆邻接表有向图邻接表实现步骤结构体创建图顶点和边数，顶点需要用一维数组保存获取顶点的下标，因为链接结点中的index域是顶点的下标值。创建结点，通过头插法（或尾插法）把结点链接到头结点的尾部打印（遍历方式后序介绍）1：结构体我们可以分为头和表结构，如图所示
那么结构体就可以这样设计代码语言：javascript复制/**
* 表头连接的表中结点定义
* */
typedef struct tableBody {
int vexIndex;//邻接点在数组中的位置下标
struct tableBody *nextarc;//指向下一个邻接点的指针
} tableBody;
/**
* 表头结点定义
* */
typedef struct tableHead {
char data;//顶点的数据域
struct tableBody *firstarc;//指向邻接点的指针
} tableHead, *tableHeadArr;//存储各链表头结点的数组
/**图-邻接表定义*/
typedef struct {
tableHead vertices[20];//图中顶点及各邻接点数组
int vexnum, arcnum;//记录图中顶点数和边或弧数
} LJBGraph;2：创建表内部注释涵盖了上述步骤。
代码语言：javascript复制void createGraph(LJBGraph *g) {
//总顶点个数，总边数
int i, j, k;
tableBody *tb;
printf("输入顶点数和边数");
scanf("%d %d", &g->vexnum, &g->arcnum);//获取顶点数和边数
//gettchar();
for (i = 0; i < g->vexnum; i++) {
char c;
printf("输入%d 个顶点值", (i + 1));
getchar();
scanf("%c", &c);
g->vertices[i].data = c; //获取顶点值，
g->vertices[i].firstarc = NULL; //将边表置为空
}
for (k = 0; k < g->arcnum; k++) {
printf("输入a,b 在图中有a-->b:");
getchar();
char a,b;
scanf("%c %c", &a, &b); //输入i,j 在图中有i-->j
tb = (tableBody *) malloc(sizeof(tableBody));
i=localIndex(g,a); //a顶点所在顶点数组中的下标值。
j=localIndex(g,b); //b顶点所在数组中的下标值。
tb->vexIndex = j;
tb->nextarc = g->vertices[i].firstarc; //头插法建立边表
g->vertices[i].firstarc = tb;//把新建的结点链接在顶点后面
/*如果为无向图，则加入以下代码
e=(EdgeNode*)malloc(sizeof(EdgeNode));
e->adjvex = i;
e->next = g->adjList[j].firstedge;
g->adjList[j].firstedge= e;*/
}
printfL(g);
DFSTraverse(g);
}寻找下标值，就是普通的遍历，在顶点数组中遍历返回下标。
代码语言：javascript复制int localIndex(LJBGraph *g,char data){
for(int i=0;i
if(g->vertices[i].data == data){
return i;
}
}
printf("没有这个字符");
return -1;
}所得有向图和无向图的结构图不一样3：打印代码语言：javascript复制void printfL(LJBGraph *g) {
//输出图的信息
printf("表为 :\n");
tableBody *p;
printf("\n");
//邻接表不需要表标题。
int i;
for (i = 0; i < g->vexnum; i++) {
printf("%d%c\t",(i),g->vertices[i].data);//表头结点
p = g->vertices[i].firstarc;
while (p) {
printf("%d\t", p->vexIndex);//外表结点
p = p->nextarc;//外表结点下移
}
printf("\n");
}
}主方法是不是代码很简单，所有东西都封装起来。
代码语言：javascript复制int main(void) {
LJBGraph *g;
createGraph(g);
return 0;
}注：比较邻接矩阵和邻接表的区别存储结构
储存方式
操作特性
邻接矩阵
一维数组（顶点）
二维数组（邻接关系）
1：易于判定顶点是否邻接，查顶点的邻接点
2：插入、删除顶点复杂
邻接表
头结点（顶点）
表结点（邻接关系）
1：易于：查询某顶点的邻接点，边或弧的插入、删除
2：判定顶点是否邻接，比邻接矩阵低效。
4：逆邻接表所谓逆邻接表就是方向相反的链接到顶点后面，一看图便知。完：下一篇讲会讲解深度优先遍历和广度优先遍历基本使用和思想。