wordpress站群目录收录,北京网络销售公司,响应式网站用什么工具做,重庆软件开发目录
单链表
用枚举表达链表
枚举enum
Box容器
创建节点
1. 创建并打印
2. match 匹配
3. 节点初始化
4.节点嵌套
追加节点
1. 尾插法
2. 链表追加方法
3. 头插法
4. 改写成单链表方法
遍历链表
1. 递归法
2. 递推法
3. 改写成单链表方法
自定义Display tr…
目录
单链表
用枚举表达链表
枚举enum
Box容器
创建节点
1. 创建并打印
2. match 匹配
3. 节点初始化
4.节点嵌套
追加节点
1. 尾插法
2. 链表追加方法
3. 头插法
4. 改写成单链表方法
遍历链表
1. 递归法
2. 递推法
3. 改写成单链表方法
自定义Display trait
创建链表
1. 递归法
2. 递推法
3. 改写成单链表方法
链表长度
翻转链表
1. 递归法
2. 递推法
3. 改写成单链表关联函数和方法
删除尾节点
汇总小结
相关方法
自定义trait
完整代码
真题实战
合并两个有序链表 Mmerge-two-sorted-lists 单链表
单链表Linked List是一种线性数据结构由一系列节点组成每个节点包含一个数据元素和一个指向下一个节点的指针。单链表的特点是每个节点只能指向一个下一个节点没有指向上一个节点的指针。
单链表的基本操作包括插入、删除、查找等。插入操作需要在指定位置插入一个新节点删除操作需要删除指定位置的节点查找操作需要找到指定值的节点位置。
单链表的优势是插入和删除操作相对简单不需要移动大量元素时间复杂度为O(1)。但单链表在查找操作上的时间复杂度是O(n)因为需要从头节点开始逐个比较直到找到目标节点。 用枚举表达链表
enum List {None,Node(i32, BoxList),
}
枚举成员 List::None 、 List::Node(i32, BoxList)
枚举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!(Its red!), Color::Green println!(Its green!), Color::Blue println!(Its 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, BoxList),
}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, BoxList),
}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, BoxList),
}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, BoxList),
}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, BoxTree, BoxTree),
} 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, BoxList),
}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, BoxList),
}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, BoxList),
}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, BoxList),
}impl List {fn new(value: Optioni32) - 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, BoxList),
}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, BoxList),
}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 语句比较简洁相当于loopif 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;}}
}
使用 loopmatch 也能遍历
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, BoxList),
}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, BoxList),
}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, BoxList),
}fn traverse(head: List) {let mut cur head;while let List::Node(value, next) cur {print!({}-, value);cur next;}println!(nil);
}fn create(values: Veci32) - List {fn _helper(values: Veci32, 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, BoxList),
}fn traverse(head: List) {let mut cur head;while let List::Node(value, next) cur {print!({}-, value);cur next;}println!(nil);
}fn create(values: Veci32) - 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, BoxList),
}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: Veci32) - 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, BoxList),
}impl List {fn create(values: Veci32) - 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, BoxList),
}fn traverse(head: List) {let mut cur head;while let List::Node(value, next) cur {print!({}-, value);cur next;}println!(nil);
}fn create(values: Veci32) - 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, BoxList),
}fn traverse(head: List) {let mut curr head;while let List::Node(value, next) curr {print!({}-, value);curr next;}println!(nil);
}fn create(values: Veci32) - 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, BoxList),
}impl List {fn new(value: Optioni32) - 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: Veci32) - 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, BoxList),
}impl List {fn new(value: Optioni32) - Self {match value {Some(value) List::Node(value, Box::new(List::None)),None List::None,}}fn create(values: Veci32) - 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) - Optioni32 {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 表示链表节点包含一个整数值和一个指向下一个节点的 BoxList。
相关方法
相关的方法或关联函数归纳如下
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, ) } } } }
完整代码
InsCode - 让你的灵感立刻落地
https://inscode.csdn.net/boysoft2002/RustEnumList
#![allow(dead_code)]enum List {None,Node(i32, BoxList),
}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: Optioni32) - 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: Veci32) - 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) - Optioni32 {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, BoxList),
}fn create(values: Veci32) - 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
