Linked list problem.

This is a discussion on Linked list problem. within the C Programming forums, part of the General Programming Boards category; I am having a hard time trying to count how many items in my linked list that are divisible by ...

  1. #1
    Registered User
    Join Date
    Jul 2010
    Posts
    178

    Linked list problem.

    I am having a hard time trying to count how many items in my linked list that are divisible by an int. We will call this int 3. I have attached my divList.c function. Can anyone help? Thanks!
    Code:
    #include "ll.h"
    
    int divList (lnode * h, int div){
    	if (h == NULL) return 0;
    	if (h -> info%div == 0)
    	printf ("%d ", h -> info);
    	divList (h -> next, div);
    }

  2. #2
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    Your function is not returning values like it should. If you find a number divisible by div, you must essentially return 1 plus the value of the divList call on the remainder of the list; if the current value is not divisible by div, just return the value of the divList call on the remainder of the list.

    Code:
    int divList (lnode * h, int div){
        if (h == NULL) return 0;
        if (h -> info%div == 0)
        {
            printf ("%d ", h -> info);
            return 1 + divList (h -> next, div);
        }
        else
            return divList (h -> next, div);
    }
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

  3. #3
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by hk_mp5kpdw View Post
    Your function is not returning values like it should. If you find a number divisible by div, you must essentially return 1 plus the value of the divList call on the remainder of the list; if the current value is not divisible by div, just return the value of the divList call on the remainder of the list.

    Code:
    int divList (lnode * h, int div){
        if (h == NULL) return 0;
        if (h -> info%div == 0)
        {
            printf ("%d ", h -> info);
            return 1 + divList (h -> next, div);
        }
        else
            return divList (h -> next, div);
    }
    Unfortunately, it returns the same thing I am not looking for. I may not have made myself clear. In my input list I have the numbers of 3, 4, 0,1, 6, 8, -3, 21, and -33. All these numbers are being divided by the int 3. What happens is it prints all the numbers divisible by 3 like -33, 21, -3, 6, 0 and 3. What my actually end result or what should print is the count of the numbers divisible by 3. In this case it should print 5 because that is how many elements that were divisible by 3. I appreciate the help given.

  4. #4
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,533
    > In this case it should print 5 because that is how many elements that were divisible by 3
    What does it print? 6 perhaps?

    > What happens is it prints all the numbers divisible by 3 like -33, 21, -3, 6, 0 and 3.
    Because that's how many numbers there are...
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  5. #5
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by Salem View Post
    > In this case it should print 5 because that is how many elements that were divisible by 3
    What does it print? 6 perhaps?

    > What happens is it prints all the numbers divisible by 3 like -33, 21, -3, 6, 0 and 3.
    Because that's how many numbers there are...
    My bad, you are correct it shoud print 6. What the above functions print is -33, 21, -3, 6, 0 and 3.

  6. #6
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Got it! Here is what I did,
    Code:
    #include "ll.h"
    
    int count = 0;
    
    int divList (lnode * h, int div){
            if (h == NULL) return 0;
            if (h -> info%div == 0)
            count++;
            divList (h -> next, div);
            printf ("%d ", count);
    }
    Thanks for all the help!

  7. #7
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,533
    > Got it! Here is what I did,
    That's wrong then.
    Using a messy global variable doesn't make your function re-usable at all.


    Post #3 was correct.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  8. #8
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Not sure what you mean by "messy global variable" Post #3 is my post, could you mean post #2?

  9. #9
    and the hat of wrongness Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    32,533
    Sorry, it was hk_mp5kpdw that posted it.


    Re: "messy"
    > int count = 0;
    - You HAVE to remember to reset this each time you want to use the function.
    - The code is unusable in a multi-threaded environment.

    You can also achieve the same thing without using recursion, which would be even better.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.
    I support http://www.ukip.org/ as the first necessary step to a free Europe.

  10. #10
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by Salem View Post
    Sorry, it was hk_mp5kpdw that posted it.


    Re: "messy"
    > int count = 0;
    - You HAVE to remember to reset this each time you want to use the function.
    - The code is unusable in a multi-threaded environment.

    You can also achieve the same thing without using recursion, which would be even better.
    Our assigment is recursion and that is what the instructor wants at this time. Not sure what you mean by multi-threaded environment but I happen to have that feeling we are not there.

    Are you saying that int count = 0 needs to be set to 0 everytime the recursion loop runs? In other words, read the first element in the list, set to 0, read the next element, set to 0, etc? As it stands, the code of:
    Code:
    #include "ll.h"
    
    int count = 0;
    
    int divList (lnode * h, int div){
            if (h == NULL) return 0;
            if (h -> info%div == 0)
            count++;
            divList (h -> next, div);
            printf ("%d ", count);
    }
    gets the count of 6 elements that are divisible by 3. The only thing I have to contend with now is it prints the "6" six times and I believe that can be corrected in my printList.c function.

  11. #11
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    Instead of making count a global variable, make it into a parameter.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  12. #12
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by laserlight View Post
    Instead of making count a global variable, make it into a parameter.
    How is count a global variable? It is not a local variable since it is declared in this function only? I am a bit confused now. Why and how would I want to make it a parameter. I probably need it dumbed down to my level. Is the last code I wrote correct for what I am trying to accomplish?

  13. #13
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    21,717
    Quote Originally Posted by csharp100
    How is count a global variable? It is not a local variable since it is declared in this function only?
    You declared count at file scope. If you declared count in the function, it would either be as a parameter or as something like:
    Code:
    int divList (lnode * h, int div) {
        int count = 0;
        if (h == NULL) return 0;
        if (h -> info%div == 0)
        count++;
        divList (h -> next, div);
        printf ("%d ", count);
    }
    Quote Originally Posted by csharp100
    Why and how would I want to make it a parameter.
    Looking more closely at what you want to do, I'd say: my mistake. No, count should not be a parameter. Rather, you do not need it at all, save for the fact that you want to print the count in divList if h is not a null pointer. As such, you would use a local variable named count to store the result of the recursive call (+1), and then print that, and return it.

    Quote Originally Posted by csharp100
    Is the last code I wrote correct for what I am trying to accomplish?
    Notice that there is a path of control for which divList does not return a value. That is wrong.
    C + C++ Compiler: MinGW port of GCC
    Version Control System: Bazaar

    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  14. #14
    Registered User
    Join Date
    Jul 2010
    Posts
    178
    Quote Originally Posted by laserlight View Post
    You declared count at file scope. If you declared count in the function, it would either be as a parameter or as something like:
    Code:
    int divList (lnode * h, int div) {
        int count = 0;
        if (h == NULL) return 0;
        if (h -> info%div == 0)
        count++;
        divList (h -> next, div);
        printf ("%d ", count);
    }

    Looking more closely at what you want to do, I'd say: my mistake. No, count should not be a parameter. Rather, you do not need it at all, save for the fact that you want to print the count in divList if h is not a null pointer. As such, you would use a local variable named count to store the result of the recursive call (+1), and then print that, and return it.


    Notice that there is a path of control for which divList does not return a value. That is wrong.
    Do I really need to print it, or can I just return "count" to say printList.c.

  15. #15
    Registered User hk_mp5kpdw's Avatar
    Join Date
    Jan 2002
    Location
    Northern Virginia/Washington DC Metropolitan Area
    Posts
    3,801
    This is how I imagined the function being used/called:

    Code:
    ...
    
    int divList (lnode * h, int div){
        if (h == NULL) return 0;
        if (h -> info%div == 0)
            return 1 + divList (h -> next, div);
        else
            return divList (h -> next, div);
    }
    
    ...
    
    int main(void)
    {
        lnode * head = NULL;
        int count = 0;
    
        ...
    
        /* Stuff linked list pointed to by "head" with values. */
    
        ...
    
        /* Find out how many items in linked list are divisible by 3. */
        count = divList(head,3);
        /* Print count */
        printf("There are %d elements divisible by 3.",count);
    
        ...
    }
    It does not print the individual items it finds (I'm guessing that was just debug code) but rather just the count.
    "Owners of dogs will have noticed that, if you provide them with food and water and shelter and affection, they will think you are god. Whereas owners of cats are compelled to realize that, if you provide them with food and water and shelter and affection, they draw the conclusion that they are gods."
    -Christopher Hitchens

Page 1 of 2 12 LastLast
Popular pages Recent additions subscribe to a feed

Similar Threads

  1. singly linked circular list
    By DarkDot in forum C++ Programming
    Replies: 0
    Last Post: 04-24-2007, 08:55 PM
  2. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  3. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  4. Linked list with two class types within template.
    By SilasP in forum C++ Programming
    Replies: 3
    Last Post: 02-09-2002, 05:13 AM
  5. singly linked list
    By clarinetster in forum C Programming
    Replies: 2
    Last Post: 08-26-2001, 10:21 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21