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: Attachment 15639 (the image is the inverse of what im trying, but same concept)

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 laserlight

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;
}

---

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 laserlight

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...

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.

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?

Yes and yes.

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)

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.

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.