CODEWITHSUNDEEP
clistsearchrecursion
Iva
Iva

Reputation: 101

Searching a linked list recursively in C

I'm fairly new to C and I was trying to write a method that will search a linked list recursively, however I had no success. The function contains returns 0 if the name is not found in any of the nodes of the linked list, and 1 is is found.I seem to be getting into an infinite loop. Any help would be greatly appreciated!

#include<stdlib.h>
#include<string.h>

struct node
{
    char name[1000];
    struct node *next;
};

int contains(const struct node *pNode, const char *name)
{
    int i;
    int length = strlen(name);
    int isEqual = 0;

    while (pNode != NULL)
    {
        isEqual = 1;
        for (i = 0; i < length; i++)
        {
            if (pNode->name[i] != name[i])
            {
                isEqual = 0;
            }
        }
    }

    contains(pNode->next, name);

    return isEqual;
}

main()
{
    struct node node1 = { "Sam", NULL };
    struct node *node1Ptr = &node1;
    struct node node2 = { "Anna", node1Ptr };
    struct node *node2Ptr = &node2;
    struct node node3 = { "Adam", node2Ptr };
    struct node *node3Ptr = &node3;

    int n, k;

    // testing for a name that is the list
    n = contains(node3Ptr, "Sam");
    printf("%d\n", n);
    // testing for a name that is not in the list
    k = contains(node3Ptr, "Max");
    printf("%d\n", k);
}

Upvotes: 0

Views: 2597

Answers (6)

Iva
Iva

Reputation: 101

This is how I modified my code and now it works. Thank you all for your help, I really do appreciate it, and I have not been familiar with the strcmp functions but I will look into. Again, thank you.

int contains(const struct node *pNode, const char *name){
  int i;
  int length = strlen(name);
  int isEqual = 0;

  if(pNode == NULL){ 
      return isEqual;
    }

  isEqual = 1;
  for (i = 0; i < length; i++)
    {
        if (pNode->name[i] != name[i])
        {
            isEqual = 0;
            break;
        }
    }


 return isEqual? isEqual : contains(pNode->next, name);
}

Upvotes: 0

abelenky
abelenky

Reputation: 64682

int contains(const struct node *pNode, const char *name)
{
    if (pNode == NULL)  // Recursive base-case:  If there is no Node,
    {                   // we are at the end of the list, and the name was never found.
        return 0;       // Therefore, return 0
    }

    // If this node matches the name, return 1.  
    // If this node does NOT match the name, check the next node.
    return !strcmp(pNode->name, name)? 1 : contains(pNode->next, name);
}

If you want a really tight form:

// Untested, but I think it works... or is at least close.
int contains(const struct node *pNode, const char *name)
{
    return pNode? (!strcmp(pNode->name, name) || contains(pNode->next, name)) : pNode;
}

Upvotes: 1

vonbrand
vonbrand

Reputation: 11791

Your function can be written concisely as:

#include <string.h>
...
int contains(const struct node *pNode, const char *name)
{
    if(pNode == NULL)
        return 0;
    if(strcmp(pNode->name, name) == 0)
        return 1;
    return contains(pNode->next, name);
}

Note that the value of the recursive call to contains() in your code is never used, and thus won't ever give anything useful. Its call is done unconditionally at the end, and that explains the infinite loop.

Compile with all (reasonable) warnings enabled (-Wall for GCC and clang), it should tell you about many boo-boos. As a personal policy, if it isn't -Wall clean, there better be a good reason to believe I'm right and the compiler overzealous.

You can also simplify much of the setup of the data structure, but that is for another time.

Nice that you took care of decorating with const as required.

Upvotes: 4

C.B.
C.B.

Reputation: 8326

Your infinite loop is a direct result from the following line:

while (pNode != NULL)

Because you never change what pNode is pointing to. Essentially you are checking against Sam over and over and over... In fact, you never even get to your recursive call.

Instead, you would want to have an

if(pNode != NULL)

check, and if not, check the string. If you found the string, return 1, otherwise, return the recursive call.

If pNode==NULL you want to return 0.

Upvotes: 0

prince
prince

Reputation: 1149

In your contains method after pnode is NULL you are again calling the function which is causing the infinite loop.

Modify that as follows.

if(pnode== NULL) {
return 0;
}

Upvotes: 0

Shirin Feiz
Shirin Feiz

Reputation: 73

you should not call the function contain if you get to the endof list but you do call it infinitely. add this before your call:

if (pNode ->next != null)
contains(pNode->next,name);

you also need to stop it from calling contain if it fing the item so your condition will be like :

if (pNode ->next != null && !isEqual)
contains(pNode->next,name);

Upvotes: 0

Related Questions