how does struct pointer pass and how does struct pointer return result

Go To Last Post
4 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

 

I am using k & R book for  c programming. I am having difficulty in understanding the function given below. Whatever I understand I have explained through the comments 

 

//gcc compiler
// PC program

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

struct Node
{
   char N;                   // structure member
   struct Node * next;       // structure member
};

struct Node* newNode(int n, struct node * next)   // take argument data and pointer to structuure
{
    struct Node *new = malloc(sizeof(*new)); // allocate dynamic memory for variable new type struct
    new->Number = number;    // number = 10
    new->next = next;       // struct node * next = NULL;
    return new;  // return the pointer new type struct
}

int main()
{

    return 0;
}

 

Can anyone help me with how this function works ?

 

This topic has a solution.
Last Edited: Thu. Feb 13, 2020 - 03:36 PM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

The first call next should be NULL
The second call next is the pointer returned from the first call
Rinse and repeat.

This is the classic singly linked list. The next pointer is the link in a chain that points to the next. When next is NULL, that is the end of the list.

This reply has been marked as the solution. 
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

I'd suggest you look at an example call in main() to better understand how it is used. So (because this function use malloc() which is not a good idea for an AVR!!) you would have something like:

int main()
{
    struct Node * pStruct1;
    struct Node * pStruct2;

    pStruct1 = newNode(123, NULL);
    pStruct2 = newNode(456, pStruct1);
    return 0;
}

So this starts by creating to 16 bit pointers which are each going to hold the address of an instance of struct Node.

 

When this program starts there are no nodes yet so the first time newNode() is called you cannot pass a "next" value to have the address of a node you want to link to because there are no nodes yet. So in this case you only real option is to call the allocation function with the "next" value set to NULL. When newNode() is then called the first thing it does is to call malloc() to ask C to givce a block of memory on the heap to be used to store the new "struct Node" it is creating. If you built this code for AVR then char N would be one byte and "struct Node * next" would be a 2 byte pointer so the entire struct would be just 3 bytes. So the malloc() will create a block of 3 bytes. But as you hopefully now know from your other thread the size of things vary so if you built this for a PC then the chances are there is 1 byte for "N" but for 32 bit aligned access it will probably be held as 1 of 4 padded bytes. It's also likely that the pointer is 4 bytes too. So for a PC the chances are the malloc() might allocate 8 bytes. . Once the bytes have been allocated they then start to be used. 

 

The "new" in the function now has the address of the 3/8 byte memory block but it's not just any 3/8 bytes. It is those bytes laid out as a char field called N and a pointer field call "next". "new" points to the entire block and new->N, for example, is the address of the "N" field in the block. new->next is the address of the "next" field. So the code:

    new->Number = number;    // number = 10
    new->next = next;       // struct node * next = NULL;

stores the "number" parameter that was passed into the function into a field called "Number" but this is where things don't start to make a lot of sense. The stuct Node {} has members called N and next. It does NOT have a member called "Number" so already this code does not make sense. But let's assume that is a typographical error and N/Number are really the same  thing then it still does not make sense. The structure itself is:

struct Node
{
   char N;                   // structure member

so the N/(Number) field is a "char" - that is 1 byte. Yet the function involved in storing values into that field is:

struct Node* newNode(int n, struct node * next) 

this is saying that "n" passed into the function is "int" not a "char" ?!? so suppose we go with my main() and the function is called with 123 and then 456. Well it just so happens that 123 is below 255 so that will "fit" into a char. So even though an int value 123 is passed in it is safely stored in "char N". But 456 has a problem. It is actually (1*256 + 200) so the 1*256 won't fit into a char. So what actually gets stored is just the 200 bit.

 

So I'd start by rewriting this code in a form that is coherent, likely to compile and likely to work. That is:

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

struct Node
{
   int N;                   // structure member
   struct Node * next;       // structure member
};

struct Node* newNode(int n, struct node * next)   // take argument data and pointer to structuure
{
    struct Node *new = malloc(sizeof(*new)); // allocate dynamic memory for variable new type struct
    new->N = number;
    new->next = next;       // struct node * next = NULL;
    return new;  // return the pointer new type struct
}

int main()
{
    struct Node * pStruct1;
    struct Node * pStruct2;

    pStruct1 = newNode(123, NULL);
    pStruct2 = newNode(456, pStruct1);
    return 0;
}    

So now newNode() is called once as newNode(123, NULL). It creates one instance of struct Node on the heap then sets the N field to 123 and the "next" field to NULL. The second time it is called another instance is allocated on the heap, N is set to 456 (it fits this time) and the "next" field is set to point "backwards" to pStruct1 so the two structs are now "linked". In fact what you are creating here is known as a "linked list". It's a bit like an array (because it can store things like 123, 456) but it is not of a fixed size. Each time newNode() is called the list grows. If, each time (apart from the first) the "next" is given the address of the immediately previous one (with the first call being NULL to effectively mark "the list ends here") then as long as you always know the address of the last entry added to the list you can follow the links to get back to any other one int the list.

 

So if you want to know if 222 is stored in the list you could take the address of the last one that was allocated look at that->N and see if it holds 222. If it doesn't you need to move on so you then do something like "that = that->Next" so in this case "that" now holds the address of the previous one. You can now check that->N to see if it's the 222 you are looking for. If not do the same thing all over again. You keep going until that==NULL which means it's been set from the "next" entry in the very first item created. So you have reached the end of the list without finding 222 so it was not in the list. That is something like:

 

stuct Node * findEntry(struct Node * start, int n) {
    struct Node * that;
    that = start;
    while(1) {
        if (that->N == n) {
            // found what we're looking for
            return that;
        }
        that = that->next;
        if (that == NULL) {
            // reached the end and nothing found so indicate
            // to caller by returning NULL
            return that;
        }
}

int main(void) {
    struct Node * pStruct1;
    struct Node * pStruct2;
    struct Node * found;

    pStruct1 = newNode(123, NULL);
    pStruct2 = newNode(456, pStruct1);
    found = findEntry(pStruct2, 222);
    if (found != NULL) {
        // found->N is 222 !! It exists, it exists!
    }
}

You might want to consider now if you had several things in the list how you could delete one from the middle of the list (something you most definitely could NOT do with arrays!).

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 1

PS forgot to say that while my example code has multiple pStruct1, pStruct2 I didn't actually need this. Just:

int main(void) {
    struct Node * pStruct;
    struct Node * found;

    pStruct = newNode(123, NULL);
    pStruct = newNode(456, pStruct);
    found = findEntry(pStruct, 222);
    if (found != NULL) {
        // found->N is 222 !! It exists, it exists!
    }
}

would work as well. but I was using "1", "2" to hopefully give a clearer picture of the order in which things were happening.

 

You don't need to keep separate pointers to each node created for the very fact they are all linked. All you need is a pointer to one end of the list so you can follow the links to get to any other element in it.

 

Later you will learn about "doubly linked" lists which is the same idea but each entry not only has a "next" pointer but also a "prev"ious pointer. So you can go forwards and backwards in traversing the list. It also makes "chopping things out of the middle" a lot easier too.

Last Edited: Thu. Feb 13, 2020 - 12:55 PM