ECE 522 | Software Construction, Verification and Evolution Assignment 4: Lifetimes in List
A linked list is a linear data structure in which each element is a separate object. Every element in the list consists of two items:
– The data of this element.
– A reference to the next node.
Copyright By PowCoder代写 加微信 powcoder
The last node has a reference to an empty node. The entry point into a linked list is called the head of the list. It should be noted that head is not a separate node, but the reference to the first node. If the list is empty, then the head is an empty list.
A linked list is a dynamic data structure. The number of nodes in a list is not fixed and can grow and shrink on demand. Any application has to deal with an unknown number of objects within a linked list.
Source code: linked_list.zip
Question 1: Given the following implementation of a linked list in main.rs in the attached source code:
pub enum LinkedList
Head(T,Box
The code is missing the implementation for 4 functions, empty, new, push, and push_back.
a- Implement the function empty to return an empty linked list. The function should have the following signature:
pub fn empty()->Self{…}
b- Implement the function new which creates a new linked list with the following signature: pub fn new(t:T)->Self{…}
c- Implement the function push to insert a new element on the front of the list.
For example, if we have a list as follows:
2¡ú3¡ú5¡ú7 .push(1) should result in the following list:
1¡ú2¡ú3¡ú5¡ú7 1
ECE 522 | Software Construction, Verification and Evolution
The function has the following signature:
pub fn push(self, t:T)->Self{
d- Implement the function push_back to insert a new element at the back of the list. The function has the following signature:
pub fn push_back(&mut self, t:T){
Similarly, if we have a list as follows:
2¡ú3¡ú5¡ú7 push_back(1) should result in the following list:
2¡ú3¡ú5¡ú7¡ú1
e- Run the tests defined in the main function and make sure that all the tests pass successfully.
Question 2: Refer to the function cons (https://docs.rs/im/5.0.0/im/list/fn.cons.html) and
a- provide an explanation of the function, the answer should provide a description of what the
function does, and a detailed explanation of each parameter of the function.
b- Update your code in question 1 to use the function cons. (Use the crate ¡°im¡± version 5.0.0 for the function cons. You can also use the other functions in that crate. Please do not write the cons function from scratch.) Please save the updated code in a different project with the name: linked_list_question2.zip . Your code should use the following enum and pass the following test
use self::LinkedList::*; use im::list::*;
#[derive(Debug, PartialEq)] pub enum LinkedList
Head(List
impl
// Add your code here.
#[cfg(test)] mod tests{
use super::*;
ECE 522 | Software Construction, Verification and Evolution
fn it_works(){
let mut l = LinkedList::new(3);
l = l.push(4);
assert_eq!(l,Head(cons(4, cons(3, List::new())))); l.push_back(2);
assert_eq!(l,Head(cons(4, cons(3, cons(2,
List::new()))))); }
fn main(){
Question 3: Rust has a lot of smart pointers, such as Rc
enum Level { Low,
struct Task { id: u8,
level: Level }
fn main() {
let task = Task {
level: Level::High };
task.id=100;
println!(“Task with ID: {}”, task.id); }
Executing the previous example should result in an error, mention the error and explain how interior mutability can be applied to the problem to solve it. Rewrite the previous code so it runs. (Hint: Consider using Cell
Question 4: Consider the following program:
use std::cell::RefCell; use std::rc::Rc;
ECE 522 | Software Construction, Verification and Evolution
#[derive(Debug)] struct DoubleNode {
value: i32,
next: Rc
fn main() {
let node_a = DoubleNode { value: 100, next:
Rc::new(RefCell::new(None)), prev: Rc::new(RefCell::new(None))};
let a = Rc::new(RefCell::new(Some(node_a)));
let node_b = DoubleNode { value: 1000, next: Rc::clone(&a), prev: Rc::new(RefCell::new(None))};
let b = Rc::new(RefCell::new(Some(node_b)));
println!(” a is {:?}, rc count is {}”, a,Rc::strong_count(&a)); println!(” b is {:?}, rc count is {}”, b,Rc::strong_count(&b));
if let Some(ref mut x) = *a.borrow_mut() {(*x).prev = Rc::clone(&b);}
println!(” a rc count is {}”, Rc::strong_count(&a));
println!(” b rc count is {}”, Rc::strong_count(&b)); }
a- Explain what the program is doing?
b- Explain the data structure DoubleNode; what is it trying to implement?
c- Explain how Weak
d- Explain what is achieve by the line if let Some(ref mut x) = *a.borrow_mut() {(*x).prev = Rc::clone(&b);}
Question 5: Consider the following program, and supply the missing function.
use std::cell::RefCell; use std::rc::{Rc, Weak}; use std::fmt::Display;
// The node type stores the data and two pointers. It uses Option to represent nullability in safe Rust.
ECE 522 | Software Construction, Verification and Evolution
// It uses an Rc (Reference Counted) pointer to give ownership of the next node
// to the current node. And a Weak (weak Reference Counted) pointer to reference.
// the previous node without owning it.
// It uses RefCell for interior mutability. It allows mutation through shared references.
struct Node
prev: Option
next: Option
impl
// Constructs a node with some `data` initializing prev and next to null.
fn new(data: T) -> Self {
Self { data, prev: None, next: None }
// Appends `data` to the chain of nodes. The implementation is recursive.
fn append(node: &mut Rc
let is_last = node.borrow().next.is_none(); if is_last {
as the node
// If the current node is the last one, create a new
// set its prev pointer to the current node and store it after the current one.
let mut new_node = Node::new(data); new_node.prev = Some(Rc::downgrade(&node)); let rc = Rc::new(RefCell::new(new_node)); node.borrow_mut().next = Some(rc.clone()); Some(rc)
ECE 522 | Software Construction, Verification and Evolution
// Not the last node, just continue traversing the list:
if let Some(ref mut next) = node.borrow_mut().next { Self::append(next, data)
} else { None } }
// The doubly-linked list with pointers to the first and last nodes in the list.
struct List
first: Option
impl
// Constructs an empty list.
fn new() -> Self {
Self { first: None, last: None }
// Appends a new node to the list, handling the case where the list is empty.
fn append(&mut self, data: T) {
// ….. Write this function!
// Pretty-printing
impl
fn fmt(&self, w: &mut std::fmt::Formatter) -> std::result::Result<(), std::fmt::Error> {
write!(w, “[“)?;
let mut node = self.first.clone();
while let Some(n) = node {
write!(w, “{}”, n.borrow().data)?; node = n.borrow().next.clone();
if node.is_some() {
write!(w, “, “)?; }
write!(w, “]”)
fn main() { let mut
list = List::new(); println!(“{}”, list);
for i in 0..5 { list.append(i);
println!(“{}”, list); }
ECE 522 | Software Construction, Verification and Evolution
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com