PS：邻接表，存储方法跟树的孩子链表示法相类似，是一种顺序分配和链式分配相结合的存储结构。如这个表头结点所对应的顶点存在相邻顶点，则把相邻顶点依次存放于表头结点所指向的单向链表中。图的邻接表储存方式相对于邻接矩阵比较节约空间，对于邻接矩阵需要分别把顶点和边（顶点之间的关系）用一维数组和二维数组储存起来。而邻接表则是把顶点按照顺序储存到一维数组中，然后再通过链式方式，把有关系的顶点下标链接到后方，咱们先不考虑权重问题，结构体定义简单一点，当然加上权值也不难。下方看图解释。

邻接表

1. 有向图
2. 无向图

逆邻接表

1. 有向图

邻接表实现步骤

1. 结构体
2. 创建图
   1. 顶点和边数，顶点需要用一维数组保存
   2. 获取顶点的下标，因为链接结点中的index域是顶点的下标值。
   3. 创建结点，通过头插法（或尾插法）把结点链接到头结点的尾部
3. 打印（遍历方式后序介绍）

1：结构体

我们可以分为头和表结构，如图所示

 

那么结构体就可以这样设计

/*** 表头连接的表中结点定义* */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：创建表

内部注释涵盖了上述步骤。

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);}

寻找下标值，就是普通的遍历，在顶点数组中遍历返回下标。

 

int localIndex(LJBGraph *g,char data){    for(int i=0;i
        
         vexnum;i++){        if(g->vertices[i].data == data){            return i;        }    }    printf("没有这个字符");    return -1;}
        

所得有向图和无向图的结构图不一样

 

 

3：打印

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");    }}

主方法

是不是代码很简单，所有东西都封装起来。

int main(void) {    LJBGraph *g;    createGraph(g);    return 0;}

注：比较邻接矩阵和邻接表的区别

存储结构	储存方式	操作特性
邻接矩阵	一维数组（顶点） 二维数组（邻接关系）	1：易于判定顶点是否邻接，查顶点的邻接点 2：插入、删除顶点复杂
邻接表	头结点（顶点） 表结点（邻接关系）	1 ：易于：查询某顶点的邻接点，边或弧的插入、删除 2：判定顶点是否邻接，比邻接矩阵低效。

 

 

 

 

 

 

 

 

4：逆邻接表

所谓逆邻接表就是方向相反的链接到顶点后面，一看图便知。

完：

下一篇讲会讲解深度优先遍历和广度优先遍历基本使用和思想。