单链表
单链表(Linked List)是一种线性数据结构,由一系列节点组成,每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的特点是每个节点只能指向一个下一个节点,没有指向上一个节点的指针。
单链表的基本操作包括插入、删除、查找等。插入操作需要在指定位置插入一个新节点,删除操作需要删除指定位置的节点,查找操作需要找到指定值的节点位置。
单链表的优势是插入和删除操作相对简单,不需要移动大量元素,时间复杂度为O(1)。但单链表在查找操作上的时间复杂度是O(n),因为需要从头节点开始逐个比较直到找到目标节点。
用枚举表达链表
enum List { None, Node(i32, Box<List>), }
枚举成员: List::None 、 List::Node(i32, Box)
枚举enum
Rust 是一种编程语言,支持多种类型的的数据,其中之一就是枚举类型(Enum)。枚举类型是一种特殊的数据类型,它定义了一组可能的值。每个值都有一个特定的类型,并且可以用来表示不同的含义。
Rust 中的枚举类型通常使用关键字 enum
来定义,后接名称;枚举有多个成员(variant),每个成员是该 enum
类型的一个可能值。
例如,定义一个表示颜色类型的的枚举:
enum Color { Red, Green, Blue, }
这个 Color
类型有三种可能的值:Red
、Green
和 Blue,
使用这些值来存储不同颜色的值。
枚举类型的一个重要作用是使得代码更具可读性和可维护性。例如,如果使用一个 String
类型的颜色值,必须要确保该字符串始终有效,否则程序可能会崩溃。而使用枚举类型,可以明确指定可能的值,从而减少了此类错误的发生。
另外,Rust 还支持模式匹配,可以方便地检查一个枚举类型的值是哪个模式,这使得代码更加简洁和可读。例如:
let c = Color::Red; match c { Color::Red => println!("It's red!"), Color::Green => println!("It's green!"), Color::Blue => println!("It's blue!"), };
在这个例子中,使用 match
表达式来检查 c
的值是哪个模式。根据不同的模式,可以执行不同的代码。
Box容器
Rust中的Box是一种通用容器,可以存储任意类型的数据。它类似于C++中的unique_ptr,但还提供了一些额外的功能。
通过使用Box,您可以在堆上分配内存,而不需要手动管理内存的分配和释放。这使得使用Box成为一种方便的方式来存储和管理动态分配的内存。
Box还提供了一些优势,例如能够解决递归类型的大小问题。在Rust中,基本类型无法实现递归,但可以使用Box将递归类型的大小固定下来。
以下是一个使用Box的简单示例:
use std::boxed::Box; fn main() { let ibox = Box::new(5); println!("{}", ibox); println!("{}", *ibox); println!("{}", ibox.as_ref()); }
这个程序创建了一个Box容器,输出结果为3个5,但有不同的含义:
println!("{}", ibox);
这行代码使用 println! 宏打印一个 Box 对象 ibox 的值。{} 是一个占位符,表示将对象的值插入到此处。在这种情况下,ibox 的值将被打印出来,因为 Box 类型实现了 Display trait,可以将其值转换为字符串形式。
println!("{}", *ibox);
这行代码使用 println! 宏打印 ibox 解引用后的值。在 Rust 中,* 运算符用于解引用指针,即获取指针指向的实际值。在这种情况下,ibox 是一个 Box 对象,存储了一个整数值。通过解引用操作,我们获取到这个整数值并打印出来。
println!("{}", ibox.as_ref());
这行代码使用 println! 宏打印 ibox 的引用。as_ref() 方法返回一个引用,可以用于访问 Box 对象中的数据。在这种情况下,我们将 ibox 转换为引用,并通过引用访问其值并打印出来。
通过使用Box,可以方便地在Rust中管理和访问动态分配的内存,而不需要手动管理内存的分配和释放。
创建节点
1. 创建并打印
创建单个节点,并使用 #[derive(Debug)] 及 println! 打印输出:
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } fn main() { let head = List::Node(1, Box::new(List::None)); println!("{:?}", head); let head = List::Node(2, Box::new(List::None)); println!("{:?}", head); }
输出:
Node(1, None)
Node(2, None)
2. match 匹配
创建节点,并使用match表达式匹配枚举成员:
enum List { None, Node(i32, Box<List>), } fn main() { let list1 = List::None; let list2 = List::Node(1, Box::new(List::None)); match list1 { List::None => println!("List::None"), List::Node(_, _) => println!("List::Node"), } match list2 { List::None => println!("List::None"), List::Node(value, _) => println!("List::Node({})", value), } }
输出:
List::None
List::Node(1)
3. 节点初始化
new()初始化函数:fn new(value: i32)
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } impl List { fn new(value: i32) -> Self { List::Node(value, Box::new(List::None)) } } fn main() { let head = List::new(1); println!("{:?}", head); let head = List::new(2); println!("{:?}", head); let head = List::new(3); println!("{:?}", head); }
输出:
Node(1, None)
Node(2, None)
Node(3, None)
4.节点嵌套
通过嵌套多个节点形成单链表:
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } fn main() { let head = List::Node( 1, Box::new(List::Node( 2, Box::new(List::Node( 3, Box::new(List::Node( 4, Box::new(List::None), )), )), )), ); println!("{:?}", head); }
输出:
Node(1, Node(2, Node(3, Node(4, None))))
通过枚举类型表达成一个单链表,同样,这种方法甚至还能表达一棵二叉树:
#[derive(Debug)] enum Tree { None, Node(i32, Box<Tree>, Box<Tree>), } fn main() { let tree = Tree::Node( 1, Box::new(Tree::Node(2, Box::new(Tree::None), Box::new(Tree::None))), Box::new(Tree::Node( 3, Box::new(Tree::Node(4, Box::new(Tree::None), Box::new(Tree::None))), Box::new(Tree::Node(5, Box::new(Tree::None), Box::new(Tree::None))), ), ), ); println!("{:?}", tree); }
输出:
Node(1, Node(2, None, None), Node(3, Node(4, None, None), Node(5, None, None)))
二叉树相对单链表要复杂,有空再研究;还是继续探究单链表的其它操作吧。
追加节点
1. 尾插法
函数 append() 在链表尾部追加节点:
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } fn append(list: &mut List, value: i32) { match list { List::None => { *list = List::Node(value, Box::new(List::None)); } List::Node(_, next) => { append(next, value); } } } fn main() { let mut head = List::Node( 1, Box::new(List::Node( 2, Box::new(List::Node( 3, Box::new(List::Node( 4, Box::new(List::None), )), )), )), ); println!("{:?}", head); append(&mut head, 5); println!("{:?}", head); }
输出:
Node(1, Node(2, Node(3, Node(4, None))))
Node(1, Node(2, Node(3, Node(4, Node(5, None)))))
2. 链表追加方法
把append()函数改造成链表方法:
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } impl List { fn new(value: i32) -> Self { List::Node(value, Box::new(List::None)) } fn append(self, value: i32) -> Self { match self { List::None => List::Node(value, Box::new(List::None)), List::Node(v, next) => List::Node(v, Box::new(next.append(value))), } } } fn main() { let head = List::new(1); println!("{:?}", head); let head = head.append(2); println!("{:?}", head); let head = head.append(3); println!("{:?}", head); }
输出:
Node(1, None)
Node(1, Node(2, None))
Node(1, Node(2, Node(3, None)))
3. 头插法
除了尾部追加,也能在头部插入:
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } fn main() { let mut head = List::Node(1, Box::new(List::None)); head = List::Node(2, Box::new(head)); head = List::Node(3, Box::new(head)); head = List::Node(4, Box::new(head)); println!("{:?}", head); }
输出:
Node(4, Node(3, Node(2, Node(1, None))))
头插法得到一个反序的单链表:
4. 改写成单链表方法
对比append()和.push_back()不同之处:
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } impl List { fn new(value: Option<i32>) -> Self { match value { Some(value) => List::Node(value, Box::new(List::None)), None => List::None, } } fn append(self, value: i32) -> Self { match self { List::None => List::new(Some(value)), List::Node(v, next) => List::Node(v, Box::new(next.append(value))), } } fn push_back(&mut self, value: i32) { match self { List::None => { *self = List::new(Some(value)); } List::Node(_, next) => { next.push_back(value); } } } } fn main() { let head = List::new(None); println!("{:?}", head); let head = head.append(1); let head = head.append(2); println!("{:?}", head); println!(); let mut head = List::new(Some(1)); println!("{:?}", head); for value in 2..5 { head.push_back(value); } println!("{:?}", head); }
输出:
None
Node(1, Node(2, None))
Node(1, None)
Node(1, Node(2, Node(3, Node(4, None))))
push_back()推荐使用递归法,代码比较精炼;递推迭代法如下:
fn push_back(&mut self, value: i32) { match self { List::None => { *self = List::new(Some(value)); } List::Node(_, next) => { if let List::None = &**next { *next = Box::new(List::new(Some(value))); } else { let mut curr = next; while let List::Node(_, ref mut next) = **curr { curr = next; } *curr = Box::new(List::new(Some(value))); } } } }
遍历链表
1. 递归法
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } fn traverse(list: &List) { match list { List::None => println!("nil"), List::Node(value, next) => { print!("{}->", value); traverse(next); } } } fn main() { let head = List::Node( 1, Box::new(List::Node( 2, Box::new(List::Node( 3, Box::new(List::None), )), )), ); println!("{:?}", head); traverse(&head); }
输出:
Node(1, Node(2, Node(3, None)))
1->2->3->nil
2. 递推法
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } fn traverse(head: &List) { let mut cur = head; while let List::Node(value, next) = cur { print!("{}->", value); cur = next; } println!("nil"); } fn main() { let head = List::Node( 1, Box::new(List::Node( 2, Box::new(List::Node( 3, Box::new(List::None), )), )), ); println!("{:?}", head); traverse(&head); }
输出:
Node(1, Node(2, Node(3, None)))
1->2->3->nil
while let 语句比较简洁,相当于loop+if let:
fn traverse(head: &List) { let mut cur = head; loop { if let List::Node(value, next) = cur { print!("{}->", value); cur = next; } else { println!("nil"); break; } } }
使用 loop+match 也能遍历:
fn traverse(head: &List) { let mut cur = head; loop { match cur { List::None => { println!("nil"); break; } List::Node(value, next) => { print!("{}->", value); cur = next; } } } }
3. 改写成单链表方法
enum List { None, Node(i32, Box<List>), } impl List { fn traverse(&self) { let mut curr = self; while let List::Node(value, next) = curr { print!("{}->", value); curr = next; } println!("nil"); } } fn main() { let head = List::Node( 1, Box::new(List::Node( 2, Box::new(List::Node( 3, Box::new(List::None), )), )), ); head.traverse(); }
输出:
1->2->3->nil
自定义Display trait
为与遍历函数区分,在trait输出时用“Nil”标记
use std::fmt; #[derive(Debug)] enum List { None, Node(i32, Box<List>), } impl fmt::Display for List { fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { match self { List::None => write!(f, "Nil"), List::Node(value, next) => { write!(f, "{}->", value)?; write!(f, "{}", *next)?; Ok(()) } } } } fn traverse(head: &List) { let mut cur = head; while let List::Node(value, next) = cur { print!("{}->", value); cur = next; } println!("nil"); } fn main() { let head = List::Node( 1, Box::new(List::Node( 2, Box::new(List::Node( 3, Box::new(List::None), )), )), ); println!("{}", head); traverse(&head); }
输出:
1->2->3->Nil
1->2->3->nil
创建链表
直接把动态数组Vec创建成单链表。
1. 递归法
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } fn traverse(head: &List) { let mut cur = head; while let List::Node(value, next) = cur { print!("{}->", value); cur = next; } println!("nil"); } fn create(values: Vec<i32>) -> List { fn _helper(values: &Vec<i32>, index: usize) -> List { if index < values.len() { let value = values[index]; let next = Box::new(_helper(values, index + 1)); List::Node(value, next) } else { List::None } } _helper(&values, 0) } fn main() { let values = vec![1, 2, 3, 4, 5]; let head = create(values.clone()); println!("{:?}", head); traverse(&head); }
输出:
Node(1, Node(2, Node(3, Node(4, Node(5, None)))))
1->2->3->4->5->nil
2. 递推法
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } fn traverse(head: &List) { let mut cur = head; while let List::Node(value, next) = cur { print!("{}->", value); cur = next; } println!("nil"); } fn create(values: Vec<i32>) -> List { let mut list = List::None; for &value in values.iter().rev() { list = List::Node(value, Box::new(list)); } list } fn main() { let values = vec![1, 2, 3, 4, 5]; let head = create(values.clone()); println!("{:?}", head); traverse(&head); }
输出:
Node(1, Node(2, Node(3, Node(4, Node(5, None)))))
1->2->3->4->5->nil
3. 改写成单链表方法
enum List { None, Node(i32, Box<List>), } impl List { fn traverse(&self) { let mut curr = self; while let List::Node(value, next) = curr { print!("{}->", value); curr = next; } println!("nil"); } fn create(values: Vec<i32>) -> List { let mut list = List::None; for &value in values.iter().rev() { list = List::Node(value, Box::new(list)); } list } } fn main() { let head = List::create(vec!(1,2,3,4,5)); head.traverse(); }
输出:
1->2->3->4->5->nil
链表长度
遍历链表时改打印为计数即可:
enum List { None, Node(i32, Box<List>), } impl List { fn create(values: Vec<i32>) -> List { let mut list = List::None; for &value in values.iter().rev() { list = List::Node(value, Box::new(list)); } list } fn traverse(&self) { let mut curr = self; while let List::Node(value, next) = curr { print!("{}->", value); curr = next; } println!("nil"); } fn get_size(&self) -> usize { let mut length = 0; let mut curr = self; while let List::Node(_, next) = curr { length += 1; curr = next; } length } } fn main() { let head = List::create(vec![1, 2, 3]); head.traverse(); let length = head.get_size(); println!("Length of list: {}", length); let head = List::create(vec![1, 2, 3, 4, 5]); head.traverse(); let length = head.get_size(); println!("Length of list: {}", length); }
输出:
1->2->3->nil
Length of list: 3
1->2->3->4->5->nil
Length of list: 5
翻转链表
把单链表翻转,即头尾反向。
1. 递归法
#[derive(Debug)] enum List { None, Node(i32, Box<List>), } fn traverse(head: &List) { let mut cur = head; while let List::Node(value, next) = cur { print!("{}->", value); cur = next; } println!("nil"); } fn create(values: Vec<i32>) -> List { let mut list = List::None; for &value in values.iter().rev() { list = List::Node(value, Box::new(list)); } list } fn reversed(list: &List) -> List { fn _helper(list: &List, prev: List) -> List { match list { List::None => prev, List::Node(value, next) => { _helper(next, List::Node(*value, Box::new(prev))) }, } } _helper(list, List::None) } fn main() { let values = vec![1, 2, 3, 4, 5]; let head = create(values); traverse(&head); let head = reversed(&head); traverse(&head); }
输出:
1->2->3->4->5->nil
5->4->3->2->1->nil
2. 递推法
enum List { None, Node(i32, Box<List>), } fn traverse(head: &List) { let mut curr = head; while let List::Node(value, next) = curr { print!("{}->", value); curr = next; } println!("nil"); } fn create(values: Vec<i32>) -> List { let mut list = List::None; for &value in values.iter().rev() { list = List::Node(value, Box::new(list)); } list } fn reversed(head: &List) -> List { let mut list = List::None; let mut curr = head; while let List::Node(value, next) = curr { list = List::Node(*value, Box::new(list)); curr = next; } list } fn main() { let values = vec![1, 2, 3, 4, 5]; let head = create(values); traverse(&head); let head = reversed(&head); traverse(&head); }
输出:
1->2->3->4->5->nil
5->4->3->2->1->nil
3. 改写成单链表关联函数和方法
对比关联函数reversed()和方法.reverse()不同之处:
enum List { None, Node(i32, Box<List>), } impl List { fn new(value: Option<i32>) -> Self { match value { Some(value) => List::Node(value, Box::new(List::None)), None => List::None, } } fn traverse(&self) { let mut curr = self; while let List::Node(value, next) = curr { print!("{}->", value); curr = next; } println!("nil"); } fn create(values: Vec<i32>) -> List { let mut list = List::None; for &value in values.iter().rev() { list = List::Node(value, Box::new(list)); } list } fn reversed(&self) -> Self { let mut list = List::new(None); let mut curr = self; while let List::Node(value, next) = curr { list = List::Node(*value, Box::new(list)); curr = next; } list } fn reverse(&mut self) { let mut tail = List::new(None); let mut curr = std::mem::replace(self, List::None); while let List::Node(value, next) = std::mem::replace(&mut curr, List::None) { let node = List::Node(value, Box::new(tail)); (tail, curr) = (node, *next); } std::mem::swap(self, &mut tail); } } fn main() { let values = vec![1, 2, 3, 4, 5]; let mut head = List::create(values); head.traverse(); head.reverse(); head.traverse(); head = List::reversed(&head); head.traverse(); }
输出:
1->2->3->4->5->nil
5->4->3->2->1->nil
1->2->3->4->5->nil
删除尾节点
删除链表尾节点pop(),并返回尾节点的值
#![allow(dead_code)] enum List { None, Node(i32, Box<List>), } impl List { fn new(value: Option<i32>) -> Self { match value { Some(value) => List::Node(value, Box::new(List::None)), None => List::None, } } fn create(values: Vec<i32>) -> List { let mut list = List::None; for &value in values.iter().rev() { list = List::Node(value, Box::new(list)); } list } fn traverse(&self) { let mut curr = self; while let List::Node(value, next) = curr { print!("{}->", value); curr = next; } println!("nil"); } fn pop(&mut self) -> Option<i32> { match self { List::None => None, List::Node(value, next) => { if let List::None = **next { let popped_value = *value; *self = List::None; Some(popped_value) } else { next.pop() } } } } } fn main() { let values = vec![1, 2, 3, 4, 5]; let mut head = List::create(values); head.traverse(); for _ in 1..=6 { if let Some(value) = head.pop() { println!("Popped value: {}", value); } else { println!("List is empty"); } head.traverse(); } }
输出:
1->2->3->4->5->nil
Popped value: 5
1->2->3->4->nil
Popped value: 4
1->2->3->nil
Popped value: 3
1->2->nil
Popped value: 2
1->nil
Popped value: 1
nil
List is empty
nil
汇总小结
List 枚举定义了链表的两种可能状态:None 和 Node。
其中,Node 表示链表节点,包含一个整数值和一个指向下一个节点的 Box。
相关方法
相关的方法或关联函数,归纳如下:
new:创建一个新的链表节点或空链表。
append:在链表尾部添加一个节点,并返回添加后的链表。
push_back:在链表尾部添加一个节点,将链表修改为添加后的结果。
create:根据给定的数组构建一个链表。
reversed:反转链表,返回一个反转后的链表。
reverse:反转链表,将链表修改为反转后的结果。
traverse:遍历并打印链表中的节点值。
get_size:遍历出链表的节点数,返回链表长度。
pop:删除链表尾节点,并返回尾节点的值。
自定义trait
自定义trait Display,使链表的输出不依赖trait Debug:
```Rust
impl std::fmt::Display for List {
fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
match self {
List::None => write!(f, "nil"),
List::Node(value, next) => {
write!(f, "{}->", value)?;
write!(f, "{}", *next)?;
write!(f, "")
}
}
}
}
```
完整代码
https://inscode.csdn.net/@boysoft2002/RustEnumList
#![allow(dead_code)] enum List { None, Node(i32, Box<List>), } impl std::fmt::Display for List { fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { match self { List::None => write!(f, "nil"), List::Node(value, next) => { write!(f, "{}->", value)?; write!(f, "{}", *next)?; Ok(()) } } } } impl List { fn new(value: Option<i32>) -> Self { match value { Some(value) => List::Node(value, Box::new(List::None)), None => List::None, } } fn append(self, value: i32) -> Self { match self { List::None => List::new(Some(value)), List::Node(v, next) => List::Node(v, Box::new(next.append(value))), } } fn push_back(&mut self, value: i32) { match self { List::None => { *self = List::new(Some(value)); } List::Node(_, next) => { next.push_back(value); } } } fn create(values: Vec<i32>) -> Self { let mut list = List::new(None); for &value in values.iter().rev() { list = List::Node(value, Box::new(list)); } list } fn get_size(&self) -> usize { let mut length = 0; let mut curr = self; while let List::Node(_, next) = curr { length += 1; curr = next; } length } fn reversed(&self) -> Self { let mut list = List::new(None); let mut curr = self; while let List::Node(value, next) = curr { list = List::Node(*value, Box::new(list)); curr = next; } list } fn reverse(&mut self) { let mut tail = List::new(None); let mut curr = std::mem::replace(self, List::None); while let List::Node(value, next) = std::mem::replace(&mut curr, List::None) { let node = List::Node(value, Box::new(tail)); (tail, curr) = (node, *next); } std::mem::swap(self, &mut tail); } fn pop(&mut self) -> Option<i32> { match self { List::None => None, List::Node(value, next) => { if let List::None = **next { let popped_value = *value; *self = List::None; Some(popped_value) } else { next.pop() } } } } fn traverse(self: &Self) { let mut curr = self; while let List::Node(value, next) = curr { print!("{}->", value); curr = next; } println!("nil"); } } fn main() { let head = List::new(None); head.traverse(); let head = head.append(1); let head = head.append(2); head.traverse(); println!(); let mut head = List::new(Some(1)); head.traverse(); for value in 2..5 { head.push_back(value); } head.traverse(); println!(); let values = vec![1, 2, 3, 4, 5]; head = List::create(values); head.traverse(); head = head.reversed(); println!("{}", head); head.reverse(); println!("{}", head); let length = head.get_size(); println!("Length of list: {}", length); println!(); if let Some(value) = head.pop() { println!("Popped value: {}", value); } else { println!("List is empty"); } head.traverse(); println!("Length of list: {}", head.get_size()); }
输出:
nil
1->2->nil
1->nil
1->2->3->4->nil
1->2->3->4->5->nil
5->4->3->2->1->nil
1->2->3->4->5->nil
Length of list: 5
Popped value: 5
1->2->3->4->nil
Length of list: 4
真题实战
合并两个有序链表 Mmerge-two-sorted-lists
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例 1:
输入:l1 = [1,2,4], l2 = [1,3,4]
输出:[1,1,2,3,4,4]
示例 2:
输入:l1 = [], l2 = []
输出:[]
示例 3:
输入:l1 = [], l2 = [0]
输出:[0]
提示:
两个链表的节点数目范围是 [0, 50]
-100 <= Node.val <= 100
l1 和 l2 均按 非递减顺序 排列
代码:
#[derive(Clone)] enum List { None, Node(i32, Box<List>), } fn create(values: Vec<i32>) -> List { let mut list = List::None; for &value in values.iter().rev() { list = List::Node(value, Box::new(list)); } list } fn traverse(head: &List) { let mut cur = head; while let List::Node(value, next) = cur { print!("{}->", value); cur = next; } println!("nil"); } fn merge_lists(l1: List, l2: List) -> List { match (l1.clone(), l2.clone()) { (List::None, _) => l2, (_, List::None) => l1, (List::Node(x, box1), List::Node(y, box2)) => { if x < y { List::Node(x, Box::new(merge_lists(*box1, l2))) } else { List::Node(y, Box::new(merge_lists(l1, *box2))) } } } } fn main() { let nums1 = vec![1, 2, 4]; let nums2 = vec![1, 2, 3]; let list1 = create(nums1); let list2 = create(nums2); traverse(&list1); traverse(&list2); let merged = merge_lists(list1, list2); traverse(&merged); }
输出:
1->2->4->nil
1->2->3->nil
1->1->2->2->3->4->nil
本文完