提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  其他

当前栏目

rust 入门笔记：使用rust实现双向链表、二叉树

笔记 入门
2023-03-07 09:08:35 时间

这是 os summer of code 2020 项目每日记录的一部分：

github地址：https://github.com/yunwei37/os-summer-of-code-daily

其他一些 rust 的小练习：

笨办法系列

参考：Learn C The Hard Way 中文版

  • c32-list: 练习32：双向链表
  • c33-sort: 练习33：链表算法
  • c40-bst: 练习40：二叉搜索树
  • c42-stack-queue: 练习42：栈和队列
  • c38-hashal：练习38：哈希算法

Leecode题目用Rust实现

参考：https://leetcode-cn.com/problemset/all/

文件夹中包含：

  • README.md: 题目的出处和相关描述信息
  • solution.rs: rust语言实现代码
  • solution.c: c语言的实现代码

题目目录：

  • leetcode-best-time-to-buy-and-sell-stock - 121. 买卖股票的最佳时机
  • leetcode-binary-tree-inorder-traversal - 94. 二叉树的中序遍历
  • leetcode-game-of-life - 289. 生命游戏
  • leetcode-maximum-depth-of-binary-tree - 104. 二叉树的最大深度
  • leetcode-maximum-subarray - 53. 最大子序和
  • leetcode-remove-element - 27. 移除元素
  • leetcode-set-matrix-zeroes - 73. 矩阵置零
  • leetcode-valid-parentheses - 20. 有效的括号
  • leetcode-longest-consecutive-sequence - 128. 最长连续序列
  • leetcode-friend-circles - 547. 朋友圈

双向链表

注意，这里是很早的时候写的代码，实际上实现双向链表最好要使用 weak 来避免循环引用和内存泄漏问题。

数据结构定义：

use std::rc::Rc;
use std::cell::RefCell;
use std::clone::Clone;

#[derive(Debug)]
struct ListNode
{
    value :i32,
    next: Option<Rc<RefCell<ListNode>>>,
    prev: Option<Rc<RefCell<ListNode>>>
}

#[derive(Debug)]
pub struct List{
    count: i32,
    first: Option<Rc<RefCell<ListNode>>>,
    last: Option<Rc<RefCell<ListNode>>>
}

函数实现

impl ListNode {
    fn new(value:i32) -> Rc<RefCell<ListNode>>{
        let pointer = Rc::new(RefCell::new(ListNode {
            value,
            next: None,
            prev: None,
        }));
        Rc::clone(&pointer)
    }
}

impl List {

    pub fn new() -> List {
        let first = ListNode::new(0);
        let last = ListNode::new(0);
        first.borrow_mut().next = Some(Rc::clone(&last));
        last.borrow_mut().prev = Some(Rc::clone(&first));
        List {
            count: 0,
            first: Some(first),
            last: Some(last),
        }
    }

    pub fn list_count(&self) -> i32 {
        self.count
    }

    pub fn list_push(&mut self,value:i32){
        let node = ListNode::new(value);
        if let Some(ref l) = self.last {
            let mut n = node.borrow_mut();
            n.next = Some(Rc::clone(&l));
            if let Some(ref p) = l.borrow().prev {
                n.prev = Some(Rc::clone(&p));
                p.borrow_mut().next = Some(Rc::clone(&node));
            };
            l.borrow_mut().prev = Some(Rc::clone(&node));
        };
        self.count = self.count+1;
    }

    pub fn list_unshift(&mut self, value:i32){
        let node = ListNode::new(value);
        if let Some(ref f) = self.first {
            let mut n = node.borrow_mut();
            n.prev = Some(Rc::clone(&f));
            if let Some(ref p) = f.borrow().next {
                n.next = Some(Rc::clone(&p));
                p.borrow_mut().prev = Some(Rc::clone(&node));
            };
            f.borrow_mut().next = Some(Rc::clone(&node));
        };
        self.count = self.count+1;
    }

