2 dimensional double linked list structure

This is a discussion on 2 dimensional double linked list structure within the C Programming forums, part of the General Programming Boards category; Hi, I have been given a coursework to make a 2 dimensional double linked lists. Basically like a nxn sort ...

  1. #1
    Registered User
    Join Date
    Nov 2010
    Posts
    11

    Talking 2 dimensional double linked list structure

    Hi,
    I have been given a coursework to make a 2 dimensional double linked lists. Basically like a nxn sort of structure, where each square/node has the address of the ones adjacent to it(and it has to be double linked)

    so i wrote a code, and my program crashes after i end it

    i think its a problem with the data entry(as each node has to have a definitive value)

    please help, im a novice in programming. Also, my code doesnt give me the proper output that i want.

    I went through a few forums and there wasnt much help out there. Can the term 'sparse matrix' be of any use to me??

    Thanks in advance.

    #include <stdio.h>
    #include <stdlib.h>

    struct record{
    int value1;
    struct record *ptr_nxt;
    struct record *ptr_bck;
    struct record *ptr_up;
    struct record *ptr_dwn;

    };

    typedef struct record node;

    main(){
    node *start, *curr, *prev;
    int i,j,rows,cols;

    printf("Please enter the no. of rows you want:\n");
    scanf("%d",&rows);

    printf("Please enter the no. of columns you want:\n");
    scanf("%d",&cols);

    start = (node *)malloc(sizeof(node));
    curr = start;
    prev = start;

    printf("Please type in the value for field:\n");
    scanf("%d",&curr->value1);

    curr->ptr_bck = NULL;
    curr->ptr_up = NULL;

    for(i=1;i<rows;i++){ /*initialisation of outer loop*/
    curr->ptr_nxt = (node *)malloc(sizeof(node));


    printf("Please type in the value for row no. %d\n",i);

    for(j=0;j<cols;j++){
    curr->ptr_dwn = (node *)malloc(sizeof(node));
    prev = curr;
    curr = curr->ptr_dwn;
    curr->ptr_up = prev;

    printf("Please type in the value:\n");
    scanf("%d",&curr->value1);


    }
    curr->ptr_dwn = NULL;
    prev = curr;
    curr = curr->ptr_nxt;
    curr->ptr_bck = prev;
    }curr->ptr_nxt = NULL;

    curr = start;

    for(i=0;i<rows;i++){
    for(j=0;j<cols;j++){
    printf("%p %p %p %d %p %4p\n",curr,curr->ptr_nxt,curr->ptr_dwn,curr->value1,curr->ptr_bck,curr->ptr_up);
    curr = curr->ptr_dwn;
    }
    curr = curr->ptr_nxt;
    }
    }
    Attached Files Attached Files
    Last edited by kyber; 12-11-2010 at 10:46 PM.

  2. #2
    and the Hat of Guessing tabstop's Avatar
    Join Date
    Nov 2007
    Posts
    14,185
    Quote Originally Posted by kyber View Post
    Hi,
    I have been given a coursework to make a 2 dimensional double linked lists. Basically like a nxn sort of structure, where each square/node has the address of the ones adjacent to it(and it has to be double linked)

    so i wrote a code, and my program crashes after i end it

    i think its a problem with the data entry(as each node has to have a definitive value)
    Don't see anything wrong with the data entry, as it's pretty hard to get scanf wrong when working with numbers. The links, though, worry me. I see you sometimes going down, and sometimes going across, but never setting both at the same time (i.e., you have rows, and you have columns, but you don't have a rectangle).

    please help, im a novice in programming. Also, my code doesnt give me the proper output that i want.
    So what do you want, and what do you get?

    I went through a few forums and there wasnt much help out there. Can the term 'sparse matrix' be of any use to me??
    No. If you had read a little bit more, you would have seen that a double-linked list (a bit like what you have got here) is a standard way to implement a sparse matrix. Since you don't want a sparse matrix, then you don't care.

  3. #3
    Registered User
    Join Date
    Nov 2010
    Posts
    11
    like if when do the data entry by defining the rows and columns as 2*2 than the output should show me 4 nodes.
    so i should be able to see the value that i put in my last node. but that node instead of displaying the value (int) it displays the address(no idea where it came from) and the nodes before that have perfectly working output(show the address and the data they carry)

    its the last one that is annoying me, doesnt show the value carried by the node

  4. #4
    Registered User
    Join Date
    Nov 2010
    Posts
    11

    Angry

    and after displaying and everything the program crashes.

  5. #5
    Registered User
    Join Date
    Nov 2010
    Posts
    11
    heres the screenshot so u can get the idea....
    Attached Images Attached Images  
    Last edited by kyber; 12-11-2010 at 11:10 PM.

  6. #6
    Registered User
    Join Date
    Nov 2010
    Posts
    11
    Quote Originally Posted by tabstop View Post
    Don't see anything wrong with the data entry, as it's pretty hard to get scanf wrong when working with numbers. The links, though, worry me. I see you sometimes going down, and sometimes going across, but never setting both at the same time (i.e., you have rows, and you have columns, but you don't have a rectangle).
    How do i make it go simultaneously than?? and sorry for the misinformation. It doesnt take one of the values of the nodes and doesnt display the lst one

  7. #7
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    Are you ever going to have "empty" spots?
    Are you linking all directions when you add a node?
    Code:
    struct foo
    {
        struct foo *north, *east, *south, *west;
        type value;
    };
    Given a single node, are you linking it to everything in every direction? If I write an insert function:
    Code:
    int insertatxy( struct foo *n, size_t x, size_t y );
    ...
    insertatxy( n, 3, 4 );
    Are you properly linking all of your directions? Assuming I'm understanding what you think you're trying to do. If so, are you sure? What happens if:
    Code:
    a b c d e
    f g h i j
    k l m n o
    p q r s t
    u v w x y
    If you were inserting m, you would need to link m->north to h, and h->south to m; m->east to n, and n->west to m; m->south to r, and r->north to m; and finally, m->west to l, and l->east to m.

    Are you doing all of that? Are you treating this as if it were really a 2D array of nodes that you're linking, or are you really thinking it's still just a list of lists? If you allow for empty nodes, what happens:
    Code:
    insertatxy( a,0,0 );
    insertatxy( g,1,1 );
    How are you checking to see if you can do that?

    Quzah.
    Hope is the first step on the road to disappointment.

  8. #8
    Registered User
    Join Date
    Nov 2010
    Posts
    11
    Quote Originally Posted by quzah View Post
    Are you ever going to have "empty" spots?
    Are you linking all directions when you add a node?
    Code:
    struct foo
    {
        struct foo *north, *east, *south, *west;
        type value;
    };
    Given a single node, are you linking it to everything in every direction? If I write an insert function:
    Code:
    int insertatxy( struct foo *n, size_t x, size_t y );
    ...
    insertatxy( n, 3, 4 );
    Are you properly linking all of your directions? Assuming I'm understanding what you think you're trying to do. If so, are you sure? What happens if:
    Code:
    a b c d e
    f g h i j
    k l m n o
    p q r s t
    u v w x y
    If you were inserting m, you would need to link m->north to h, and h->south to m; m->east to n, and n->west to m; m->south to r, and r->north to m; and finally, m->west to l, and l->east to m.

    Are you doing all of that? Are you treating this as if it were really a 2D array of nodes that you're linking, or are you really thinking it's still just a list of lists? If you allow for empty nodes, what happens:
    Code:
    insertatxy( a,0,0 );
    insertatxy( g,1,1 );
    How are you checking to see if you can do that?

    Quzah.
    Well, it was sort of the starting program..but thanks a lot for your inputs. It gave me a lead on what to do next! cheers.

  9. #9
    Registered User
    Join Date
    Nov 2010
    Posts
    11
    okay, i spent like the whole day trying to figure out how to insert the nodes so that the adjacent ones get manipulated as well, but no luck..
    could anyone please please give a sample code of how i can insert a node into the 2d linked list?
    my brain is dead...

  10. #10
    ATH0 quzah's Avatar
    Join Date
    Oct 2001
    Posts
    14,826
    In a regular linked list, or even a double linked list, you have one node that anchors them all down. Just like in an array, you have a single spot that is considered the start. In a 2D array, you have this same spot, but you can go two directions from it. The problem with doing what you're trying to do, is that if you allow for empties, then you have to actually keep track of every node as a distinct entry point, because if you add one out in the middle of nowhere, how do you know what it hooks to? So you either treat the whole thing like a dynamic array, in which point, there's no need to really link them, or you have to actually auto-fill every missing node. What's that mean?
    Code:
    insert( a,0,0 );
    Insert one at the start:
    Code:
    a
    Now do this:
    Code:
    insert( g,1,1 );
    So we have to fill in all the missing pieces:
    Code:
    a 1
    2 g
    You have to insert 1 so you can link it to a, so you can link it to g, and have it be a dummy, and/or, you have to insert a blank 2 node so you can link it to a and then to g; or both.

    Then, you have to decide how you're going to check for blanks. Do you always check for row first, then column, or do you check for column, and then row, or do you check both, or do you allow for checking from any point? What happens if:
    Code:
    * * * d *
    * * * * *
    * * * * *
    * * * * *
    * * * * y
    What happens if those are the only two nodes you have, and you want to insert what would be s? (One north, and one west, of y.) Do you insert off of empty a, down the left row, then across? Do you link from d, down to where s would be, or do you build up from y?

    These are the things you have to think about. Also, all of this "works" because my data is just 25 consecutive values, that nicely divide up along rows and columns. Is your data going to be like that, or how are you going to decide what row and column it should fall upon?

    Quzah.
    Hope is the first step on the road to disappointment.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Reverse function for linked list
    By Brigs76 in forum C++ Programming
    Replies: 1
    Last Post: 10-25-2006, 10:01 AM
  2. Unknown Math Issues.
    By Sir Andus in forum C++ Programming
    Replies: 1
    Last Post: 03-06-2006, 05:54 PM
  3. Replies: 6
    Last Post: 03-02-2005, 01:45 AM
  4. Linked List Help
    By CJ7Mudrover in forum C Programming
    Replies: 9
    Last Post: 03-10-2004, 09:33 PM
  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