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

heres the screenshot so u can get the idea....

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.

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.