C++代写：CSE232 DisjointSet

实现数据结构中的DisjointSet，实现并完成接口。

Assignment Overview

Last one. You are going to build a DisjointSet (DJSet) data structure, a so called forest of singly-linked lists, that allows for member ship and join operations.

Background

You can look up more about a DisjointSet, what we will call a DJSet, here https://en.wikipedia.org/wiki/Disjoint-set_data_structure. The basic idea is that we have a vector of pointers to different singly linked lists. These lists represent groups that are members of the same set.

Consider the following example. Jimmy, Jody, Jamie and Judy are all individuals, i.e. they are single elements of the DJSet. Thus each element of the DJSet is a pointer to the head of a linked list, and each list at the moment consists of a single node. They would look as follows:

If I want to add another person, I can use the add method, for example adding Jilly, adding her to the end of the vector again as a single node in a linked list

I want to make Judy and Jimmy “friends”, that is make them a member of the same set. I use the join method to add Judy to Jimmy. The list with Jimmy as a head now has two nodes.

Note that Judy is now linked to Jimmy, and everybody else shifted down in the vector. That is, the size of the vector is one less because one of the linked list head nodes was moved to the end of another list (see note at the end).

If I similarly make Jimmy a friend of Jamie, Jimmy and everybody who Jimmy links to is joined to the Jamie list (a friend of Jimmy’s is a friend of mine), like so.

Here is a two step. First make Jody a friend of Jilly. Then make Jody a friend of Jimmy. The tricky part here is that to make that last step work, I need to find the head node of both Jody and Jimmy (who are not head nodes themselves) and join them. Thus the head node of Jody (which is Jilly) is added to the end of the list headed by Jamie (who is the head node of the list with Jimmy). Fun eh?

If I want to know if Judy is in the set somewhere, use the member method with the value Judy. This method either returns a nullptr, meaning Judy isn’t in the DJSet, or the head pointer of the list where Judy is a member, in this case Jamie.

Specification

The specification is mostly provided in hackerrank (or on the website) as the starter code. But here are the highlights.

Element class

It is templated on the data_ member and has a next_ pointer. It provides two constructors function. Fill in the indicated areas, as previously.

DJSet class

The private data element in this class is a vector. Pay attention to that! Each element of the vector is a pointer to an Element, to the head of a singlylinked list. That is going to be the focus of your work. How do you work with not just one list, but with a vector of such lists. We’ll discuss that more below

Parts that are declared but not defined. You cannot change the declarations, but you must provide the definitions.

• default constructor
• constructor with a single T value. You turn that single T into an Element Node and make this the first, and only, linked list in the vector.
• constructor with a vector set of values. Each of those values is turned into an Element node and made the head of a list in the vector. If there are 3 elements in the parameter vector, then there will be three lists in the DJSet vector, each with a single Element node.
  • However: there is only one copy allowed of each T value in the entire DJSet. Thus you must check for each element you are adding to see if there is copy somewhere. If there is a copy, it is ignored and not added.
  • As this is a constructor, you know the DJSet starts empty. Thus you can just check the parameter vector for copies. You could also check to see if a copy is in the DJSet as you add using the member method (below).
• copy constructor
• destructor operator=
• member: takes a single T parameter, returns an Element*.
  • The member method looks in every list in the vector to find where and whether the T value exists as a node anywhere in all those lists.
    • there should only be one example of every T value in all the vector lists.
  • The Element* returned is either:
    • nullptr, value doesn’t exist anywhere in the DJSet
    • The head of the list where the T value is found.
• add: takes a single T parameter, returns an Element*
  • The method turns the T into an Element and appends it to the end of the DJSet vector if the element does not already exist in the DJSet.
  • The Element* returned is either:
    • nullptr, indicating that T value is already in the DJSet and was not added
    • A pointer to the Element added to the DJSet.
• join: takes two T values, returns an Element*
  • the parameter interpretation is that the first T value is being added to the second T value.
  • more specifically the head node of the list where the first parameter was found is being moved to the tail of the head node of the list where the second parameter was found.
    • the member method makes this all fairly straight forward. Find the member of both the parameters, then do the pointer arithmetic to join the head of the first to the tail of the second
    • by the way, you have to walk the list starting at the head of second to find the tail. There is no tail pointer here.
  • The Element* returned is:
    • nullptr if either of the T parameters is not found. No action is taken in this case
    • The pointer to the head node of the list to which the elements were joined.
  • Note that the size of the vector is one smaller after a join. The list that is moved to the tail of the primary list is erased from the vector.
• operator
  • declaration is there, you need to fill in the definition in the header as previously. See the hackerrank output for details the but here are the basics:
    • if the underlying vector is empty (no lists), it prints “empty”
    • if vector is not empty, then every element from begin() to end() should point to a list. Print each list on a separate line.
    • Each element on each line is separated by a “-“, for pointer. The end “-“ still shows up, indicating it points to nothing/nullptr

Anything else you need!!!

You are defining your class, so any other functions/members you might need, feel free to add them. The test will only involve using the main provided.

Important things to Note

Deliverables

proj11.cpp your source code solution along with the main program unchanged!

1. Please be sure to use the specified file names
2. Save a copy of your file in your CSE account disk space (H drive on CSE computers).
3. Test on hackerrank.
4. You will electronically submit a copy of the file using the “handin” program.

Assignment Notes

1. The copy constructor and destructor are trickier than they first look. You have a vector of linked lists. Each of the linked lists must be copied/destroyed as they were in the Single Linked List example. If the size of the vector is 5, then you have to copy 5 lists and/or destroy 5 lists. If you were to just copy the vector, you would copy the pointers but not the linked list memory they point to!!
2. To help with that, I wrote (for myself) a copy_one_list method to copy one linked list.
   You might find such a method useful.
3. You probably have to use the vector erase method in the join method to avoid
   Segfaults and holes in the vector. For example:
   Left to right, we joined Judy (index 2) to Jimmy (index 0) and we also erased the pointer at (index 2). When you do an erase, the rest of the vector shifts down leaving no “holes” and no extra pointers. If you don’t erase, you get:
   Thus two pointers to Judy. When you print the entire vector, Judy would print twice: once as a next_ of Jimmy and once as a head node. To do an erase you need an iterator to the location you want to erase. To erase the first position, for example, you would do v_.erase(v_.begin() ). You could find the iterator you need or loop through until you find it. Either way, erase takes an iterator argument, not a pointer.
   Finally, note that deleting the pointer in red above does not in any way affect the linked lists. It simply removes the extra pointer and compacts the array.