如何使用rust實現(xiàn)簡單的單鏈表
前言
作為初學者，在掌握了rust的基本語法和所有權(quán)機制，嘗試寫一下常見數(shù)據(jù)結(jié)構(gòu)和算法，目標是為了更好的理解rust的所有權(quán)機制。 受限于個人目前對rust仍處于入門階段，因此本文代碼實現(xiàn)不一定是最合適的，甚至可能存在問題。
今天的目標是用rust實現(xiàn)一個簡單的單鏈表LinkedList，同時為此鏈表提供從頭部插入元素(頭插法)、翻轉(zhuǎn)鏈表、打印鏈表的功能。
1.鏈表節(jié)點的定義
實現(xiàn)鏈表，首先是實現(xiàn)鏈表的節(jié)點，根據(jù)其他編程語言的經(jīng)驗，于是用rust首先寫出了下面的鏈表節(jié)點結(jié)構(gòu)體定義:
代碼片段1:
struct Node<T> {
data: T,
next: Option<Node<T>>, // recursive type `Node` has infinite size
}在代碼片段1中，定義一個Node結(jié)構(gòu)體，data字段使用了泛型類型T用于鏈表節(jié)點的數(shù)據(jù)。 next使用了Option枚舉，即如果該節(jié)點沒有下一個節(jié)點時，next是可空的，在rust中沒有其他編程語言中的空值(null, nil)，而是提供了Option的解決方案，如果該鏈表節(jié)點的下個節(jié)點為空，則其next取值為Option::None。
遺憾的是代碼片段1是無法編譯通過的，報了recursive type ``Node`` has infinite size的編譯錯誤?；仡橰ust內(nèi)存管理的基礎知識，Rust需要在編譯時知道一個類型占用多少空間，Node結(jié)構(gòu)體內(nèi)部嵌套了它自己，這樣在編譯時就無法確認其占用空間大小了。 在Rust中當有一個在編譯時未知大小的類型，而又想要在需要確切大小的上下文中使用這個類型值的時候，可以使用智能指針Box。將next字段的類型修改為Option<Box<Node<T>>>，這樣嵌套的類型為Box，嵌套的Node將會被分配到堆上，next字段在棧上存儲的只是智能指針Box的數(shù)據(jù)(ptr, meta)，這樣在編譯時就能確定Node類型的大小了。將代碼片段1的修改如下:
代碼片段2:
struct Node<T> {
data: T,
next: Option<Box<Node<T>>>,
}
修改完成后，可以編譯通過了。根據(jù)next: Option<Box<Node<T>>>，每個鏈表節(jié)點Node將擁有它下一個節(jié)點Node的所有權(quán)。
2.鏈表的定義
定義完鏈表之后，下一步再定義一個結(jié)構(gòu)體LinkedList用來表示鏈表，將會封裝一些鏈表的基本操作。 結(jié)構(gòu)體中只需方一個鏈表頭節(jié)點的字段head，類型為Option<Box<Node<T>>>。
代碼片段3:
/// 單鏈表節(jié)點
#[derive(Debug)]
struct Node<T> {
data: T,
next: Option<Box<Node<T>>>,
}
/// 單鏈表
#[derive(Debug)]
struct LinkedList<T> {
head: Option<Box<Node<T>>>,
}為了便于使用，再給Node和LinkedList這兩個結(jié)構(gòu)體各添加一下關(guān)聯(lián)函數(shù)new。
代碼片段4:
impl<T> Node<T> {
? ? fn new(data: T) -> Self {
? ? ? ? Self { data: data, next: None }
? ? }
}
impl<T> LinkedList<T> {
? ? fn new() -> Self {
? ? ? ? Self { head: None }
? ? }
}Node的new函數(shù)用來使用給定的data數(shù)據(jù)創(chuàng)建一個孤零零的(沒有下一個節(jié)點的)節(jié)點。
LinkedList的new函數(shù)用來創(chuàng)建一個空鏈表。
3.實現(xiàn)從鏈表頭部插入節(jié)點的prepend方法
前面已經(jīng)完成了鏈表和鏈表節(jié)點的定義，下面我們?yōu)殒湵韺崿F(xiàn)了prepend方法，這個方法將采用頭插法的方式向鏈表中添加節(jié)點。
代碼片段5:
impl<T> LinkedList<T> {
? ? fn new() -> Self {
? ? ? ? Self { head: None }
? ? }
? ? /// 在鏈表頭部插入節(jié)點(頭插法push front)
? ? fn prepend(&mut self, data: T) -> &mut Self {
? ? ? ? // 從傳入數(shù)據(jù)構(gòu)建要插入的節(jié)點
? ? ? ? let mut new_node = Box::new(Node::new(data));
? ? ? ? match self.head {
? ? ? ? ? ? // 當前鏈表為空時, 插入的節(jié)點直接作為頭節(jié)點
? ? ? ? ? ? None => self.head = Some(new_node),
? ? ? ? ? ? // 當前鏈表非空時, 插入的節(jié)點作為新的頭節(jié)點插入到原來的頭結(jié)點前面
? ? ? ? ? ? Some(_) => {
? ? ? ? ? ? ? ? // 調(diào)用Option的take方法取出Option中的頭結(jié)點(take的內(nèi)部實現(xiàn)是mem::replace可避免內(nèi)存拷貝), 作為新插入節(jié)點的下一個節(jié)點
? ? ? ? ? ? ? ? new_node.next = self.head.take();
? ? ? ? ? ? ? ? // 將新插入的節(jié)點作為鏈表的頭節(jié)點
? ? ? ? ? ? ? ? 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.為鏈表實現(xiàn)Display trait定制鏈表的打印顯示
前面我們實現(xiàn)了鏈表頭部插入節(jié)點的prepend方法，并在main函數(shù)中構(gòu)建了一個鏈表，以Debug的形式打印出了鏈表的信息。
為了使打印信息更好看，我們決定為LinkedList實現(xiàn)Display trait，使鏈表打印的格式類似為1 -> 2 -> 3 -> 4 -> 5 -> None。
代碼片段6:
use std::fmt::Display;
......
impl<T: Display> Display for LinkedList<T> {
? ? fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
? ? ? ? if self.head.is_none() {
? ? ? ? ? ? // 如果鏈表為空, 只打印None
? ? ? ? ? ? write!(f, "None\n")?;
? ? ? ? } else {
? ? ? ? ? ? // 下面將遍歷鏈表, 因為只是打印, 能獲取鏈表各個節(jié)點的數(shù)據(jù)就行, 所以不需要獲取所有權(quán)
? ? ? ? ? ? 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.為鏈表實現(xiàn)翻轉(zhuǎn)鏈表功能的reverse方法
代碼片段7:
impl<T> LinkedList<T> {
? ? ......
? ? /// 翻轉(zhuǎn)鏈表
? ? fn reverse(&mut self) {
? ? ? ? let mut prev = None; // 記錄遍歷鏈表時的前一個節(jié)點
? ? ? ? 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<T>，和其他對象一樣，Box<T>對象同一時刻只能有一個可變引用，而在上面的插入過程中，第2行，有兩個指針指向同一個頭結(jié)點，這個在Rust中是有問題的。
那在Rust里面，要實現(xiàn)在頭部插入的功能，首先得把指針從head里面拿出來，然后再放到新的結(jié)點里面去，而不是直接復制，這里需要用到Option中的take方法，即把Option中的東西取出來。
總結(jié)
到此這篇關(guān)于如何使用rust實現(xiàn)簡單的單鏈表的文章就介紹到這了,更多相關(guān)rust實現(xiàn)單鏈表內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
這篇文章主要介紹了rust中protobuf生成與使用,本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2023-05-05
要開始在 Rust 中使用 JSON,您需要安裝一個可以輕松操作 JSON 的庫,目前可用的流行crate之一是 serde-json,在本文中,我們將討論如何在 Rust 中使用 JSON 解析庫,以及比較最流行的庫及其性能2024-03-03
wmproxy已用Rust實現(xiàn)http/https代理,?socks5代理,?反向代理,?負載均衡,?靜態(tài)文件服務器,websocket代理,四層TCP/UDP轉(zhuǎn)發(fā),內(nèi)網(wǎng)穿透等,本文給大家介紹從零開始使用Rust編寫nginx(TLS證書快過期了),感興趣的朋友一起看看吧2024-03-03
這篇文章主要為大家介紹了Tauri?打開本地文件踩坑分析解決，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進步，早日升職加薪2023-04-04
ubstrate是一個區(qū)塊鏈開發(fā)框架，它提供了一系列模塊化和可擴展的組件，可以幫助開發(fā)人員快速構(gòu)建自定義區(qū)塊鏈。 Runtime是Substrate區(qū)塊鏈的核心部分，文中有詳細的代碼示例，需要的朋友可以參考下2023-05-05
Rust中的宏是一種強大的工具，可以幫助開發(fā)人員編寫可重用、高效和靈活的代碼，這篇文章主要介紹了Rust中的宏：聲明宏和過程宏,需要的朋友可以參考下2023-04-04
Cargo 是 Rust 的構(gòu)建系統(tǒng)和包管理器，?多數(shù) Rustacean 們使? Cargo 來管理他們的 Rust 項?，因為它可以為你處理很多任務，?如構(gòu)建代碼、下載依賴庫并編譯這些庫，這篇文章主要介紹了Rust中Cargo的使用,需要的朋友可以參考下2022-11-11
JSON在Web開發(fā)中被廣泛應用于數(shù)據(jù)交換,本文主要介紹了Rust語言操作JSON,包括序列化、反序列化、JSON創(chuàng)建等多個方面,具有一定的參考價值,感興趣的可以了解一下2024-03-03
在Rust中,trait定義了一組方法,這些方法可以被一個或多個類型實現(xiàn),當你為某個類型實現(xiàn)一個trait時,你可以為該trait中的每個方法提供自己的具體實現(xiàn),本文將給大家介紹一下trait中的個方法是否可以重寫,需要的朋友可以參考下2023-10-10
本文主要介紹了Rust標量類型的具體使用,其中包括整數(shù)類型、浮點類型、布爾類型以及字符類型,具有一定的參考價值,感興趣的可以了解一下2024-03-03