基础数据结构
目录
•
线性结构
•
二叉堆
•
并查集
•
哈希表
•
应用举例
一、线性结构
基础知识
•
数组
•
带头结点的双链表
– He a d
结点
:
虚拟头结点
– Fir s t
结点
:
第一个有实际内容的结点
•
队列
:
循环队列与
Open-Close
表
例
1.
最小值
•
实现一个
n
个元素的线性表
A
。每次可以修
改其中一个元素，也可以询问闭区间
[p, q]
中元素的最小值。
• 1<=n,m<=100000
分析
•
利用二级检索的思想
–
设块长为
L,
则一共有
n/L
个块
–
维护数组
B,
保存每个块的最小值
• Modify(x, y)
– A[x] = y
O(1)
–
重算
x
所在块的最小值
(
更新
B)
O(L)
9 10 11 12 13 14 15 16
8
7
6
5
4
3
1 2
13~16
9~12
5~8
1~4
Min
操作
• Min(a, b)
–
把区间
[a, b]
分成若干部分
–
完整块
:
一共最多
n/L
个块
O(n/L)
–
非完整块
:
首尾各最多
L-1
个元素
O(L)
•
每次操作时间复杂度
: O(n/L+L)
–
设
L=O(n
1/2
)
则渐进时间复杂度为
O(n
1/2
)
√ √ √
√
√
√
例
2.
最接近的值
•
给一个
n
个元素的线性表
A
，对于每个数
A
i
，
找到它之前的数中，和它最接近的数。即
对于每个
i
，计算
C
i
=min{|
A
i
-
A
j
| | 1<=
j
<
i
}
•
规定
C
1
=0
。
分析
•
问题的关键
:
你只需要解决
离线
问题
–
在线问题
:
每输入一个
A
i
,
立刻输出
C
i
–
离线问题
:
在给出任何输出之前得到所有
A
i
•
预处理
:
用
O(nlogn)
时间给所有
A
i
排序
–
很快就会学到了
☺
•
主算法
–
根据从小到大的顺序构造双向链表
–
依次计算
C
n
, C
n-1
, …, C
1
在线问题可能么
?
主算法
• A={2, 6, 5, 10, 4, 7},
依次计算
C
6
, C
5
, C
4
–
每次计算
C
i
时
,
链表中恰好是
计算
C
i
需要的元素
–
计算
C
i
只需比较两个元素，然后删除
A
i
O(1)
2
2
4
4
5
5
6
6
7
7
10
10
2
2
4
4
5
5
6
6
10
10
2
2
5
5
6
6
10
10
例
3.
移动窗口
•
有一个长度为
n
的数组，还有一个长度为
k<=n
的窗口。窗口一开始在最左边的位
置，能看到元素
1, 2, 3, …k
。每次把窗口往
右移动一个元素的位置，直到窗口的右边
界到达数组的元素
n
。
分析
•
考虑最小值。假设窗口从左往右移动
•
保存
5
是不明智的
,
因为从
现在
开始一直到
5
离开窗口
, 5
始终被
4“
压制
”
，永远都不可能
成为最小值。删除
5
不会影响
结果
•
启发
：算最小值的
有用
元素形成一个递增
序列，最小值就是队首元素
•
关键：
窗口右移操作
…
4
5
3
… 2
分析
•
窗口右移：
队首出队，新元素入队，然后
在队列中删除它前面比它大的元素
•
实现
–
用链表储存窗口内
有用
元素
–
则窗口右移的时间和删除元素的
总
次数成正比
•
元素被删除后不会再次被插入，因此每个
元素最多被删除一次，总次数为
O(n),
即：
算法时间总复杂度为
O(n)
…
4
12
11
9
7
5
3
3
…
例
4.
程序复杂度
•
给出一段程序，计算它的时间复杂度。这段程序
只有三种语句：
– OP <x >
：执行一条时间耗费为
x
的指令。这里的
x
为不
超过
100
的正整数。
– LOOP <x>
：与
END
配套，中间的语句循环
x
次，其中
x
可以为规模
n
，也可以是不超过
100
的正整数。
– EN D
：与
LOOP
配套，循环终止。
•
注意：
OP
语句的参数不能为变量
n
，而
LOOP
语
句的参数可以为变量
n
，但不允许有其他名字的变
量。这样，整个程序的时间复杂度应为
n
的多项
式。你的任务就是计算并显示出这个多项式。
例
4.
程序复杂度
•
输出仅包含一行，即时间复杂度的多项
式。这个多项式应该按通常的方式显示处
理，即不要输出
0n
这样的项，
n
项也不要输
出为
n^1
，等等。
OP 1
LOOP n
LOOP 10
LOOP n OP 7 END
OP 1
END
END
70n^2+10n+1
分析
•
考虑特殊情况：没有变量
n
只有常数的情况
•
两种思路
–
递归求解：不直接，附加开销大
/
–
基于栈的扫描算法：实现简单明了，效率高
☺
•
扫描过程（基本想法）
– LO O P x
和
OP x,
把语句入栈
– END,
不断从栈里弹出语句，直到弹出
LOOP
•
弹出过程中累加操作数
x
，然后乘以循环次数
y
•
把
OP x*y
压入栈中，相当于用一条
OP
等效一个
LOOP
分析
•
栈扫描算法的直接推广
–
栈里的每个操作数不是数，而是多项式
–
多项式加法，多项式与整数的乘积
–
所有通过至少一个数据的同学都采用此法
•
问题
–
多项式如何表示
–
多项式操作的时间复杂度是怎样的？
复杂性
•
大部分数据涉及到高精度整数运算
•
高精度运算的复杂性
–
写起来相对麻烦
–
时间复杂度：
O(n
2
) (nlogn is possible, but…)
–
空间复杂度
•
实际情况：所有使用了高精度运算的同学
在时间
“
爆
”
掉之前空间先
“
爆
”
掉
–
每个数
10000
位
, n
次数可达
10000
（或更多）
–
栈里面可以有
10000
个多项式，
10
12
=1T !!!!!
空间
…
空间
…
空间
…
•
是否可以找到一个空间需求比较小的算
法？
哪怕时间效率略一点都可以
•
输出文件已经不小了，需要尽量少的保存
中间结果，因此最好不要栈！
–
只要有栈，最坏情况中间结果的空间大小就是
输出大小乘以栈的最大深度，而输出
…
“
把括号展开
”
•
先想办法去掉所有
LOOP/END
•
借助
当前乘数
确定这次
OP
的
最终
效果
OP 1
LOOP n
LOOP 10
LOOP n
OP 7
END
OP 1
END
END
OP
1
* 1
OP
(n*10*n)
* 7
OP
(n*10)
* 1
基本算法
•
设当前乘数为
m,
结果多项式为
ans
–
初始化
m= 1, ans = 0
•
主循环：一条一条语句处理
–
遇到
LOOP x
，
m = m * x
–
遇到
END
，
m = m / x
–
遇到
OP x, ans = ans + m * x
•
数据结构：设
m = an
b
，则用数对
(a, b)
表示
m
，
a
是高精度整数，
b
是
int
类型
•
除了结果多项式
ans
和
a
，
其他空间可忽略
二、二叉堆
堆
•
堆
(heap)
经常被用来实现优先队列
(priority
queue):
可以把元素加入到优先队列中
,
也
可以从队列中取出
优先级最高
的元素
–
Insert(T, x):
把
x
加入优先队列中
–
DeleteMin(T, x):
获取优先级最高的元素
x,
并
把它从优先队列中删除
堆的操作
•
除了实现优先队列
,
堆还有其他用途
,
因此
操作比优先队列多
–
Getmin(T, x):
获得最小值
–
Delete(T, x):
删除任意已知结点
–
DecreaseKey(T, x, p):
把
x
的优先级降为
p
–
Build(T, x):
把数组
x
建立成最小堆
•
显然
,
用堆很容易实现优先队列
堆的定义
•
堆是一个完全二叉树
–
所有叶子在同一层或者两个连续层
–
最后一层的结点占据尽量左的位置
•
堆性质
–
为空
,
或者最小元素在根上
–
两棵子树也是堆
存储方式
•
最小堆的元素保存在
heap[1..hs]
内
–
根在
heap[1]
– K
的左儿子是
2k, K
的右儿子是
2k+1,
– K
的父亲是
[k/2]
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
14
14
删除最小值元素
•
三步法
–
直接删除根
–
用最后一个元素代替根上元素
–
向下调整
13
13
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
1
1
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
13
13
向下调整
•
首先选取当前结点
p
的较大儿子
.
如果比
p
大
,
调整
停止
,
否则交换
p
和儿子
,
继续调整
13
13
2
2
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
2
2
13
13
3
3
4
4
5
5
6
6
7
7
8
8
9
9
10
10
11
11
12
12
void swim(int p){
int q = p>>1, a = heap[p];
while(q && a<heap[q]){ heap[p]=heap[q]; p=q; q=p>>1; }
heap[p] = a;
}
插入元素和向上调整
•
插入元素是先添加到末尾
,
再
向上调整
•
向上调整
:
比较当前结点
p
和父亲
,
如果父亲比
p
小，停止
;
否则交换父亲和
p,
继续调整
void sink(int p){
int q=p<<1, a = heap[p];
while(q<=hs){
if(q<hs&&heap[q+1]<heap[q])q++;
if(heap[q]>=a) break;
heap[p]=heap[q]; p=q; q=p<<1;
}
heap[p] = a;
}
堆的建立
•
从
下往上逐层
向下调整
.
所有的叶子无需调整
,
因此从
hs/2
开始
.
可用数学归纳法证明循环变量
为
i
时
,
第
i+1, i+2, …n
均为最小堆的根
void insert(int a)
{ heap[++hs]=a; swim(hs); }
int getmin()
{ int r=heap[1]; heap[1]=heap=[hs--];
sink(1); return r; }
int decreaseKey(int p, int a )
{ heap[p]=a; swim(p); }
void build()
{ for(int i=hs/2;i>0;i--) sink(i); }
时间复杂度分析
•
向上调整
/
向下调整
–
每层是常数级别
,
共
logn
层
,
因此
O(logn)
•
插入
/
删除
–
只调用一次向上或向下调整
,
因此都是
O(logn)
•
建堆
–
高度为
h
的结点有
n/2
h+1
个
,
总时间为
lo
g
l o g
1
0 0
( )
2 2
n n
h h
h h
n h
O h O
n
⎢ ⎥
⎢ ⎥
⎣ ⎦
⎣ ⎦
+
= =
⎛ ⎞
⎡ ⎤
× =
⎜ ⎟
⎢ ⎥
⎜ ⎟
⎢ ⎥
⎝ ⎠
∑ ∑
例
1. k
路归并问题
•
把
k
个有序表合并成一个有序表
.
•
元素共有
n
个
.
分析
•
每个表的元素都是从左到右移入新表
•
把每个表的当前元素放入二叉堆中
,
每次删
除最小值并放入新表中
,
然后加入此序列的
下一个元素
•
每次操作需要
logk
时间
,
因此总共需要
nlogk
的时间
例
2.
序列和的前
n
小元素
•
给出两个长度为
n
的有序表
A
和
B,
在
A
和
B
中
各任取一个
,
可以得到
n
2
个和
.
求这些和最
小的
n
个
分析
•
可以把这些和看成
n
个有序表
:
– A[1]+B[1] <= A[1]+B[2] <= A[1]+B[3] <=…
– A[2]+B[1] <= A[2]+B[2] <= A[2]+B[3] <=…
– …
– A[n]+B[1] <= A[n]+B[2] <= A[n]+B[3] <=…
•
类似刚才的算法
,
每次
O(logn),
共取
n
次最
小元素
,
共
O(nlogn)
例
3.
轮廓线
•
每一个建筑物用一个三元组表示
(L, H, R),
表示
左边界
,
高度和右边界
•
轮廓线用
X, Y, X, Y…
这样的交替式表示
•
右图的轮廓线为
: (1, 11, 3, 13, 9, 0, 12, 7, 16,
3, 19, 18, 22, 3, 23, 13, 29, 0)
•
给
N
个建筑，求轮廓线
分析
•
算法一
:
用数组记录每一个元线段的高度
–
离散化
,
有
n
个元线段
–
每次插入可能影响
n
个元线段
, O(n),
共
O(n
2
)
–
从左到右扫描元线段高度
,
得轮廓线
•
算法二：每个建筑的左右边界为事件点
–
把事件点排序
,
从左到右扫描
–
维护建筑物集合
,
事件点为线段的插入删除
–
需要求最高建筑物
,
用堆
,
共
O(nlogn)
例
4.
丑数
•
素因子都在集合
{2, 3, 5, 7}
的数称为
ugly
number
•
求第
n
大的丑数
分析
•
初始：把
1
放入优先队列中
•
每次从优先队列中取出一个元素
k
，把
2k,
3k, 5k, 7k
放入优先队列中
•
从
2
开始算，取出的第
n
个元素就是第
n
大的
丑数
•
每取出一个数，插入
4
个数，因此任何堆里
的元素是
O(n)
的，时间复杂度为
O(nlogn)
例
5.
赛车
•
有
n
辆赛车从各不相同的地方以各种的速度
(
速度
0<v
i
<100)
开始往右行驶，不断有超车现象发生。
•
给出
n
辆赛车的描述（位置
x
i
，速度
v
i
），赛车已
按照位置排序（
x
1
<x
2
<…<x
n
）
•
输出超车总数以及按时间顺序的前
m
个超车事件
V
3
V
4
V
1
V
2
X
2
X
3
X
4
X
1
分析
•
事件个数
O(n
2
),
因此只能一个一个求
•
给定两辆车，超越时刻预先可算出
•
第一次
超车
可能
在哪些辆车之间？
–
维护所有车的前方相邻车和追上时刻
•
局部：此时刻不一定是该车下个超车时刻！
•
全局：所有时刻的
最小值
就是下次真实超车时刻
•
维护：超车以后有什么变化？
–
相对顺序变化
…
改变三个车的前方相邻车
–
重新算追上时刻，调整三个权
–
简单的处理方法：删除三个再插入三个
例
6.
可怜的奶牛
•
农夫
John
有
n
（
n
≤
100 000
）头奶牛，可是由于
它们产的奶太少，农夫对它们很不满意，决定每
天把产奶最少的一头做成牛肉干吃掉。但还是有
一点舍不得，
John
打算如果不止有一头奶牛产奶
最少，当天就大发慈悲，放过所有的牛。
•
由于
John
的奶牛产奶是周期性的，
John
在一开始
就能可以了解所有牛的最终命运，不过他的数学
很差，所以请你帮帮忙，算算最后有多少头奶牛
可以幸免于难。每头奶牛的产奶周期
T
i
可能不
同，但不会超过
10
。在每个周期中，奶牛每天产
奶量不超过
200
。
分析
•
如果采用最笨的方法，每次先求出每头牛的产奶
量，再求最小值，则每天的复杂度为
O(n)
，总复
杂度为
O(Tn)
，其中
T
是模拟的总天数。由于周期
不超过
10
，如果有的牛永远也不会被吃掉，那么
我们需要多模拟
2520
天（
1
，
2
，
3
，
…
，
10
的最
小公倍数）才能确定
•
周期同为
t
的奶牛在没有都被吃掉之前，每天的最
小产奶量也是以
t
为周期的。因此如果把周期相同
的奶牛合并起来，每天只需要比较
10
类奶牛中每
类牛的 最小产奶量就可以了，每天的复杂度为
O(k)
，其中
k
为最长周期
分析
•
假设周期为
6
的牛有
4
头，每次只需要比较
k
组牛的
“
代表
”
就可以了，每天模拟的时间复
杂度为
O
(
k
)
。
项
目
第
6
n
+ 1
天 第
6
n
+ 2
天 第
6
n
+ 3
天 第
6
n
+ 4
天 第
6
n
+ 5
天 第
6
n
+ 6
天
牛
1
2
5
3
5
7
4
牛
2
3
1
6
7
5
4
牛
3
5
3
3
5
3
9
牛
4
4
4
3
8
8
2
合 并 结 果
2
（ 牛
1
）
1
（ 牛
2
）
3
（ 多 ）
5
（ 多 ）
3
（ 牛
3
）
2
（ 牛
4
）
分析
•
只要周期为
6
的牛都不被吃掉，
这个表一直是有效
的
。但是在吃掉一头奶牛后，我们需要修改这个
表，使它仍然记录着每天的最小产奶量
–
方法一
:
重新计算，时间
O(h)
，其中
h
是该组的牛数
–
方法二
:
把
一个周期中每天
的最小产奶量组织成堆，每
次删除操作的复杂度是
O(klogh)
•
由于每头奶牛最多被吃掉一次，因此用在维护
“
最
小产奶量结构
”
的总复杂度不超过
O(nklogn)
。每
天复杂度为
O(k)
，总复杂度为
O(Tk+nklogn)
例
7.
黑匣子
•
我们使用黑匣子的一个简单模型。它能存
放一个整数序列和一个特别的变量
i
。在初
始时刻，黑匣子为空且
i
等于
0
。这个黑匣子
执行一序列的命令。有两类命令：
• AD D (
x
)
：把元素
x
放入黑匣子；
• GE T
：
i
增
1
的同时，输出黑匣子内所有整数
中第
i
小的数。牢记第
i
小的数是当黑匣子中
的元素以非降序排序后位于第
i
位的元素
例
7.
黑匣子
编 号
命 令
i
黑 匣 子 内 容
输 出
1
A D D ( 3 )
0
3
2
G E T
1
3
3
3
A D D ( 1 )
1
1, 3
4
G E T
2
1,
3
3
5
A D D ( - 4 )
2
- 4, 1, 3
6
A D D ( 2 )
2
- 4, 1, 2, 3
7
A D D ( 8 )
2
- 4, 1, 2, 3, 8
8
A D D ( - 1 0 0 0 )
2
- 1 0 0 0, - 4, 1, 2, 3, 8
9
G E T
3
- 1 0 0 0, - 4,
1
, 2, 3, 8
1
1 0
G E T
4
- 1 0 0 0, - 4, 1,
2
, 3, 8
2
1 1
A D D ( 2 )
4
- 1 0 0 0, - 4, 1, 2, 2, 3, 8
分析
•
降序堆
H
≥
和升序堆
H
≤
如图放置
• H
≥
根节点的值
H
≥
[1]
在堆
H
≥
中最大，
H
≤
根节点的值
H
≤
[1]
在堆
H
≤
中最小
,
并满足
– H
≥
[1]
≤
H
≤
[1]
– siz e [ H
≥
]=
i
• ADD(
x
):
比较
x
与
H
≥
[1]
，若
x
≥
H
≥
[1]
，则将
x
插入
H
≤
，否则从
H
≥
中
取出
H
≥
[1]
插入
H
≤
，再将
x
插入
H
≥
• GE T: H
≤
[1]
就是待获取的对象。输
出
H
≤
[1]
，同时从
H
≤
中取出
H
≤
[1]
插入
H
≥
，以维护条件
(2)
三、并查集
并查集
•
并查集维护一些不相交集合
S={S
1
, S
2
, …,
S
r
},
每个集合
S
r
都有一个特殊元素
rep[S
i
],
称为集合代表
.
并查集支持三种操作
–
Make-Set(x):
加入一个集合
{x}
到
S,
且
rep[{x}]
= x.
注意
, x
不能被包含在任何一个
S
i
中
,
因为
S
里任何两个集合应是不相交的
–
Union(x, y):
把
x
和
y
所在的两个不同集合合并
.
相当于从
S
中删除
S
x
和
S
y
并加入
S
x
US
y
–
Find-Set(x):
返回
x
所在集合
S
x
的代表
rep[S
x
]
链结构
•
每个集合用双向链表表示
, rep[S
i
]
在链表首部
•
Make-Set(x):
显然是
O(1)
的
•
Find-Set(x):
需要不断往左移
,
直到移动到首部
.
最坏情况下是
O(n)
的
•
Union(x, y):
把
S
y
接在
S
x
的尾部
,
代表仍是
rep[S
x
].
为了查找链表尾部
,
需要
O(n)
增强型链结构
•
给每个结点增加一个指回
rep
的指针
•
Make-Set(x):
仍为常数
•
Find-Set(x):
降为常数
(
直接读
rep)
•
Union(x, y):
变得复杂
:
需要把
S
y
里所有元素的
rep
指针设为
rep[Sx]!
增强型链结构的合并
•
可以把
x
合并到
y
中，也可以把
y
合并在
x
中
技巧
1:
小的合并到大的中
•
显然
,
把小的合并到大的中
,
这一次
Union
操
作会比较节省时间
,
更精确的分析
?
•
用
n, m, f
分别表示
Make-Set
的次数
,
总操作
次数和
Find-Set
的次数
,
则有
•
定理
:
所有
Union
的总时间为
O(nlogn)
•
推论
:
所有时间为
O(m + nlogn)
•
证明
:
单独考虑每个元素
x,
设所在集合为
S
x
,
则修改
rep[x]
时
, S
x
至少加倍
.
由于
S
x
不超过
n,
因此修改次数不超过
log
2
n,
总
nlogn
树结构
•
每个集合用一棵树表示
,
根为集合代表
树结构的合并
•
和链结构类似
,
小的合并到大的中
技巧
2:
路径压缩
•
查找结束后顺便把父亲
设置为根
,
相当于有选择
的设置
rep
指针而不像链
结构中强制更新
所有
rep
路径压缩的分析
•
设
w[x]
为
x
的子树的结点数
,
定义势能函数
•
Union(x
i
, x
j
)
增加势能
.
最多会让
w[rep[xi]]
增加
w[rep[xj]]<=n,
因此势能增加不超过
logn
•
Find-Set(x)
减少势能
.
把路径压缩看作是从根到
结点
x
的向下走过程
,
则除了第一次外的其他向下
走的步骤
p
Æ
c
会让
c
的子树从
p
的子树中移出
,
即
w[p]
减少
w[c],
而其他点的
w
值保持不变
路径压缩的分析
• Find-Set
除了第一次外的其他向下走的步骤
p
Æ
c
会让
c
的子树从
p
的子树中移出
–
情况一
: w[c]>=w[p]/2,
则势能将至少减少
1
–
情况二
: w[c]<w[p]/2,
这种情况最多出现
logn
次
,
因为
w[p]
最多进行
logn
次除
2
操作就会得到
1
• Union
操作积累起来的
mlogn
的势能将被
Find-Set
消耗
,
情况一最多消耗
mlogn
次
,
情
况二本身不超过
mlogn
次
,
因此
•
定理
:
Find-Set
的总时间为
O(mlogn)
路径压缩的分析
•
定理
:
如果所有
Union
发生在
Find-Set
之前
,
则所有操作的时间复杂度为
O(m)
•
证明
:
每次
Find-Set
将会让路径上除了根的
所有结点为根的儿子
.
所有结点只会有一次
改变，因此总时间复杂度为
O(m)
•
也就是说
–
只使用技巧
1(
启发式合并
): O(m+nlogn)
–
只使用技巧
2(
路径压缩
): O(mlogn)
•
同时使用呢
?
Ackermann
函数及其反函数
树结构的完整结论
•
定理
:
m
个操作的总时间复杂度为
( (
) )
O m
α
n
void makeset(int x){ rank[x] = 0; p[x]=x; }
int findset(int x){
int i, px = x;
while (px != p[px]) px = p[px];
while (x != px) { i = p[x]; p[x] = px; x = i; }
return px;
}
void unionset (int x , int y){
x = findset(x); y = findset(y);
if(rank[x] > rank[y]) p[y] = x;
else { p[x] = y; if(rank[x] == rank[y]) rank[y]++; }
}
例
1.
亲戚
•
或许你并不知道，你的某个朋友是你的亲戚。他
可能是你的曾祖父的外公的女婿的外甥女的表姐
的孙子。如果能得到完整的家谱，判断两个人是
否亲戚应该是可行的，但如果两个人的最近公共
祖先与他们像个好几代，使得家谱十分庞大，那
么检验亲戚关系实非人力所能及。在这种情况
下，最好的帮手就是计算机。
•
为了将问题简化，你将得到一些亲戚关系的信
息，如同
Marry
和
Tom
是亲戚，
Tom
和
Ben
是亲
戚，等等。从这些信息中，你可以推出
Marry
和
Ben
是亲戚。请写一个程序，对于我们的关于亲
戚关系的提问，以最快的速度给出答案。
分析
•
本质
:
是否在图的同一个连通块
•
问题
:
图太庞大
,
每次还需要遍历
•
解决
:
用并查集
例
2.
矩形
•
在平面上画了
N
个长方形，每个长方形的边平行
于坐标轴并且顶点坐标为整数。我们用以下方式
定义印版：
–
每个长方形是一个印版；
–
如果两个印版有公共的边或内部，那么它们组成新的
印版，否则这些印版是分离的
•
数出印版的个数
.
左图有两个，右图只有一个
分析
•
把矩形看作点，有公共边的矩形连边，问
题转化为求连通分量的个数
•
判断方法：
Y
(
X
2
,
Y
2
)
)
,
(
2
2
′
′
Y
X
(
X
1
,
Y
1
)
)
,
(
1
1
′
′
Y
X
X
例
3.
代码等式
•
由元素
0
和
1
组成的非空的序列称为一个二进制代
码。一个代码等式就是形如
x
1
x
2
..
x
l
=
y
1
y
2
..
y
r
,
这里
x
i
和
y
j
是二进制的数字（
0
或
1
）或者是一个变量（如
英语中的小写字母）
•
每一个变量都是一个有固定长度的二进制代码，
它可以在代码等式中取代变量的位置。我们称这
个长度为变量的长度
•
对于每一个给出的等式，计算一共有多少组解。
•
例
: a,b,c,d,e
的长度分别是
4,2,4,4,2,
则
1bad1 = acbe
有
16
组解
分析
•
长度为
k
的变量拆成
k
个长度为
1
的变量
•
每位得到一个等式
– 1=1
或者
0=0
：冗余等式
– 1=0
或者
0=1
：无解
– a=b
：
a
和
b
相等（
a
为变量
b
可以为常数）
•
相等关系用并查集处理，最后统计集合数
为
n
，答案为
2
n
。
例
4.
围墙
•
按顺序给出
M
个整点组成的线段，找到最小
的
k
，使得前
k
条线段构成了封闭图形。
（任意两条线段只可能在端点相交）
分析
•
将所有出现过的坐标用整数表示，初始时
候每个独立成树。读入连接
A
和
B
的线段
后，将
A
、
B
所在的树和并。如果
A
、
B
在同
一棵树，那么就出现了封闭图形（因为
x
个
点
x
条边的图必定出现圈）
•
把坐标转换成编号的步骤，可以通过对坐
标进行排序，再删除重复。
•
时间
: O(MlogM)
例
5.
可爱的猴子
•
树上挂着
n
只可爱的猴子（
n
≤
2*10
5
）。
•
猴子
1
的尾巴挂在树上
•
每只猴子有两只手，每只手可以抓住最多一只猴
子的尾巴，也可以不抓。猴子想抓谁一定抓得到
•
所有猴子都是悬空的，因此如果一旦脱离了树，
猴子会立刻掉到地上。
•
第
0
，
1
，
…
，
m
（
1
≤
m
≤
400 000
）秒中每一秒
都有某个猴子把他的某只手松开，因此常有猴子
掉在地上
•
请计算出每个猴子掉到地上的时间
分析
•
并查集？
• “
时光倒流
”
•
如何标记每只猴子的时间？
–
枚举并查集的元素
–
需要访问兄弟
/
儿子？
–
链表即可
–
不用指针
例
6.
奇数偶数
•
你的朋友写下一个由
0
和
1
组成的字符串，并
告诉你一些信息，即某个连续的子串中
1
的个
数是奇数还是偶数。你的目标是找到尽量小
的
i
，使得前
i+1
条不可能同时满足
–
例如，序列长度为
10
，信息条数为
5
– 5
条信息分别为
1 2 even
，
3 4 odd
，
5 6 even
，
1
6 even
，
7 10 odd
•
正确答案是
3
，因为存在序列
(0,0,1,0,1,1)
满
足前
3
条信息，但是不存在满足前
4
条的序列
分析
•
部分序列
–
可以从
s
的奇偶性恢复整个序列
– a b even
等价于
s[b], s[a-1]
同奇偶
– a b odd
等价于
s[b], s[a-1]
不同奇偶
•
一开始每个
s[i]
自成一集合
– a b even
Æ
合并
s[b], s[a-1]
– a b odd
Æ
???
•
矛盾的标志？
例
7.
团伙
•
如果两个认识
,
那么他们要么是朋友要么是
敌人
,
规则如下
–
朋友的朋友是朋友
–
敌人的敌人是敌人
•
给出一些人的关系
(
朋友、敌人
),
判断一共
最多可能有多少个团伙
例
8.
船
•
给一个
01
矩阵
,
黑色代
表船
.
右图有一个
29
吨
的
, 3
个
7
吨的
,
两个
4
吨
的和三个一吨的
.
•
输入行数
N(<30000)
和
每行的黑色格子
(
区间
数和每个区间
)
•
输出每种重量的个数
•
一共不超过
1000
个船
,
每个的重量不超过
1000
例
9.
离线最大值
•
设计一个集合
,
初始为空，每次可以插入一
个
1~n
的数
(1~n
各恰好被插入一次
),
也可以
删除最大值
,
要求
m
次操作的总时间尽量小
.
分析
•
在最后加入
n-m
次虚拟的
MAX
操作
,
并记第
i
个
MAX
操作为
M
i
,
记
M
1
之前的插入序列为
S
1,
M
i-1
(1<i<=m)
和
M
i
之间的插入序列为
S
i
•
如果
n
在
S
j
中被插入，则
M
j
的输出一定是
n.
然后删除
M
j
，即
把
S
j
合并到
S
j+1
中
，然后再
查找
n-1
所在的序列
S
k
，则
M
k
的输出为
n-
1…
如此下去，从
n
到
1
依次查找每个数所在
序列，就可以得到它后面的
MAX
操作的结
果
,
并把它和紧随其后的序列合并
例
10.
合并队列
•
初始时
n
个数
1~n
各在单独的一列中
,
需要执
行两个操作
– Move(i, j):
把
i
所在列接到
j
所在列的尾部
– Check(i, j):
询问
i
和
j
是否在同一列
,
如果是
,
输
出二者之间的元素个数
分析
•
每个数
i
的
p[i]
表示
i
和
p[i]
在同一队列
,
且
p[i]
是
i
之前的第
d[i]
个元素
•
对于队首
x,
有
p[x]=x,
附加变量
tot[x]
表示以
x
为首的队列一共有多少个元素
– Mo v e
需要进行两次查找和一次合并
– Ch e c k
需要两次查找
• FIN D:
修改
p[i]
时要修改
d[i]
• ME R G E:
可以启发式合并么
???
四、哈希表
哈希表
•
哈希表
(Hash table)
经常被用来做字典
(dictionary),
或称符号表
(symbol-table)
直接存取表
•
直接存取表
(Direct-access table)
的基本思
想是
:
如果
key
的范围为
0~m-1
而且所有
key
都不相同
,
那么可以设计一个数组
T[0..m-1],
让
T[k]
存放
key
为
k
的元素
,
否则为空
(NIL)
•
显然
,
所有操作都是
O(1)
的
•
问题
:
key
的范围可能很大
! 64
位整数有
18,446,744,073,709,551,616
种可能
,
而字
符串的种类将会更多
!
解决方案
:
哈希函数
哈希函数的选取
•
严格均匀分布的哈希函数很难寻找
,
但一般
说来有三种方法在实际使用中效果不错
–
取余法
:
取
h(k) = k mod m
–
乘积法
:
取
h(k) = (A*k mod 2
w
) rsh (w-r)
–
点积法
:
随机向量
a
和
k
的
m
进制向量做点积
•
实践中经常采用取余法
取余法
•
一般来说不要取
m=2
r
,
因为它只取决于
k
的后
r
位
•
一般取
m
为不太接近
2
或
10
的幂
乘积法
•
取
m=2
r
,
计算机字长为
w,
则
H(k) = (A*k mod 2
w
) rsh (w-r)
•
其中
rsh
表示右移位
, A
是满足
2
w-1
<A<2
w
的
奇数
.
注意
: A
不应该太接近于
2
w
.
由于乘法
并对
2
w
取余是很快的
(
自然就会丢弃高位
),
而算术右移也很快，因此函数计算开销小
冲突解决
•
不同的
key
映射到同一个数
,
称为冲突
(collision),
冲突的两个元素显然不可能放在
哈希表的同一个位置
•
通常有两种冲突解决方案
(resolving
collisions)
–
链方法
(chaining):
把
key
相同的串成链表
–
开放地址法
(open addressing):
自己的位置被
占了
,
就去占别人的
链地址法
• Ke y
相同的元素形成一个链表
链地址法的查找效率
•
链地址法的时间效率取决于
hash
函数的分布
.
我
们假设每个
k
将等可能的被映射到任意一个
slot,
不管其他
key
被映射到什么地方
•
设
n
为
key
的数目
, m
为不同的
slot
数
,
装载因子α
= n/m,
即每个
slot
平均的
key
数
,
则
• n=O(m)
时期望搜索时间是
O(1)
的
开放地址法
•
开发地址法只使用表内的空间
.
如果冲突产生
,
计
算出第二个可能的位置
,
如果那里也有其他元素
,
再看第三个可能的位置
…
即按一个
探测序列
查找
•
位置应该是
key
和探测的次数
(probe number)
的函
数
,
第
i
次探测位置为
slot = h(k,i)
•
每个
slot
都应能被探测到
,
因此每个
k
的探测序列
<h(k,0), h(k,1), h(k,2), …,h(k,m-1)>
•
都应是
{0,1,…,m-1}
的排列
•
注意
:
开放地址法不容易
删除
元素
开放地址法示例
探测方法
•
线性探测
:
•
虽然很简单
,
但是容易形成元素堆积
•
二次哈希
:
组合两个哈希函数
•
一般效果会好很多，但应保证
h
2
(k)
和
m
互素
,
比如
取
m
为
2
的幂而让
h
2
(k)
只产生奇数
开放地址法的查找效率
•
假设每个
key
等概率的把
m!
个排列中的任何
一个作为它的探测序列
,
则有
•
定理
:
装载因子α
<1
时
,
不成功查找的期望
探测次数为
1/ (1-
α)
•
证明
:
第
i
次探测到非空
slot
的概率为
(n-i)/(m-i) < n/m =
α
•
下面各种情况按概率加权计算期望
开放地址法的查找效率
•
各种情况按概率加权
,
得期望的探测次数为
查找效率比较
•
把开放地址法说通俗一点，就是
–
装载因子为常数时
,
期望查找次数为常数
–
一半装满时
,
期望查找次数为
1/(1-0.5)=2
–
装满
90%
时
,
期望查找次数为
1/(1-0.9)=10
•
装得比较满
(
尤其是
n>m)
时
,
使用链地址法
–
在哈希表里保存每个
key
的第一个元素
first[0..m-1],
–
在一个数组
data[1..n]
里装着所有元素和下一个
元素
next[1..n]
链地址法参考代码
•
在实际应用中，推荐使用链地址法
– first[i]
表示
哈希函数值为
i
的第一个数据下标
– ke y [i]
和
next[i]
表示
第
i
个
数据的
key
和下一个
int find(int k){
int h = hash(k);
int p = first[h];
while (p){ if(key[p] == k) return p; p = next [p]; }
return 0;
}
void insert(int x){
int h = hash(key[x]); next[x] = first[h]; first[h] = x;
}
文章来源地址https://www.toymoban.com/news/detail-687109.html
文章来源：https://www.toymoban.com/news/detail-687109.html
到了这里，关于c++基础数据结构的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
