"数据结构中的词典和映射：提高信息访问效率的方式"

第9章讲述了数据结构在表示和组织数字信息方面的重要性，以及借助关键码直接查找和访问数据元素的形式在现代数据结构中的应用。其中，词典和映射是两种常见的符号表结构。 首先介绍词典结构，词典是由一组数据构成的集合，其中的每个元素都由关键码和数据项合成的词条构成。词典允许多个词条拥有相同的关键码，这是与映射结构的唯一差别。词典结构支持静态查找和动态更新操作，因此也属于符号表的一种。在本章中，词典的实现主要用跳转表和散列表两种数据结构来进行讲解。 跳转表和散列表分别对应允许雷同关键码和禁止雷同关键码的语义。跳转表是一种通过维护关键码有序排列的有序结构，提供高效的查找操作。它的特点是不仅支持基于关键码的快速查找，还能够处理范围查找的需求，因此在某些场景下具有广泛的应用。而散列表则是通过散列函数将关键码映射到一个地址，进而快速查找数据元素。散列表的优势在于对于大规模数据的查找操作，具有较好的平均时间复杂度，但也存在一些缺点，比如可能会出现冲突。 除了跳转表和散列表，词典和映射还可以用其他数据结构来实现，词典和映射中的数据元素可以表示为词条的形式，但这不是必须的。与第7章和第8章介绍的搜索树相比，符号表结构并不要求词条之间能够根据某种顺序来进行排列，因此在某些场景下，符号表可能会更加灵活和高效。 需要注意的是，词典和映射中的关键码是否允许雷同应该从语义层面来界定，而非ADT接口的层面。因此，在本章中不会过分强调词典和映射的差异，而是笼统地称之为词典，并根据允许雷同和禁止雷同的语义，分别进行统一的接口实现。 总的来说，第9章主要介绍了数据结构在表示和组织数字信息方面的重要性，以及借助关键码直接查找和访问数据元素的形式在现代数据结构中的应用。词典和映射是常见的符号表结构，它们可以用不同的数据结构来实现，例如跳转表和散列表。在实际应用中，根据场景的需求来选择相应的符号表结构，能够提高信息访问的规范性和处理的效率。