CPSC 221程序代做、代写C/C++编程设计

日期：2021-02-11 11:22

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/pl/course_instance/2287/instance_question/3710450/?variant_id=1424786 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