Need help finishing the \"C\" code below according to the instructions below: #i

Question

Need help finishing the "C" code below according to the instructions below:

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

struct Node{
int phone;
struct Node *pNext;
};
typedef struct Node node;

node * createnode(node *pNode, int num)
{
pNode = (node*)malloc(1*sizeof(node));
pNode->pNext = 0;
pNode->phone = num;
return pNode;
}

node * addnodetoend(node*pNode, int num)
{
while(pNode->pNext!=0)
    pNode = pNode->pNext;
    pNode->pNext = createnode(pNode->pNext, num);
return pNode->pNext;
}

void printlist(node * pNode)
{
do{
    printf("%d ", pNode->phone);
    pNode = pNode->pNext;
}while(pNode!=0);
}
void deletenode(node *pNode, int num)
{
while(pNode->pNext!=0)
{
    if(pNode->pNext->phone == num)
    {
      node * pTemp = pNode->pNext;
      pNode->pNext = pNode->pNext->pNext;
      free(pTemp);
    }
    pNode = pNode->pNext;
}
}

bool checkforloop(node*pNode)
{
return false;
}

int main()
{
node * pRoot;
pRoot = createnode(pRoot,0);
node * pTemp=addnodetoend(pRoot, 100);

addnodetoend(pRoot, 200);
node * pEnd = addnodetoend(pRoot, 300);
pEnd->pNext = pTemp;

if(checkforloop(pRoot)==true)
    printf("There is a loop ");
else
    printf("No loop ");

node * pRoot2;
pRoot2 = createnode(pRoot2,0);
addnodetoend(pRoot2, 100);

addnodetoend(pRoot2, 200);
addnodetoend(pRoot2, 300);

if(checkforloop(pRoot2)==true)
    printf("There is a loop ");
else
    printf("No loop ");

return 0;}

In a linked list it is possible to have a loop, as in Figure 1 2 3 4 Figure 1: Linked list with a loop You can tell if a list has a loop in it by using the Tortoise and the Hare algorithm. Have two pointers to the start of the list. Move the Hare pointer two steps each cycle, and the Tortoise pointer one. For example, at the beginning of the algorithm both pointers start at one, and then after the first step the Hare points to three, and the Tortoise points to two. Keep repeating until both pointers are equal (There is a loop), or you reach the end of the list(There is no loop) In the code below implement this algorithm in the function checkforloop. It should return true for the first linked list and false for the second one.

Explanation / Answer

The code is as follows :

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
struct Node{
int phone;
struct Node *pNext;
};
typedef struct Node node;
node * createnode(node *pNode, int num)
{
pNode = (node*)malloc(1*sizeof(node));
pNode->pNext = 0;
pNode->phone = num;
return pNode;
}
node * addnodetoend(node*pNode, int num)
{
while(pNode->pNext!=0)
pNode = pNode->pNext;
pNode->pNext = createnode(pNode->pNext, num);
return pNode->pNext;
}
void printlist(node * pNode)
{
do{
printf("%d ", pNode->phone);
pNode = pNode->pNext;
}while(pNode!=0);
}
void deletenode(node *pNode, int num)
{
while(pNode->pNext!=0)
{
if(pNode->pNext->phone == num)
{
node * pTemp = pNode->pNext;
pNode->pNext = pNode->pNext->pNext;
free(pTemp);
}
pNode = pNode->pNext;
}
}
bool checkforloop(node*pNode)
{
node *tort = pNode, *hare = pNode; // initializing the two pointers
while (tort && hare && hare->pNext) // to check if we haven't reached the end of the list
{
tort = tort->pNext; // incremeting by one
hare = hare->pNext->pNext; // incrementing by two
if (hare == tort) // to check if equal
{
//printf("Found Loop "); this just prints it twice , so removing it
return true; // break out of the loop
}
}
return false; // if no loop , return
}
int main()
{
node * pRoot;
pRoot = createnode(pRoot,0);
node * pTemp=addnodetoend(pRoot, 100);
addnodetoend(pRoot, 200);
node * pEnd = addnodetoend(pRoot, 300);
pEnd->pNext = pTemp;
if(checkforloop(pRoot)==true)
printf("There is a loop ");
else
printf("No loop ");
node * pRoot2;
pRoot2 = createnode(pRoot2,0);
addnodetoend(pRoot2, 100);
addnodetoend(pRoot2, 200);
addnodetoend(pRoot2, 300);
if(checkforloop(pRoot2)==true)
printf("There is a loop ");
else
printf("No loop ");
return 0;}

Output :

There is a loop
No loop

Related Questions

Navigate

• Browse (All)
• Browse N
• Subjects

---

---

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