题目：
（一）：二叉排序树
- 问题：从键盘输入数据建立二叉排序树，实现查找、遍历和格式化打印
- 要求：建立BST，实现查找（成功/不成功），计算查找长度
- 测试：自行设计测试数据，注意边界情况
（二）：哈希表设计
- 问题：为30个中文拼音人名设计哈希表，平均查找长度≤2
- 要求：使用除留余数法构造哈希函数，可选线性探测、再散列或链地址法处理冲突
- 测试：使用熟悉的30个人名作为数据
（三）：实现二叉排序树的插入和删除功能
（四）：从教科书上介绍的哈希函数构造方法中选出适用者并设计几个不同的哈希函数，
比较他们的地址冲突率（可以用更大的名字集合作实验）。
（五）：研究必做实验（2）的30个人名的特点，努力找一个哈希函数，
使得对于不同的拼音名一定不发生地址冲突。
（六）：在哈希函数确定的前提下尝试各种不同处理冲突的方法，
考察平均查找长度的变化和造好的哈希表中关键字的聚集性。二叉排序树
数据结构可以照搬之前的二叉树，这里做了微调：
use anyhow::{Context, Result};
struct SearchTree{
root : Option<Box<Node>>
}
struct Node{
value : i32,
left : Option<Box<Node>>,
right : Option<Box<Node>>,
}
impl SearchTree {
fn new () -> SearchTree {
SearchTree{
root : None,
}
}
fn insert (&mut self, value : i32) {
if self.root.is_none() {
self.root = Some(Box::new(Node{value : value, left : None, right : None}));
}else {
if let Some(ref mut node) = self.root {
node.insert(value);
}
}
}
fn build(&mut self, values : Vec<i32>) {
for v in values {
self.insert(v);
}
}
fn search(&self, value : i32) -> Option<bool> {
if self.root.is_none() {
return Option::None;
}else{
let root = self.root.as_ref().unwrap();
let (result, depth )= root.search(value,0);
println!("查找次数: {}",depth + 1);
result
}
}
fn print(&self) {
if let Some(root) = self.root.as_ref() {
root.print(0);
}
}
// 默认使用中序遍历了
fn traverse (&self) {
if let Some(root) = self.root.as_ref() {
root.in_order_traverse();
}
}
fn delete (&mut self, value : i32) -> Result<()>{
if self.root.is_some() {
self.root = Node::delete(self.root.take(), value);
Ok(())
}else {
anyhow::bail!("根节点为空")
}
}
}
impl Node{
fn insert (&mut self, value : i32) {
if value == self.value {
return;
}else if value > self.value {
match self.right{
Some(ref mut node) => node.insert(value),
None => self.right = Some(Box::new(Node{value : value, left : None, right : None}))
}
}else{
match self.left{
Some(ref mut node) => node.insert(value),
None => self.left = Some(Box::new(Node{value : value, left : None, right : None}))
}
}
}
fn search(&self, target : i32, depth : usize) -> (Option<bool>,usize) {
match self.value {
val if val == target => (Some(true),depth),
val if val < target => {
// 去右子树找
match self.right {
Some(ref node) => node.search(target, depth + 1),
None => (Some(false),depth)
}
}
val if val > target => {
// 去左子树找
match self.left {
Some(ref node) => node.search(target, depth + 1),
None => (Some(false),depth)
}
}
_ => (None,depth),
}
}
fn print(&self, depth : usize) {
if let Some(r) = &self.right {
r.print(depth + 1);
}
let spaces = " ".repeat(depth * 2);
println!("{}{}", spaces, self.value);
if let Some(l) = &self.left {
l.print(depth + 1);
}
}
fn pre_order_traverse(&self) {
println!("{}",self.value);
if let Some(l) = &self.left {
l.pre_order_traverse();
}
if let Some(r) = &self.right {
r.pre_order_traverse();
}
}
fn in_order_traverse(&self) {
if let Some(l) = &self.left {
l.in_order_traverse();
}
println!("{}",self.value);
if let Some(r) = &self.right {
r.in_order_traverse();
}
}
fn delete(root: Option<Box<Node>>, target : i32) -> Option<Box<Node>> {
let mut node = root?;
let v = node.value;
if v < target {
node.right = Self::delete(node.right.take(), target);
Some(node)
} else if v > target {
node.left = Self::delete(node.left.take(), target);
Some(node)
} else if v == target {
match (node.left.take(), node.right.take()) {
// 无子节点
(None, None) => None,
// 只有一个子节点
(left @ Some(_), None) => left,
(None, right @ Some(_)) => right,
// 有两个子节点可以用左子树的最大节点或右子树的最小节点替换，或者直接用左孩子替换再把右子树接到末尾
(Some(left), Some(right)) => {
let min_val = Self::min_value(&right);
let mut new_node = Box::new(Node {
value: min_val,
left: Some(left),
right: None,
});
// 删除右子树中的最小节点
new_node.right = Self::delete(Some(right), min_val);
Some(new_node)
}
}
}else {
None
}
}
fn min_value(node: &Box<Node>) -> i32 {
let mut current = node;
while let Some(left) = ¤t.left {
current = left;
}
current.value
}
}两层结构体，SearchTree对所有功能进行了一次封装
大部分实现都很常规，唯一麻烦的是删除操作，虽然递归的所有权问题很麻烦，但依然要比遍历看着简单
还有min_value也是一种妥协，如果要返回Option
测试：
#[cfg(test)]
mod tests {
use crate::SearchTree;
//#[test]
fn test_insert(){
let mut tree = SearchTree::new();
assert_eq!(tree.search(0), Option::None);
let nums = vec![3,8,3,2,4,1,5,9,16];
tree.build(nums);
assert_eq!(tree.search(3), Some(true));
assert_eq!(tree.search(5), Some(true));
assert_eq!(tree.search(9), Some(true));
assert_eq!(tree.search(16), Some(true));
assert_eq!(tree.search(33), Some(false));
}
//#[test]
fn test_print(){
let mut tree = SearchTree::new();
let nums = vec![3,8,3,2,4,1,5,9,16];
tree.build(nums);
tree.traverse();
tree.print();
}
#[test]
fn test_delete(){
let mut tree = SearchTree::new();
// 插入和搜索
tree.build(vec![5, 3, 7, 2, 4, 6, 8]);
assert_eq!(tree.search(5), Some(true));
assert_eq!(tree.search(3), Some(true));
assert_eq!(tree.search(10), Some(false));
// 删除叶子节点
tree.delete(2).unwrap();
assert_eq!(tree.search(2), Some(false));
// 删除有一个子节点的节点
tree.delete(7).unwrap();
assert_eq!(tree.search(7), Some(false));
assert_eq!(tree.search(6), Some(true));
// 删除有两个子节点的节点
tree.delete(5).unwrap();
assert_eq!(tree.search(5), Some(false));
// 验证树仍然有效
tree.print();
tree.traverse();
}
}哈希表
没规定哈希表的大小，凭直觉填45了
基本实现：
use anyhow::Result;
struct MyHash{
data : Vec<Option<String>>,
len : usize,
}
impl MyHash {
fn new() -> MyHash {
let len = 45;
let table = vec![Option::None;len];
MyHash{
data : table,
len
}
}
fn hash_1(&self, input : &str) -> usize{
let len = input.len();
let mut total: usize = 0;
for i in 0..len{
total += input.as_bytes()[i] as usize;
}
println!("Hash of {} is {}", input, total% self.len);
total % (self.len - 2) // 43，质数
}
fn insert(&mut self , input : &str) -> anyhow::Result<()> {
// 哈希映射
let index = self.hash_1(input);
let start = index;
let mut current = index;
loop {
if self.data[current].is_none() {
self.data[current] = Some(input.to_string());
return Ok(());
}
current = (current + 1) % self.len;
if current == start {
anyhow::bail!("表已满！");
}
}
}
fn find(&self , key:&str) -> (bool,usize){
let index = self.hash_1(key);
let start = index;
let mut current = index;
let mut length = 1;
loop{
if let Some(val) = self.data[current].as_ref(){
if val == key{
return (true,length);
}
}
current = (current + 1) % self.len;
length += 1;
if current == start || self.data[current].is_none(){
return (false,length)
}
}
}
}
#[cfg(test)]
mod tests {
use crate::hash::MyHash;
//#[test]
fn test_hash() {
let mut myHash = MyHash::new();
let names = ["abc", "bac", "caa", "dee", "hello", "renming"];
for name in names.iter(){
myHash.insert(name);
}
for name in names.iter(){
assert!(myHash.find(name).0);
}
}
#[test]
fn test_find() {
let mut table = MyHash::new();
let test_names = vec![
"rust","cargo","c","cpp","c_sharp","python","java","ruby","haskell","elixir",
"kotlin","lua","javascript","typescript","jerryscript","go","maven","docker","k8s","zig",
"Swift","php","asm","auceptin","tokio","sqlx","request","tauri","tracing","anyhow"
];
// 插入所有名字
for name in &test_names {
table.insert(name).unwrap();
}
let mut total_search_length = 0;
for name in &test_names {
let (found, length) = table.find(name);
assert!(found, "插入的名字应该能找到: {}", name);
total_search_length += length;
}
let average = total_search_length as f64 / test_names.len() as f64;
println!("平均查找长度：{}",average);
assert!(average.abs() < 2f64);
}
}现在的平均查找长度是：1.6666666666666667
再测试几个哈希函数：
- 直接定址法： 2.933333333333333
- 平方取中法： 1.9666666666666666
- 乘余取整法： 3.4
- 折叠法 ：1.4333333333333333
也跟这些办法的具体实现有关：
fn hash_1(&self, input : &str) -> usize{
let method = 4;
match method {
0 => {
// 除留余数法
let len = input.len();
let mut total: usize = 0;
for i in 0..len{
total += input.as_bytes()[i] as usize;
}
println!("Hash of {} is {}", input, total% self.len);
total % (self.len - 2) // 43，质数
}
1 =>{
// 直接定址法
if !input.is_empty() {
// 取ASCII加和为key
let len = input.len();
let mut total: usize = 0;
for i in 0..len{
total += input.as_bytes()[i] as usize;
}
// 加上字符串长度作为偏移
total.wrapping_add(input.len()) % self.len
} else {
0
}
}
2 =>{
// 平方取中法
let mut total: usize = 0;
// 将字符串转换为一个大数
for &b in input.as_bytes() {
total = total.wrapping_mul(31).wrapping_add(b as usize);
}
// 平方
let square = total.wrapping_mul(total);
// 取中间几位（取32位的中间16位）
let middle = (square >> 8) & 0xFFFF;
middle as usize % self.len
}
3 => {
// 乘余取整法
let a: f64 = 0.6180339887; // 黄金分割数
let mut k: f64 = 0.0;
// 将字符串转换为数值
for &b in input.as_bytes() {
k = k * 256.0 + b as f64;
}
// 取小数部分
let fractional = (k * a) % 1.0;
// 乘以表大小
(fractional * self.len as f64).floor() as usize
}
_ =>{
// 折叠法
let chunk_size = 4; // 每4个字符一组
let bytes = input.as_bytes();
let mut sum: usize = 0;
for chunk in bytes.chunks(chunk_size) {
let mut chunk_value: usize = 0;
for &b in chunk {
chunk_value = (chunk_value << 8) | (b as usize);
}
sum = sum.wrapping_add(chunk_value);
}
sum % self.len
}
}
}五和六逃了