日本免费高清视频-国产福利视频导航-黄色在线播放国产-天天操天天操天天操天天操|www.shdianci.com

學無先后，達者為師

網站首頁 編程語言 正文

如何使用rust實現簡單的單鏈表_相關技巧

作者：架構小白 ? 更新時間： 2022-05-21 編程語言

前言

作為初學者，在掌握了rust的基本語法和所有權機制，嘗試寫一下常見數據結構和算法，目標是為了更好的理解rust的所有權機制。 受限于個人目前對rust仍處于入門階段，因此本文代碼實現不一定是最合適的，甚至可能存在問題。

今天的目標是用rust實現一個簡單的單鏈表LinkedList，同時為此鏈表提供從頭部插入元素(頭插法)、翻轉鏈表、打印鏈表的功能。

1.鏈表節點的定義

實現鏈表，首先是實現鏈表的節點，根據其他編程語言的經驗，于是用rust首先寫出了下面的鏈表節點結構體定義:

代碼片段1:

struct Node {
    data: T,
    next: Option>, // recursive type `Node` has infinite size
}

在代碼片段1中，定義一個Node結構體，data字段使用了泛型類型T用于鏈表節點的數據。 next使用了Option枚舉，即如果該節點沒有下一個節點時，next是可空的，在rust中沒有其他編程語言中的空值(null, nil)，而是提供了Option的解決方案，如果該鏈表節點的下個節點為空，則其next取值為Option::None。

遺憾的是代碼片段1是無法編譯通過的，報了recursive type ``Node`` has infinite size的編譯錯誤。回顧Rust內存管理的基礎知識，Rust需要在編譯時知道一個類型占用多少空間，Node結構體內部嵌套了它自己，這樣在編譯時就無法確認其占用空間大小了。 在Rust中當有一個在編譯時未知大小的類型，而又想要在需要確切大小的上下文中使用這個類型值的時候，可以使用智能指針Box。將next字段的類型修改為Option>>，這樣嵌套的類型為Box，嵌套的Node將會被分配到堆上，next字段在棧上存儲的只是智能指針Box的數據(ptr, meta)，這樣在編譯時就能確定Node類型的大小了。將代碼片段1的修改如下:

代碼片段2:

struct Node {
    data: T,
    next: Option>>,
}

修改完成后，可以編譯通過了。根據next: Option>>，每個鏈表節點Node將擁有它下一個節點Node的所有權。

2.鏈表的定義

定義完鏈表之后，下一步再定義一個結構體LinkedList用來表示鏈表，將會封裝一些鏈表的基本操作。 結構體中只需方一個鏈表頭節點的字段head，類型為Option>>。

代碼片段3:

/// 單鏈表節點
#[derive(Debug)]
struct Node {
    data: T,
    next: Option>>,
}

/// 單鏈表
#[derive(Debug)]
struct LinkedList {
    head: Option>>,
}

為了便于使用，再給Node和LinkedList這兩個結構體各添加一下關聯函數new。

代碼片段4:

impl Node {
? ? fn new(data: T) -> Self {
? ? ? ? Self { data: data, next: None }
? ? }
}

impl LinkedList {
? ? fn new() -> Self {
? ? ? ? Self { head: None }
? ? }
}

Node的new函數用來使用給定的data數據創建一個孤零零的(沒有下一個節點的)節點。

LinkedList的new函數用來創建一個空鏈表。

3.實現從鏈表頭部插入節點的prepend方法

前面已經完成了鏈表和鏈表節點的定義，下面我們為鏈表實現了prepend方法，這個方法將采用頭插法的方式向鏈表中添加節點。

代碼片段5:

