Thread: Sandclock Linked Lists

  1. #1
    Registered User
    Join Date
    May 2015
    Posts
    90

    Sandclock Linked Lists

    Basically the problem is to go through a matrix (a vector of linked lists) in a 'sand-clock' fashion (as in right; diag left-down; right; diag right-up).

    I made the program, but after testing it, I found out that when making the first diagonal, I lose sight of the contiguous node, and I can never access it again.

    So what I thought was either:
    1. Save every contiguous node in some temporal variable.
    2. Re-route the initial vector list to skip the node that is the diagonal, therefore being able to access it.
    3. Save the memory adresses in some vector and then access them.

    I would like to know if someone has a better idea of it, some already made algorithm or anything.
    I'm not sure if the original matrix could be edited as in point 2, but if it can then that would be my way to go. Is there any other way to do this that doesn't involve any of my 3 solutions?

    Fiskker.

    Some image: Sandclock Linked Lists-reloj-png (the image is the inverse of what im trying, but same concept)
    Last edited by Fiskker; 01-31-2019 at 01:41 PM.

  2. #2
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    It might be helpful to post the program demonstrating what you have tried. I don't understand what you mean by "lose sight of the contiguous node".

    Since you're representing the matrix as a vector of linked lists, I guess that you're dealing with a sparse matrix?
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  3. #3
    Registered User
    Join Date
    May 2015
    Posts
    90
    Quote Originally Posted by laserlight View Post
    It might be helpful to post the program demonstrating what you have tried. I don't understand what you mean by "lose sight of the contiguous node".

    Since you're representing the matrix as a vector of linked lists, I guess that you're dealing with a sparse matrix?
    What I mean by it is that when you edit the matrix, you go to the N node in the first row, then change it and make it point to the N-1 node in the second row, then go to the N-1 node in the second row and make it point to the N-2 node in the third row, etc.

    But after doing that, you cannot acces what's left after the diagonal (to the right of the diagonal), because the pointers are now not pointing 'forward' anymore.
    I'm sorry, i have a hard time explaining it if it isn't graphically.

    Anyway, it is a vector of singly linked lists, all of the same size, thus could be seen as a square matrix with n,m >= 2m where m = 1,...,M (even numbers).

    Ive a matrix VL that looks like:
    Code:
    [ ]--->[1| ]--->[2|\]
    [ ]--->[3| ]--->[4|\]
    I want to print change the pointers and make it like a 'sand-clock' so that going through the list yields:
    Code:
     1 -> 2 -> 3 -> 4 -> 1 -> 2 -> .... (indefinietely)
    Code:
    Code:
    int main(void)
    {
        int i, j, value;
        lista_t VL[CANTIDAD];
    
        for(i = 0; i < CANTIDAD; i++)
        {
            VL[i] = NULL;
    
            for(j = 0; j < CANTIDAD; j++)
            {
                printf("Ingresar valor fila %d: \n", i+1);
                scanf("%d", &value);
                push(&(VL[i]), value);
            }
        }
    
        diagonalizar(VL);
    
        return EXIT_SUCCESS;
    
    }
    void diagonalizar(lista_t VL[])
    {
        int i = 0;
    
        for(i = 0; i < 2; i++)
        {
            anexar(VL, i);
        }
    }
    
    void anexar(lista_t VL[], int i)
    {
        int j;
        lista_t temp;
        /* i = 0 indicates annexing diagonally donwards <V; i = 1 indicates annexing diagonally upwards <^*/
        if(!i)
        {
            for(j = 0; j < (CANTIDAD-1); j++)
            {
                temp = run(VL, j, CANTIDAD-j);
                temp->sig = run(VL, j+1, CANTIDAD-j-1);
            }
        } else {
    
            for(j = CANTIDAD-1; j > 0; j--)
            {
                temp = run(VL, j, j+1);
                temp->sig = run(VL, j-1, j);
            }
        }
    }
    
    lista_t run(lista_t VL[], int fila, int cant)
    {
        lista_t temp = VL[fila];
        int i;
    
        for(i = 0; i < (cant-1); i++)
        {
            temp = temp->sig;
        }
    
        return temp;
    }
    Last edited by Fiskker; 01-31-2019 at 05:25 PM.

  4. #4
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Why are you modifying the matrix? You're tracing a path, so you should store pointers to the entries in another container such that they are linked to form the path, e.g., in a linked list. By modifying the matrix itself, you have effectively "destroyed" it, i.e., it is no longer a matrix.

    I suggest that you do this with a 2D array (as in vector of vectors) as the matrix representation, since you are not actually dealing with a sparse matrix. This will help you to use a linked list to store pointers to the matrix entries while resisting the urge to change the next pointers of the linked lists in the matrix representation, which perhaps would be easier for you to envision. Later, you can rework this for your original vector of linked lists representation.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  5. #5
    Registered User
    Join Date
    May 2015
    Posts
    90
    Quote Originally Posted by laserlight View Post
    Why are you modifying the matrix? You're tracing a path, so you should store pointers to the entries in another container such that they are linked to form the path, e.g., in a linked list. By modifying the matrix itself, you have effectively "destroyed" it, i.e., it is no longer a matrix.

    I suggest that you do this with a 2D array (as in vector of vectors) as the matrix representation, since you are not actually dealing with a sparse matrix. This will help you to use a linked list to store pointers to the matrix entries while resisting the urge to change the next pointers of the linked lists in the matrix representation, which perhaps would be easier for you to envision. Later, you can rework this for your original vector of linked lists representation.
    As for the why, it is an exercise that is given in this way and has to be solved so that you modify the matrix in the manner that I presented in my first post (see image).

    I'm not sure what you mean by 'entries'?
    Also when you say 'store pointers to the entries in another container', do you mean I should ask for memory for new pointers, and then append my matrix to it? I feel like I would not be doing what I'm supposed to if that's the case, because I must modify the matrix they give me.

    I think that point 3 is the best I could do... As in store both diagonals in some vectors and then append it to the last node at the first and last row...

  6. #6
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    An "entry" is an element in the matrix representation. I note that you didn't mention anything about modifying the matrix in your first post, only that you intended to traverse it (typically something that is done without modifying the structure).

    Yes, a secondary container will involve obtaining memory for new pointers, but you don't "append" your "matrix to it"; the pointers will point to the entries of your matrix that form this path.

    Anyway, if you do use a secondary container, you can always relink the underlying linked list nodes (i.e., the entries) later if you want to change the underlying structure.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  7. #7
    Registered User
    Join Date
    May 2015
    Posts
    90
    Yes, sorry.

    Okay, yes, I was thinking that the container should have pointers pointing to each entry of both diagonals. Is this what you say in your second paragraph?

    Just to be sure, the second container is a vector of pointers that point to each entry in the order that I'd like to go through the matrix, is this correct?

  8. #8
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Yes and yes.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  9. #9
    Registered User
    Join Date
    May 2015
    Posts
    90
    Thanks.

    By the way, to do the same thing but backwards (as in going from the last node to the first node in both 'row only paths'), do you agree that I would need 3 pointers to keep track of everything that's going on? (smth like prev, cur, next)

  10. #10
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by Fiskker
    By the way, to do the same thing but backwards (as in going from the last node to the first node in both 'row only paths'), do you agree that I would need 3 pointers to keep track of everything that's going on? (smth like prev, cur, next)
    I think it is best that you implement the code to find out as it probably depends on what algorithm to use and say, whether the matrix representation uses doubly linked lists, e.g., maybe with the secondary container approach or doubly linked lists you don't need so many local pointers.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  11. #11
    Registered User
    Join Date
    May 2015
    Posts
    90
    I ended up using a loop that repeats rg(A)-1 times, starting from the last node with a temporary variable, linking it to the previous one and updating the temporary variable.
    Just in case anyone else is doing something similar and finds this.

    Found myself using the run function for pretty much every case.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Double Linked Dynamic Lists Vs Unrolled Linked Lists
    By lantzvillian in forum C Programming
    Replies: 6
    Last Post: 02-14-2012, 01:07 PM
  2. Replies: 4
    Last Post: 05-01-2010, 10:19 PM
  3. Question about Linked lists of lists
    By hear_no_evil in forum C Programming
    Replies: 2
    Last Post: 11-08-2004, 02:49 AM
  4. question on linked lists(stack with linked lists)
    By dionys in forum C Programming
    Replies: 1
    Last Post: 06-02-2004, 11:08 AM
  5. Linked List of Linked lists Revisited.
    By Qui in forum C++ Programming
    Replies: 11
    Last Post: 04-11-2004, 09:45 PM

Tags for this Thread