C++代写：ECE244LinkedLists

练习 Linked List 的用法，完成一个绘图管理的应用程序。
![Linked List](https://www.softwaretestinghelp.com/wp-
content/qa/uploads/2019/06/structure-of-a-singly-linked-list-300x70.png)

Objectives

The main objective of this assignment is to give you practice in creating and
manipulating linked lists in C++. In the process, the assignment re-enforces
earlier concepts of writing classes with constructors and the destructor. It
also serves as an exercise on dynamic allocation and de-allocation of data
without memory leaks. This is done by writing a program (called “the program”
hereafter) extending your previous lab assignment to represent the Shapes
database as a set of linked lists, but with a simplified set of commands in
which there are (mostly) no errors in input. This assignment will require more
code writing compared to the previous assignments. You are encouraged to start
early.

Problem Statement

The assignment consists of two parts. In the first part, you will write a
command parser similar to that of the previous lab. The parser provides a
textual input interface to your program. In contrast to the previous lab, you
need not check for errors in the input (with some exceptions). These commands
create shapes, create groups of shapes, move shapes across groups and delete
shapes/groups.
Each command consists of an operation keyword followed by arguments. The
command and the arguments are separated by one or more spaces. Thus, the code
you will write for this part of the assignment should take input from the
standard input, parse it, and print responses. The command parser loops,
processing input as long as input is available.
In the second part of the assignment, you will implement a linked list based
data structure to serve as a simple “database” of objects that store the
created shapes. To do so, you will implement several classes: Shape,
ShapeNode, ShapeList, GroupNode and GroupList.

Specifications

Similar to the previous lab, it is important that you follow the
specifications below carefully. Where the specification says shall or must (or
their negatives), following the instruction is required to receive credit for
the assignment. If instead it says may or can, these are optional suggestions.
The use of should indicates a recommendation; compliance is not specifically
required. However, some of the recommendations may hint at a known-good way to
do something or pertain to good programming style.
Example input and output for the program are provided in Section 4 for your
convenience. They do not cover all parts of the specification. You are
responsible for making sure your program meets the specification by reading
and applying the description below.

Coding Requirements

1. The code you will write shall be contained in only the source files named Parser.cpp, Shape.cpp, ShapeNode.cpp, ShapeList.cpp, GroupNode.cpp and GroupList.cpp. Skeletons of these files are released with the assignment’s zip file on the course website. The zip file also contains corresponding .h files: globals.h, Shape.h, ShapeNode.h. ShapeList.h, GroupNode.h and GroupList.h. These .h files contain comments that describe the classes defined in them and their methods. Please note that the .h files are NOT to be modified in any way. Modifying these files almost always results in a mark of 0 for the assignment. You may make use of helper functions to split up the code for readability and to make it easier to re-use. These functions (and their prototypes) must be in one of the aforementioned .cpp files. That is, you must not add any new .h or .cpp files.
2. Input and output must be done only using the C++ standard library streams cin and cout.
3. The stream input operator >> and associated functions such as fail() and eof() shall be used for all input. C-style IO such as printf and scanf shall not be used.
4. Strings shall be stored using the C++ library type string, and operations shall be done using its class members, not C-style strings.
5. C-library string-to-integer conversions (including but not limited to atoi, strtol, etc.) shall not be used.
6. The Standard Template Library (STL) shall not be used. The point of this assignment is for you to create your own linked list implementation.
7. Your program shall not leak memory. Unlike the previous assignment, you will be penalized for leaking memory.

Command Line Input

Input will be given one command on one line at a time. The entire command must
appear on one line. All input must be read using the C++ standard input cin.
The program shall indicate that it is ready to receive user input by prompting
with a greater-than sign followed by a single space (> ); see Section 4 for an
example. Input shall always be accepted one line at a time, with each line
terminated by a newline character.
Unlike the previous lab, you shall assume that input values are error-free
(i.e., commands are always valid, integers are always valid, no arguments are
missing, no extra arguments, etc.). Nonetheless, there will be some errors you
must check for and print an appropriate error message (see Section 3.3). In
this case, the input line shall be discarded, and processing shall resume at
the next line. The program shall continue to accept and process input until an
end-of-file (eof) condition is received.
Each line of valid input shall start with a command name, followed by zero or
more arguments, each separated by one or more space characters. The number and
type of arguments accepted depend on the command. The arguments and their
permissible types/ranges are shown below in
Table 1.

