Homework 2 : Classes and Data Structure Answer
Homework 2 : Classes and Data Structure
C++ : CS111 EIE111 LP104
Macau Univ. of Sci. and Tech. 2021 Spring
Instructor: Zhiyao Liang
April 23 2021
源码传送门
传送门：https://pan.baidu.com/s/1rJeuQQrrSyfoOx0ObdOWmA?pwd=1111
I. Purpose and ideas of the homework
We will design C++ classes to implement the data structures of linked list, stack, and queue. At least 5 classes will be defined and tested. This
homework covers the knowledge up to chapter 11 of the textbook [2]. Some ideas of abstract data type and data structure, such as the circulararray based queue, are described in Chapter 17 of the C textbook [3] that we learned in the previous semester.
In this homework, all the data are simply integers. You can upgrade the program later so that all types of data can possibly be managed by these
data structures.
For using operator overloading, you may find that there are many choices on which operator to be overloaded, what are the parameters and return
values of these functions. There are subtle issues of overloading prefix vs. postfix operators [4]. A task of this homework is designing some
operator to be overloaded.
One area of C++ that we have not touched is error handling using exceptions. Therefore, be careful when you use some library functions or
operators of C++ if you want to handle errors, because maybe C++ uses exceptions, instead of return values to represent errors. For example, the
new operator in C++ throws exceptions, when allocating memory has error, and never returns NULL , that is unlike the C's malloc() functions
[5]. Therefore, in the suggested way of implementing a linked list class, there is no handling of errors when using new to create a node. The only
conditions that need be checked. Exceptions are described in Chapter 15 of [2], and on some webpages like [6].
II. Tasks of the homework
We will write a C++ program.
Task 1: prepare the files:
The program contains 7 files:
- list.h : It contains the declaration code of the class List .
- list.cpp It contains the function definitions of the class List .
- stack.h It contains the declarations of the two stack classes ArrStack and ListStack
- stack.cpp : It contains the function definitions of the two stack classes ArrStack and ListStack .
- queue.h : It contains the declarations of the two queue classes ArrQueue and ListQueue .
- queue.cpp : It contains the function definitions of the two queue classes ArrQueue and ListQueue .
- driver.cpp : It contains the main function, which tests the 5 classes.
Tasks 2: A class of linked list
Write the code of a class List . Create two files list.h and list.cpp . Put the declaration code of the class List in list.h , and put the
function definitions of List in list.cpp .
A list node is described by a structure type Node that contains the following members:
- data , which is an integer.
- prev , a pointer pointing to the previous (left) neighbor node. It is NULL when there is no previous neighbor.
- next , a pointer pointing to the next (right) neighbor node. It is NULL when there is no next neighbor.
A doubly-linked list of nodes is described by a class List , which contains at least the following members:
private part:
head , a pointer to the first (left most) node in the list. When the list is empty, head is NULL .
tail , a pointer to the last (right most) node in the list. When the list is empty, tail is NULL .
len , the length (number of nodes) in the list. It is 0 when the list is empty.
public part:
List() : A default constructor, which initialize an empty list.
List(int arr[], int num) : A constructor that can copy the integers of an array into a list. It has has two parameters:
arr , which corresponds to the name of an integer array.
num , which is the number of integers in the array.
For example, after the following statements, lis records a list of 5 nodes created on the heap memory containing the integers from
1 to 5.
int arr[5] = {1, 2, 3, 4, 5};
List lis = List(arr, 5);
~List() : A destructor, which will release (using the delete operator) all nodes of the list. Note that when each node is created, it is
allocated on the heap (using the new operator); therefore, when the lifetime of the list ends, all nodes should be released.
void append(int n) : a function, which accepts an integer parameter n , and create a new node that contains n , and append the
new node at the tail (end) of the list. The address of the new node becomes the tail of the list.
void prepend(int n) : a function, which accepts an integer parameter n , and create a new node that contains n , and put the new
node at the head (beginning) of the list. The address of the new node becomes the head of the list.
bool delete_left(int &n) : When the list is not empty, delete the leftmost integer (and its node) from the list and save the deleted
integer in n , update size , head or tail if necessary, and return true . If the list is empty, do nothing, and return false .
bool delete_right(int &n) : Just like delete_left , the difference is that this function deletes the right-most integer from the list.
int length(void) , a function with no parameter, which returns the length ( len ) of the list.
void print(void) , a function with no parameter. It prints the integers of the list.
operator<<(std::ostream ot , const List & lis) , a friend function (not a member) that overloads the << operator. For example
std::cout << lis ; // prints all integers of the List lis.
You can add more public functions to support operations like :
Find an integer in the list.
Delete an integer in the list.
Delete all integers in the list.
Create an array based on the list
...
Where to put the declaration of Node?
There are several choices:
(1) Declare Node in list.h , but outside of the class List . This is the common style when we write a C program. If the Node class will be used
by two different list classes, then maybe it is a better choice.
(2) You can put the declaration of the Node structure inside the List class. Some discussions on this topic at website of [1]. There are two
further choices on where to put the Node structure in the class List :
- (2.a): In the public part. This is needed if there will be some function that is not a members of that class List , and this function need to use the
concept of Node. - (2.b): In the private part. Maybe the user of a list does not need to be aware of the concept of a node, so, it could be no problem to hide the
declaration of Node in the private part. This means a simpler (and easier) interface of the List class.
You can make your own decisions on where to put the Node declaration. You can also add more useful members to the List class.
Task 3: a class of stack based on integer array
Define a class ArrStack , which is like as ListStack , while the main difference is that its data storage is based on an array.
Put the declaration statements of ArrStack in stack.h, and function definitions in stack.cpp.
In Chapter 10 of the textbook [2], there is an example of stack class based on array, which is quite similar to the ArrStack class described below.
The declaration of the ArrStack should contain the following:
private part:
ARR_MAX , a symbolic integer constant, whose value can be decided by you. Remember that there are at least two different ways of
defining a symbolic constant in a class, like:
enum {MONTHS_IN_A_YEAR = 12};
static const int MINUTES_IN_AN_HOUR = 60;
arr , an integer array of ARR_MAX elements.
size , the number of data items (integers) currently saved in the stack. It is between 0 and ARR_MAX . This member can also be used as
the index of the array that is the top of the stack. In other words, where to put the next integer.
public part:
ArrStack() : A default constructor : It initialize an empty stack. I.e., size = 0 .
~ArrStack() : A destructor : If there is no dynamically allocated space, then this destructor can do nothing. You can decide the
behavior of this function. Maybe just print a message like "destructor of ArrStack is called".
bool push(int n) : A function that accepts an integer parameter n . If the stack is already full ( size == ARR_MAX ), then this function
do nothing and return false . Otherwise, saved n at arr[size] , increment size , and return true .
bool pop(int & n) : A function that accepts an integer reference parameter n . If the stack is empty ( size == 0 ), then n is not
changed and false is returned.; Otherwise, n is changed as arr[size] , size is decremented, and true is returned.
bool is_full() const : a function with no parameter. It returns a bool value true if size == ARR_MAX , otherwise return false .
bool is_empty() const : a function with no parameter. It returns a bool value true if size == 0 , otherwise return false .
int get_size() const : an inline function, it simply returns size .
int print() const : print the integers in the stack, without popping them out.
ArrStack & operator+(int n) : the function overloads the + operator, so that an integer can be pushed into the stack. It accepts an
integer n . If the stack is not full, then n is pushed onto the stack, otherwise the stack is not changed. No matter the pushing operation
is successful or not, the reference of the stack itself is returned. Such a return value can support a chain of the + operator. Some
examples of using the overloaded + operator are listed as follows:
ArrStack s; // stack s is empty
s+1; // push 1 onto the stack s.
s + 100 + 9 + x ; // push 3 integers on to the stack: two constants followed by a variable x
ArrStack & operator- (int & x) : the function overloads the - operator. It accepts an integer reference n . If the stack is not empty,
then the integer at the top of the stack (arr[size-1]) will be saved into n , and size is decremented. Otherwise, if the stack is empty,
nothing is popped and n does not change. A reference of the stack itself is returned. Such a return value can support a chain of the -
operator. Some examples of using the overloaded + operator are listed as follows:
ArrStack stk;
int x, y, z;
// after some initialization code
stk - x - y - z; // pop three integers and save them on x y and z.
stk - x - x - x; // pop three integers, do not care about saving them (all saved on x)
std::ostream & operator<<(std::ostream & os, const ArrStack & stk) const : The function overloads the << operator. It is a
friend function (not a member). It prints the content of the stack, the integers from the bottom to the top, without popping the integers
out. For example:
std::cout << someArrStack << " These integers on the stack " << std::endl ;
Task 4: a class of stack based on linked list
The ListStack class contains the following names (member or non-member):
private part:
lis , an List object. The data are saved in lis .
You can add some private members as you like.
public part (ideas explained below):
All functions in the public part of ArrStack also appear in the ListStack , but use the name ListStack for the names of constructor,
destructor, and the type of some reference parameters.
Therefore, ArrStack and ListStack have the same interface.
For ListStack , maybe the functions like is_full() is not important. But you can set of a limit of maximum number of integers on the
stack as you like.
Note that, one one integer is popped out from the stack (removed from the list), the space of the node should be released using the
delete operator.
The constructor ListStack() creates lis as an empty list.
Make sure that when the lifetime of a ListStack object ends, the space of its list is released. There are two ways to do it.
- Do nothing, because the destructor of the List class will be called automatically when the lifetime of lis ends.
- Write some code to explicitly delete the all the nodes in lis . For example, if there is some public function like delete_all() in the
List class, then he destructor ~ListStack() can call delete_all() . Or can call the call the function delete_left() repeatedly.
However, the destructor ~List() should not be called explicitly.
Which way do you choose? Pleas explain briefly why.
Task 5: a class of queue based on circular array
The content of the class ArrQueue is described as follows:
private part:
ARR_MAX , a positive integer constant.
arr , an integer array of ARR_MAX elements.
size , an non-negative integer, representing the number of integers in the queue at the moment. It is always true that 0 size
ARR_MAX .
front , the index of element in the queue that entered the queue the earliest. When the queue is empty, it is an invalid index -1.
end , the index of the element in the queue that entered the queue the latest. When the queue is empty, it is an invalid index -1.
Note that with the idea of circular array, it is true that
end == (front + size -1) % ARR_MAX
public part:
ArrQueue() : the default constructor, it initialize an empty queue. size is 0, front and end are -1.
~ArrQueue() : the destructor. Remember to release the memory on dynamic memory if there is any. Otherwise, do nothing is ok. For
testing purpose, you can print some message.
bool enqueue（int n) : If the queue is full, do nothing and return false . Otherwise, enter n into the queue, arr[end] becomes ,
increment size , increment end circularly, and return true;
bool dequeue (int & n) : If the queue is empty, do nothing and return false . Otherwise, save the value arr[frong] into n ,
increment size , increment front circularly, and return true;
int get_size() : return the value of size . It is better to be an inline function.
≤ ≤
n
bool is_full() : if size is ARR_MAX , return true, otherwise return false.
bool is_empty() : if size is 0, return true, otherwise return false.
void print() :
ArrQueue & operator+(int n) : overload the + operator so that integers can enter the queue using some convenient syntax. If the
queue is not full, then enter the integer n into the queue, size and end are updated. Otherwise, nothing is changed on the queue. It
returns the reference of the ArrQueue object itself so that + can be used repeatedly in an expression.
ArrQueue & operator-(int &n) : overload the - operator so that integers can leave (dequeue) the queue using some convenient
syntax. If the queue is not empty, then the integer at front is removed from the the queue and saved into n . Otherwise, nothing is
changed on the queue. It returns the reference of the ArrQueue object itself so that + can be used repeatedly in an expression. Some
example of using the overloaded + and - operators :
ArrQueue aq ;
aq + 1 + 2 + 99; // entering integers 1, 22, and 99 into the queue.
aq + 100； // size is 4 now.
int v, w, x, y, z, ; //
aq - x - y - z; // x is 1, y is 2, z is 99. It calls the he operator-() function.
aq - w; // w is 100, queue is empty now
aq - v; // v is not changed, because the queue is empty.
std::ostream & operator<<(std::ostream & os, const ArrQueue & q) : A friend function. With this function, the content of the
queue can be conveniently printed using cout . For example:
cout << someArrQueue << "These are the integers in the queue, front to end \n".
The destructor should release the space dynamically allocated for each node.
The function is_full() may not be important for ListQueue ,
Task 6: a class of queue based on linked list
The content of the class ListQueue is the following:
private part
lis : a List object.
You can add some private names as you like. Here the conept of front or end should be some address of node. Maybe you do not need
to declare the size , front , or end members, because lis has the information (size, head and tail).
public part （ideas explained below):
All public functions of ArrQueue also appear in ListQueue , except the name of the constructor and destructor, and some parameter
type should be changed according to ListQueue .
Especially, like the situation of ListStack , make sure that when the lifetime of a ListQueue ends, its list space is all released.
Task 7: Test all the classes
In the file driver.cpp , write a main function, so that all the public functions of all the classes are called. The correctness of calling these public
functions should be known by some messages printed on the screen. For example:
// testing the ArrStack
ArrStack as; // default constructor called.
cout << as.size() << endl
as.push(1); // testing push
as.push(2);
as + 3; ;
cout << as.size() << endl;
int x , y, z;
as.pop(x); // testing pop
as.pop(y);
cout << " x = " << x << "y = " << y << endl ;
as + 99 + 100 + 101 - z; // testing the overloaded + and -
cout << as << endl // testing the overloaded <<
Task 9: Extra features
- Adding one function into some class that are not mentioned above.
- Adding one operator overloading function (different from the previous one) that is not mentioned above.
- How to compile your program? Describe the command-line instruction of compiling your program as a line of comment on the top of the file
driver.cpp
You are welcome to add more features into the program. Mention your activities clearly in my_scores.xlsx or readme.txt ,
Task 8: recording the
Fill the file my_scores.xlsx. according to the requirements of the file.
Task 9: Submission
Upload the files to the webpage of Moodle at MUST.
The files needing to be submitted include:
All the source code, .cpp and .h files.
my_scores.xlsx
A text file readme.txt , describing the group member, how did you test your program (what is the command), the record of screen of
testing your program, anything you want to say.
Do not include other files, like .o, .obj, .exe, or any project files created by some software tools.
At most 3 students can form a group to submit the files together
only one student need to submit the files. Make sure to clearly mention the names of all members in the submitted file my_scores.xlsx
and readme.txt .
Deadline: May 7 (Friday) 2021 11:00pm
References
[1] "Define a struct inside a class in C++" https://stackoverflow.com/questions/2543205/define-a-struct-inside-a-class-in-c/2543285
[2] "C++ Primer Plus", Stephen Prata, edition 6, ISBN：978-0321-77640-2, Pearson.
[3] "C Primer Plus" (6th Edition) (Developer’s Library), Stephen Prata, Addison-Wesley Professional, Indianapolis, IN, USA, 2013.
[4] "Increment ++ and Decrement -- Operator Overloading in C++ Programming" https://www.programiz.com/cpp-programming/incrementdecrement-operator-overloading
[5] "Will new operator return NULL?" https://stackoverflow.com/questions/3389420/will-new-operator-return-null
[6] C++ Exception Handling https://www.tutorialspoint.com/cplusplus/cpp_exceptions_handling.htm