C++代写：CMPSC122 Set and SDLL

发表于   |   分类于

代写数据结构中的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
14
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
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.

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:

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.

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
17
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:

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