在Rust中将节点附加到空的LinkedList，self.head.borrow_next()为None，而不是self.tail

cld4siwp  于 2022-12-29  发布在  其他
关注(0)|答案(1)|浏览(142)

我曾试图重新实现LinkedIn的 rust ，下面是我的代码：

  1. #![allow(dead_code)]
  3. use std::cell::{RefCell, Ref, RefMut};
  4. use std::rc::Rc;
  6. type WrappedNode<T> = Rc<RefCell<Node<T>>>;
  8. #[derive(Debug, PartialOrd, PartialEq, Clone)]
  9. pub struct Node<T> where
  10.   T: Clone 
  11.   {
  12.     next: Option<WrappedNode<T>>,
  13.     data: T,
  14. }
  16. #[derive(Debug, PartialOrd, PartialEq)]
  17. pub struct LinkedList<T> where
  18.   T: Clone 
  19.   {
  20.     head: Option<WrappedNode<T>>,
  21.     tail: Option<WrappedNode<T>>,
  22. }
  24. impl<T> Iterator for LinkedList<T> where
  25.   T: Clone 
  26.   {
  27. type Item = WrappedNode<T>;
  28.   
  29.   fn next(&mut self) -> Option<Self::Item> {
  30.     unimplemented!()
  31.   }
  32. }
  34. impl<T> Node<T> where
  35.   T: Clone
  36.   {
  37.   pub fn new(data: T) -> Self {
  38.     Self {
  39.       next: None,
  40.       data,
  41.     }
  42.   }
  44.   pub fn borrow_data(self: &Self) -> &T {
  45.     &self.data
  46.   }
  48.   pub fn borrow_next(self: &Self) -> Option<Ref<Node<T>>> {
  49.     match &self.next {
  50.       Some(next_exists) => {
  51.         Some(next_exists.borrow())
  52.       },
  53.       None => {
  54.         None
  55.       }
  56.     }
  57.   }
  59.   pub fn borrow_mut_next(self: &Self) -> Option<RefMut<Node<T>>> {
  60.     match &self.next {
  61.       Some(next_exists) => {
  62.         Some(next_exists.borrow_mut())
  63.       },
  64.       None => {
  65.         None
  66.       }
  67.     }
  68.   }
  70.   pub fn set_next(self: &mut Self, next: Node<T>) {
  71.     let next_node = Rc::new(RefCell::new(next));
  72.     self.next = Some(next_node);
  73.   }
  74. }
  76. impl<T> LinkedList<T> where
  77.   T: Clone
  78.   {
  79.   pub fn new_empty() -> Self {
  80.     Self {
  81.       head: None,
  82.       tail: None,
  83.     }
  84.   }
  86.   pub fn new_with_node(first_node: Node<T>) -> Self {
  87.     let mut new_ll = Self::new_empty();
  88.     Self::append(&mut new_ll, first_node);
  89.     new_ll
  90.   }
  92.   pub fn append(&mut self, node: Node<T>) {
  93.     assert!(node.next.is_none()); // make sure its not joining two linkedlists
  94.     
  95.     match self.tail.take() {
  96.       Some(old_tail) => {
  97.         old_tail
  98.           .borrow_mut()
  99.           .set_next(node.clone());
  100.         },
  102.       None => {
  103.         let mut node_clone = node.clone();
  104.         node_clone.next = self.tail.clone();
  105.         self.head = Some(Rc::new(RefCell::new(node_clone)));
  106.       }
  107.     }
  108.     self.tail = Some(Rc::new(RefCell::new(node)));
  109.   }
  110.   
  111. }
  113. // CRUD -> create new, add to head tail, read head tail, update anywhere, delete anywhere, delete head tail
  115. #[cfg(test)]
  116. mod tests {
  117.   use super:: {Node, LinkedList};
  118.   use std::rc::Rc;
  119.   use std::cell::RefCell;
  120.   
  121.   #[test]
  122.   fn test_node_ref_data() {
  123.     let node = Node::new(5);
  124.     assert_eq!(node.borrow_data(), &5);
  125.   }
  127.   #[test]
  128.   fn test_node_ref_next() {
  129.     let node = Node::new(5);
  130.   assert!(node.borrow_next().is_none());
  131.   }
  133.   #[test]
  134.   fn test_node_set_next() {
  135.     let mut node = Node::new(33);
  136.     let next_node = Node::new(34);
  137.     Node::set_next(&mut node,
  138.                    next_node);
  139.     assert_eq!(node
  140.                .borrow_next()
  141.                .unwrap()
  142.                .borrow_data(), &34);
  143.   }
  145.   #[test]
  146.   fn test_ll_new_empty() {
  147.     #[derive(Debug, PartialEq, PartialOrd, Clone)]
  148.     struct NTH;
  149.     let new_ll = LinkedList::<NTH>::new_empty();
  150.     assert_eq!(new_ll, LinkedList{head: None, tail: None})
  151.   }
  153.   #[test]
  154.   fn test_ll_new_with_node() {
  155.     let new_node = Node::new(45);
  156.     let new_node_two = new_node.clone();
  157.     let new_node_three = new_node.clone();
  158.     let new_ll = LinkedList::new_with_node(new_node);
  159.     let new_node_two = Some(Rc::new(RefCell::new(new_node_two)));
  160.     let new_node_three = Some(Rc::new(RefCell::new(new_node_three)));
  161.     
  162.     assert_eq!(new_ll, LinkedList{head: new_node_two, tail: new_node_three})
  163.   }
  165.   #[test]
  166.   fn test_ll_new_with_node_head_borrow_next_is_tail() {
  167.     let new_node = Node::new(45);
  168.     let new_node_two = new_node.clone();
  169.     let new_ll = LinkedList::new_with_node(new_node);
  170.     let new_node_two = Some(Rc::new(RefCell::new(new_node_two)));
  171.     assert_eq!(new_ll
  172.             .head
  173.             .unwrap()
  174.             .borrow()
  175.             .borrow_next()
  176.             .unwrap()
  177.             .borrow_data(), new_node_two.unwrap().borrow().borrow_data());
  178.   }
  180.   #[test]
  181.   fn test_ll_append_tail() {
  182.     let new_node = Node::new(45);
  183.     let new_node_two = new_node.clone();
  184.     let mut new_ll = LinkedList::new_with_node(new_node);
  185.     let new_node_two = Some(Rc::new(RefCell::new(new_node_two)));
  187.     let append_node = Node::new(77);
  188.     LinkedList::append(&mut new_ll, append_node);
  189.     assert_eq!(new_ll
  190.               .tail
  191.               .unwrap()
  192.               .borrow()
  193.               .borrow_data(), &77)
  194.   }
  196.   #[test]
  197.   fn test_ll_append_first_borrow_next() {
  198.     let new_node = Node::new(45);
  199.     let new_node_two = new_node.clone();
  200.     let mut new_ll = LinkedList::new_with_node(new_node);
  201.     let new_node_two = Some(Rc::new(RefCell::new(new_node_two)));
  203.     let append_node = Node::new(77);
  204.     LinkedList::append(&mut new_ll, append_node);
  205.     assert_eq!(new_ll
  206.               .head
  207.               .unwrap()
  208.               .borrow()
  209.               .borrow_next()
  210.               .unwrap()
  211.               .borrow_data(), &77)
  212.   }
  214. // end of tests
  215. }

