Thread: Pointer to struct...

Well, what do you not understand?

Your code is saying here I have a new complex type called node which is a struct and it contains an integer and a pointer to another struct just like itself, and by the way after I am done defining it just rename the whole shabam to ListNode.

You can look at it like this:

Imagine you have a set of boxes that have names written on top of them and each box has two compartments.

In the first compartment you find a number. In the second you find the name of the next box you have to look into.

In your example, the struct is the BOX, the pointer to the struct is the NAME OF THE BOX (i.e. address) and the int vertex is the NUMBER IN THE BOX.

Note that a box does not contain ANOTHER BOX. It contains an address of another box(i.e. a pointer). I think this is the source of your confusion.

Correct. The idea of a list is that you can't select an element in the middle of it. You have to go there from the start node moving along from pointer to pointer until you get to it.

To continue the analogy, imagine you have a list of boxes like the ones described in the previous post and the box containing number 7 has a prize inside. Just by looking at the boxes there is no way for you to know which one has number 7 inside. So the logical way to start looking for it is to "iterate the list". You start at the first box, open it, if the number is not 7 check the name of the next box you have to open next and so on...

That is a pointer to a pointer to a node. If a pointer to a node is going to tell you where to find the node (i.e. the box) a pointer to a pointer to a node is going to tell you where to find the label on the box.

A pointer behaves like any other variable in C, if left un-initialized it points to some random place. You want to initialize it first by allocating memory for the node and then making the node pointer point to that memory location, like so:

Code:

ListNode *adj_list;
adj_list = malloc(sizeof(ListNode));

if(adj_list == NULL) printf("NO MEMORY AVAILABLE");
else{
/* Now it's ok to write to adj_list */
 adj_list->vertex = 7;
 adj_list->next = NULL;
}

thanks...

supposing that we have a list and want to access every "cell" so as to see if a value is already in the list...
how can we do this?

the following is what i have thought untill now...it may be wrong however!! :P

i have made, lets say 10 pointers type ListNode with malloc like this:

Code:

adj_list = (ListNode **)malloc(10*sizeof(ListNode *));

if i am right till now i think that the first 'pointer' is a box which has:
- a value and
- a pointer to the next box.
- and also an address

then,

i call a function named read_edges() in which, i type (10 times) a pair of Int values and call another function named search_and_insert (the call is inside read_edges() ) in which i check if a value is already in the list.

Code:

int read_edges(ListNode **adj_list, int n){
	int k, a, b, i;
		printf("Please type a value for k: ");
		scanf("%d", &k); 
		for(i=0; i<k; i++){
			printf("Dwse ena zeugos timwn:");
			scanf("%d %d", &a, &b);
				if( (a>=0)&&(a<=(n-1)) && (b>=0)&&(b<=(n-1)) ){
					search_and_insert(adj_list[i] , a);
					search_and_insert(adj_list[i], b);
				}else{
					printf("Ektos diasthmatos ta zeugi a,b!\n");
				}
		}
return 0;
}

the problem now is that i can' t write the search_and_insert function...i almost know what to do, but i "loose" everything in my mind then thinking with pointers!!!

i would appreciate any help!

oh, i forgot to post how search_and_insert must be...see below:

Code:

int *search_and_insert(ListNode *front, int v){
	front = NULL; //initialize front to NULL
	/*
         now i think that i must have a while loop here but i do not know the codition... :/
        */
        if(*front != NULL){
		//....do not know again what to write...
	}
		
}

lastly, i know that i have a BIG problem in pointers but all the above is an exercise (probably difficult)...
thank you guys...

Think about it like this: A pointer is an address! (a memory address).

When I was a beginner and got confused about pointers I always found it easy to repeat that in my mind. The type of the pointer just tells you what KIND of data is stored at that address. If you have an int pointer, then the pointer is an address where you will find an integer. If the pointer is of struct node type, then the pointer is an address where you will find a struct node.

There really isn't any more to this than that. When you call malloc() you are asking for an address where you can read/write data of a particular type.

So now you will ask: ok mr. smarty pants if a pointer is an address then what is a pointer-pointer. It is the address of a pointer instance. Confused yet?

Code:

//This is an int stored somewhere in static memory
int nr = 5; 

