Introduction
：
typedef SDLL DLList;
main()
{
DLList lst;
lst.addToHead(“alice”);
lst.addToHead(“jim”);
lst.addToHead(“alice”);
lst.addToTail(“sam”);
lst.addToTail(“pete”);
lst.removeDuplicates();
for (int i = 1; i <= lst.getSize(); i++)
lst[i][0] = toupper(lst[i][0]);
lst.printAll();
lst.reverse();
lst.printAll();
return 0;
}
，
Requirement
P a g e | 1
CMPSC 122 – Intermediate Programming
Assignment #4
Spring 2017
Due Date: Thursday, April 13, 2017
Total Points: 100
Question 1 (40 points):
A set is a collection of unordered items that contains no duplicates. Sets are important in Mathematics and are
useful in programming to keep track of distinct items such as the courses someone registered for, or a person’s
friends in a social network. Implement a class called MySet that represents a set of integers. MySet class will be
composed of a singly linked list object as a data member. You should use the list implementation (LList) that
we went through in class.
The class should use two member variables:
- items: a singly linked list of integers
- size: an integer variable that keeps track of the number of elements in the set
The class should have the following functionalities:
Function Prototype Description
MySet()
The default constructor. Creates an empty set.
int getSize()const
Returns the number of elements in the set.
bool isEmpty()const
Returns true if the set is empty, false otherwise.
void add(int el)
Adds a new element el to the set. The element is added only
if the set does not have el as a member.
void remove(int el)
Removes el from the set.
void intersection(MySet T, MySet I) The intersection of this and T. The result will be stored in I.
I is the set containing the elements that are in both this and
T.
void Union(MySet T, MySet U)
The union of this and T. The result will be stored in U. U is
the set containing the elements that are in this or T, or both.
U is a set, so there should be no duplicate items.
P a g e | 2
void difference(MySet T, MySet D)
The difference of this and T. The result will be stored in D.
D is the set containing the elements that are in this but not in
T.
string toString()
Returns the contents of the set in a string format.
For example, the following code:
int main()
{
MySet s;
MySet t;
s.add(1);
s.add(2);
t.add(3);
t.add(2);
MySet a;
s.Union(t, a);
cout << a.toString() << endl;
return 0;
}
Will result in:
{1, 2, 3}
The following modifications should be done on LList class that we went through in class in order to
simplify this question:
Function Prototype Description
void printAll() const
string toString()
Replace printAll( ) with toString( ). toString( ) returns the
contents of the list in a string format.
void deleteNode(int el) Add the following function, which deletes the node with the
integer value that is equal to el.
int operator Add the following function, which returns the address of the
integer element at the i’s node. Assume the index of the first
element of the LList to be zero. You do not need to worry
about boundary checks.
Provide a main( ) method that makes sure that each member function of mySet is working properly.
P a g e | 3
Question 2 (60 points):
Implement a class called String Doubly Linked List (SDLL). This class should represent a doubly
linked list structure where each node stores a string value as its data. The linked list structure should
be your own implementation so you cannot make use of the Standard Library Templates (STL) that
is provided by C++. The class should have the following functionalities:
Function Prototype Description
SDLL() The default constructor. Creates an empty doubly linked list.
~SDLL() The default destructor. Deletes all the nodes in a doubly linked
list.
bool isEmpty()const Returns true if the list is empty, false otherwise.
void addToHead(string element) Adds a new node to the head of the linked list.
void addToTail(string element) Adds a new node to the tail of the linked list.
string deleteFromHead() Deletes the first node in the linked list. Returns the value of
the deleted node.
string deleteFromTail() Deletes the last node in the linked list. Returns the value of the
deleted node.
void deleteNode(string element) Deletes the first node with a string value equals to the element.
bool isInList(string val) const Returns true if the list has a node with string equals to val, false
otherwise.
void printAll() const Displays the contents of the linked list.
void removeDuplicates() Deletes all the nodes in a linked list with duplicate string
values.
void reverse() Reverses the contents of the linked list. This function should
not use a temporary linked list to accomplish this task.
int getSize() Returns the number of elements in the linked list.
string operator Returns the address of the data at the i’s node. Assume the
index of the first element of the SDLL list to be one and not
zero.
P a g e | 4
The two functions deleteFromHead and deleteFromTail should issue an error when the doubly linked list
is empty. The [ ] operator should perform. boundary checks and should issue an error when the user
tries to access an element outside the range of the linked list. You are going to make use of C++
assertions to indicate an error.
For example, the following code:
int main()
{
DLList lst;
lst.addToHead(“alice”);
lst.addToHead(“jim”);
lst.addToHead(“alice”);
lst.addToTail(“sam”);
lst.addToTail(“pete”);
lst.removeDuplicates();
for (int i = 1; i <= lst.getSize(); i++)
lst[i][0] = toupper(lst[i][0]);
lst.printAll();
lst.reverse();
lst.printAll();
return 0;
}
Will result in:
Alice Jim Sam Pete
Pete Sam Jim Alice
Provide a main( ) method that makes sure that each member function of SDDL is working properly.
main( ) should provide a menu driven interface that allows the user to test whether each member
function of SDLL is working properly. The menu should provide the following functionalities:
o Create a new String Doubly Linked List
o Get Size: the current number of nodes in the list
o Insert:
Insert a new element at the head of the linked list
Insert a new element at the tail of the linked list
o Delete:
Delete the first node
Delete the last node
Delete a specific node
o Search for a string value
o Reverse the list
P a g e | 5
o Remove any duplicates
o Print all the elements in the list
o Quit the program
What to hand in
Please submit your C++ source files for questions 1 2 electronically through Canvas.