运维开发网

如何用rust实现简单的单链表

运维开发网 https://www.qedev.com 2022-06-18 17:43 出处:网络
实现单链表在别的语言里面可能是一件简单的事情,单对于Rust来说,绝对不简单,下面这篇文章主要给大家介绍了关于如何使用rust实现简单的单链表的相关资料,文中通过实例代码介绍的非常详细,需要的朋友可以

实现单链表在别的语言里面可能是一件简单的事情,单对于Rust来说,绝对不简单,下面这篇文章主要给大家介绍了关于如何使用rust实现简单的单链表的相关资料,文中通过实例代码介绍的非常详细,需要的朋友可以


前言

作为初学者,在掌握了rust的基本语法和所有权机制后,试着写下常用的数据结构和算法,目标是更好的理解rust的所有权机制。受限于个人,rust还处于初级阶段,所以本文的代码实现不一定是最合适的,甚至可能会出现问题。

今天的目标是用rust实现一个简单的LinkedList。同时提供从头插入元素、翻转链表、打印链表的功能。



1.链表节点的定义

要实现链表,第一步是实现链表的节点。根据其他编程语言的经验,下面这个链表的节点结构的定义是用rust写的:

代码片段1:

struct Nodelt;Tgt; { data: T, next: Optionlt;Nodelt;Tgt;gt;, // recursive type `Node` has infinite size}

在代码片段1中,定义了一个节点结构,数据字段将泛型类型T用于链表节点的数据。使用选项枚举,即如果这个节点没有下一个节点,那么next就是空。rust中没有其他编程语言中的空值(null,nil),但是提供了Option的解决方案。如果这个链表节点的下一个节点是空,那么它的下一个值就是option::。

不幸的是,代码片段1无法编译,并且报告了递归类型'' node ''具有无限大小的编译错误。回顾一下Rust内存管理的基础知识,Rust需要知道一个类型在编译时占用了多少空个空间。节点结构将自己嵌入其中,所以在编译时无法确认其占用的空房间的大小。在Rust中,当有一个类型的大小在编译时未知,并且您希望在需要精确大小的上下文中使用该类型的值时,您可以使用智能指针框。将下一个字段的类型修改为OptionltBoxltNodeltTgtgt;gt;这样,嵌套的类型是Box,嵌套的节点将被分配到堆中。下一个字段只存储堆栈上智能指针框的数据(ptr,meta),这样就可以在编译时确定节点类型的大小。将代码片段1修改如下:

代码片段2:

struct Nodelt;Tgt; { data: T, next: Optionlt;Boxlt;Nodelt;Tgt;gt;gt;,}

修改后可以编译通过。根据下一步:OptionltBoxltNodeltTgtgt;gt;,每个链表节点将拥有其下一个节点的所有权。


2.链表的定义

定义了LinkedList之后,下一步就是定义一个结构链表来表示链表,它会封装链表的一些基本操作。结构中只需要链表头节点的一个字段头,类型为OptionltBoxltNodeltTgtgt;gt;。

代码片段3:

/// 单链表节点#[derive(Debug)]struct Nodelt;Tgt; { data: T, next: Optionlt;Boxlt;Nodelt;Tgt;gt;gt;,}/// 单链表#[derive(Debug)]struct LinkedListlt;Tgt; { head: Optionlt;Boxlt;Nodelt;Tgt;gt;gt;,}

为了便于使用,在Node和LinkedList这两个结构中添加了新的关联函数。

代码片段4:

impllt;Tgt; Nodelt;Tgt; { fn new(data: T) -gt; Self { Self { data: data, next: None } }}impllt;Tgt; LinkedListlt;Tgt; { fn new() -gt; Self { Self { head: None } }}

Node的新功能是用给定的数据创建一个孤立的(没有下一个节点)节点。

LinkedList的新函数用来创建空链表。


3.实现从链表头部插入节点的prepend方法

在完成了链表和链表节点的定义后,我们实现了链表的prepend方法,通过头插入的方式将节点添加到链表中。

代码片段5:

impllt;Tgt; LinkedListlt;Tgt; { fn new() -gt; Self { Self { head: None } } /// 在链表头部插入节点(头插法push front) fn prepend(amp;mut self, data: T) -gt; amp;mut Self { // 从传入数据构建要插入的节点 let mut new_node = Box::new(Node::new(data)); match self.head { // 当前链表为空时, 插入的节点直接作为头节点 None =gt; self.head = Some(new_node), // 当前链表非空时, 插入的节点作为新的头节点插入到原来的头结点前面 Some(_) =gt; { // 调用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方法,并在主函数中构建了一个链表,以Debug的形式打印出链表的信息。

为了让打印出来的信息更好看,我们决定为LinkedList实现Display trait,这样链表打印的格式类似于1-gt;2-gt;3-gt;4-gt;5-gt;没有.

代码片段6:

use std::fmt::Display;......impllt;T: Displaygt; Display for LinkedListlt;Tgt; { fn fmt(amp;self, f: amp;mut std::fmt::Formatterlt;'_gt;) -gt; 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, "{} -gt; ", 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 -gt; 2 -gt; 3 -gt; 4 -gt; 5 -gt; None}


5.为链表实现翻转链表功能的reverse方法

代码片段7:

impllt;Tgt; LinkedListlt;Tgt; { ...... /// 翻转链表 fn reverse(amp;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 -gt; 2 -gt; 3 -gt; 4 -gt; 5 -gt; None ll.reverse(); // 5 -gt; 4 -gt; 3 -gt; 2 -gt; 1 -gt; None println!("{ll}");}


注意事项

只有一个变量引用。

在C中,如果你想在链表的头部插入一个元素,你可以这样写

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

但是在Rust中你不能这样做。

在Rust中,常见的指针是BoxltTgt,和其他对象一样,BoxltTgt一个对象在同一时刻只能有一个变量引用,但是在上面的插入过程中,第2行有两个指针指向同一个头节点,这在Rust中是有问题的。


在Rust中,要实现插入头部的功能,必须先将指针从头部取出,然后放入一个新的节点中,而不是直接复制。这里需要用到Option中的Take方法,也就是把Option中的东西拿出来。


总结

到目前为止,这篇关于如何使用rust实现简单的单链表的文章已经介绍到这里了。关于rust如何实现单链表的更多信息

0

精彩评论

暂无评论...
验证码 换一张
取 消