RT-Thread-基于 Rust 的单向链表实现RT-Thread问答社区

基于 Rust 的单向链表实现

发布于 2021-04-28 09:24:13 浏览：1258 订阅该版

[tocm]

## 利用结构体 (struct) 定义成员变量
num 表示当前结点值，next 指向下一个结点的指针。
```
#[derive(Debug)]
pub struct List {
    pub num: i32,
    pub next: Option<Box<List>>,
}
```

## 利用 impl 关键字来定义结构体成员方法
```
impl List {
}
```

### 创建链表
```
pub fn new(value: i32) -> List {
    List {
        next: None,
        num: value
    }
}
```

### 添加结点
```
pub fn append(&mut self, value: i32) {
    let _node = List::new(value);
    self.get_last_node().next = Some(Box::new(_node));
}
```

### 计算链表长度
```
pub fn len(&self) -> u32 {
    match &self.next {
        Some(list) => list.len() + 1,
        None => 0,
    }
}
```

### 找到最后一个结点
```
pub fn get_last_node(&mut self) -> &mut Self {
    if let Some(ref mut node) = self.next {
        node.get_last_node()
    }
    else {
        return self;
    }
}
```

### 遍历链表
```
pub fn traverse(&self) {
    let mut node_num = 0;
    let mut curr = self.next.as_ref();
    while curr.is_some() {
        print!("node{}: {:?}\n", node_num, curr);
        curr = curr.unwrap().next.as_ref();
        node_num += 1;
    }
}
```
### 删除结点值为 value 的结点
```
pub fn delete_node(head: Option<Box<List>>, value: i32) -> Option<Box<List>> {
    let mut head = head;
    let mut curr = head.as_mut();
    while curr.is_some() && curr.as_ref().unwrap().next.is_some() {
        if curr.as_ref().unwrap().next.as_ref().unwrap().num == value {
            let next = curr.as_mut().unwrap().next.as_mut().unwrap().next.take();
            curr.as_mut().unwrap().next = next;
        }
        else {
            curr = curr.unwrap().next.as_mut();
        }
    }
    return head;
}
```

## 测试代码
```
#[derive(Debug)]
pub struct List {
    pub num: i32,
    pub next: Option<Box<List>>,
}

impl List {
    pub fn new(value: i32) -> List {
        List {
            next: None,
            num: value
        }
    }

// 翻转链表
    pub fn reverse_list(head:Option<Box<List>>) -> Option<Box<List>> {

let mut prev = None; // 上一个节点
        let mut cur = head; // 当前节点
        while let Some(mut _node) = cur { // 用take置换next中的节点需要 mut
            cur = _node.next.take(); // 换出 next 作为下一次的 cur
            _node.next = prev; // 把next指向前一个节点
            prev = Some(_node);  // 更新 prev
        }
        return prev;  // 跳出循环时,prev就是翻转后的头节点
    }

// 遍历链表
    pub fn traverse(&self) {
        let mut node_num = 0;
        let mut curr = self.next.as_ref();
        while curr.is_some() {
            print!("node{}: {:?}\n", node_num, curr);
            curr = curr.unwrap().next.as_ref();
            node_num += 1;
        }
    }

// 删除节点, 删除节点值为 value 的节点
    pub fn delete_node(head: Option<Box<List>>, value: i32) -> Option<Box<List>> {
        let mut head = head;
        let mut curr = head.as_mut();
        while curr.is_some() && curr.as_ref().unwrap().next.is_some() {
            if curr.as_ref().unwrap().next.as_ref().unwrap().num == value {
                let next = curr.as_mut().unwrap().next.as_mut().unwrap().next.take();
                curr.as_mut().unwrap().next = next;
            }
            else {
                curr = curr.unwrap().next.as_mut();
            }
        }
        return head;
    }

// 找到最后一个节点
    pub fn get_last_node(&mut self) -> &mut Self {
        if let Some(ref mut node) = self.next {
            node.get_last_node()
        }
        else {
            return self;
        }
    }
    // 添加节点
    pub fn append(&mut self, value: i32) {
        let _node = List::new(value);
        self.get_last_node().next = Some(Box::new(_node));
    }

// 计算链表长度
    pub fn len(&self) -> u32 {
        match &self.next {
            Some(list) => list.len() + 1,
            None => 0,
        }
    }
}

fn main() {
    // 创建一个新的链表
    let mut list = List::new(0);
    // 添加节点
    list.append(1);
    list.append(2);
    list.append(3);
    list.append(4);
    println!("linked list has length: {}", list.len());
    // 遍历列表
    println!("{:?}", list.traverse());
    // 删除列表 value 为 2 的节点，并返回新列表
    let new_list = List::delete_node(Some(Box::new(list)), 2);
    println!("{:?}", new_list);
}

linked list has length: 4
node0: Some(List { num: 1, next: Some(List { num: 2, next: Some(List { num: 3, next: Some(List { num: 4, next: None }) }) }) })
node1: Some(List { num: 2, next: Some(List { num: 3, next: Some(List { num: 4, next: None }) }) })
node2: Some(List { num: 3, next: Some(List { num: 4, next: None }) })
node3: Some(List { num: 4, next: None })
()
Some(List { num: 0, next: Some(List { num: 1, next: Some(List { num: 3, next: Some(List { num: 4, next: None }) }) }) }
```