Argument	Description, type, and range
name	a string consisting of any non-whitespace characters3 ; except
strings that represent commands, shape types or reserved words (e.g., pool).
type	a string that represents the type of a shape and must be one of:
ellipse, rectangle or triangle
loc	a positive integer (0 or larger) that represents the location of the
shape in either the x or y dimension
size	a positive integer (0 or larger) that represents the size of a shape
in either the x or y dimension
The valid commands, their arguments, and their output if the command and its
arguments are all legal are shown below in Table 2. In the case of the draw
command, which takes no arguments, the program prints not only the message
shown in the table, but also all the groups and shapes in the database (see
the example in Section 4).
Command	Arguments
—	—
shape	name type loc loc size size
group	name
draw
move	name1 name2
delete	name
If there is an error, a message shall be displayed as described in Section
3.3. Otherwise, a successful command produces a single line of output on the
C++ standard output, cout, as shown in Table 2. The values in italics in Table
2 must be replaced with the values given by the command argument. Strings must
be reproduced exactly as entered. Where locs or sizes are printed, they shall
appear on the order entered in the command.

Error Checking

Errors shall cause a message to be printed to cout, consisting of the text
“error:” followed by a single space and the error message from Table 3. In the
messages, italicized values such as name

Error message	Cause
invalid name	The name used for a shape or a group is a reserved word
(e.g., a command word, a shape type or pool)
name name exists	A shape/group with the name name exists in the database,
i.e., has once been created and has not been deleted
shape name not found	A shape with the name name specified in a command
does not exist
group name not found	A group with the name name specified in a command
does not exist
should be replaced by the value causing the error. Error message output must
comply exactly (content, case, and spacing) with the table below to receive
credit. There are no trailing spaces following the text.
The program is not required to deal with errors other than those listed in
Table 3. Please note:

1. The commands and the shape types are case sensitive. Thus, while a shape or a group cannot be named pool or triangle, it can be named Pool or triAngle.
2. For every line of input, your program must output something. Either a message indicating success (Table 2) or an error (Table 3). For an empty line of input (nothing or just whitespace) your program should just output the command prompt.
3. You are guaranteed that autotester will not use test cases that have any errors other than the ones listed above. However, You may reuse your code from lab assignment 3 along with its error checking, if you wish. This part of your code will not be exercised or tested.

Program Use

Users of the program use the command line to create and delete shapes, similar
to the previous assignment. In addition, users can create and delete shape
groups, where a group is a collection of already created shapes. Finally,
users can “draw” the groups and shapes, meaning to print them to the standard
output.
A database is used to organize the shapes and the groups. When the database is
initially created, there is only one group called pool. A shape command
creates a new Shape object and this object is by default a member of the pool
group. The group command is used to create a new group, initially empty. The
move command is used to move a shape from the group it is currently in to a
new group (which can be the one it is currently in). A shape cannot belong to
more than one group.
The delete command can be used to delete shapes or groups. If used to delete a
shape, only the shape specified in the command is deleted from the group it
currently in. If the command is used to delete a group, then all the shapes in
the group are moved to the pool group and the group is deleted. The pool group
cannot be deleted (pool is a reserved word that cannot be used in commands or
as shape/group names).
The examples in Section 4 further illustrate the above commands, the actions
they take and the output they produce.

The Database

The program shall keep track of all shapes and groups using a linked list
based data structure. An example of which is shown in Figure 1. There is a
linked list of type GroupList s that represents the list of groups created
during program execution. Each node in the list is a GroupNode, which in turn
has a pointer to a ShapeList that represents the shapes belonging to the
group. A ShapeList is a linked list of ShapeNodes, where each ShapeNode has a
pointer to the Shape object it represents.
At the onset of execution, a GroupList object is created to represent a linked
list of GroupNodes. The list contains exactly one GroupNode with the name
pool. The ShapeList of the pool is initially empty. As shapes are created,
they are added the pool group by inserting them at the end of its ShapeList.
When new groups are created, they are added to the end of the GroupList. Thus,
the order of the groups on the GroupList is that of the order in which they
are created.
When a shape is deleted, it is removed from the ShapeList of the group it
currently belongs to. When a group is deleted, all the ShapeNodes in it
ShapeList are added at the end of the pool’s ShapeList, keeping their order,
and the corresponding GroupNode is deleted from the GroupList.
It is critical that your program deletes all dynamic data it allocates so as
no memory leaks occur. In this assignment, memory leaks will be checked for
and reported by exercise and the autotester, and there is penalty for having
memory leaks. It is highly recommended that you use the valgrind memory
checking program. A tutorial on valgrind as released with the previous
assignment. Please learn and use this tool. It is used by exercise to check
for memory leaks in your code.

