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

Quote:

---

Originally Posted by kyber

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

Quote:

---

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?

Quote:

---

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.

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

and after displaying and everything the program crashes.

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

Quote:

---

Originally Posted by tabstop

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

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.

Quote:

---

Originally Posted by quzah

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.

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

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.