Rust 鏈表

       思考了很久，決定還是寫下來，寫一個系列的數據結構 Rust 實現。今天先開始鏈表。鏈表我們在學數據結構時已經知道，它有一個特性就是先進先出。

我們先定義節點結構：

type Link = Option<Rc<RefCell<Node>>>;
#[derive(Clone)]
struct Node {
    pub value: String,
    next: Link,
}

節點的 next 指向下一個節點，下一個節點可能爲空，也可能爲一個節點。所以這裏使用 Option 進行包裝，但是爲啥必須使用 Rc，首先，Rc 是智能指針，它爲引用計數的縮寫，引用計數意味着記錄一個值引用的數量來知曉這個值是否仍在被使用。如果某個值有零個引用，就代表沒有任何有效引用並可以被清理。Rc 用於當我們希望在堆上分配一些內存供程序的多個部分讀取，而且無法在編譯時確定程序的哪一部分會最後結束使用它的時候。如果確實知道哪部分是最後一個結束使用的話，就可以令其成爲數據的所有者，正常的所有權規則就可以在編譯時生效。RefCell 允許在運行時執行不可變或可變借用檢查。它們只能在單線程中使用。

我們定義鏈表的結構：

struct LinkList {
    head: Link,
    tail: Link,
    pub length: u64,
}

head，和 tail 都指向一個節點。從 tail 中添加一個新節點，從 head 中獲取一個節點。

我們實現節點和鏈表。先實現節點，創建一個新節點：

impl Node {
// 這裏可以確定的創建一個節點，所以直接使用這個類型，而不加Option
    fn new(value: String) -> Rc<RefCell<Node>> {
        Rc::new(RefCell::new(Node {
            value: value,
            next: None,// 可以爲空的
        }))
    }
}

然後實現鏈表：

impl LinkList {
// 創建一個空的鏈表
    pub fn new_empty()->LinkList{
        LinkList { head: None, tail: None, length: 0 }
    }
// 從尾部插入一個節點
    pub fn append(&mut self,value:String){
        let new = Node::new(value); // 創建一個新節點
        // 查看尾部是否有節點，有節點則將該節點指向新的節點，
        // 沒有節點代表是第一個節點，頭部也要指向該節點。
        match self.tail.take(){
            Some(old)=>old.borrow_mut().next=Some(new.clone()),
            None=>self.head=Some(new.clone())
        };
        // 將節點的數量加1
        self.length+=1;
        // 將尾部也指向這個新的節點
        self.tail=Some(new);
    }
// 從頭部取出一個節點
    pub fn pop(&mut self)->Option<String>{
    // 從頭部取出一個節點，使用閉包函數
    // 將頭部的數據獲取後，檢查該節點的下一個節點是否爲空，
    // 如果爲空，代表最後一個節點，tail也需要釋放引用。
    // 如果不爲空，則將頭部的引用指向這個節點。
    // 然後將頭部的節點數據返回。
        self.head.take().map(|head|{
            if let Some(next)=head.borrow_mut().next.take(){
                self.head = Some(next);
            }else{
                self.tail.take();
            }
            self.length -=1;
            Rc::try_unwrap(head).ok().expect("Something is terribly wrong").into_inner().value
        })
    }
}

這裏的 take() 方法多說兩句，take 方法將 Option 中的值取出，留下 None，取出來的值如果使用必須爲 mut 類型。

鏈表的使用方法：

fn main() {
// 創建一個空鏈表，然後插入數據，再彈出數據。
    let mut list = LinkList::new_empty();
    list.append(String::from("A"));
    list.append(String::from("B"));
    list.append(String::from("C"));
    list.append(String::from("D"));
    let value = list.pop();
    println!("the value is {:?}",value);
    let value = list.pop();
    println!("the value is {:?}",value);
    let value = list.pop();
    println!("the value is {:?}",value);
    let value = list.pop();
    println!("the value is {:?}",value);
    let value = list.pop();
    println!("the value is {:?}",value);
    let value = list.pop();
    println!("the value is {:?}",value);
}

很簡單的鏈表實現，如果你有好的想法和建議，歡迎留言！

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/B1NwYCpw1sPMkozW-kTCjA

猜你喜歡