刚刚恶补了下相关知识,有了些理解,希望对题主有帮助。
首先要更正下对链表的理解:大多数情况下我们理解链表总理解为上下级的关系,即下个节点率属于上个节点,在二叉树里更直观地认为是父节点、子节点,这种先入为主的概念很容易禁锢我们的观点,导致对链表使用局限。其实链表也可以表示为动态数组,数组的元素并无上下级关系,是平等的,连起来仅仅是为了好搜索数组内元素。因此,你完全可以不用链表来表示邻接表,而用一个足够大的数组来表示顶点相邻的关系,只不过用链表更灵活。
有了这个认识,就可以来表述邻接表了:邻接表首先由一个表头,用于存储顶点信息,因为定点数不固定,所以表头也可以用一个链表存储,表头定义为{顶点名称,邻接表指针,下个顶点指针},题主实例有6个顶点,则表头链表有6个元素,邻接表定义为{权值,顶点名称,下个元素指针},有了这些数据结构定义,则题主实例邻接表可表述如下:
表头:{V1,V1邻接表,指向V2}{V2,V2邻接表,指向V3}{V3,V3邻接表,指向V4}{V4,V4邻接表,指向V5}{V5,V5邻接表,指向V6}{V6,V6邻接表,NULL}
V1邻接表:{1,V4,指向下个元素}{1,V2,NULL}
V2邻接表:{1,V5,指向下个元素}{1,V3,NULL}
.
.
.
V6邻接表:{0,0,NULL}
大致如此吧,期待大神指正!