我有一个链表:
pub struct Node<T> {
val: T,
next: Option<Box<Node<T>>>
}
pub struct LinkedList<T> {
head: Option<Box<Node<T>>>
}
我的问题是关于这个删除重复项的函数:
impl<T: Clone + Eq + Hash> LinkedList<T> {
pub fn remove_dupes(&mut self) {
let mut set = HashSet::new();
let mut current = &mut self.head;
while let Some(mut node) = current.take() { // AO
if set.contains(&node.val) {
*current = node.next.take();
} else {
set.insert(node.val.clone());
let next = node.next.take(); // A1 take rest of list. Node.next is now None
*current = Some(node); // A2 restore ownership of node to current but its now pointing to None.
current = &mut current.as_mut().unwrap().next; // *A3* None because (A1) took ownership. *Why is this line necessary?*
*current = next; // A4 move to next node to continue with rest of list
}
}
}
它以一种更容易理解的方式工作并删除重复项,就像下面这样做:
impl<T: Clone + Eq + Hash> LinkedList<T> {
pub fn remove_dupes(&mut self) {
let mut set = HashSet::new();
let mut current = &mut self.head;
while let Some(mut node) = current.take() //B0 {
if set.contains(&node.val) {
*current = node.next.take();
} else {
set.insert(node.val.clone());
*current = Some(node); // B1
current = &mut current.as_mut().unwrap().next; // B2
}
}
}
我对铁 rust 还很陌生,正在努力理解记忆中正在发生的事情.我不明白A3行--current = &mut current.as_mut().unwrap().next;
行--有什么必要,也不知道它到底在做什么,但没有它,函数就不能工作.有人能不能
- 详细说明第一个功能中发生了什么,以及为什么此功能可以将所有权恢复到当前状态并移动到下一个 node ?
- 解释为什么在函数返回后,self.head仍然指向列表的原始头,但却指向列表的末尾(无),如果A3行中的
current = &mut current.as_mut().unwrap().next
行被注释掉了.
我有一个操场,这里的代码(打印调试语句时有点吵):https://play.rust-lang.org/?version=stable&mode=debug&edition=2018&gist=0015a922b6cc0f7284c9b37d0dfb95e6
我的理解如下,可能是有缺陷的:
-
while let Some(mut node) = current.take()
(A0)这一行在循环的每一次迭代中获取current的所有权,将其赋予变量"node".第current
章没有结果 -
let next = node.next.take();
node.next(A1) This line takes ownership of 第node.next
章没有结果 -
*current = Some(node);
个 (A2)再次将电流指向该 node .Current不再是None.它现在指向 node {val:(无论当前值是什么),Next:None} -
current = &mut current.as_mut().unwrap().next;
个 (A3)如果没有此行,循环仍将前进,但当函数返回到调用方时,链表最终将指向列表的末尾(无).这里current.as_mut().unwrap().next;
的值应该始终为None,因为我们从 node 上夺走了所有权.下一步是A1. -
*current = next;
(A4)将current指向A1中next
中存储的下一个 node .
请注意,注释掉倒数第二行(A3)相当于
pub fn remove_dupes(&mut self) {
let mut set = HashSet::new();
let mut current = &mut self.head;
let mut restore:&mut Option<Box<Node<T>>> = &mut None;
while let Some(mut node) = current.take() {
if set.contains(&node.val) {
*current = node.next.take();
} else {
set.insert(node.val.clone());
let next = node.next.take();
*restore = Some(node);
current = &mut restore.as_mut().unwrap().next;
*current = next;
}
}
}
pub fn remove_dupes(&mut self) {
let mut set = HashSet::new();
let mut current = &mut self.head;
while let Some(mut node) = current.take() {
if set.contains(&node.val) {
*current = node.next.take();
} else {
set.insert(node.val.clone());
let next = node.next.take();
*current = Some(node);
*current = next;
}
}
}
在调用后打印链接列表(使用我的格式化程序),结果是Head==None:
LL(0): |None|