I don\'t really understand this portion on my assignment, the code language is C

Question

I don't really understand this portion on my assignment, the code language is C++. If someone can help me either by descripting it by words or by a picture drawing nodes on how the code of the function highlighted below works and whats the code for this function to work correctly. I would appriciate very much. Thank You :]

*Please note:

My task is to take in a list, remove duplicates (if they aren't the first duplicate), and then create a mirror image of the list. If there is only one duplicate of the data, then use that node and move it instead of deleting it. If there are no duplicates, create a node for it. I'm not allowed to use outside functions to do this. Which means a lot of pointer manipulation.

My thought process on it was that I would have an anchor and loop through to find if there are any duplicates. If there are, move the first duplicate to the end of the list and delete the rest of the duplicates. This would create the first half of the list as the original list and the second half would be the mirror.

Does nothing if given list is empty.

If given list is not empty, process it so that it comprises of 2 halves:

(1)

The first half contains a sequence of distinct items (that the given list originally contains).

(2)

The second half contains a sequence of distinct items that form a "mirror image" of the items in the first half.

The distinct data items are derived from the data items in the given list:

If given list (originally) has multiple nodes containing a certain distinct value, the second such node (i.e. the earliest duplicate) is to be used as the "mirror-image" node.

NOTE:

Although the node to be used as the "mirror-image" node does not have to be the first duplicate, you are to make it so for the purpose of this exercise.

All remaining duplicates (if any, of a certain distinct value) are to be deleted from the list.

NOTE:

No memory leak should be incurred, of course.

If given list (originally) has only a single node containing a certain distinct value, a new node for that value is to be created and used as the "mirror-image" node.

The sequence of distinct values in the first half must appear in the same order in which the first of the corresponding values originally (upon entering the function) appears in the given list.

Algorithm should:

NOT change the data of any existing nodes.

Destroy ONLY existing nodes that constitute second duplicate, third duplicate, etc. of a certain distinct value.

Recall that the first duplicate is not to be destroyed but instead used as a "mirror-image" node.

Create new nodes and copy data between nodes ONLY under the "given list (originally) has only a single node containing a certain distinct value" circumstances.

Creating pointer-to-node's (to provide temporary storage for node addresses) does not constitute creating new nodes or copying of items.

NOT make any temporary copies of any of the data items (using any kind of data structures including but not limited to arrays, linked lists and trees).

This means that the algorithm should largely involve the manipulation of pointers.

Function must be iterative (NOT recursive) - use only looping construct(s), without the function calling itself (directly or indirectly).

Function should NOT call any other functions to help in performing the task.

Does nothing if given list is empty.

Explanation / Answer

void MakeDistinctMirrorPairs(Node *& head)
{
int dup = 0;
if (head == 0 ) return;
if (head == 0)
{
head = head->link;
Node *nodePtr = new Node;
nodePtr->data = head->data;
head->link = nodePtr;
nodePtr->link = 0;
return;
}
Node *anc = head;
Node *mirror = 0;
{
head = head->link;
Node *nodePtr = new Node;
nodePtr->data = head->data;
head->link = nodePtr;
nodePtr->link = 0;
return;
}
Node *anc = head;
Node *mirror = 0;
while(anc != 0)
{
dup = 0;
if(anc->link != 0)
{
Node *pre = anc;
Node *cur = anc->link;
while(cur != 0)
{
if(cur->data == anc->data )
{
dup++;
if(dup == 1)
{
pre->link = cur->link;
cur->link = mirror;
mirror = cur;
cur = pre;
}
if(dup > 1)
{
pre->link = cur->link;
delete cur;
cur = pre;
}
}
pre = cur;
cur = cur->link;
}
}
if(dup == 0)
{
Node *newNode = new Node;
newNode->data = anc->data;
newNode->link = mirror;
mirror = newNode;
}
anc = anc->link;
}
anc = head;

while(anc->link != 0)
anc = anc->link;
anc->link = mirror;
anc = head;
while(anc != 0)
{
cout<<anc->data;
anc = anc->link;
}
cout<<endl;
return;
}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.