此crate 包含不同数据结构的实现

最小堆

use project::datastructures::heap::Heap;
use project::datastructures::heap::MinH;

let mut heap = MinH::default();

heap.insert(3);
heap.insert(1);
heap.insert(2);

assert_eq!(heap.remove(), Some(1));
assert_eq!(heap.remove(), Some(2));
assert_eq!(heap.remove(), Some(3));
assert_eq!(heap.remove(), None);

最大堆

use project::datastructures::heap::Heap;
use project::datastructures::heap::MaxH;

let mut heap = MaxH::default();

heap.insert(1);
heap.insert(2);
heap.insert(3);

assert_eq!(heap.remove(), Some(3));
assert_eq!(heap.remove(), Some(2));
assert_eq!(heap.remove(), Some(1));
assert_eq!(heap.remove(), None);

栈

use project::datastructures::linear::LLStack;
use project::datastructures::linear::LL;

let mut stack = LLStack::default();

stack.push(1);
stack.push(2);
stack.push(3);

assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(1));
assert_eq!(stack.pop(), None);

队列

use project::datastructures::linear::LLQueue;
use project::datastructures::linear::LL;

let mut stack = LLQueue::default();

stack.push(1);
stack.push(2);
stack.push(3);

assert_eq!(stack.pop(), Some(1));
assert_eq!(stack.pop(), Some(2));
assert_eq!(stack.pop(), Some(3));
assert_eq!(stack.pop(), None);

双链表

use project::datastructures::linear::DLL;
use project::datastructures::linear::LL;

let mut ll = DLL::default();

ll.insert_head(1);
ll.insert(2, 1);
ll.insert_sorted(3);

let mut iter = ll.iter();
assert_eq!(iter.next(), Some(&1)); // Get current, move cursor forward
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next_back(), Some(&3)); // Get current, move cursor back
assert_eq!(iter.next_back(), Some(&2)); // Get current, move cursor back
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);

单链表

use project::datastructures::linear::LL;
use project::datastructures::linear::SLL;

let mut ll = SLL::default();

ll.insert_head(1);
ll.insert(2, 1);
ll.insert_sorted(3);

let mut iter = ll.iter();

assert_eq!(iter.next(), Some(&1)); // Get current, move cursor forward
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), None);

循环双链表

use project::datastructures::linear::CDLL;
use project::datastructures::linear::LL;

let mut ll = CDLL::default();

ll.insert_head(1);
ll.insert(2, 1);
ll.insert_sorted(3);

let mut iter = ll.iter();

assert_eq!(iter.next(), Some(&1)); // Get current, move cursor forward
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next_back(), Some(&3)); // Get current, move cursor back
assert_eq!(iter.next_back(), Some(&2)); // Get current, move cursor back
assert_eq!(iter.next_back(), Some(&1)); // Get current, move cursor back
assert_eq!(iter.next_back(), Some(&3)); // Get current, move cursor back
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&1));

循环单链表

use project::datastructures::linear::CSLL;
use project::datastructures::linear::LL;

let mut ll = CSLL::default();

ll.insert_head(1);
ll.insert(2, 1);
ll.insert_sorted(3);

let mut iter = ll.iter();

assert_eq!(iter.next(), Some(&1)); // Get current, move cursor forward
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&1));
assert_eq!(iter.next(), Some(&2));
assert_eq!(iter.next(), Some(&3));
assert_eq!(iter.next(), Some(&1));

二叉搜索树

use project::datastructures::trees::BST;

let mut tree = BST::default();

tree.insert(3);
tree.insert(2);
tree.insert(4);
tree.insert(1);

//     3
//    / \
//   2   4
//  /
// 1
assert_eq!(tree.traverse_in_order(), [&1, &2, &3, &4]);
assert_eq!(tree.traverse_breadth_first(), [&3, &2, &4, &1]);

assert_eq!(tree.delete(&4), Some(4));

//     3
//    /
//   2
//  /
// 1
assert_eq!(tree.traverse_in_order(), [&1, &2, &3]);
assert_eq!(tree.traverse_breadth_first(), [&3, &2, &1]);
assert_eq!(tree.search(&0), None);
assert_eq!(tree.search(&2), Some(&2));

Adelson-Velsky和Landis (AVL) 树

use project::datastructures::trees::AVL;

let mut tree = AVL::default();

tree.insert(3);
tree.insert(2);
tree.insert(4);
tree.insert(1);

//     3
//    / \
//   2   4
//  /
// 1
assert_eq!(tree.traverse_in_order(), [&1, &2, &3, &4]);
assert_eq!(tree.traverse_breadth_first(), [&3, &2, &4, &1]);

assert_eq!(tree.delete(&4), Some(4));

//   2
//  / \
// 1   3
assert_eq!(tree.traverse_in_order(), [&1, &2, &3]);
assert_eq!(tree.traverse_breadth_first(), [&2, &1, &3]);
assert_eq!(tree.search(&0), None);
assert_eq!(tree.search(&2), Some(&2));