代写数据结构中的Set和String Doubly Linked List的实现,完成成员函数。
Question 1
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. |
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:1
2
3
4
5
6
7
8
9
10
11
12
13
14int 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:
Provide a main( ) method that makes sure that each member function of mySet is working properly.
Question 2
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:
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:1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17int 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:
- Create a new String Doubly Linked List
- Get Size: the current number of nodes in the list
- Insert:
- Insert a new element at the head of the linked list
- Insert a new element at the tail of the linked list
- Delete:
- Delete the first node
- Delete the last node
- Delete a specific node
- Search for a string value
- Reverse the list
- Remove any duplicates
- Print all the elements in the list
- Quit the program
What to hand in
Please submit your C++ source files for questions 1 & 2 electronically through Canvas.