how to use the same principle..

This is a discussion on how to use the same principle.. within the C Programming forums, part of the General Programming Boards category; i need to find out if a linked list ends with NULL or go back to one of its members ...

  1. #1
    Banned
    Join Date
    Oct 2008
    Posts
    1,535

    how to use the same principle..

    i need to find out if a linked list ends with NULL
    or go back to one of its members

    i was told to ue the turtle rabbit algorithm
    which cuts the first half of a given list

    i cant understan how the turtle rabbit algorithm is linked to my problem
    ??

  2. #2
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    Well, you can always scan through the list and check each node to see if you have wrapped back around to the beginning of the list. If you reach the beginning again, that means the list is circular and therefore doesn't end with NULL.

    If the list can wrap back around to any node (not just the head), then you will need to store a list of visited nodes, and check each node you go to to see if you have already visited it. If you have already visited it, then the list does not end with NULL.

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by bithub View Post
    a list of visited nodes
    that could be an array of node pointers.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    Quote Originally Posted by bithub View Post
    Well, you can always scan through the list and check each node to see if you have wrapped back around to the beginning of the list. If you reach the beginning again, that means the list is circular and therefore doesn't end with NULL.

    If the list can wrap back around to any node (not just the head), then you will need to store a list of visited nodes, and check each node you go to to see if you have already visited it. If you have already visited it, then the list does not end with NULL.
    i need to use only something similar to the rabbit turtle
    algorithm

  5. #5
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    In that case, create 2 node pointers to iterate through the list. Every iteration through your loop, increment the turtle node pointer to the next node and increment the rabbit pointer two nodes ahead. Keep doing this until either the rabbit equals NULL, or the turtle equals the rabbit.

  6. #6
    Banned
    Join Date
    Oct 2008
    Posts
    1,535
    yes that the turtle rabit algorithm

    how to use it in order to find out if the last node
    point to NULL
    or it points to some other node in the list

  7. #7
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by bithub View Post
    Keep doing this until either the rabbit equals NULL, or the turtle equals the rabbit.
    Why would the turtle ever equal the rabbit?

    Quote Originally Posted by transgalactic2 View Post
    how to use it in order to find out if the last node
    point to NULL
    or it points to some other node in the list
    You can't.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  8. #8
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    Why would the turtle ever equal the rabbit?
    Because the rabbit is moving faster than the turtle. Therefore, if there is a loop, the rabbit will eventually catch the turtle and they will be on the same node.

    how to use it in order to find out if the last node
    point to NULL
    or it points to some other node in the list
    If the rabbit ever hits NULL, then the last node points to NULL. If the rabbit ever lands on the same node as the turtle, then there is a loop.

  9. #9
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    Quote Originally Posted by bithub View Post
    Because the rabbit is moving faster than the turtle. Therefore, if there is a loop, the rabbit will eventually catch the turtle and they will be on the same node.
    Okay, that makes sense now. I was thinking that the rabbit would be perpetually two steps ahead, but obviously it is 2 then 4 then 6 then 8, etc.

    I just did this on paper and noticed that with both odd and even numbered lists the rabbit seems to circle and land on the turtle by the end of the rabbit's second pass, which is also by the end of the turtle's *first* pass.
    Code:
    --------
    .|
    -.-|
    --.--|
    |--.----
    -|--.
    ---|-.
    -----|.
    -------X
    Here's eight nodes in a circular list where "." is the turtle, "|" is the rabbit and X is both.
    Last edited by MK27; 07-01-2009 at 04:59 PM.
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  10. #10
    Registered User
    Join Date
    Sep 2004
    Location
    California
    Posts
    3,246
    I just did this on paper and noticed that with both odd and even numbered lists the rabbit seems to circle and land on the turtle by the end of the rabbit's second pass, which is also by the end of the turtle's *first* pass.
    Yeah, the efficiency should be O(n).

  11. #11
    Registered User
    Join Date
    Oct 2008
    Location
    TX
    Posts
    2,047
    Quote Originally Posted by transgalactic2 View Post
    yes that the turtle rabit algorithm

    how to use it in order to find out if the last node
    point to NULL
    or it points to some other node in the list
    The turtle-rabbit algorithm for detecting loops in a linked list implementation is an established one.
    Did you try to Google it? There are plenty of code examples to help get you started on this quest.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Liskov substitution principle
    By George2 in forum C++ Programming
    Replies: 9
    Last Post: 02-25-2008, 05:30 AM
  2. Packet Interception(?)
    By muehl in forum Networking/Device Communication
    Replies: 6
    Last Post: 10-28-2005, 08:47 PM
  3. Bush vs. Kerry
    By jlou in forum A Brief History of Cprogramming.com
    Replies: 178
    Last Post: 11-29-2004, 03:45 PM
  4. Principal of least privilege
    By carlin70 in forum C++ Programming
    Replies: 2
    Last Post: 02-22-2003, 08:15 PM
  5. principle components analysis
    By mijter in forum C++ Programming
    Replies: 0
    Last Post: 04-18-2002, 08:48 AM

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