Data structures basic questions

This is a discussion on Data structures basic questions within the C Programming forums, part of the General Programming Boards category; I was starting out with data structures, but had these few doubts: Code: struct node { int x; node *next; ...

  1. #1
    Registered User
    Join Date
    Apr 2007
    Posts
    13

    Data structures basic questions

    I was starting out with data structures, but had these few doubts:

    Code:
    struct node {
      int x;
      node *next;
    };
    Now, If we have a pointer *p such that

    Code:
    struct node *p= malloc(sizeof(node));
    Do we have 2 pointers now ?
    1. Pointer p ?
    2. pointer p->next ?

    Im really confused at to where these 2 pointers point to ?

  2. #2
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,014
    p points to your currently allocated node struct.
    I take it this is a linked list. In such case, next will point to another node struct.
    The idea is to create something like a ladder - you begin at one step, then you continue to the next step via next, until the end.

    In this case, p->next points somewhere, which is undefined.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  3. #3
    Registered User
    Join Date
    Apr 2007
    Posts
    13
    Quote Originally Posted by Elysia View Post
    p points to your currently allocated node struct.
    I take it this is a linked list. In such case, next will point to another node struct.
    The idea is to create something like a ladder - you begin at one step, then you continue to the next step via next, until the end.

    In this case, p->next points somewhere, which is undefined.
    Well, that creates another problem for me.

    So, p points to currently allocated node struct memory.
    Suppose that memory is 1776.

    If the start pointer of linked list is *start pointing to first node [Address: 2113]

    If we want to add nodes, delete nodes, we always do this :
    Code:
    p=start
    What does this do ? Wont p now point to 2113 ?
    Now there is no pointer to point to the previously allocated memory location !
    If this is true , what is the use of declaring memory in location 1776 anyway in the first place?

  4. #4
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,014
    Quote Originally Posted by WarDoGG View Post
    What does this do ? Wont p now point to 2113 ?
    Indeed.

    Now there is no pointer to point to the previously allocated memory location !
    True.

    If this is true , what is the use of declaring memory in location 1776 anyway in the first place?
    The idea is that you would have another pointer there.
    Consider:

    Code:
    typedef struct node node;
    node* p = malloc( sizeof(node) ); // Addr: 1000
    node* start = p;
    p = malloc( sizeof(node) ); // Addr: 2000
    start->next = p;
    p = malloc( sizeof(node) ); // Addr: 3000
    start->next->next = p;
    p->next = NULL;
    p = NULL;
    While this may look complicated, the idea is simple. The "next" pointer inside the node structure now connects the list.
    The first node may end up at, say, address 1000. We assign that to start, so now start & p = 1000.
    Now we allocate another node at 2000, assigned to p.
    Now, p = 2000, start = 1000.
    We connect this node by setting start->next = p (2000).
    Now we allocate another node (3000), overwriting the previous address (2000), but since start->next is 2000, that doesn't matter. The memory is not lost.
    Now we connect this by walking the list (start (1000) -> next (2000) -> next = 3000). We set the next pointer to the newest node, at address 3000.
    We then set the next in the node at 3000 to NULL, to indicate the end of the list.
    Then we set the p pointer to NULL.
    But since start->next->next is 3000, the address in p isn't lost.

    It's all about connecting a list, where the next pointer contains the address of your nodes.
    It's then possible to walk the list and free the memory later without p.

    (Did that make sense?)
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  5. #5
    Registered User
    Join Date
    Apr 2007
    Posts
    13
    Quote Originally Posted by Elysia View Post
    start->next = p;
    Is this allowed ? I thought it isnt.

    What is the difference between *start and *p ???

    Im asking this because :

    we create *p by :

    Code:
    struct node *p = malloc(sizeof(node));
    But we create *start by just:

    Code:
    struct node *start=NULL;
    So, whats the difference in both these statements ? Can start have a start->next ?

    Also, how do i pronounce
    start ->next
    ??

  6. #6
    Kernel hacker
    Join Date
    Jul 2007
    Location
    Farncombe, Surrey, England
    Posts
    15,677
    Quote Originally Posted by WarDoGG View Post
    Is this allowed ? I thought it isnt.

    What is the difference between *start and *p ???

    Im asking this because :

    we create *p by :

    Code:
    struct node *p = malloc(sizeof(node));
    But we create *start by just:

    Code:
    struct node *start=NULL;
    In the original code posted by elysia, it is start = p

    So, whats the difference in both these statements ? Can start have a start->next ?
    start->next is valid to use if start points to valid memory (NULL does not count as "valid memory"). Of course, if start->next has not been set to a valid memory location, then we would be breaking the rules if we access that memory location.

    Also, how do i pronounce start ->next ??[/QUOTE]

    I would say "start" "arrow" "next", or "start" "pointer to" "next".

    --
    Mats
    Compilers can produce warnings - make the compiler programmers happy: Use them!
    Please don't PM me for help - and no, I don't do help over instant messengers.

  7. #7
    C++まいる!Cをこわせ!
    Join Date
    Oct 2007
    Posts
    23,014
    Quote Originally Posted by WarDoGG View Post
    Is this allowed ? I thought it isnt.
    Why shouldn't it be?

    What is the difference between *start and *p ???
    start and p are merely pointers.

    Im asking this because :

    we create *p by :

    Code:
    struct node *p = malloc(sizeof(node));
    But we create *start by just:

    Code:
    struct node *start=NULL;
    No, we create a node and store its address in p.
    We do not create a *start.
    You seem to have the wrong understanding of pointers.
    When I define a pointer, I do this:

    node* p;
    Red indicates the TYPE of the pointer that the pointer POINTS to.
    Green indicates that the variable we create is a pointer, and not a struct node.
    And lastly, the blue defines the NAME of the POINTER.

    A pointer is not a storage unit. It merely holds the address of something.
    That's why we use malloc to actually create the something. Malloc returns an address to what you created, so we store that ADDRESS in a pointer.

    The type tells the compiler what kind of thing the pointer holds the address to (points to).
    Therefore, we can safely share these addresses between pointers of the same type, which I did several times.
    Quote Originally Posted by Adak View Post
    io.h certainly IS included in some modern compilers. It is no longer part of the standard for C, but it is nevertheless, included in the very latest Pelles C versions.
    Quote Originally Posted by Salem View Post
    You mean it's included as a crutch to help ancient programmers limp along without them having to relearn too much.

    Outside of your DOS world, your header file is meaningless.

  8. #8
    Registered User
    Join Date
    Apr 2007
    Posts
    13
    Well. thanks a ton !

    All those explanations really helped. Thanks again.

    Quote Originally Posted by Elysia View Post
    Why shouldn't it be?


    start and p are merely pointers.


    No, we create a node and store its address in p.
    We do not create a *start.
    You seem to have the wrong understanding of pointers.
    When I define a pointer, I do this:

    node* p;
    Red indicates the TYPE of the pointer that the pointer POINTS to.
    Green indicates that the variable we create is a pointer, and not a struct node.
    And lastly, the blue defines the NAME of the POINTER.

    A pointer is not a storage unit. It merely holds the address of something.
    That's why we use malloc to actually create the something. Malloc returns an address to what you created, so we store that ADDRESS in a pointer.

    The type tells the compiler what kind of thing the pointer holds the address to (points to).
    Therefore, we can safely share these addresses between pointers of the same type, which I did several times.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. COntrol structures and functions questions
    By angelicscars in forum C Programming
    Replies: 1
    Last Post: 11-21-2005, 11:50 AM
  2. Replies: 2
    Last Post: 06-16-2005, 11:03 AM
  3. Replies: 4
    Last Post: 06-14-2005, 06:45 AM
  4. C diamonds and perls :)
    By Carlos in forum A Brief History of Cprogramming.com
    Replies: 7
    Last Post: 05-16-2003, 11:19 PM
  5. different sized data structures
    By breed in forum C Programming
    Replies: 3
    Last Post: 03-04-2002, 02:00 PM

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21