邻接多重表与普通邻接表的对比详解

邻接多重表与邻接表是数据结构中用于表示图的一种方式，它们都是用来描述图中顶点与顶点之间的连接关系。邻接表是一种简单且常用的数据结构，它将每个顶点的邻接点信息存储在一个链表中，每个链表元素对应一个邻接顶点。在邻接表中，每条边仅由一个链表节点表示，通常包含指向目标顶点的指针和可能的额外信息，如边的权重等。 而邻接多重表是对邻接表的一种扩展，它在同一条边的表示上有所不同。在邻接多重表中，为了记录一条边可能存在的多个副本（例如在有向图中的多个出边），同一条边可能会被表示为两个表结点。第一个表结点通常包含边的基本信息，第二个表结点则可能用于存储额外的属性，如计数器或标记。这样做的好处是可以更灵活地处理复杂图的连接情况，但会增加存储开销。 在严蔚敏的数据结构讲义中，这两个概念被用于教学，并通过实例图7-15来展示，展示了如何用邻接多重链表表示一个无向图。邻接表和邻接多重表的操作实现上虽然有相似之处，但针对不同的需求，如处理边的多重性，邻接多重表的实现会更为复杂。 在讨论数据结构的学习路径时，提到《数据结构与算法分析》课程会涉及C语言编程实践，因为数据结构的实现通常需要编程支持。此外，课程强调了数学基础知识的重要性，特别是离散数学，因为它为理解数据结构和算法提供了基础。例如，设计查找特定人物电话号码的算法，或者处理图书馆书目检索、教师资料管理等实际问题时，都需要运用到数据结构的知识。 ADT（抽象数据类型）的概念在这里被进一步阐述，它与数据类型虽有相似之处，但ADT更强调的是抽象和信息隐蔽。ADT不仅包括系统预定义的数据类型，还允许用户自定义数据类型。一个ADT由值域和一组操作定义，这些操作隐藏了底层数据存储和实现的细节，使得用户只需要关心数据的抽象接口和服务。 在讲解C语言时，提到了数组下标从0开始的特性，这对于理解线性表的顺序存储尤为重要。顺序存储的优点在于访问速度快，但插入和删除操作效率低，因为可能需要移动大量元素，可能导致空间浪费和难以动态调整数组大小。这些内容都是理解数据结构和算法性能的关键要素。