Answered step by step
Verified Expert Solution
Link Copied!

Question

1 Approved Answer

(Please explain and show output) (cyclic_ll.c) #include typedef struct node { int value; struct node *next; } node; int has_cycle(node *head) { // Your code

image text in transcribed(Please explain and show output)

(cyclic_ll.c)

#include

typedef struct node {

int value;

struct node *next;

} node;

int has_cycle(node *head)

{

// Your code goes here:

}

void test_has_cycle(void)

{

int i;

node nodes[25]; //enough to run our tests

for(i=0; i

nodes[i].next = 0;

nodes[i].value = 0;

}

nodes[0].next = &nodes[1];

nodes[1].next = &nodes[2];

nodes[2].next = &nodes[3];

printf("Checking first list for cycles. There should be none, has_cycle

says it has %s cycle ",

has_cycle(&nodes[0])?"a":"no");

nodes[4].next = &nodes[5];

nodes[5].next = &nodes[6];

nodes[6].next = &nodes[7];

nodes[7].next = &nodes[8];

nodes[8].next = &nodes[9];

nodes[9].next = &nodes[10];

nodes[10].next = &nodes[4];

printf("Checking second list for cycles. There should be a cycle,

has_cycle says it has %s cycle ",

has_cycle(&nodes[4])?"a":"no");

nodes[11].next = &nodes[12];

nodes[12].next = &nodes[13];

nodes[13].next = &nodes[14];

nodes[14].next = &nodes[15];

nodes[15].next = &nodes[16];

nodes[16].next = &nodes[17];

nodes[17].next = &nodes[14];

printf("Checking third list for cycles. There should be a cycle,

has_cycle says it has %s cycle ",

has_cycle(&nodes[11])?"a":"no");

nodes[18].next = &nodes[18];

printf("Checking fourth list for cycles. There should be a cycle,

has_cycle says it has %s cycle ",

has_cycle(&nodes[18])?"a":"no");

nodes[19].next = &nodes[20];

nodes[20].next = &nodes[21];

nodes[21].next = &nodes[22];

nodes[22].next = &nodes[23];

printf("Checking fifth list for cycles. There should be none, has_cycle

says it has %s cycle ",

has_cycle(&nodes[19])?"a":"no");

printf("Checking length-zero list for cycles. There should be none,

has_cycle says it has %s cycle ",

has_cycle(NULL)?"a":"no");

}

int

main(void)

{

test_has_cycle();

return 0;

}

(Assignment 2, individual) Cyclic Linked list In cyclic_Il.c, complete the function has_cycle) to implement the following algorithm for checking if a singly-linked list has a cycle. Recall that if p is a pointer to a struct, p->member refers to a member variable in the struct, and is equivalent to (*p).member. 1. Start with two pointers at the head of the list 2. On each iteration, increment the first pointer by one node and the second pointer by two nodes. If it is not possible to do one or both because of a null pointer, then we know there is an end to the list and there is therefore no cycle 3. We know there is a cycle if a. The second pointer is the same as the first pointer b. The next node of the second pointer is pointed to by the first pointer The reason we know there is a cycle with the two conditions in 3) is that second pointer has wrapped around to the first one in the circle and we have detected it. After you have correctly implemented has_cycle, the program you get when you compile cyclic_Il.c will tell you that has_cycle agrees with what the program expected it to output

Step by Step Solution

There are 3 Steps involved in it

Step: 1

blur-text-image

Get Instant Access to Expert-Tailored Solutions

See step-by-step solutions with expert insights and AI powered tools for academic success

Step: 2

blur-text-image

Step: 3

blur-text-image

Ace Your Homework with AI

Get the answers you need in no time with our AI-driven, step-by-step assistance

Get Started

Recommended Textbook for

Oracle RMAN For Absolute Beginners

Authors: Darl Kuhn

1st Edition

1484207637, 9781484207635

More Books

Students also viewed these Databases questions

Question

What are the two components of total risk?

Answered: 1 week ago