邻接多重表与普通邻接表的差异详解：严蔚敏数据结构讲解

邻接多重表与邻接表是数据结构中用于表示图的两种常见方式。它们在处理有向或无向图时有着不同的特性。首先，让我们了解一下这两个概念： 1. **邻接表**: 邻接表是一种简单且常用的数据结构，它通过数组或链表来表示图中的节点和它们之间的连接。每个节点通常包含一个指向相邻节点的指针列表。在无向图中，每条边通常由两个节点的引用共同表示，一个作为起点，另一个作为终点。例如，图7-15中的无向图，通过邻接表可以用一个链表表示每个节点的邻居，如v1指向v2和v3，v2同时指向v1和v3。 2. **邻接多重表**: 邻接多重表是对邻接表的扩展，当图中存在一条边连接两个节点多次（多条边）时，邻接多重表会在链表中对应这条边的每个端点创建一个表结点，而不是像邻接表那样仅用一个表结点。这样做的目的是为了方便存储和查询多重边的情况。例如，在图中，v2与v3之间有两条边，所以在邻接多重表中会有两个表结点来表示这两条边。 两者的主要区别在于处理边的重复性。邻接表在单个表结点中合并表示，对于简单的图结构（如无重复边的图），两者表现一致。然而，当图中存在重边或多边时，邻接多重表提供了更直观和准确的表示方式。 在数据结构的学习中，邻接表和邻接多重表是重要的概念，特别是在图算法的实现中。理解这两种表示方法有助于设计和优化搜索、遍历、最短路径等算法。《数据结构(C语言版)》这本书由严蔚敏和吴伟民编著，提供了对这些概念的深入讲解，并可能包含了相关的算法设计和实现练习。 编写程序时，需要根据具体问题和图的性质选择合适的表示方式。例如，如果边的权重或出现频率很重要，邻接多重表可能更为合适；而若图较为简单，邻接表可能就足够高效。理解这两种数据结构对于编写高效和灵活的图处理程序至关重要。 此外，数据结构课程还会介绍其他类型的数据结构，如数组、链表、树、图等，以及它们在处理不同类型问题时的优势。例如，电话号码查询系统的例子展示了线性表的简单一对一关系，而磁盘目录文件系统的例子则体现了层次结构的组织方式。 邻接表和邻接多重表是数据结构课程的核心内容，它们在实际编程和问题解决中扮演着关键角色，理解和掌握这些概念对于提升算法和程序设计能力具有重要意义。