作业练习2:类与数据结构

面向对象程序设计(C++)
WHUT-CS 2022 Spring

I.作业目的与要求

本次实验主要在于学习使用C++类结构编程实现基本数据结构的功能，包括链表、栈和队列等。本次作业所涉及的
功能代码应满足或遵循以下几点:

• A. 本次作业中，各数据结构所管理的数据对象均为整型数据，你可以在以后对代码进行改动和升级后使其能够管理更多可能的数据对象;
• B. 本次作业中，需要完成操作符重载的相关功能设计，对此可能存在多种解决方案，可根据设计和功能要求选择你认为合理的解决方案，包括操作符参数、返回值、前缀操作符、后缀操作符等实现细节的选择;
• C. 由于还未学习异常处理等相关知识，因此在使用部分库函数需要注意对异常的处理方式以避免程序意外退出。在部分库函数中，C++通过抛出异常对象(exception) 而不是通过特定返回值(0或nul) 来表示错误情况，因此在完成部门功能的编写时，可能需要通过前置条件检查以确保程序不会抛出异常。完成作业时也可以通过查询相关章节或网络资源以正确使用异常;
• D.严格保持整洁的代码格式、统一的命名规则和适当的代码注释以提高代码的整洁性和可读性;

注意:作业练习的考察范围涵盖本课程的全部学习内容，不完全遵循授课章节的顺序，也不完全遵循课堂讲授范围，部分知识点的学习和运用需根据教材或参考书内容加以自学

源码传送门

传送门：https://pan.baidu.com/s/1rJeuQQrrSyfoOx0ObdOWmA?pwd=1111

II.作业内容

Task1:准备源文件

本次作业任务要求至少包含如下7个源代码文件:

• list.h:用于List类的功能声明头文件;
• list.cpp: 用于List类的功能实现源文件;
• stack.h: 用于Arrstack类和Liststack类的功能声明头文件;
• stack.cpp: 用于ArrStack类和ListStack类的功能实现源文件;
• queue.h: 用于ArrQueue类和ListQueue类的功能声明头文件;
• queue.cpp: 用于ArrQueue类和ListQueue类的功能实现源文件;
• driver.h: 包含主函数main的入口程序源文件;

Task2:实现双向链表(doubly-linked list)功能

分别在list.h和list.cpp文件中编写代码完成双向链表的功能声明和实现，该类应满足以下一-些功能要求:
分别在ist.h和list.cpp文件中编写代码完成双向链表的功能声明和实现，该类应满足以下一些功能要求:

• 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.

1. Do nothing, because the destructor of the List class will be called automatically when the lifetime of lis ends.
2. 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

1. Adding one function into some class that are not mentioned above.
2. Adding one operator overloading function (different from the previous one) that is not mentioned above.
3. 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