impl LinkedList {
? ? fn new() -> Self {
? ? ? ? Self { head: None }
? ? }

? ? /// 在鏈表頭部插入節點(頭插法push front)
? ? fn prepend(&mut self, data: T) -> &mut Self {
? ? ? ? // 從傳入數據構建要插入的節點
? ? ? ? let mut new_node = Box::new(Node::new(data));
? ? ? ? match self.head {
? ? ? ? ? ? // 當前鏈表為空時, 插入的節點直接作為頭節點
? ? ? ? ? ? None => self.head = Some(new_node),
? ? ? ? ? ? // 當前鏈表非空時, 插入的節點作為新的頭節點插入到原來的頭結點前面
? ? ? ? ? ? Some(_) => {
? ? ? ? ? ? ? ? // 調用Option的take方法取出Option中的頭結點(take的內部實現是mem::replace可避免內存拷貝), 作為新插入節點的下一個節點
? ? ? ? ? ? ? ? new_node.next = self.head.take();
? ? ? ? ? ? ? ? // 將新插入的節點作為鏈表的頭節點
? ? ? ? ? ? ? ? self.head = Some(new_node);
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? self
? ? }
}

fn main() {
? ? let mut ll = LinkedList::new();
? ? ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
? ? print!("{ll:?}"); // LinkedList { head: Some(Node { data: 1, next: Some(Node { data: 2, next: Some(Node { data: 3, next: Some(Node { data: 4, next: Some(Node { data: 5, next: None }) }) }) }) }) }
}

4.為鏈表實現Display trait定制鏈表的打印顯示

前面我們實現了鏈表頭部插入節點的prepend方法，并在main函數中構建了一個鏈表，以Debug的形式打印出了鏈表的信息。

為了使打印信息更好看，我們決定為LinkedList實現Display trait，使鏈表打印的格式類似為1 -> 2 -> 3 -> 4 -> 5 -> None。

代碼片段6:

use std::fmt::Display;

......

impl Display for LinkedList {
? ? fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
? ? ? ? if self.head.is_none() {
? ? ? ? ? ? // 如果鏈表為空, 只打印None
? ? ? ? ? ? write!(f, "None\n")?;
? ? ? ? } else {
? ? ? ? ? ? // 下面將遍歷鏈表, 因為只是打印, 能獲取鏈表各個節點的數據就行, 所以不需要獲取所有權
? ? ? ? ? ? let mut next = self.head.as_ref();
? ? ? ? ? ? while let Some(node) = next {
? ? ? ? ? ? ? ? write!(f, "{} -> ", node.data)?;
? ? ? ? ? ? ? ? next = node.next.as_ref();
? ? ? ? ? ? }
? ? ? ? ? ? write!(f, "None\n")?;
? ? ? ? }
? ? ? ? Ok(())
? ? }
}

fn main() {
? ? let mut ll = LinkedList::new();
? ? ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
? ? print!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
}

5.為鏈表實現翻轉鏈表功能的reverse方法

代碼片段7:

impl LinkedList {
? ? ......

? ? /// 翻轉鏈表
? ? fn reverse(&mut self) {
? ? ? ? let mut prev = None; // 記錄遍歷鏈表時的前一個節點
? ? ? ? while let Some(mut node) = self.head.take() {
? ? ? ? ? ? self.head = node.next;
? ? ? ? ? ? node.next = prev;
? ? ? ? ? ? prev = Some(node);
? ? ? ? }
? ? ? ? self.head = prev;
? ? }
}

fn main() {
? ? let mut ll = LinkedList::new();
? ? ll.prepend(5).prepend(4).prepend(3).prepend(2).prepend(1);
? ? println!("{ll}"); // 1 -> 2 -> 3 -> 4 -> 5 -> None
? ? ll.reverse(); // 5 -> 4 -> 3 -> 2 -> 1 -> None
? ? println!("{ll}");
}

注意事項

只有一個可變引用

在C里面，如果要在鏈表的頭部插入元素，可以這樣寫

Node* new_node = create_new_node(v);
new_node->next = head;
head = new_node;

但是在Rust里面你不能這樣做。

在Rust中，常見的指針是Box，和其他對象一樣，Box對象同一時刻只能有一個可變引用，而在上面的插入過程中，第2行，有兩個指針指向同一個頭結點，這個在Rust中是有問題的。

那在Rust里面，要實現在頭部插入的功能，首先得把指針從head里面拿出來，然后再放到新的結點里面去，而不是直接復制，這里需要用到Option中的take方法，即把Option中的東西取出來。

總結

原文鏈接：https://blog.frognew.com/2022/03/rust-algorithm-linked-list.html

欄目分類
最近更新