数据结构与Rust开发实战

### 数据结构与Rust开发实战 在编程领域，数据结构是构建高效算法和程序的基础。本文将深入探讨几种重要的数据结构，包括二叉搜索树、哈希表和图，并介绍如何使用Rust语言实现它们。此外，还会介绍如何使用Rust进行Windows应用程序开发，以一个简单的计算器应用为例。 #### 二叉搜索树操作 二叉搜索树（Binary Search Tree, BST）是一种重要的树形数据结构，它具有排序性质，即左子树的所有节点值小于根节点值，右子树的所有节点值大于根节点值。以下是一些基本的BST操作代码示例： ```rust bst.insert(2); bst.insert(1); bst.insert(3); bst.insert(10); bst.insert(5); bst.insert(2); bst.in_order(&bst.root); println!("find 2 : {}", bst.find(2)); println!("find 5 : {}", bst.find(5)); println!("find 15 : {}", bst.find(15)); ``` 中序遍历（in-order traversal）BST总是按排序顺序打印值，这是BST的一个重要特性。 #### 哈希表 哈希表（Hash Table）是一种以关联方式存储数据的数据结构，它通过键（key）来存储和访问对应的值（value）。哈希表使用哈希函数将键映射到一个唯一的索引，从而实现快速的数据存储和访问。 ##### 哈希表原理 哈希表使用一个底层容器（通常是数组）来存储数据，并使用哈希函数计算容器中的索引（哈希码）。在理想情况下，哈希函数为每个键计算一个唯一的索引，但在实际应用中，可能会出现多个键映射到同一个索引的情况，这种现象称为哈希冲突（collision）。常见的处理哈希冲突的方法有两种： - **链地址法（Chaining）**：将多个条目存储在表中的同一索引处，像单链表一样将这些值链接起来。 - **线性探测法（Linear Probing）**：将第一个映射到某个索引的值存储在该索引的正确位置，对于后续映射到该索引的键，在表中搜索下一个未占用的索引。 ##### 哈希表实现 以下是一个使用Rust实现的简单哈希表示例，用于存储人员的姓名和净资产： ```rust pub fn hash(s: &String) -> usize { let mut result: usize = 5381; for c in s.bytes() { result = result*33 + c as usize; } result } #[derive(Default, Clone)] struct HashEntry { key: String, value: i32, in_use: bool, } pub struct HashTable { table: Vec<HashEntry>, } const TABLE_SIZE: usize = 10000; impl HashTable { pub fn new() -> Self { Self { table: vec![HashEntry::default(); TABLE_SIZE], } } pub fn insert(&mut self, key: String, new_value: i32) { if let Some(index) = self.get_index(&key) { self.table[index].value = new_value; } else { let mut index = hash(&key) % TABLE_SIZE; while self.table[index].in_use { index = (index + 1) % TABLE_SIZE; } self.table[index].in_use = true; self.table[index].key = key; self.table[index].value = new_value; } } fn get_index(&self, key: &String) -> Option<usize> { let mut index = hash(&key) % TABLE_SIZE; for _ in 0..TABLE_SIZE { if !self.table[index].in_use { break; } if self.table[index].key == *key { break; } index = (index + 1) % TABLE_SIZE; } if self.table[index].in_use && self.table[index].key == *key { Some(index) } else { None } } pub fn get(&self, key: &String) -> Option<&i32> { if let Some(index) = self.get_index(key) { Some(&self.table[index].value) } else { None } } } fn main() { let mut hash = HashTable::new(); hash.insert(String::from("abhishek"), 1_000_000); hash.insert(String::from("vijay"), 2_000_000); hash.insert(String::from("abhishek"), 1_500_000); let x:String = String::from("abhishek"); println!("value for {} = {}", x, hash.get(&x).unwrap()); } ``` 在上述代码中，我们使用了djb2哈希算法来计算哈希码。`HashEntry`结构体表示哈希表中的一个条目，包含键、值和一个布尔标志，用于表示该位置是否正在使用。`HashTable`结构体包含一个`HashEntry`向量，用于存储哈希表的所有条目。 #### 图及其表示 图（Graph）是一种由节点（顶点，Vertices）和边（Edges）组成的数据结构，边用于连接两个顶点。图可以分为有向图（Directed Graph）和无向图（Undirected Graph），取决于边是否有方向。 ##### 图的表示方法 图可以使用邻接表（Adjacency List）来表示，邻