首页   快速返回

数据结构要点     所属分类 architecture
编程=数据结构+算法 

数据结构是以某种特定的布局方式存储数据的容器。
这种“布局方式”决定了数据结构对于某些操作是高效的,而对于其他操作则是低效的。
理解各种数据结构,在处理实际问题时选取最合适的数据结构。

常见的数据结构
数组 栈 队列 链表 树 图
字典树 
散列表/哈希表

一维数组  多维数组(数组的数组)

数组的基本操作
Insert 在指定索引位置插入一个元素
Get 返回指定索引位置的元素
Delete 删除指定索引位置的元素
Size 得到数组所有元素的数量

数组常见问题

寻找数组中第二小的元素
找到数组中第一个不重复出现的整数
合并两个有序数组
重新排列数组中的正值和负值


栈
把栈想象成一列垂直堆放的书。为了拿到中间的书,需要移除放置在这上面的所有书。LIFO(后进先出) 
实现 撤销操作

Push 在顶部插入一个元素
Pop 返回并移除栈顶元素
isEmpty 如果栈为空,则返回true
Top 返回顶部元素,但并不移除它


使用栈计算后缀表达式
对栈的元素进行排序
判断表达式是否括号平衡


队列
FIFO 先进先出

Enqueue()  在队列尾部插入元素
Dequeue()  移除队列头部的元素
isEmpty() 如果队列为空,则返回true
Top()  返回队列的第一个元素

使用队列表示栈
对队列的前k个元素倒序
使用队列生成从1到n的二进制数

链表

链表一般用于实现文件系统、哈希表和邻接表。

单链表(单向)
双向链表(双向)

反转链表
检测链表中的循环
返回链表倒数第N个节点
删除链表中的重复项

图是一组以网络形式相互连接的节点 ,节点也称为顶点。 
一对节点(x,y)称为边(edge),表示顶点x连接到顶点y。边可以包含权重/成本,显示从顶点x到y所需的成本。

vertex 

无向图
有向图

图的两种表示
邻接矩阵
邻接表


图遍历算法
广度优先搜索
深度优先搜索

实现广度和深度优先搜索
检查图是否为树
计算图的边数
找到两个顶点之间的最短路径

树

树形结构是一种层级式的数据结构,由顶点(节点)和连接它们的边组成。 
树类似于图,但区分树和图的重要特征是树中不存在环路。

Root - 根节点
Parent - 父节点
Child - 子节点
Leaf - 叶子节点
Sibling - 兄弟节点

上一篇     下一篇
Redis HyperLogLog 使用

git回退到之前的版本

git合并处理

hive四种存储格式

java版hyperLogLog

磁盘io与直接io