本次加拿大代写是lisp数据结构编程的一个Lab

Learning objectives of this lab

Students who successfully complete this lab should be able to

1. write programs that use lisp’s built-in list data structure
2. describe and develop programs that manipulate programmer-defined singly-linked “cons cell” lists
3. describe the algorithmic complexity of list operators

Exercise 1

Preamble

1. On emacs, C-x C-f to create a new file called slinked-lib.lisp, copy-paste the code below in it, then C-x C-s to save it. The program below
provides data structures and functions that allow for the manipulation of singly-linked lists.

(defstruct node
data next)

(defstruct my-list
(head nil :type (or node null))
(tail nil :type (or node null))
(size 0 :type (integer 0)))

;; Constructors

(defun cr-listn (n)
“Creates a singly-linked list of size n initializing the DATA slot to 0.”
(if (zerop n) (make-my-list)
(my-cons 0 (cr-listn (1- n)))))

(defun my-cons (data list)
“Analogous to CONS but operates on a singly-linked list.”
(when (null list) (:= list (make-my-list)))
(let ((new-head (make-node :data data
:next (my-list-head list))))
(make-my-list :head new-head
:tail (my-list-head list)
:size (1+ (my-list-size list)))))

;; Accessors

(defun my-car (list)
“Analogous to CAR but operates on a singly-linked list.”
(let ((item (my-list-head list)))
(when item (node-data item))))

(defun my-cdr (list)
“Analogous to CDR but operates on a singly-linked list.”
(let ((tail (my-list-tail list)))

(if tail
(make-my-list :head tail
:tail (node-next tail)
:size (1- (my-list-size list)))
(make-my-list)))) ;returns an empty cons cell list
(defun my-elt (list index)
“Analogous to ELT but operates on a singly-linked list.”
(when (and (>= index 0) (< index (my-list-size list)))
(labels ((elt-aux (list i)
(if (zerop i) (my-car list)
(elt-aux (my-cdr list) (1- i)))))
(elt-aux list index))))
;; Modifier
(defun my-setf (list index value)
“Analogous to SETF but operates on a singly-linked list.”
(when (and (>= index 0) (< index (my-list-size list)))
(labels ((setf-aux (list i)
(if (zerop i) (setf (node-data (my-list-head list)) value)
(setf-aux (my-cdr list) (1- i)))))
(setf-aux list index))))

2. Load slinked-lib.lisp on the REPL

RTL-USER> (load “slinked-lists.lisp”)

What you are asked

Mofify timing-graph-frwrk.lisp to accomplish the following:

1. Using generate-points as a source of inspiration, write a function (you can choose any name you want for it) that compares the performance
of Common Lisp’s function elt, which operates on regular lists, and function my-elt (see code above), which operates on singly-linked lists.
You should use your favourite graph plotting tool (e.g., gnuplot) to generate two plots from the two data files created by your modified timing-
graph-frwrk.lisp program: one showing Lisp’s elt efficiency and another showing my-elt efficiency.

Note: If you feel lost on how to start, go back to Lab03 and see how the plot generation was done there.

Lastly, save these two images inside Exercise-1/ directory and call them efficiency-plot-elt.png and efficiency-plot-my-elt.png, repectively.

2. Create a text file called efficiency-analysis.txt and in it, answer the following questions:

1. By referencing the plot, what is the time complexity of elt?
2. By referencing the plot, what is the time complexity of my-elt?
3. Which is more efficient of the two functions (elt and my-elt) and why? Explain your reasoning by refering to the graphs.