Program Classes and Files

The Shape Class

The Shape class holds the properties of a shape, including its name, type,
location, and size. It is mostly identical to the Shape class in the previous
assignment. The definition of the class appears in Shape.h. Examine the file
and read through the comments to understand the variables and methods of the
class. You must implement this class in the file Shape.cpp.

The ShapeNode Class

This class defines a node in a linked list of ShapeNodes. It has two data
members: myShape, which points to the Shape object associated with the node,
and next, which is a pointer to the next ShapeNode in a list. It is defined in
the file ShapeNode.h and you must implement this class in the file
ShapeNode.cpp. Read through the comments in ShapeNode.h to find out what the
methods of the class do.

The GroupNode Class

This class defines a node in a linked list of GroupNodes. It has three data
members: name, which stores the name of the group, myShapeList, which points
to the ShapeList object associated with the group, and next, which is a
pointer to the next GroupNode in a list. It is defined in the file GroupNode.h
and you must implement this class in the file GroupNode.cpp. Again, read
through the comments in GroupNode.h to find out what the methods of the class
do.

The ShapeList Class

This class defines a linked list of ShapeNodes. It contains a single data
member, head, which points to the first ShapeNode in the list. It is defined
in the file ShapeList.h and the files contains comments that describe what the
methods of the class do. You must implement this class in ShapeList.cpp.

The GroupList Class

This class defined a linked list of GroupNodess. It contains one data member
called head, which is a pointer to the first GroupNode in the list. The class
is defined in the file GroupList.h and you must implement it in the file
GroupList.cpp. The comments in the GroupList.h indicate what the methods of
the class should do.

The Command Line Parser

A suggested (but not mandatory) structure for your command line parser appears
in the skeleton Parser.cpp file released within the assignment’s zip file. It
is identical to that of the previous assignment and it is recommended that you
reuse your code from that assignment.

Examples

An Annotated Example

The program when first started, is ready to receive input:
>
Now the user types a command (ending with Enter) to create a new rectangle
called sqr located at x and y positions of 10 and 10 and with a x and y sizes
of 30 and 40:
> shape sqr rectangle 10 10 30 40
To which the program should respond with the message indicating the successful
creation of the shape:
sqr: rectangle 10 10 30 40
The user then creates a new ellipse called circ:
> shape circ ellipse 30 40 10 10
To which the program should respond with the message for a successful creation
of a shape:
circ: ellipse 30 40 10 10
The user then creates a new triangle called trig:
> shape trig triangle 60 80 30 50
To which the program should respond with the message for a successful creation
of a shape:
trig: triangle 60 80 30 50
The user issues a draw command and the following is printed:
drawing:
pool:
sqr: rectangle 10 10 30 40
circ: ellipse 30 40 10 10
trig: triangle 60 80 30 50
Observe how the shapes belong to the pool group and are printed in the order
in which they were created. Now the user creates a new group called no
corners:
group no_corners
The program should respond by printing:
no_corners: group
The user issues a draw command and the following is printed:
drawing:
pool:
sqr: rectangle 10 10 30 40
circ: ellipse 30 40 10 10
trig: triangle 60 80 30 50
no_corners:
Observe how the no corners group is printed after the pool group and is empty.
Now, the user moves the shape circ to the group no corners:
move circ no_corners
The program should respond:
moved circ to no_corners
The user issues a draw command and the following is printed:
drawing:
pool:
sqr: rectangle 10 10 30 40
trig: triangle 60 80 30 50
no_corners:
circ: ellipse 30 40 10 10
Observe how the circ is now in the no corners group and is removed from the
pool group. The user deletes the no corners group:
delete no_corners
The program should respond as:
no_corners: deleted
Finally, the user issues a draw command and the following is printed:
drawing:
pool:
sqr: rectangle 10 10 30 40
trig: triangle 60 80 30 50
circ: ellipse 30 40 10 10
Observe how the group no corners is no longer printed since it is deleted.
Also observe how circ is back at the end of the pool group.