    pub fn list_shift(&mut self) -> i32 {
        if self.count == 0 {
            panic!("No Items for pop!");
        }
        let mut value = 0;
        let mut pointer_pnext = None;
        if let Some(ref f) = self.first {
            if let Some(ref p) = f.borrow().next {
                if let Some(ref pnext) = p.borrow().next {
                    pointer_pnext = Some(Rc::clone(&pnext));
                    pnext.borrow_mut().prev = Some(Rc::clone(&f));
                }
                value = p.borrow().value;
            };
            f.borrow_mut().next = pointer_pnext;
        };
        self.count = self.count-1;
        value
    }

    pub fn list_pop(&mut self) -> i32 {
        if self.count == 0 {
            panic!("No Items for pop!");
        }
        let mut value = 0;
        let mut pointer_pnext = None;
        if let Some(ref l) = self.last {
            if let Some(ref p) = l.borrow().prev {
                if let Some(ref pnext) = p.borrow().prev {
                    pointer_pnext = Some(Rc::clone(&pnext));
                    pnext.borrow_mut().next = Some(Rc::clone(&l));
                }
                value = p.borrow().value;
            };
            l.borrow_mut().prev = pointer_pnext;
        };
        self.count = self.count-1;
        value
    }

    pub fn list_first(&self) -> i32 {
        if self.count == 0 {
            panic!("No Items!");
        }
        let mut value = 0;
        if let Some(ref f) = self.first {
            if let Some(ref n) = f.borrow().next {
                value = n.borrow().value;
            };
        }
        value
    }

    pub fn list_last(&self) -> i32 {
        if self.count == 0 {
            panic!("No Items!");
        }
        let mut value = 0;
        if let Some(ref l) = self.last {
            if let Some(ref p) = l.borrow().prev {
                value = p.borrow().value;
            };
        }
        value
    }

    pub fn list_clear(&mut self){
        while self.count > 0 {
            self.list_pop();
        }
    }

}

测试

#[cfg(test)]
mod test {
    use super::*;
    #[test]
    fn test_push_pop(){
        let mut a = List::new();
        a.list_push(1);
        a.list_push(2);
        assert_eq!(a.list_pop(),2);
        assert_eq!(a.list_pop(),1);
    }

    #[test]
    fn test_shift(){
        let mut a = List::new();
        a.list_unshift(3);
        a.list_unshift(1);
        a.list_unshift(2);
        assert_eq!(a.list_shift(),2);
        assert_eq!(a.list_shift(),1);
    }

    #[test]
    fn test_shift_push(){
        let mut a = List::new();
        a.list_push(1);
        a.list_push(2);
        assert_eq!(a.list_shift(),1);
        assert_eq!(a.list_shift(),2);
    }

    #[test]
    fn test_clear(){
        let mut a = List::new();
        a.list_push(1);
        a.list_push(2);
        a.list_clear();
        assert_eq!(a.list_count(),0);
    }

    #[test]
    #[should_panic]
    fn test_pop_empty(){
        let mut a = List::new();
        a.list_push(1);
        a.list_pop();
        a.list_pop();
    }

    #[test]
    fn test_first_last(){
        let mut a = List::new();
        a.list_push(1);
        a.list_push(2);
        a.list_push(3);
        assert_eq!(a.list_first(),1);
        assert_eq!(a.list_last(),3);
    }
}

二叉树

数据结构定义：

use std::rc::Rc;
use std::mem::swap;
use std::cell::RefCell;

struct TreeNode {
    key:i32,
    value:String,
    vaild:bool,
    left: Option<Rc<RefCell<TreeNode>>>,
    right: Option<Rc<RefCell<TreeNode>>>
}

pub struct Bst {
    count:i32,
    root: Option<Rc<RefCell<TreeNode>>>
}

函数实现

