上一篇是根据rust语言圣经的指导写的迭代器版本，这次我想用一种更贴近过程式的风格
实验一：城市链表
城市链表:
将若干城市的信息，存入一个带头结点的链表中。结点中的城市信息包括:城市名和标进行有关查找、插入、删除、更新等操作。城市的位置坐标。要求能够利用城市名和位置
基本要求:
①给定一个城市名，返回其位置坐标:
②给定一个位置坐标P和一个距离 D，返回所有与 P的距离小于等于 D 的城市。
测试数据:
依据软件工程的测试技术自己确定，注意则试边界数据。首先是定义单链表的结构，不需要实现泛型：
type Link= Option<Rc<RefCell<Node>>>;
struct Head{
first : Link,
}
#[derive(Clone)]
struct Node{
city_name : String,
p_x : f64,
p_y : f64,
next : Link,
}由于不能保证字符串可以在编译期确定，所以这里不能用&str，虽说实验没做要求
先写几个简单的：
impl Head{
fn new() -> Head{
let new_list= Head{first: None };
new_list
}
fn insert(&mut self, name: String, x :c_double, y:c_double){
let mut new_node = Node::new(name, x, y);
new_node.next = self.first.take();
self.first = Some(Rc::new(RefCell::new(new_node)));
}
}
impl Node {
fn new(name: String, x:c_double, y:c_double) -> Node {
let new_node = Node{city_name : name, p_x: x, p_y: y, next : Option::None};
new_node
}
}
mod test{
use super::Head;
#[test]
fn test_insert(){
let mut head = Head::new();
head.insert("beijing".to_string(), 0.0, 0.0);
head.insert("tianjin".to_string(),4.0,4.5);
}
}take可以将option里的东西拿出来，移交所有权并替换为None，用在这里再合适不过。
接下来就要面临所有权的问题：
fn find_with_name(&self, name:String) -> (f64, f64){
let mut current = &self.first;
while let Some(node) = current {
if name == node.borrow().city_name{
return (node.borrow().p_x, node.borrow().p_y);
}else {
current = node.borrow().next;
}
}
(-1f64, -1f64)
}问题出在current = node.borrow().next;，current明明是一个Link的不可变引用，怎么能把Link直接给它
如果变成current = &node.borrow().next;又有了新的问题，node马上就要离开作用域被释放了，current怎么还能持有其引用
那么问题来到了current的声明let mut current = &self.first;，略作调整 let mut current = self.first.clone();这样current就不再是引用，而拷贝的实际是个指针，没有什么额外开销
fn find_with_name(&self, name:String) -> (f64, f64){
let mut current = self.first.clone();
while let Some(node) = current {
if name == node.borrow().city_name{
return (node.borrow().p_x, node.borrow().p_y);
}else {
current = node.borrow().next.clone();
}
}
(-1f64, -1f64)
}
#[test]
fn test_find_with_name(){
let mut head = Head::new();
head.insert("beijing".to_string(),0.0,0.0);
head.insert("tianjin".to_string(),4.0,4.5);
assert_eq!(head.find_with_name("beijing".to_string()), (0.0, 0.0));
assert_eq!(head.find_with_name("tianjin".to_string()).0, 4.0);
assert_eq!(head.find_with_name("tianjin".to_string()).1, 4.5);
assert_eq!(head.find_with_name("foobar".to_string()),(-1.0,-1.0));
}两次clone指针成功解决了所有权问题，测试也是顺利通过
接下来根据距离筛城市，如法炮制：
fn find_with_distance(&self,position:(f64,f64), distance:f64) -> HashMap<String,bool> {
let mut names = HashMap::new();
let mut current = self.first.clone();
while let Some(node) = current {
if Self::calculate_distance(position,(node.borrow().p_x,node.borrow().p_y)) <= distance{
names.insert(node.borrow().city_name.clone(),true);
}
current = node.borrow().next.clone();
}
names
}
fn calculate_distance(center :(f64, f64), city_position:(f64, f64)) -> f64{
let (x1, y1) = center;
let (x2, y2) = city_position;
((x2 - x1).powi(2) + (y2 - y1).powi(2)).sqrt()
}
#[test]
fn test_find_with_distance(){
let mut head = Head::new();
head.insert("beijing".to_string(),0.0,0.0);
head.insert("tianjin".to_string(),4.0,4.5);
head.insert("xianggang".to_string(),10.0,10.0);
let test1 = head.find_with_distance((0.0,4.0),5.0);
assert_eq!(test1.get("beijing"), Some(true).as_ref());
assert_eq!(test1.get("tianjin"), Some(true).as_ref());
assert_eq!(head.find_with_distance((0.0,4.0),0.0).get("beijing"), None);
}接下来是删除，事情没有那么简单，需要根据下一项的值确定具体操作，先写一下第一版：
fn remove_with_name(&mut self, name: String) {
let mut current = self.first.clone();
while let Some(node) = current {
let next = node.borrow().next.clone();
if next.unwrap().borrow().city_name == name{
node.borrow().next = next.unwrap().borrow().next.clone();
}else {
current = next;
}
}
}以上代码写得一点都不锈，不仅到处是红红的报错，而且用到了unwrap，这意味着如果值为None会直接panic，同时实际上跳过了first节点的检查
fn remove_with_name(&mut self, name: String) {
let current = self.first.clone();
if let None = current {
return;
}
if let Some(node) = current {
if node.borrow().city_name == name {
self.first = node.borrow_mut().next.take(); // 删除头结点
return;
}
}
let mut current = self.first.clone();
while let Some(node) = current {
let mut next = node.borrow().next.clone();
if let Some(next_node) = next {
if name == next_node.borrow().city_name{
node.borrow_mut().next = next_node.borrow_mut().next.take();
return;
}else {
current = node.borrow().next.clone();
}
}else {
break;
}
}
}
#[test]
fn test_remove_with_name(){
let mut head = Head::new();
head.insert("beijing".to_string(),0.0,0.0);
head.insert("tianjin".to_string(),4.0,4.5);
head.insert("xianggang".to_string(),10.0,10.0);
head.remove_with_name("beijing".to_string());
head.remove_with_name("xianggang".to_string());
assert_eq!(head.find_with_name("beijing".to_string()) ,(-1.0,-1.0));
assert_eq!(head.find_with_name("tianjin".to_string()), (4.0, 4.5));
assert_eq!(head.find_with_name("xianggang".to_string()), (-1.0,-1.0));
}这一版至少可以顺利通过测试了
最后一部分，根据name修改坐标：
fn update_with_name(&mut self, name: String, p_x: f64, p_y: f64) {
let mut current = self.first.clone();
while let Some(node) = current {
if name == node.borrow().city_name{
node.borrow_mut().p_x = p_x;
node.borrow_mut().p_y = p_y;
return;
}else {
current = node.borrow().next.clone();
}
}
}
#[test]
fn test_update_with_name(){
let mut head = Head::new();
head.insert("beijing".to_string(),0.0,0.0);
head.insert("tianjin".to_string(),4.0,4.5);
head.update_with_name("tianjin".to_string(), 1.0,2.5);
assert_eq!(head.find_with_name("tianjin".to_string()), (1.0, 2.5));
}实验二：约瑟夫环
[问题描述
约瑟夫(Joseph)问题的一种描述是:编号为 1、2、…、n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值 m，从第1个人开始按顺时针方向自1开始顺序报数，报到m时停止报数。报m 的人出列，将 TA 的密码作为新的 m 值，从 TA在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计一个程序求出出列顺序。
[基本要求]
利用单向循环链表存储结构模拟此过程，按照出列的顺序打印出各人的编号
[测试数据]
m 的初值为 20:密码:3，1，7，2，4，8，4(正确的结果应为6，1，4，7，2，3，5)
[实现提示]
程序运行后首先要求用户指定初始报数上限值，然后读取各人的密码。设n≤30。依旧是先定义链表结构：
type Link = Option<Rc<RefCell<Node>>>;
struct Node{
index : usize,
key : usize,
next: Link,
}index记录编号（可省略），key记录密码
循环链表就需要循环引用，在rust里并不是一件容易实现的事，比如直接来：
fn new(num : usize) -> Node {
let mut new_node = Node{index : num, key : 0, next: None};
new_node.next = Option::Some(Rc::new(RefCell::new(new_node)));
new_node
}new_node的所有权已经转移到了next字段，怎么还能返回呢？利用智能指针的封装可以避免这个问题，同时为了后续操作方便，增加一个头节点，保留循环链表的尾指针：
use std::rc::Rc;
use std::cell::RefCell;
struct Node {
index : usize,
key : usize,
next: Option<Rc<RefCell<Node>>>,
}
struct CircularList {
len : usize,
tail: Option<Rc<RefCell<Node>>>,
}
impl CircularList {
fn new() -> Self {
CircularList {
len : 0,
tail: None,
}
}
// 创建单节点循环链表
fn new_single_node(key: usize) -> Self {
let node = Rc::new(RefCell::new(Node {
index: 1,
key,
next: None,
}));
// 关键：让节点的 next 指向自己
node.borrow_mut().next = Some(node.clone());
CircularList {
len : 1,
tail: Some(node),
}
}
// 遍历链表
fn traverse(&self) {
if let Some(head) = &self.tail {
let mut current = head.clone();
loop {
println!("Data: {}", current.borrow().index);
let next = current.borrow().next.clone().unwrap();
current = next;
}
}
}
}
fn main() {
}
#[cfg(test)]
mod tests {
use crate::CircularList;
#[test]
fn test_new() {
let mut list = CircularList::new_single_node(1);
// 遍历链表
list.traverse(); // 输出死循环的1
}
}接下来实现push操作：
fn push_back(&mut self, key: usize) {
self.len += 1;
let new_node = Rc::new(RefCell::new(Node {
index : self.len,
key,
next: None,
}));
match &self.tail {
None => {
panic!("should new_single_node() first");
}
Some(tail) => {
let head = tail.borrow().next.clone().unwrap();
new_node.borrow_mut().next = Some(head);
tail.borrow_mut().next = Some(new_node.clone());
self.tail = Some(new_node);
}
}
}
#[test]
fn test_push_back() {
let mut list = CircularList::new_single_node(1);
list.push_back(2);
list.push_back(3);
list.push_back(4);
list.traverse();
}接下来做删除，返回index和key的元组，分为两个部分，移动尾指针到指定位置和删除尾指针节点
fn m0ve(&mut self, count: usize){
if self.tail.is_none() || self.len == 0 {
return;
}
let mut current = self.tail.clone().unwrap();
for _ in 0..count {
let next = current.borrow().next.clone().unwrap();
current = next;
}
self.tail = Some(current);
}
fn delete(&mut self, count: usize) -> (usize, usize) {
if self.tail.is_none() || self.len == 0 {
panic!("Cannot delete from empty list");
}
// 先移动尾指针到指定位置
self.m0ve(count);
let tail_node = self.tail.clone().unwrap();
if self.len == 1 {
// 如果只有一个节点，删除后链表为空
let deleted_index = tail_node.borrow().index;
let deleted_key = tail_node.borrow().key;
self.tail = None;
self.len = 0;
return (deleted_index, deleted_key);
}
// 删除尾节点的下一个节点（即头节点）
let head_node = tail_node.borrow().next.clone().unwrap();
let deleted_index = head_node.borrow().index;
let deleted_key = head_node.borrow().key;
// 获取头节点的下一个节点
let new_head = head_node.borrow().next.clone().unwrap();
// 让尾节点直接指向新的头节点，跳过要删除的节点
tail_node.borrow_mut().next = Some(new_head);
self.len -= 1;
(deleted_index, deleted_key)
}
fn test_move_and_delete() {
let mut list = CircularList::new_single_node(1);
list.push_back(2);
list.push_back(3);
list.push_back(4);
assert_eq!(list.delete(3), (4,4));
//list.traverse();
}move并不是一个可用的函数名，所以这里用了m0ve
准备完毕，接下来就可以写约瑟夫环的运行函数了：
fn run(keys : Vec<usize>, m:usize) {
//构建环
let len = keys.len();
let mut bind = CircularList::new_single_node(keys[0]);
for i in 1..len {
bind.push_back(keys[i]);
}
//输出
let mut num = m;
for _ in 0..len {
let (index, new_num)= bind.delete(num - 1);//退一个
print!("{} ",index);
num = new_num;
}
}
#[test]
fn test_run() {
let test1 : Vec<usize> = vec![3,1,7,2,4,8,4];
CircularList::run(test1.clone(), 20);
}观察输出：
running 4 tests
6 1 4 7 2 3 5 test tests::test_move_and_delete ... ok
test tests::test_new ... ok
test tests::test_run ... ok
test tests::test_push_back ... ok完美