数据结构之跳表

rust 实现阅读版本v1

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
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
use std::cell::RefCell;
use std::rc::Rc;

type Rcc<T> = Rc<RefCell<T>>;
pub fn rcc<T>(t: T) -> Rcc<T> {
Rc::new(RefCell::new(t))
}

#[derive(Debug)]
pub struct SkipNode<T: PartialOrd> {
right: Option<Rcc<SkipNode<T>>>,
down: Option<Rcc<SkipNode<T>>>,
data: Rcc<T>,
}

impl<T: PartialOrd> SkipNode<T> {
pub fn new(t: T) -> Self {
SkipNode {
right: None,
down: None,
data: rcc(t),
}
}

pub fn insert(&mut self, dt: T) -> Option<Rcc<SkipNode<T>>> {
// 如果比右边大,则继续查找右边
if let Some(ref mut rt) = self.right {
if dt > *rt.borrow().data.borrow() {
return rt.borrow_mut().insert(dt);
}
}

// 如果没有比右边大的了,则往下层找
if let Some(ref dw) = self.down {
return match dw.borrow_mut().insert(dt) {
Some(child) => match rand::random::<bool>() {
true => {
let dt = child.borrow().data.clone(); // pointer copy
let nn = SkipNode {
right: self.right.take(),
data: dt,
down: Some(child),
};
let res = rcc(nn);
self.right = Some(res.clone());
Some(res)
}
false => None,
},
None => None,
};
}

// 可能在最底层节点
let mut nn = SkipNode::new(dt);
nn.right = self.right.take();
let res = rcc(nn);
self.right = Some(res.clone());
Some(res)
}
}

fn main() {
let mut s = SkipNode::new(4);
s.insert(4);
s.insert(6);
s.insert(77);
s.insert(84);
s.insert(23);
s.insert(1);
println!("{:?}", s);
println!("Hello, world!");
}
  • Copyrights © 2019-2024 Klusfq
  • Visitors: | Views: