-
Notifications
You must be signed in to change notification settings - Fork 0
/
data structure
58 lines (35 loc) · 2.41 KB
/
data structure
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
数据结构：数据 与 数据之间的关系。逻辑关系和存储关系。
存储时：数据的存储顺序与位置关系就是存储关系
E.g. 存储手机电话的时候， 最原始：按照“先到先得”的顺序，逐次向下添加新的手机号码；
但引入了姓氏首字母后，手机号码就得到了分类存储。
逻辑结构：与计算机存放的位置无关 元素之间的关系
线性结构：数组、队列、链表、栈。
一个直接前趋结点 + 一个直接后趋结点
非线性结构：
一个节点 有多个后继节点 + 多个前驱节点
多维数组 + 广义表 + 树结构 + 图结构
物理结构 or 存储结构 逻辑结构在计算机存储空间中的存放形式
顺序结构 + 链式存储 + 索引存储 + 散列存储
顺序结构： 用一组地址连续的存储单元 依次store 线性表的各个元素
链式存储：在内存中存储的元素不一定是连续的 任意地址的存储单元 存储元素
元素的节点存放数据元素 + 指针指向相邻元素的地址信息
散列 + 链表（数组） 散列对应散列值 同一散列值下面的的链表有多个槽 用来存放不同的元素
时间复杂度：执行当前算法所消耗的时间
空间复杂度：执行当前算法所占用的内存空间 二者 鱼和熊掌
散列：
理想情况：简单均匀散列
第一反应取模运算（取余数）但这个运算依赖原数中的最后一位，如果最后一位都是不均匀分布的（即包含了real value对应的位置是不均匀的1 2 4 11 22 44 111 222 444）9个数 但只放到了3个槽
一般 选择不接近2的整数幂的 素数
Tree
Node + edge 没有父节点的节点称为根节点
每一个非根结点有且只有一个父节点
除了根节点外，每一个子节点可以分为多个不相交的子树。
左子树和右子树有顺序 01
各个结点的值 均大于 其左子树上任意一个结点的值
均小于 其右子树上任意一个结点的值
Hash 记录的存储位置 = f(key) f是散列函数 将哈希函数转换为整型数字
将数字对数组长度进行取余 - 取余结果当作数组的下标
堆是一个完全二叉树 除了最后一层外 其他层节点个数都是满的
顺序：从上到下 从左到右 依次编号 每一个节点值都大于等于或小于子树的每一个节点值
图：vertex + edge
图有有向图和无向图