user6005857 - 8 months ago 45

C Question

Suppose I have the following struct:

`struct _node {`

int id;

char *name;

struct node *next;

};

I want to write a function that goes through the linkedlist and looks for structs whose name member contains a certain substring and adds those structs to a new linkedlist and returns the new linkedlist.

I attempted doing this using strstr but at some point I am getting an infinite loop and I can't figure out exactly why the infinite loop is happening.

Here is my function:

`struct _node *containSubstr(struct _node *head, char needle[]) {`

if (head == NULL) {

printf("BLOOP BLEEP BOOP BEEP.\n");

exit(EXIT_FAILURE);

}

struct _node *curr = head;

struct _node *returnHead = createEmptyNode();

while (curr != NULL) {

char haystack[strlen(curr->name)];

strcpy(haystack, curr->name);

strToLower(needle);

strToLower(haystack);

if (strstr(haystack, needle) != NULL) {

// this is where I get the infinite loop

append(returnHead, curr);

}

curr = curr->next;

}

return returnHead;

}

The functions append and createEmptyNode are tested and work fine.

I went over the logic multiple times and I think this must work. I filled my code with print statements and it seems like after it finds all the nodes that contain the substring it keeps repeating the last node and goes into an infinite loop.

Here is my append function:

`void append(struct _node *head, struct _node *newNode) {`

if (head == NULL) {

printf("BLOOP BLEEP BOOP BEEP.\n");

exit(EXIT_FAILURE);

}

struct _node *curr = head;

if(curr == NULL) {

head = newNode;

}

else {

while(curr->next != NULL) {

curr = curr->next;

}

curr->next = newNode;

}

}

Answer

Imagine this case: you have a list *L* that contains just 2 nodes (*A* and *B*) in your linked list. Imagine that both nodes *A* and *B* contain a substring you are looking for:

Original list *L*:

A->B->NULL

So after first iteration your new list *L2* should look like this:

A->NULL

But in your append function you don't create a deep copy of a new node. Therefore, your new list *L2* looks like this:

Empty_node->A->B->NULL

In the next step you move to node *B*. So you take your *L2* and append there *B*. Your *L2* after second iteration looks like this:

Empty_node->A->B->B (B points to itself).

Since you don't create deep copies you are actually always working with list *L* and when you append node *B* to what you think is the list *L2* you actually append *B* to *L* and then *B* points to itself (`curr->next = newNode;`

in your `append`

function). So in the next iteration you are again asking if *B* contains the string you are looking for.

**Conclusion**

You need to create deep copies when creating new list.

In the current setup your `append`

function modifies original list.

Source (Stackoverflow)