< 返回我的博客

Deen 发表于 2019-01-18 11:48

Tags:linedlist

实现一个方法fn remove(head: Option<Box<LinkedList>>, val: i32) -> Option<Box<LinkedList>> 即,删除链表中值为val的结点,返回删除后的链表。

我现在有两个问题:

  1. 此函数签名中,head是获得了ownership的,但是似乎不是mutable的,这个怎么解呢?如果一个对象在声明时没有带mut,是不是之后都不能改了(refcell除外)。
  2. 怎样删除链表中间的结点呢?我看了learn rust with too many linkedlist上,知道怎么删除表头,但是如果要删除表中的元素,需要通过ref遍历到该结点,此时链表处于被引用状态是不可变的,如何实现删除呢?我发现标准库的链表也没有提供删除中间结点的API?有没有哪位大佬能帮忙解惑一下,谢谢

评论区

写评论
Military-axe 2021-06-25 12:29

我用的是类似二叉树的定义结构体

use std::{cell::RefCell, rc::Rc};

type LinkNode<K> = Option<Rc<RefCell<Node<K>>>>;

#[derive(Debug)]
struct Node<K> {
    data: K,
    next: LinkNode<K>,
}

然后删除的写法是

impl Node{
pub fn delete(head: &LinkNode<K>, position: usize){
        let mut count = 0;
        if let Some(mut root) = head.clone() {
            loop {
                if count != position {
                    let tmp = root.borrow().next.clone();
                    if let Some(next) = tmp {
                        count += 1;
                        root = next.clone();
                    } else {
                       panic!("LinkNode no too long");
                    }
                } else {
                    let tmp = root.borrow().next.clone();
                    if let Some(next) = tmp{
                        if let Some(nextt) = next.borrow().next.clone(){
                            root.borrow_mut().next = Some(nextt.clone());
                        }else{
                            root.borrow_mut().next = None;
                        }
                    }
                    break;
                }
            }
        }
    }
}

因为box不可以两个指针指向同一个,我又不想用递归的写法,于是就这么写,但是我也不知道怎么删除节点把那块内存删除掉

xcaptain 2019-04-02 10:30

一般标准的链表都只提供从表头删除功能,如果想删除一个节点可以参考官方的实现https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/linked_list.rs#L217 这个方法使用了unsafe关键字,但是很容易理解

在官方的链表实现中还有一个drain_filter的方法 https://github.com/rust-lang/rust/blob/master/src/liballoc/collections/linked_list.rs#L767 看起来又更复杂了

可以试试能不能把这个unlink_node的方法改造成safe的

kaigedong 2019-03-25 13:42

前几天的Rust日报里,推送了链表的实现,不知道你还用不用得到。 https://github.com/rust-unofficial/too-many-lists

1 共 3 条评论, 1 页