“数据结构”课程设计

括号匹配的检验

检测括号序列是否匹配，例如 <{[]()}> 匹配， <{[()}]> 不匹配。

关键代码：

let mut stack: Vec<(usize, char)> = Vec::new();
for (i, c) in s.chars().enumerate() {
  if is_left(c) {
    stack.push((i, c));
  } else if is_right(c) {
    if stack.is_empty() {
      return Err(ParseError::Unpaired(vec![i]));
    }
    let (j, left) = stack.pop().unwrap();
    if !is_match(left, c) {
      return Err(ParseError::Unpaired(vec![j, i]));
    }
  } else {
    return Err(ParseError::UnknownChar(i, c));
  }
}
if !stack.is_empty() {
  return Err(ParseError::Unpaired(vec![stack.pop().unwrap().0]));
}
Ok(())

效果：

(123)
 ^ unknown character: '1'
(){[]<>}
ok
()[{]}
   ^^ bracket is not paired
{[]<>
^ bracket is not paired
[]{}) 
    ^ bracket is not paired

二叉树及应用

根据标记了空子树的前序遍历生成二叉树

输出前序、中序、后序遍历，和图形表示（类似 tree 命令）

关键代码：

struct BiTree {
  data: char,
  son: [Option<Box<BiTree>>; 2],
}
fn from_preorder_str(chars: &mut Chars) -> Option<Self> {
  let c = chars.next().unwrap();
  if c == '_' {
    None
  } else {
    let mut node = Self::from_char(c);
    if let Some(sub) = Self::from_preorder_str(chars) {
      node.son[0] = Some(Box::new(sub));
    }
    if let Some(sub) = Self::from_preorder_str(chars) {
      node.son[1] = Some(Box::new(sub));
    }
    Some(node)
  }
}
fn _preorder_str(&self, res: &mut String) {
  res.push(self.data);
  if let Some(son) = &self.son[0] {
    son._preorder_str(res);
  }
  if let Some(son) = &self.son[1] {
    son._preorder_str(res);
  }
}
fn _inorder_str(&self, res: &mut String) { ... }
fn _postorder_str(&self, res: &mut String) { ... }
fn _show(&self, res: &mut String, prefix: &mut String) {
  // ... 处理 prefix 字符串
  if let Some(son) = &self.son[1] {
    son._show(res, prefix);
  } else {
    res.push_str("*\n");
  }
  if let Some(son) = &self.son[0] {
    son._show(res, prefix);
  } else {
    res.push_str("*\n");
  }
  prefix.truncate(prefix_len);
}

效果：

ABC__DE_G__F___
Preorder: ABCDEGF
Inorder: CBEGDFA
Postorder: CGEFDBA
A
├─ *
└─ B
   ├─ D
   │  ├─ F
   │  │  ├─ *
   │  │  └─ *
   │  └─ E
   │     ├─ G
   │     │  ├─ *
   │     │  └─ *
   │     └─ *
   └─ C
      ├─ *
      └─ *

员工管理系统

每个员工的信息包括：编号、姓名、性别、出生年月、学历、职务、电话、住址等。

实现以下功能：

1. 排序：按不同关键字，对所有员工的信息进行排序。
2. 查询：按特定条件查找员工。
3. 更新：按编号对某个员工的某项信息进行修改。
4. 插入：加入新员工的信息。
5. 删除：按编号删除已离职的员工的信息。

原理：使用 BTreeMap 维护顺序，使用 Rc 维护主键， Weak 维护其他字段。

关键代码：

const STR_INFO_COUNT: usize = 5;
const FIELD_NAME: [&str; STR_INFO_COUNT] = [
  "name",
  "education",
  "position",
  "phone",
  "address",
];
pub struct Employee {
  id: u32,
  gender: Gender,
  birth: Date,
  email: Email,
  other: [String; STR_INFO_COUNT],
}
pub struct Manager {
  id_map: BTreeMap<u32, Rc<Employee>>,
  gender_map: BTreeMap<Gender, Vec<Weak<Employee>>>,
  birth_map: BTreeMap<Date, Vec<Weak<Employee>>>,
  email_map: BTreeMap<Email, Vec<Weak<Employee>>>,
  other_map: [BTreeMap<String, Vec<Weak<Employee>>>; STR_INFO_COUNT],
}
pub fn insert(&mut self, v: &[&str]) -> Result<(), &'static str> {
  let rc_emp = Rc::new(Employee::parse_str(v)?);
  let entry = self.id_map.entry(rc_emp.id);
  if let Occupied(_) = entry {
    return Err("Employee ID already exists");
  } else {
    entry.or_insert(rc_emp.clone());
  }
  self
    .gender_map
    .entry(rc_emp.gender.clone())
    .or_default()
    .push(Rc::downgrade(&rc_emp));
  // ... 处理其他字段
  Ok(())
}
pub fn get(&self, emp_id: u32) -> Option<&Employee> {
  self.id_map.get(&emp_id).map(|rc| rc.as_ref())
}
pub fn update(&mut self, emp_id: u32, v: &[&str]) -> Result<(), &'static str> {
  let emp = self.id_map.get_mut(&emp_id).ok_or("Employee not found")?;
  let new_emp = Employee::clone(emp).update(v)?;
  *emp = Rc::new(new_emp);
  Ok(())
}
pub fn sort_by(&mut self, field_name: &str) -> Result<Vec<Weak<Employee>>, &'static str> {
  Ok(match field_name {
    "id" => self
      .id_map
      .values()
      .map(|rc| Rc::downgrade(rc))
      .collect(),
    // ... 处理其他字段
  })
}

效果：

>> add id=1 name=a gender=m 

>> add name=b

>> add id=123 name=c gender=f

>> add id=3 email=abc
Failed to add employee: Invalid email

>> add id=3 email=abc@i

>> add id=3
Failed to add employee: Employee ID already exists

>> update 3 name=name3 phone=12345

>> add idd=5
Failed to add employee: Invalid field

>> add id=5 birth=2000-2-30
Failed to add employee: Invalid birth

>> add id=5 birth=2000-2-28

>> add id=6 name=y gender=suffix_automaton

>> sortby name
ID: 5 Gender:  Birth: 2000-2-28 Email:  name:  education:  position:  phone:  address: 
ID: 1 Gender: Male Birth: 0-0-0 Email:  name: a education:  position:  phone:  address: 
ID: 0 Gender:  Birth: 0-0-0 Email:  name: b education:  position:  phone:  address: 
ID: 123 Gender: Female Birth: 0-0-0 Email:  name: c education:  position:  phone:  address: 
ID: 6 Gender: suffix_automaton Birth: 0-0-0 Email:  name: y education:  position:  phone:  address: 

>> exit

总结