用法

此包包含 Rust 中最常用的数据结构和算法。

要使用此包，只需将以下字符串添加到您的 Cargo.toml

flex-algo = "0.7.0"

版本号遵循 semver 规范。

然后，如以下示例所示，在 Rust 源代码中使用数据结构。

请注意，如果您需要 serde 支持，应使用 --features serde 编译。

文档

请在此处阅读 API 文档

Dijkstra 算法

此包实现了一个 Dijkstra 算法，通过给定的图计算最短路径。

这受到了 JavaScript 实现的启发，请参考 此处

示例

use flex_algo::Dijkstra;

fn main() {
  let times = vec![
      (1, 2, 9), (1, 4, 2), (2, 5, 1), (4, 2, 4), (4, 5, 6), (3, 2, 3), (5, 3, 7), (3, 1, 5)
  ];
  let dijkstra = Dijkstra::new(5, times);
  let (max, path) =  dijkstra.shortest_path(1).unwrap();
  println!("shortest path: {:?}", path);
  assert_eq!(max, 14);
}

优先队列

此包实现了一个可以更改对象优先级的优先队列。优先级存储在 Vec 中，队列实现为索引的堆。

这受到了 JavaScript 实现的启发，请参考 此处

示例

use flex_algo::PriorityQueue;

fn main() {
  // priorities
  let distances = [1, 6, 14, 2, 7];
  // queue
  let mut pq = PriorityQueue::new(|a: &usize,b: &usize| distances[*a] < distances[*b]);
  assert_eq!(pq.is_empty(), true);
  pq.push(0);
  pq.push(1);
  pq.push(2);
  pq.push(3);
  pq.push(4);
  let value = pq.pop().unwrap();
  println!("pop priority queue(closure): {:?}", value);
}

图

此包实现了一个图数据结构。

这受到了 JavaScript 实现的启发，请参考 BFS 拓扑排序 DFS

示例

use flex_algo::Graph;

fn main() {
    let mut graph = Graph::new(6, vec![(1, 0), (2, 1), (2, 5), (0, 3), (4, 3), (3, 5), (4, 5)]);
    println!("graph: {:?}", graph);
    assert_eq!(graph.is_acyclic_bfs(), true);
    assert_eq!(graph.is_acyclic_top_sort(), true);
}

二叉树

此包实现了二叉树数据结构。

这受到了 JavaScript 和 Rust 实现的启发：[JS](https://replit.com/@ZhangMYihua/Maximum-depth#main.js, https://replit.com/@ZhangMYihua/Level-Order, https://replit.com/@ZhangMYihua/Binary-tree-right-side-view-DFS#index.js, https://replit.com/@ZhangMYihua/Number-of-Nodes-in-Complete-Binary-Tree#index.js) Rust)

创建二叉树

use flex_algo::BinaryTree;

fn main() {
    let mut tree = BinaryTree::new();
    let v = vec![Some(1), Some(2), Some(3), None, None, Some(4), Some(5), Some(6)];
    tree.insert(&v);

    // print in preorder
    tree.print_preorder(0);

    // get the depth of the tree
    let depth = tree.depth();
    println!("depth: {}", depth);
    assert_eq!(depth, 4);

    // get the level order of the tree
    let level_order = tree.level_order();
    println!("level order: {:?}", level_order);
    assert_eq!(level_order, vec![vec![1], vec![2, 3], vec![4, 5], vec![6]].to_vec());

    // get the right side view
    let mut res: Vec<i32> = Vec::new();
    tree.right_side_view(0, &mut res);
    println!("right side view: {:?}", res);
    assert_eq!(res, vec![1, 3, 5, 6]);

    // get the left side view
    let mut res: Vec<i32> = Vec::new();
    tree.left_side_view(0, &mut res);
    println!("left side view: {:?}", res);
    assert_eq!(res, vec![1, 2, 4, 6]);
}

二叉搜索树（BST）

此软件包实现了二叉搜索树数据结构。

本实现受到以下JavaScript和Rust实现的启发： JS Rust

创建二叉树

use flex_algo::BST;

fn main() {
    let mut bst = BST::new();
    bst.insert(3);
    bst.insert(2);
    bst.insert(1);
    
    let is_valid = bst.is_valid(i32::MIN, i32::MAX);
    assert_eq!(is_valid, true);

    bst.print_preorder(0);

    let none = bst.search(5);
    assert_eq!(none, None);

    let found = bst.search(2);
    assert_eq!(found, Some(2));
}