数据结构与算法的Rust实现: my-algo-rs
该项目的目的是在Rust的语境下探讨数据结构与算法的最佳实践,对比我们的实现与标准实现的异同,有助于更好地理解为何它们会被实现成这样. 项目的推进动力来源于相关的数据结构与算法方面的杂题,并无明确的路线.
如何研究本项目
克隆本仓库:
git clone https://github.com/Nouzan/my-algo-rs.git
cd my-algo-rs
1. 探索文档
- 通过
cargo doc
生成文档 - 在浏览器打开
my-algo-rs/target/doc/my-algo/index.html
. - 开始你的旅程.
2. 直接阅读源码
从examples
和test
入手了解本项目.
3. 在你自己的项目中进行尝试
创建新的二进制项目:
cargo new your-project
在cargo.toml
中添加对该项目的依赖:
[dependencies]
my-algo = { git = "https://github.com/Nouzan/my-algo-rs.git" }
在项目中引入一些结构,并尝试使用它们:
use my_algo::{
ch2::{IndexError, List, ListExt},
vec::MyVec,
};
fn main() -> Result<(), IndexError> {
let mut list = MyVec::new();
for i in 0..10 {
list.insert(list.len(), i)?;
}
list.shift(5)?;
for i in 0..list.len() {
println!("{}", list.get(i)?);
}
Ok(())
}
内容
vec
)
向量表(- 参考The Rustonomicon实现的向量:
vec::MyVec
.
ch1
)
幂与斐波那契数列(- 任何幺半群均可使用的幂算法:
ch1::power
. - 一些斐波那契数列算法:
ch1::{fib, fib_linear, fib_recurrence}
, 其中ch1::fib
是基于幂算法实现的, 复杂度为O(lgn)
.
ch2
)
线性表(- 顺序表, 偏等顺序表, 偏序顺序表上的一些算法:
ch2::{List, ListExt, PartialEqListExt, PartialOrdListExt}
, 为vec::MyVec
和Vec
实现了上述Trait
. - 整数顺序表上的一些算法:
ch2::ISizeListExt
. - 不带头结点的单链表和带头结点的单链表的实现及其上的一些算法:
ch2::linked_list::{sll::LinkedList, shll::LinkedList}
. - 不带头结点的循环双链表的实现及其上的一些算法:
ch2::linked_list::cdll::LinkedList
. - 单链表特质:
ch2::linked_list::{SinglyLinkedList, SinglyLinkedListExt}
.
ch3
)
栈与队列(- 栈特质:
ch3::{Stack, StackExt}
. - 队列特质:
ch3::{Queue, QueueExt}
. - 共享栈、双栈:
ch3::{SharedStack, DoubleStack}
, 并用共享栈、双栈实现Queue
(TODO: 有一些情况下判满算法会出错, 后面发一个issue描述一下情况). - 循环队列:
ch3::CircularQueue
.
ch4
)
树(- 基本树特质:
BinTree, BinTreeMut, BinTreeCursor, BinTreeCursorMut
- 可向父母移动的树特质:
MoveParentBinTree, MoveParentBinTreeMut, MoveParentCursor, MoveParentCursorMut
- 向量二叉树(没有处理空间释放问题,空间性能较差):
vec_binary_tree::VecBinaryTree
- 链式二叉树(带哨兵根结点):
linked_binary_tree::LinkedBinaryTree
- 带父母指针的链式二叉树:
doubly_linked_binary_tree::DoublyLinkedBinaryTree
- 完全二叉堆:
compelete_heap::CompeleteMaxHeap
- 左式堆:
left_heap::LeftHeap
- 非平衡二叉查找树(BST):
bst::TreeMap<Tree>
(对树generic),bst2::TreeMap
(基于不带哨兵根的链式树) - AVL树:
avlt::AVLTreeMap<Tree>
(要求Tree: MoveParentBinTreeMut
) - 伸展树:
st::SplayTree<Tree>
(要求Tree: MoveParentBinTreeMut
) - B树:
bt::BTreeMap
(有待将VecDeque<T>
优化为[T]
) - 红黑树:
rbt::RedBackTreeMap<Tree>
(要求Tree: MoveParentBinTreeMut
) - 左倾红黑树:
llrbt::RedBackTreeMap
(基于bst2::TreeMap
)