两个测试失败，如下所示：

  1. running 8 tests
  2. test same_type_linked_list::tests::test_ll_new_empty ... ok
  3. test same_type_linked_list::tests::test_ll_append_tail ... ok
  4. test same_type_linked_list::tests::test_ll_new_with_node_head_borrow_next_is_tail ... FAILED
  5. test same_type_linked_list::tests::test_ll_append_first_borrow_next ... FAILED
  6. test same_type_linked_list::tests::test_ll_new_with_node ... ok
  7. test same_type_linked_list::tests::test_node_ref_data ... ok
  8. test same_type_linked_list::tests::test_node_set_next ... ok
  9. test same_type_linked_list::tests::test_node_ref_next ... ok
  11. failures:
  13. ---- same_type_linked_list::tests::test_ll_new_with_node_head_borrow_next_is_tail stdout ----
  14. thread 'same_type_linked_list::tests::test_ll_new_with_node_head_borrow_next_is_tail' panicked at 'called `Option::unwrap()` on a `None` value', src/same_type_linked_list.rs:176:14
  16. ---- same_type_linked_list::tests::test_ll_append_first_borrow_next stdout ----
  17. thread 'same_type_linked_list::tests::test_ll_append_first_borrow_next' panicked at 'called `Option::unwrap()` on a `None` value', src/same_type_linked_list.rs:210:16
  18. note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
  20. failures:
  21.     same_type_linked_list::tests::test_ll_append_first_borrow_next
  22.     same_type_linked_list::tests::test_ll_new_with_node_head_borrow_next_is_tail

我怀疑在向空的LinkedList追加新的Node<T>（具体为Node<u64>）时，self.head.next没有指向self.tail，尽管我明确地设置了它。当我对borrow_next()返回的None值调用unwrap()时，错误发生。Node<T>的关联方法返回字段.next的引用。这意味着理想情况下应该返回对new_ll.tail的引用的new_ll.head.borrow_next()改为返回None，这意味着当第一节点被附加/插入到完全空的LinkedList中时，它不指向new_11.tail。

rust

1条答案

按热度按时间
xnifntxz

xnifntxz1#

查看您的代码，head节点是您在中给予的节点

  1. LinkedList::new_with_node()

它的召唤

  1. pub fn new_empty() -> Self {
  2.     Self {
  3.       head: None,
  4.       tail: None,
  5.     }

也就是说，它初始化时没有头节点，所以当你用一个节点构造你的列表时，你就添加了一个头

  1. pub fn new_with_node(first_node: Node<T>) -> Self {
  2.     let mut new_ll = Self::new_empty();
  3.     Self::append(&mut new_ll, first_node);
  4.     new_ll
  5.   }
  7.   pub fn append(&mut self, node: Node<T>) {
  8.     assert!(node.next.is_none()); // make sure its not joining two linkedlists
  9.     
  10.     match self.tail.take() {
  11.       Some(old_tail) => {
  12.         old_tail
  13.           .borrow_mut()
  14.           .set_next(node.clone());
  15.         },
  17.       None => {
  18.         let mut node_clone = node.clone();
  19.         node_clone.next = self.tail.clone();
  20.         self.head = Some(Rc::new(RefCell::new(node_clone)));
  21.       }
  22.     }

还可以通过显式地将新创建的列表作为self传递来调用append。

  1. Self::append(&mut new_ll, first_node);

你可以称之为

  1. new_ll.append(first_node)

您假设在测试中头部之外还有另一个节点：

  1. assert_eq!(new_ll
  2.               .head
  3.               .unwrap()
  4.               .borrow()
  5.               .borrow_next()
  6.               .unwrap()
  7.               .borrow_data(), &77)
展开查看全部
赞(0）分享  回复(0）举报  2022-12-29
我来回答

相关问题

    查看更多

    热门标签

    更多
    JavaquerypythonNode开发语言requestUtil数据库Table后端算法LoggerMessageElementParser

    最新问答

    更多
    • 蜀ICP备13028337号-1 大数据知识库 https://www.saoniuhuo.com © All rights reserved
    • 本站内容来源互联网,如果侵犯您的权益请联系我们删除, 联系方式：448109455@qq.com