Full session

The following is an example session. Note that the text from the prompt (> )
up to the end of the line is typed by the user, whereas the prompt and line
without a prompt are program output.
> shape my_circle ellipse 50 65 20 20
my_circle: ellipse 50 65 20 20
> shape my_square rectangle 100 150 60 60
my_square: rectangle 100 150 60 60
> shape a_circle ellipse 120 200 40 40
a_circle: ellipse 120 200 40 40
> shape my_triangle triangle 40 75 90 90
my_triangle: triangle 40 75 90 90
> draw
drawing:
pool:
my_circle: ellipse 50 65 20 20
my_square: rectangle 100 150 60 60
a_circle: ellipse 120 200 40 40
my_triangle: triangle 40 75 90 90
> group my_first_group
my_first_group: group
> shape my_rectangle rectangle 100 275 90 180
my_rectangle: rectangle 100 275 90 180
> shape my_rectangle triangle 70 50 10 5
error: name my_rectangle exists
> shape second_triangle triangle 70 50 10 5
second_triangle: triangle 70 50 10 5
> draw
drawing:
pool:
my_circle: ellipse 50 65 20 20
my_square: rectangle 100 150 60 60
a_circle: ellipse 120 200 40 40
my_triangle: triangle 40 75 90 90
my_rectangle: rectangle 100 275 90 180
second_triangle: triangle 70 50 10 5
my_first_group:
> move my_triangle my_first_group
moved my_triangle to my_first_group
> move my_circle my_first_group
moved my_circle to my_first_group
> draw
drawing:
pool:
my_square: rectangle 100 150 60 60
a_circle: ellipse 120 200 40 40
my_rectangle: rectangle 100 275 90 180
second_triangle: triangle 70 50 10 5
my_first_group:
my_triangle: triangle 40 75 90 90
my_circle: ellipse 50 65 20 20
> delete my_first_group
my_first_group: deleted
> draw
drawing:
pool:
my_square: rectangle 100 150 60 60
a_circle: ellipse 120 200 40 40
my_rectangle: rectangle 100 275 90 180
second_triangle: triangle 70 50 10 5
my_triangle: triangle 40 75 90 90
my_circle: ellipse 50 65 20 20
> delete pool
error: invalid name
> delete abc
error: shape abc not found
>

Procedure

Create a sub-directory called lab4 in your ece244 directory, and set its
permissions so no one else can read it. Download the lab4.zip file, un-zip it
and place the resulting files in the lab4 directory.
In the release, there are 6 .h files: globals.h, Shape.h, ShapeNode.h,
ShapeList.h, GroupNode.h and GroupList.h. The first has a number of global
definitions and the remaining ones define the various classes, as described in
Section 3.6. You may NOT modify these files to add to or delete from their
content. Modifying the files commonly results in a mark of zero for the
assignment.
In the release, there are also 6 .cpp files in which you will add your code:
Parser.cpp, Shape.cpp, ShapeNode.cpp, ShapeList.cpp, GroupNode.cpp and
GroupList.cpp. In the first file, you will implement the command parser code.
In the rest you will implement the various classes described in Section 3.6.
Finally, there is a Makefile that is used by NetBeans to separately compile
your project. Do not modify this file either.
Write and test the program to conform to the specifications laid out in
Section 3. The example sessions in Section 4 may be used for testing. Further,
there is a reference executable provided. When in doubt, run the executable to
observe its behaviour. Should there be any conflict between the specifications
in this handout and the reference executable, please follow what the reference
executable does. To execute the reference solution, run the following command:
~ece244i/public/Parser.exe
The ~ece244i/public/exercise command will also be helpful in testing your
program. You should exercise the executable, i.e., Parser.exe, using the
command:
~ece244i/public/exercise 4 Parser.exe
As with previous assignments, some of the exercise test cases will be used by
the autotester during marking of your assignment. We will not provide all the
autotester test cases in exercise.
It is highly recommended to create additional test cases yourself to ensure
you fully meet the specification listed above.

Deliverables

Submit the Parser.cpp, Shape.cpp, ShapeNode.cpp, ShapeList.cpp, GroupNode.cpp
and GroupList.cpp files as lab 4 using the command
~ece244i/public/submit 4