数组|常见的8中数据结构( 二 ) 1976年

文章插图
图分为两种:

无向图
有向图

在编程语言中，图有可能有以下两种形式表示：

邻接矩阵(Adjacency Matrix)
邻接表(Adjacency List)

遍历图有两周算法

广度优先搜索(Breadth First Search)
深度优先搜索(Depth First Search)

6. 树
树(Tree)是一个分层的数据结构，由节点和连接节点的边组成。树是一种特殊的图，它与图最大的区别是没有循环。
【数组|常见的8中数据结构】树被广泛应用在人工智能和一些复杂算法中，用来提供高效的存储结构。
下图是一个简单的树以及与树相关的术语：

文章插图
树有很多分类：

N 叉树(N-ary Tree)
平衡树(Balanced Tree)
二叉树(Binary Tree)
二叉查找树(Binary Search Tree)
平衡二叉树(AVL Tree)
红黑树(Red Black Tree)
2-3 树(2–3 Tree)

其中，二叉树和二叉查找树是最常用的树。
7. 前缀树
前缀树(Prefix Trees 或者 Trie)与树类似，用于处理字符串相关的问题时非常高效。它可以实现快速检索，常用于字典中的单词查询，搜索引擎的自动补全甚至 IP 路由。
下图展示了“top”, “thus”和“their”三个单词在前缀树中如何存储的：

文章插图
单词是按照字母从上往下存储， “p”, “s”和“r”节点分别表示“top”, “thus”和“their”的单词结尾。
8. 哈希表
哈希(Hash)将某个对象变换为唯一标识符，该标识符通常用一个短的随机字母和数字组成的字符串来代表。哈希可以用来实现各种数据结构，其中最常用的就是哈希表(hash table) 。
哈希表通常由数组实现。
哈希表的性能取决于 3 个指标：

哈希函数
哈希表的大小
哈希冲突处理方式

下图展示了有数组实现的哈希表，数组的下标即为哈希值，由哈希函数计算，作为哈希表的键(key) ，而数组中保存的数据即为值(value)：

文章插图