数据结构：邻接多重表与邻接表对比解析

"邻接多重表与邻接表的区别-数据结构PPT--严蔚敏(清华大学)" 在数据结构中，邻接多重表（Adjacency Multilist）和邻接表（Adjacency List）是两种常用的表示图数据结构的方法。它们主要用于存储无向图或有向图的边关系。这里我们将详细探讨它们的区别以及各自的特点。 首先，邻接多重表是一种更加灵活的表示方式，它可以允许图中的同一对顶点之间存在多条边。在邻接多重表中，每条边都由一个表节点表示，即使对于无向图，每一对相邻顶点间的边也会被单独存储，因此，如果同一对顶点之间有多条边，就会有多个表节点。例如，在无向图中，如果顶点v1和v2之间有两条边，那么邻接多重表会有两个表示这两条边的节点。 相对地，邻接表在表示无向图时，每对顶点之间的边通常只用两个表节点表示，即在两个顶点的邻接表中各存储一次这条边。这样，如果v1和v2之间有两条边，邻接表会在v1的邻接表中添加一个指向v2的节点，同时也在v2的邻接表中添加一个指向v1的节点。这种表示方式节省了空间，但牺牲了一定的灵活性，因为它不能直接表示多条边。 在信息存储上，除了标志域（用于区分边的性质等）之外，邻接多重表和邻接表在无向图的情况下表达的信息是相同的。然而，由于结构的不同，它们在某些操作上的实现会有所差异，比如查找、遍历和修改边的操作可能会有所不同。 学习数据结构时，我们还需要掌握其他相关的知识，例如离散数学的基础，这是理解和实现数据结构算法的关键。此外，C语言编程能力也是必不可少的，因为许多数据结构的实现都会使用C语言。同时，数据结构的抽象数据类型（ADT）概念也是非常重要的，它提供了一种定义和使用数据类型的高级方法，强调了数据的逻辑结构和操作，而非具体实现细节。ADT包括定义、表示和实现三个部分，并且具备抽象和信息隐蔽的特性，使得设计出的数据结构更加通用，可以应用于各种问题。 举例来说，ADT可以用来设计电话簿系统，当给定一个姓名时，ADT应该能提供相应的电话号码，如果电话簿中没有该姓名，ADT则应返回找不到的标志。类似的应用场景还有图书馆的书目检索系统、教师资料档案管理系统，甚至是复杂的交通灯控制系统。 在存储结构方面，顺序存储的线性表如数组，其优点在于快速访问任意位置的元素，但插入和删除操作可能需要移动大量元素，效率较低，且数组大小固定，不便于动态扩展。相比之下，链式存储结构，如链表，虽然访问速度相对较慢，但在插入和删除操作上有优势，可以根据需要动态调整空间。 理解和掌握邻接多重表和邻接表的区别，以及数据结构、ADT和编程基础，是深入学习计算机科学，特别是算法和数据处理领域不可或缺的基础。