数据结构实验：加权图与哈希表的探索与实践

### 数据结构实验：加权图与哈希表的探索与实践 在数据结构的学习与实践中，加权图和哈希表是两个重要的概念。下面我们将深入探讨它们的相关知识和实验内容。 #### 加权图相关实验 在通信网络的设计中，我们常常会遇到这样的问题：当一条通信线路因天气或设备故障而无法工作时，整个网络是否还能保证所有交换中心之间的通信？这就涉及到加权图的连通性问题。 一个图如果任意两个顶点之间都存在路径，那么这个图就是连通的。而顶点的度是指连接该顶点的边的数量，其中自环边算两条。通过简单的图论知识，我们可以得出一个规则：如果一个连通图的所有顶点的度都是偶数，那么移除图中的任意一条边，得到的图仍然是连通的。 为了验证这个规则，我们需要实现一个加权图的抽象数据类型（ADT）操作 `areAllEven`，用于检查图中每个顶点的度是否为偶数。具体步骤如下： 1. **实现 `areAllEven` 操作**：将该操作添加到 `wtgraph.cpp` 文件中，其原型已包含在 `wtgraph.h` 文件的 `WtGraph` 类声明中。 2. **激活测试程序中的命令**：在 `test13.cpp` 测试程序中，移除以 “//D” 开头的行的注释分隔符（和字符 ‘D’），激活 ‘D’（度）命令。 3. **准备测试计划**：设计一个测试计划，包含各种顶点连接方式的图。测试计划表格如下： | 测试用例 | 命令 | 预期结果 | 检查情况 | | ---- | ---- | ---- | ---- | | | | | | 4. **执行测试计划**：运行测试计划，如果发现 `areAllEven` 操作实现有误，进行修正后再次执行测试计划。 另外，在使用 Floyd 算法计算图中每对顶点之间的最短路径时，我们不仅想知道最短路径的成本，还想知道路径上经过的顶点。对于路径矩阵中的每个条目 (j, k)，我们只需要知道从 j 到 k 的最短路径上 j 之后的顶点的索引，即最短路径上的第二个顶点的索引。通过这个增强的路径矩阵，我们可以列出给定顶点对之间最短路径上的顶点。例如，对于路径矩阵中的条目 (0, 4)，它表示从顶点 A 到顶点 E 的最短路径成本为 230，且最短路径上的第二个顶点是索引为 1 的顶点 B，所以最短路径形式为 AB...E。 同时，我们还需要给出一个不能用少于五种颜色进行正确着色的图的例子，并思考这个例子是否与四色定理相矛盾。 #### 哈希表相关实验 在数据处理中，我们之前实现的数据结构在插入和检索操作上的平均性能通常为 O(N)，最好情况下为 O(log₂N)。当数据量变得非常大时，这些性能就显得不够理想。而哈希表 ADT 则尝试提供 O(1) 的搜索、插入和检索性能，它是一种在许多场景下都非常受欢迎的数据结构，例如大多数电子图书馆目录都基于哈希表实现。 哈希表的理想目标是将每个键唯一地映射到数组中的特定位置，这个映射过程由哈希操作完成。哈希操作接受键作为输入，并返回一个整数作为哈希表的索引。 当键是整数时，哈希函数可以直接返回该整数作为索引。但如果键值超出了数组的有效位置，我们可以使用取模运算将键映射到有效的索引值。然而，哈希计算很容易为多个键生成相同的索引值，这就是所谓的冲突。解决冲突的一种方法是链地址法，即将产生相同索引的所有键连接到数组的相应位置形成一个链。 哈希表的数据项是通用类型 DT，其结构是一个单链表数组。数据项插入的链表由其哈希操作计算出的索引决定，而在特定链表中的插入顺序则由插入的时间顺序决定。 哈希表 ADT 包含以下操作： | 操作 | 要求 | 结果 | | ---- | ---- | ---- | | `HashTbl ( int initTableSize ) throw ( bad_alloc )` | 无 | 构造函数，创建空的哈希表 | | `~HashTbl ()` | 无 | 析构函数，释放存储链表的内存 | | `void insert ( const DT &newDataItem ) throw ( bad_alloc )` | 哈希表未满 | 将新数据项插入到适当的链表中。如果链表中已存在具有相同键的数据项，则更新该数据项的非键字段；否则，将其插入到链表末尾 | | `bool remove ( KF searchKey )` | 无 | 搜索哈希表中具有指定键的数据项。如果找到，则移除该数据项并返回 true；否则，返回 false | | `bool retrieve ( KF searchKey, DT &dataItem )` | 无 | 搜索哈希表中具有指定键的数据项。如果找到，则将该数据项复制到 `dataItem` 并返回 true；否则，返回 false，`dataItem` 未定义 | | `void clear ()` | 无 | 移除哈希表中的所有数据项 | | `bool isEmpty () const` | 无 | 如果哈希表为空，返回 true；否则，返回 false | | `bool isFull () const` | 无 | 如果哈希表已满，返回 true；否则，返回 false | | `void showStructure () const` | 无 | 输出哈希表中的数据项。如果哈希表为空，输出 “Emp