//This is a pointer telling me the address where nr is stored
int* addressOfNumber = &nr; 

//This is a pointer telling me the address of where the pointer to the number is stored
int** addressOfPointerToNumber = &addressOfNumber; 

//Modify the value at the address addressOfNumber is pointing at to 7(basically, modify nr)
(*addressOfNumber) = 7; 

//Modify the value at the address pointed to by the pointer addressOfPointerToNumber is 
//pointing to to 9 (basically modify nr again through two levels of indirection)
(**adressOfPointerToNumber) = 9;

If you don't like this blame von Neumann. He was the one with the silly idea to store everything in the same memory :P. (The things we could do without that limitation....)

Insertion in a linked list should usually done at the front or the end because that is the least computationally expensive place to insert. If you want to insert in the middle of the list, you first have to go through the whole list to find it. In some cases this may be necessary but if that is what you need, then a linked list is not the DATA STRUCTURE you want to use to represent your data.

You don't need to reinvent the wheel here, if you can't figure out the ALGORITHM for insertion you can look it up (on wikipedia or something) and it will most likely tell you the pseudocode to do it. Then you just have to adapt that to your C syntax and move on little by little.

So, i think i got the whole think with pointers but i must know what i have first...
what i mean?...

inside main() i say:

Code:

adj_list = (ListNode **)malloc(10*sizeof(ListNode *));

which means that i have an array (size n). each cell of the array is a pointer type ListNode. ok i got it...but WHERE EXACTLY DOES EACH POINTER SHOWS?

If the pointer is of struct node type, then the pointer is an address where you will find a struct node.

you can take a look at the struct in my first post...if i helps...
thanks...

Originally Posted by brack

So, i think i got the whole think with pointers but i must know what i have first...
what i mean?...

inside main() i say:

Code:

adj_list = (ListNode **)malloc(10*sizeof(ListNode *));

which means that i have an array (size n). each cell of the array is a pointer type ListNode. ok i got it...but WHERE EXACTLY DOES EACH POINTER SHOWS?

you can take a look at the struct in my first post...if i helps...
thanks...

Each pointer points to some VALID memory location where you can write information pertaining to listnode objects. If you want to really know the address you can do this for one or more of the nodes in order to print it:

Code:

 //This will print the actual memory address ListNode[0] is pointing at
 printf("%p",(void*)ListNode[0]);

After doing that you will probably see a hexadecimal number.

Initially after the malloc there is random stuff at that memory location so you can't use it before initializing it. All malloc is doing is giving you a place to store your stuff but you have to store it yourself.

Each pointer points to some VALID memory location where you can write information pertaining to listnode objects. If you want to really know the address you can do this for one or more of the nodes in order to print it:

Code:

//This will print the actual memory address ListNode[0] is pointing at
printf("%p",(void*)ListNode[0]);

After doing that you will probably see a hexadecimal number.

Initially after the malloc there is random stuff at that memory location so you can't use it before initializing it. All malloc is doing is giving you a place to store your stuff but you have to store it yourself.

it was probable what i was thinking and not so helpfull....pfff
nevermind, there is a function named read_edges(ListNode **adj_list, int n). i must read a value for k (k is the number of edges). For k times i must now read pairs of (a, b) which are integer numbers. Suppose a, b is a pair. if a is out of range or b is out of range or a AND b are out of range (RANGE: [0 - n-1]) then i must move on the next pair. in the other case i must call 2 times another function search_and_insert().
i hope you understood....

please take a look at the code and tell me what i do wrong...

Code:

int read_edges(ListNode **adj_list, int n){
	int k;
	int a, b;
	int i;
		scanf("%d", &k); 
		scanf("%d%d", &a, &b);

				if( (a>=0)&&(a<=(n-1)) && (b>=0)&&(b<=(n-1)) ){
					search_and_insert(adj_list[i], a);
					search_and_insert(adj_list[i], b);
				}else{
					printf("out of range a,b !\n");
                                        scanf("%d%d", &a, &b);
                                }
return 0;
}

thanks so much...

Well a few things here:

1) i is uninitialized so adj_list[i] is probably going to give you a segmentation fault.

2) Why are you inserting a and b in the same place adj_list[i]?

Post your search and insert function or preferrably, your entire code.

Check that the values you read with scanf are stored correctly in a,b and k.