Acyclic

This is a discussion on Acyclic within the C++ Programming forums, part of the General Programming Boards category; i need write a program to check if a list is acyclic, which means that a travel from any node ...

  1. #1
    Registered User
    Join Date
    Oct 2006
    Posts
    7

    Acyclic

    i need write a program to check if a list is acyclic, which means that a travel from any node in the list must not come back to the node itself.
    a node is a struct type defined like that
    Code:
    struct Node{
    int data;
    Node *next;
    };
    but i am not allowed to allocate memory proportional to the list size and i even don't know the list size.

    i now have no idea to do it, can anything give me a hand, please?

  2. #2
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    Here's a very simple one. http://en.wikipedia.org/wiki/Floyd's_cycle-finding_algorithm

    Understand the whole thing where the first pointer will 'catch-up' to the second deal.

    ╔╗╔╦══╦╗╔╦══╦╗
    ║╚╝║╔╗║╚╝║╔╗║║
    ║╔╗║╠╣║╔╗║╠╣╠╣
    ╚╝╚╩╝╚╩╝╚╩╝╚╩╝

    codez http://code.google.com/p/zxcvbn/

  3. #3
    Registered User
    Join Date
    Oct 2006
    Posts
    7
    thanks
    but i am not allow to allocate memory proportional to the list size, so i may not use that algorithm.

  4. #4
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    There is no memory allocation involved in that (O1 storage). If you have a hard time conceptualizing the text, make sure to read 'visualizing the algorithm'

    ╔╗╔╦══╦╗╔╦══╦╗
    ║╚╝║╔╗║╚╝║╔╗║║
    ║╔╗║╠╣║╔╗║╠╣╠╣
    ╚╝╚╩╝╚╩╝╚╩╝╚╩╝

    codez http://code.google.com/p/zxcvbn/

  5. #5
    Registered User
    Join Date
    Oct 2006
    Posts
    7
    Thank you for your advise and i have make it. the assignment need me to do this task by two different methods, are there any other method you can suggest?
    Last edited by kcfung; 10-14-2006 at 08:33 PM.

  6. #6
    Registered User Tonto's Avatar
    Join Date
    Jun 2005
    Location
    New York
    Posts
    1,465
    Does it also have to be O(1) storage? Does it have to be completely different from that other technique?

    ╔╗╔╦══╦╗╔╦══╦╗
    ║╚╝║╔╗║╚╝║╔╗║║
    ║╔╗║╠╣║╔╗║╠╣╠╣
    ╚╝╚╩╝╚╩╝╚╩╝╚╩╝

    codez http://code.google.com/p/zxcvbn/

  7. #7
    Registered User
    Join Date
    Oct 2006
    Posts
    7
    I don't think so, i am only not allowed to allocate memory proportional to the list size and i even don't know the list size, and i can't modify the list , that is all

Popular pages Recent additions subscribe to a feed

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