PA1.1 – CPSC 221 | PrairieLearn
PA1.1. PA1 (2020W2)
Due: Feb 8, 23:59
Goals and Overview
In this PA (Programming Assignment) you will:
learn about the course programming environment
learn about vectors
learn about pointers
learn about linked lists
learn about management of dynamic memory
The Assignment
Problem Specification
A Linked List is a dynamic linear structure designed to hold any type of data. In this exercise,
we develop and use a linked list to manipulate blocks of pixels from an image.
We have broken the image below into 10 equal-width vertical strips called Blocks.
(artwork by Mrs. Tabitha Eller)
Each Block is placed in a Node of a Chain, in order from left to right as shown here:
The Chain can be rearranged, and the image reassembled to create a puzzle.
Programming
Assignment 1
Assessment overview
Total points: 5/14
Score: 35%
Question
Value:
History:
Awarded points:
Report an error in this
question
14
5
5/14
Previous question Next question
Attached files
No attached files
Attach a file
Attach text
2021/2/9 PA1.1 – CPSC 221 | PrairieLearn
https://ca.prairielearn.org/p… 2/5
Your code will take such a scrambled image and unscramble it!
We have provided a starting point for achieving this functionality. It is your task to complete
and expand on our implementation.
The diagram above illustrates the infrastructure of the chain. Most notably, it is a doubly-linked
list, with a head pointer to the first node. Each node in a doubly-linked list contains two
pointers, one to the previous node in the list prev and one to the next node next. The prev
pointer of the first node and the next pointer of the last node are NULL.
Specifications for each function you write are contained in the given code. The list of functions
here should serve as a checklist for completing the exercise.
In block.cpp
int width() const: Return the width of the current block.
int height() const: Return the height of the current block.
void build(PNG & im, int x, int width): From the PNG image im, grab the vertical,
rectangular strip of pixels whose upper left corner is at position (x,0), and whose
dimensions are width by height of the image im.
void render(PNG & im, int x) const: Draw the current block at position (x,0) in im.
In chain.cpp
void clear(): Helper function for destructor and assignment operator.
void copy(const Chain & other): Helper function for copy constructor and assignment
operator.
~Chain(): Destructor.
Node insertAfter(Node p, const Block & ndata): Insert a new node after the node
pointed to by p in the Chain.
void swap(Node p, Node q): Swaps the two nodes pointed to by p and q in the Chain.
void unscramble(): Rearranges the Chain into its original order based on minimizing the
difference between adjacent blocks.
Implementation Constraints and Advice
We will be grading your work on functionality, efficiency, and memory use. All Chain
functionality, aside from the insert and the copy functions, can be achieved by moving existing
nodes, rather than by allocating new ones and/or making copies. If you are tempted to use the
new function when you are manipulating the Chain, ask yourself if you can achieve your goal by
reassigning pointers, instead.
Finally, you’ll note that we are asking you to implement special memory management functions
(constructor, destructor, assignment) for the Chain class. You should ask yourself why we have
not made similar requests for the Block class. Why doesn’t it need a destructor, copy