impl TreeNode {
    fn new(key:i32,value:String) -> Rc<RefCell<TreeNode>>{
        Rc::new(RefCell::new(TreeNode {
            key,
            value,
            vaild:true,
            left: None,
            right: None,
        }))
    }
}



fn bst_search(node:&Rc<RefCell<TreeNode>>,key:i32) -> Option<String>{
    let mut result:Option<String> = None;
    //println!("search {} {}",key,node.borrow().key);
    if key == node.borrow().key {
        if node.borrow().vaild {
            return Some(node.borrow().value.clone());
        }else {
            return None;
        }
    }
    else if key < node.borrow().key{
        if let Some(ref n) = node.borrow().left {
            result = bst_search(n,key);
        }
    }
    else {
        if let Some(ref n) = node.borrow().right {
            result = bst_search(n,key);
        }
    }
    //println!("res {:?}",result);
    result
}

fn do_delete(node:&Rc<RefCell<TreeNode>>,key:i32){
    let mut node1 = node.borrow_mut();
    if key == node1.key {
        node1.vaild = false;
    }
    else if key < node1.key{
        if let Some(ref n) = node1.left {
            do_delete(n,key);
        }
    }
    else {
        if let Some(ref n) = node1.right {
            do_delete(n,key);
        }
    }
}


fn do_insert(node:&Rc<RefCell<TreeNode>>,key:i32,value:String) {
    let mut node1 = node.borrow_mut();
    //println!("doinsert {} {} {}",key,value,node1.key);
    if key < node1.key {
        match node1.left {
            None => {
                node1.left = Some(TreeNode::new(key,value));
            },
            Some(ref n) => {
                do_insert(n,key,value);
            }
        }
    }
    else if key > node1.key {
        match node1.right {
            None => {
                node1.right = Some(TreeNode::new(key,value));
            },
            Some(ref n) => {
                do_insert(n,key,value);
            }
        }
    }else{
        node1.vaild = true;
        node1.value = value;
    }
}

impl Bst {

    pub fn new() -> Bst {
        Bst {
            count:0,
            root:None
        }
    }

    pub fn insert(&mut self,key:i32,value:String){
        if let Some(_) = self.bst_get(key) {
            return;
        }
        match self.root {
            None => {
                self.root = Some(TreeNode::new(key,value));
            },
            Some(ref n) => {
                do_insert(&n,key,value);
            }
        }
        self.count = self.count+1;
    }

    pub fn bst_get(&self,key:i32) -> Option<String>{
        match self.root {
            None => None,
            Some(ref n) => bst_search(n,key)
        }
    }


    pub fn bst_delete(&self,key:i32){
        if let None = self.bst_get(key) {
            return;
        }
        match self.root {
            None => {},
            Some(ref n) => {
                do_delete(n,key)
            }
        };
    }

}

测试

#[cfg(test)]
mod test {
    use super::*;

    fn insert(t:&mut Bst){
        t.insert(5,String::from("Hello5"));
        t.insert(3,String::from("Hello3"));
        t.insert(6,String::from("Hello6"));
        t.insert(4,String::from("Hello4"));
        t.insert(1,String::from("Hello1"));
    }

    #[test]
    fn test_search(){
        let mut t = Bst::new();
        insert(&mut t);
        assert_eq!(t.bst_get(6),Some(String::from("Hello6")));
        assert_eq!(t.bst_get(1),Some(String::from("Hello1")));
        assert_eq!(t.bst_get(5),Some(String::from("Hello5")));
        assert_eq!(t.bst_get(3),Some(String::from("Hello3")));
        assert_eq!(t.bst_get(7),None);
    }

    #[test]
    fn test_insert_delete(){
        let mut t = Bst::new();
        insert(&mut t);
        t.bst_delete(4);
        assert_eq!(t.bst_get(4),None);
        t.insert(4,String::from("Hellokkk"));
        assert_eq!(t.bst_get(4),Some(String::from("Hellokkk")));
    }

}

相关文章