笔记02 数据结构
数据结构
数据结构,以某种特定的布局方式
存储数据的容器。
这种布局方式决定了数据结构对于某些操作是高效的,
而对于其他操作则是低效的。
在处理实际问题时选取最合适的数据结构。
常见数据结构5 图
图是一组以网络形式相互连接的节点。
节点也称为顶点。
一对节点(x,y)称为边(edge)
表示顶点x连接到顶点y。
边可以包含权重/成本,
显示从顶点x到y所需的成本。
图的类型
- 无向图
- 有向图
在程序语言中,图的表示形式
- 邻接矩阵
- 邻接表
常见图遍历算法
- 广度优先搜索
- 深度优先搜索
常见数据结构6 树
树形结构是一种层级是的数据结构,
有顶点(节点)和连接它们的边组成。
树类似于图,但区分树和图的重要特征是
树中不存在环路。
树形结构被广泛应用于人工智能和复杂算法,
它可以提供解决问题的有效存储机制。
- root 根节点
- parent 父节点
- child 子节点
- leaf 叶子节点
- sibling 兄弟节点
—
- N元树
- 平衡树
- 二叉树 (最常用)
- 二叉搜索树 (最常用)
- AVL树
- 红黑树
- 2-3树
常见数据结构7 字典树 (Trie)
字典树,也称为“前缀树”,
是一种特殊的树状数据结构,
对于解决字符串相关问题非常有效。
它能够提供快速检索,主要用于搜索字典中的单词,
在搜索引擎中自动提供建议,
甚至被用于IP的路由。
常见数据结构8 散列表(哈希表)
哈希法(Hashing)是一个用于唯一标识对象
并将每个对象的存储在一些预先计算的唯一索引(称为“键”key)中的过程。
因此,对象以键值对的形式存储,
这些键值对的集合被称为“字典”。
可以使用键搜索每个对象。
基于哈希法有很多不同的数据结构,
但最常用的数据结构是哈希表
。