A company hires consultants form a variety of satellite software companies to im
ID: 3806984 • Letter: A
Question
A company hires consultants form a variety of satellite software companies to implement their code, which include many incompetent programmers who ten to mess up pointers,. To safeguard against such errors, please write a simple subroutine that checks for loops in a given list. Provide a pseudo code for a function thhat checks a linked list for loops, if it find a loop, it is further required to eliminate the loop. getLength() which accurately returns to you the length of the list and a pointer to the head of the list, in other words, you are required to implement void detectAndRemoveLoops(). C++
Please base on the following sample stack code. Thank you for your help
#include<iostream>
#include<stdlib.h>
using namespace std;
class chunk {
public:
int value;
chunk *next;
chunk() {
value = 0;
next = NULL;
}
};
class Stack {
public:
chunk *top;
Stack() {
top = NULL;
}
void push(int x) {
chunk *temp;
temp = new chunk;
temp->value = x;
if (top == NULL) {
top = temp;
}
else {
temp->next = top;
top = temp;
}
}
void pop() {
if (top == NULL) {
cout << "Empty stack, nothing to delete" << endl;
}
else {
chunk *temp;
temp = top;
top = temp->next;
cout << "About to delete: " << temp->value << endl;
delete temp;
}
}
void display() {
chunk *traverse = top;
if (top == NULL) {
cout << "Empty Stack. Nothing to display" << endl;
}
else {
while (traverse != NULL) {
cout << traverse->value << "-->" << endl;
traverse = traverse->next;
}
}
}
};
int main()
{
Stack ourStack;
int choice = 0;
while (1) {
cout << "Press 1 to add "<< endl;
cout << "Press 2 to delete "<< endl;
cout << "Press 3 to display" << endl;
cout << "Anything else to quit" << endl;
cin >> choice;
switch (choice) {
case 1: cout << "Add what?" << endl;
int value;
cin >> value;
ourStack.push(value);
break;
case 2: ourStack.pop();
break;
case 3: ourStack.display();
break;
default: exit(1);
}
}
}
Explanation / Answer
void detectAndRemoveLoops(chunk *head)
{
chunk *ptr1 = head;
chunk *ptr2 = head->next;
// Search for loop using ptr1 and ptr2 pointers
while (ptr2 && ptr2->next)
{
if (ptr1 == ptr2)
break;
ptr1 = pyr1->next;
ptr2 = ptr2 ->next->next;
}
/* If loop exists */
if (ptr1 == ptr2)
{
ptr1 = head;
while (ptr1 != ptr2 ->next)
{
ptr1 = ptr1 ->next;
ptr2 = ptr2 ->next;
}
/* since ptr2->next is the looping point */
ptr2->next = NULL; /* remove loop */
}
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.