第一个项目
创建一个对链表处理的库,包含链表新建,插入,获取元素,反转,排序等。具体功能在开发的时候详细说明。
链表
链表是一种常见的数据结构,它由一系列节点组成,每个节点包含数据元素和指向下一个节点的引用。链表可以分为单向链表、双向链表和循环链表等不同类型。
单向链表中,每个节点包含一个数据元素和一个指向下一个节点的引用。最后一个节点的引用通常为空(null)。
双向链表中,每个节点除了包含数据元素和指向下一个节点的引用外,还包含指向前一个节点的引用。
循环链表是一种特殊的链表,其中最后一个节点指向第一个节点,形成一个循环。
链表的优点是插入和删除操作效率高,时间复杂度为O(1)。然而,链表的缺点是访问元素的效率较低,需要遍历整个链表,时间复杂度为O(n)。
头结点
带头结点的链表是指在链表的头部增加一个空节点,这个节点不存储数据,仅用于简化链表操作。不带头结点的链表则直接从存储数据的第一个节点开始。
带头结点的链表在实现上更加简单,因为不需要特殊处理头节点为空的情况,而不带头结点的链表则需要额外处理头节点为空的情况。带头结点的链表可以简化插入和删除操作的代码逻辑,但会浪费一个节点的存储空间。
接下来没有特殊说明我们的链表都默认带头结点,而头结点的值设为其包含的元素个数。
创建一个库项目
cargo new --lib 库名
定义链表
#[derive(Debug)]
pub struct LinkedNode
data: T,
next: Option
}
#[derive(Debug)]
pub struct LinkedList
head: Option
}
定义节点的结构体LinkedNode,它包含一个data字段,存储当前节点的数据,next字段是一个枚举类型,包含了指向下一个节点的指针。定义了链表的结构体LinkedList,它包含一个字段head,是一个枚举类型,包含了一个指向第一个节点的指针。
从上面的代码中,其实我们发现LinkedNode结构体就已经使用和表示链表结构,为什么还要创建一个新的结构体Linked_list来将Node封装进去呢?
LinkedNode
抽象层次: Node
在实践中,这种分层设计的方式通常有助于提高代码的清晰度、可维护性和可拓展性。
新建表
impl
pub fn new(value: T) -> Self {
LinkedNode {
data: value,
next: None,
}
}
}
impl
pub fn new(value: T) -> Self {
LinkedList {
head: Some(Box::new(LinkedNode::new(value))),
}
}
}
编写测试
先使用属性宏#[cfg(test)]来标记一个测试模块,该属性指示编译器仅在测试的时候被编译。同时使用#[test]来标记一个测试函数。
// Unit tests
#[cfg(test)]
mod test {
use super::*;
#[test]
fn test_linked_node() {
let node = LinkedNode::new(1);
assert_eq!(node.data, 1);
}
#[test]
fn test_linked_list() {
let list = LinkedList::new(1);
assert_eq!(list.head.as_ref().unwrap().data, 1);
}
}
运行测试
运行 cargo test 命令时,会触发 Rust 项目中的测试套件,并执行所有标记为测试函数的代码块。
测试通过 ✅
版本管理
我们的项目第一步初步搭建已经完成了,为了方便对项目进行管理,我们使用Git。
如果没有接触过Git可以自行搜索其相关的用法,并不复杂,后续我们的项目都是基于Git进行版本管理的。
rust使用cargo创建一个项目的时候,如果你上级目录没有git仓库,或者你没有特殊禁用生成git仓库,它会自动给你初始化一个git仓库
# 项目根目录下初始化一个git仓库
git init
# 将已经修改的项目添加到暂存区
git add .
# 将暂存区的内容提交到本地仓库
git commit -m "相关内容的描述"
#
现在我们将一个初始项目搭建起来了,后续我们的开发流程在确定要实现某一个功能后就在如下几个环节之间循环开发:
编写测试 -> 运行测试 -> 修复错误 -> 测试通过 -> 版本管理
下一章我们将对链表的数据进行增删改查。
推荐文章
发表评论