Linked list, New try (was:Linked list, no out put,help)

Discussion in 'C Programming' started by fool, Jul 1, 2006.

  1. fool

    fool Guest

    Dear group,

    Thanks for all those who helped previously.

    Now I get some value printed. Is that the value of the list getting
    printed? Am I
    really polluted the list?

    Previous thread link (sorry for google)
    http://groups.google.com/group/comp...b772b/578ac16a2ed4ed35?hl=en#578ac16a2ed4ed35

    #include<stdio.h>
    #include<stdlib.h>
    struct node
    {
    int data;
    struct node *next;
    };

    struct node *add_node(struct node *p, int funct_data)
    {
    struct node *t = p;
    /* passed by values. So I save the argument value in a
    * temp variable.Am I correct?*/

    t = malloc(sizeof *t);
    if(!t)
    {
    printf("mem error");
    exit(EXIT_FAILURE);
    }
    t->data = funct_data;
    return t;
    }

    int main(void)
    {
    struct node *p,*q;
    int i;
    q=malloc(sizeof *q);
    if(!q)
    exit(EXIT_FAILURE);
    for(i=0 ; i< 6 ; i++)
    {
    q = add_node(p, i);
    printf("%d\n",q->data);
    }
    return 0;
    }
     
    fool, Jul 1, 2006
    #1
    1. Advertising

  2. fool

    Michael Mair Guest

    fool schrieb:
    > Dear group,
    >
    > Thanks for all those who helped previously.
    >
    > Now I get some value printed. Is that the value of the list getting
    > printed? Am I
    > really polluted the list?


    Sorry, I do not understand the question.
    You do not really have a list but a set of allocated list nodes.
    The value of the list cannot be printed.

    >
    > Previous thread link (sorry for google)
    > http://groups.google.com/group/comp...b772b/578ac16a2ed4ed35?hl=en#578ac16a2ed4ed35


    Sum the results up, please.

    > #include<stdio.h>
    > #include<stdlib.h>
    > struct node
    > {
    > int data;
    > struct node *next;
    > };
    >
    > struct node *add_node(struct node *p, int funct_data)
    > {
    > struct node *t = p;
    > /* passed by values. So I save the argument value in a
    > * temp variable.Am I correct?*/


    Yes. Note that the argument value does not need to be saved.

    >
    > t = malloc(sizeof *t);


    Now you overwrite the "temp variable" to which you saved p.

    > if(!t)
    > {
    > printf("mem error");


    Consider writing error messages to stderr instead of stdout.

    > exit(EXIT_FAILURE);
    > }
    > t->data = funct_data;


    You forgot to link t and p, e.g.
    t->next = p;

    > return t;
    > }
    >
    > int main(void)
    > {
    > struct node *p,*q;
    > int i;
    > q=malloc(sizeof *q);


    You assign a value to q.
    p is not initialised.

    > if(!q)
    > exit(EXIT_FAILURE);
    > for(i=0 ; i< 6 ; i++)
    > {
    > q = add_node(p, i);


    You overwrite the value of q and use p uninitialised.
    This means you have a memory leak and "all bets are off",
    respectively.

    > printf("%d\n",q->data);
    > }
    > return 0;
    > }


    Consider this corrected version (not largely tested):

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


    struct node {
    int data;
    struct node *next;
    };

    struct node *prepend_node (struct node *pSuccessor, int new_data)
    {
    struct node *pNew = malloc(sizeof *pNew);
    if(NULL == pNew)
    {
    fprintf(stderr, "mem error\n");
    exit(EXIT_FAILURE);
    }
    pNew->data = new_data;
    pNew->next = pSuccessor;

    return pNew;
    }

    void print_list (const struct node *pFirst)
    {
    const struct node *pNode;

    printf("Contents:");
    for (pNode = pFirst; NULL != pNode; pNode = pNode->next) {
    printf("\t%d", pNode->data);
    }
    printf("\n");
    }

    void free_list (struct node *pFirst)
    {
    struct node *pNode, *pNext;

    if (pFirst) {
    for (pNode = pFirst; NULL != pNode; pNode = pNext) {
    pNext = pNode->next;
    free(pNode);
    }
    }
    }

    int main (void)
    {
    struct node *list = NULL;
    int i;

    for(i=0 ; i< 6 ; i++)
    {
    list = prepend_node(list, i);
    print_list(list);
    }
    free_list(list);

    return 0;
    }


    Cheers
    Michael
    --
    E-Mail: Mine is an /at/ gmx /dot/ de address.
     
    Michael Mair, Jul 1, 2006
    #2
    1. Advertising

  3. fool

    santosh Guest

    fool wrote:
    > Dear group,
    >
    > Thanks for all those who helped previously.
    >
    > Now I get some value printed. Is that the value of the list getting
    > printed? Am I
    > really polluted the list?
    >
    > Previous thread link (sorry for google)
    > http://groups.google.com/group/comp...b772b/578ac16a2ed4ed35?hl=en#578ac16a2ed4ed35
    >
    > #include<stdio.h>
    > #include<stdlib.h>
    > struct node
    > {
    > int data;
    > struct node *next;
    > };
    >
    > struct node *add_node(struct node *p, int funct_data)
    > {
    > struct node *t = p;


    Why this assignment? p just contains an indeterminate value. This will
    lead to undefined behaviour.

    > /* passed by values. So I save the argument value in a
    > * temp variable.Am I correct?*/
    >
    > t = malloc(sizeof *t);
    > if(!t)
    > {
    > printf("mem error");


    Add a newline or call fflush(stdout). Otherwise the above statement is
    not garenteed to appear on the console.

    > exit(EXIT_FAILURE);


    You've allocated memory in main(). If you simply exit(), that memory
    might be lost to the system. You should return to main() indicating an
    error, free() the memory and then exit().

    > }
    > t->data = funct_data;
    > return t;
    > }
    >
    > int main(void)
    > {
    > struct node *p,*q;
    > int i;
    > q=malloc(sizeof *q);


    add_node() allocates an instance of struct node and returns. Here
    you've set q to point to another instance of struct node. Then below
    you overwrite q to contain the address of the node allocated in
    add_node(), thus losing access to the original node and causing a
    memory leak.

    Either allocate the structure in main() or in add_node(), not in both.

    > if(!q)
    > exit(EXIT_FAILURE);


    Again you're exiting with free()'ing the memory. This won't matter for
    demos, but unless you get into the habit of free()'ing now, you'll
    mess-up later on in serious code.

    > for(i=0 ; i< 6 ; i++)
    > {
    > q = add_node(p, i);


    Here's where you overwrite the node allocated above with the one
    allocated in add_node(). Remove the allocation in main() and simply let
    add_node() do it.

    Incidentally, since add_node() allocates a fresh copy of struct node,
    each time it's called you'll have to save a copy of the pointer it
    returns each time. Otherwise you simply lose access to the previously
    malloc()'ed structures, again a memory leak.

    > printf("%d\n",q->data);
    > }
    > return 0;
    > }


    I suggest a complete rewrite, based on either pete's code posted
    earlier or sample implementations given in a good book like K&R2. You
    need to understand memory allocation and deacllocation better. You'll
    also need to think about the overall structure of your linked list
    program.

    As written, the code above is fragile and erroneous to the extreme.
     
    santosh, Jul 1, 2006
    #3
  4. Re: Linked list, New try

    "santosh" <> writes:

    > fool wrote:
    >> Dear group,
    >>
    >> Thanks for all those who helped previously.
    >>
    >> Now I get some value printed. Is that the value of the list getting
    >> printed? Am I
    >> really polluted the list?
    >>
    >> Previous thread link (sorry for google)
    >> http://groups.google.com/group/comp...b772b/578ac16a2ed4ed35?hl=en#578ac16a2ed4ed35
    >>
    >> #include<stdio.h>
    >> #include<stdlib.h>
    >> struct node
    >> {
    >> int data;
    >> struct node *next;
    >> };
    >>
    >> struct node *add_node(struct node *p, int funct_data)
    >> {
    >> struct node *t = p;

    >
    > Why this assignment? p just contains an indeterminate value. This will
    > lead to undefined behaviour.


    to the op : see the call from main(). You didnt set p.

    >
    >> /* passed by values. So I save the argument value in a
    >> * temp variable.Am I correct?*/


    yes, but you havent passed anything into p.

    >>
    >> t = malloc(sizeof *t);
    >> if(!t)
    >> {
    >> printf("mem error");

    >
    > Add a newline or call fflush(stdout). Otherwise the above statement is
    > not garenteed to appear on the console.
    >
    >> exit(EXIT_FAILURE);

    >
    > You've allocated memory in main(). If you simply exit(), that memory
    > might be lost to the system. You should return to main() indicating an
    > error, free() the memory and then exit().


    Out of curiosity and OT , what systems/OSs dont replace mallocs in the
    event of a program crash or exit() call?

    >
    >> }
    >> t->data = funct_data;
    >> return t;
    >> }
    >>
    >> int main(void)
    >> {
    >> struct node *p,*q;
    >> int i;
    >> q=malloc(sizeof *q);

    >
    > add_node() allocates an instance of struct node and returns. Here
    > you've set q to point to another instance of struct node. Then below
    > you overwrite q to contain the address of the node allocated in
    > add_node(), thus losing access to the original node and causing a
    > memory leak.
    >
    > Either allocate the structure in main() or in add_node(), not in both.
    >
    >> if(!q)
    >> exit(EXIT_FAILURE);

    >
    > Again you're exiting with free()'ing the memory. This won't matter for


    No he's not. The memory wasnt allocated. In this case..

    To the OP : dont forget your "next" pointer. Look at the parameters you
    are calling add_node with from main. Use a debugger or printfs to
    examine the data being passed to your add_node function - you will see
    "p" is not initialised and "next" is not used to keep the list.

    best of luck!
     
    Richard G. Riley, Jul 1, 2006
    #4
  5. fool

    santosh Guest

    Re: Linked list, New try

    Richard G. Riley wrote:
    > "santosh" <> writes:

    .... snip ...
    > > You've allocated memory in main(). If you simply exit(), that memory
    > > might be lost to the system. You should return to main() indicating an
    > > error, free() the memory and then exit().

    >
    > Out of curiosity and OT , what systems/OSs dont replace mallocs in the
    > event of a program crash or exit() call?


    Well, Windows versions before and inclusive of 98 sometimes failed to
    recover all the memory after a process exited. I agree that today's
    protected mode OSes recover all the memory, but forgetting to free()
    still entails a memory leak during program execution. This could become
    significant if the program in question is a daemon/service.

    Besides, free()'ing allocated memory is good practise. It forces you to
    mentally keep track of your resources, and be aware about the state of
    your process.
     
    santosh, Jul 1, 2006
    #5
  6. Re: Linked list, New try

    Richard G. Riley wrote:
    <snip>
    >
    > Out of curiosity and OT , what systems/OSs dont replace mallocs in the
    > event of a program crash or exit() call?
    >


    RTOS's like vxWorks don't. Inside kernel or kernel-like environments
    (task/tasklet/thread) you're not likely to get much help either.


    Mark F. Haigh
     
    Mark F. Haigh, Jul 2, 2006
    #6
  7. fool

    Ben Pfaff Guest

    Re: Linked list, New try

    "Mark F. Haigh" <> writes:

    > Richard G. Riley wrote:
    >> Out of curiosity and OT , what systems/OSs dont replace mallocs in the
    >> event of a program crash or exit() call?


    > RTOS's like vxWorks don't. Inside kernel or kernel-like environments
    > (task/tasklet/thread) you're not likely to get much help either.


    Those environments are usually freestanding, not hosted, as I
    understand it. Freestanding environments don't necessarily have
    a malloc function in their libraries at all.
    --
    "What is appropriate for the master is not appropriate for the novice.
    You must understand the Tao before transcending structure."
    --The Tao of Programming
     
    Ben Pfaff, Jul 2, 2006
    #7
  8. Re: Linked list, New try

    Ben Pfaff wrote:
    > "Mark F. Haigh" <> writes:
    >
    > > Richard G. Riley wrote:
    > >> Out of curiosity and OT , what systems/OSs dont replace mallocs in the
    > >> event of a program crash or exit() call?

    >
    > > RTOS's like vxWorks don't. Inside kernel or kernel-like environments
    > > (task/tasklet/thread) you're not likely to get much help either.

    >
    > Those environments are usually freestanding, not hosted, as I
    > understand it. Freestanding environments don't necessarily have
    > a malloc function in their libraries at all.


    To tell you the truth, I'm not sure if vxWorks is technically hosted or
    freestanding. It's at least hosted-ish. It contains a complete C89
    implementation/library. The thing is, _you_ have to write the code
    that spawns a new task (ie thread), then calls the program's main()
    with the appropriate arguments. Note that only one program may have a
    main(), or you will get symbol collisions, since all programs loaded
    share a C namespace as well as (typically) an identical view of and
    identical permissions to memory and hardware resources.


    Mark F. Haigh
     
    Mark F. Haigh, Jul 2, 2006
    #8
  9. fool

    Morris Dovey Guest

    fool (in ) said:

    | Dear group,
    |
    | Thanks for all those who helped previously.
    |
    | Now I get some value printed. Is that the value of the list getting
    | printed? Am I
    | really polluted the list?

    You still have problems (not the least of which is that your thread
    has been hijacked.)

    I've reworked your code into something that I like better - and I've
    added the printf() statements that allow seeing what the list really
    looks like.

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto
     
    Morris Dovey, Jul 2, 2006
    #9
  10. fool

    Morris Dovey Guest

    It'd probably have been more help if I'd actually pasted the code into
    the message. :*)

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

    /* Define data structures */

    struct node
    { int data;
    struct node *next;
    };
    struct list
    { struct node *head;
    struct node *tail;
    };

    /* Add a node to the specified list */

    struct node *add_node(struct list *q, int funct_data)
    { struct node *t = malloc(sizeof *t);

    if (!t)
    { printf("add_node: memory allocation failed\n");
    exit(EXIT_FAILURE);
    }
    t->data = funct_data;
    t->next = NULL;
    if (q->head) q->tail->next = t;
    else q->head = t;
    q->tail = t;
    return t;
    }

    /* Free allocated nodes in list */

    void zap(struct node *e)
    { if (e->next) zap(e->next);
    free(e);
    }

    /* Test program with debug printf()s */

    int main(void)
    { struct list q = { NULL,NULL };
    struct node *p;
    int i;

    printf("\nAdding nodes to list...\n\n");
    for(i=0 ; i< 6 ; i++)
    { p = add_node(&q, i);
    printf("%d\n",p->data);
    }

    printf("\nList @ %p {%p %p}\n\n",&q,q.head,q.tail);
    for (p=q.head; p; p=p->next)
    { printf("Node @ %p {%d %p}\n",p,p->data,p->next);
    }
    if (q.head) zap(q.head);
    q.head = NULL;
    return 0;
    }

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto
     
    Morris Dovey, Jul 2, 2006
    #10
  11. Morris Dovey said:

    <snip>
    >
    > printf("\nList @ %p {%p %p}\n\n",&q,q.head,q.tail);
    > for (p=q.head; p; p=p->next)
    > { printf("Node @ %p {%d %p}\n",p,p->data,p->next);


    When printing a pointer value, you need to cast it to void * if it is not
    already of that type:

    printf("\nList @ %p {%p %p}\n\n",
    (void *)&q, (void *)q.head, (void *)q.tail);

    for (p=q.head; p; p=p->next)
    { printf("Node @ %p {%d %p}\n",
    (void *)p, (void *)p->data, (void *)p->next);

    --
    Richard Heathfield
    "Usenet is a strange place" - dmr 29/7/1999
    http://www.cpax.org.uk
    email: rjh at above domain (but drop the www, obviously)
     
    Richard Heathfield, Jul 2, 2006
    #11
  12. fool

    Morris Dovey Guest

    Richard Heathfield (in ) said:

    | When printing a pointer value, you need to cast it to void * if it
    | is not already of that type:

    Thanks. (The scary part is that the cast actually makes sense to me.)

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto
     
    Morris Dovey, Jul 2, 2006
    #12
  13. fool

    Chris Torek Guest

    Re: Linked list, New try

    In article <>
    Mark F. Haigh <> wrote:
    >To tell you the truth, I'm not sure if vxWorks is technically hosted or
    >freestanding.


    These days, both: an "RTP" is effectively hosted, while "kernel" code
    is freestanding.

    >It's at least hosted-ish. It contains a complete C89
    >implementation/library.


    Complete (mostly? -- it uses the Dinkumware code) C99 library, for
    RTPs. The compilers are still not quite there yet though. The
    kernel-side code is significantly smaller.

    >The thing is, _you_ have to write the code
    >that spawns a new task (ie thread), then calls the program's main()
    >with the appropriate arguments. Note that only one program may have a
    >main(), or you will get symbol collisions, since all programs loaded
    >share a C namespace as well as (typically) an identical view of and
    >identical permissions to memory and hardware resources.


    Except in RTPs. RTPs do share (the read-only code of) libraries,
    but have private data space and namespaces.
    --
    In-Real-Life: Chris Torek, Wind River Systems
    Salt Lake City, UT, USA (40°39.22'N, 111°50.29'W) +1 801 277 2603
    email: forget about it http://web.torek.net/torek/index.html
    Reading email is like searching for food in the garbage, thanks to spammers.
     
    Chris Torek, Jul 2, 2006
    #13
  14. fool

    Morris Dovey Guest

    The code I posted showed assembly of a FIFO list. As usual, I had
    second thoughts and decided that the OP may have been trying to build
    a LIFO list. Since sleep wasn't much of an option, I put the following
    together before wandering off...

    [ With thanks to RJH for catching my failure to cast pointers before
    printing. ]

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

    struct node
    { struct node *next;
    int data;
    };

    struct node *add_lifo(struct node **list,int data)
    { struct node *new = malloc(sizeof *new);
    if (!new) exit(EXIT_FAILURE);
    new->next = *list;
    new->data = data;
    return *list = new;
    }

    int main(void)
    { int i;
    struct node *list = NULL;
    struct node *p;
    for (i=0; i<6; i++) add_lifo(&list,i);
    printf("\nList @ %p -> %p\n\n",(void*)&list,(void*)list);
    for (p=list; p; p=p->next)
    { printf("Node @ %p {%p %d}\n",(void*)p,(void*)p->next,p->data);
    }
    return 0;
    }

    --
    Morris Dovey
    DeSoto Solar
    DeSoto, Iowa USA
    http://www.iedu.com/DeSoto
     
    Morris Dovey, Jul 2, 2006
    #14
  15. On 30 Jun 2006 23:53:47 -0700, "fool" <> wrote:

    >Dear group,
    >
    > Thanks for all those who helped previously.
    >
    > Now I get some value printed. Is that the value of the list getting
    >printed? Am I
    >really polluted the list?
    >
    >Previous thread link (sorry for google)
    >http://groups.google.com/group/comp...b772b/578ac16a2ed4ed35?hl=en#578ac16a2ed4ed35
    >
    >#include<stdio.h>
    >#include<stdlib.h>
    > struct node
    > {
    > int data;
    > struct node *next;
    > };
    >
    >struct node *add_node(struct node *p, int funct_data)
    >{
    > struct node *t = p;
    > /* passed by values. So I save the argument value in a
    > * temp variable.Am I correct?*/


    Since the very next statement changes the value of t, this
    initialization is of no value.

    >
    > t = malloc(sizeof *t);
    > if(!t)
    > {
    > printf("mem error");
    > exit(EXIT_FAILURE);
    > }
    > t->data = funct_data;
    > return t;


    You have returned the address of the new node to the caller but you
    have not linked this node to the list. You may have intended
    p->next = t;
    but that has problems as discussed below.

    >}
    >
    >int main(void)
    >{
    > struct node *p,*q;
    > int i;
    > q=malloc(sizeof *q);


    q now points to an uninitialized block of memory aligned and sized for
    holding a node.

    > if(!q)
    > exit(EXIT_FAILURE);


    The question here is why do you care if the malloc succeeded. You
    never use the value in q to address a node. So why did you call
    malloc in the first place?

    > for(i=0 ; i< 6 ; i++)
    > {
    > q = add_node(p, i);


    p is uninitialized. Its value is indeterminate. Any attempt to
    evaluate it, such as being passed to a function, causes undefined
    behavior.

    Each time you execute this statement, the previous value in q gets
    destroyed, causing a memory leak.

    > printf("%d\n",q->data);
    > }
    > return 0;
    >}


    In order to have a linked list, each node in the list except the last
    must point to the next. In your case, this would be accomplished by
    setting the next member of the parent node to the address of the new
    node.

    It is also common to use a pointer to identify the first node in a
    list. Common approaches include a stand-alone pointer or a defined
    node where only the next member is used.


    Remove del for email
     
    Barry Schwarz, Jul 3, 2006
    #15
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. bienwell
    Replies:
    4
    Views:
    3,854
    bienwell
    May 27, 2005
  2. John Salerno
    Replies:
    20
    Views:
    859
    John Salerno
    Aug 11, 2006
  3. Linked list, no out put,help

    , Jun 30, 2006, in forum: C Programming
    Replies:
    8
    Views:
    295
    goose
    Jun 30, 2006
  4. joshd
    Replies:
    12
    Views:
    675
    John Carson
    Oct 2, 2006
  5. Fabio Z Tessitore

    who is simpler? try/except/else or try/except

    Fabio Z Tessitore, Aug 12, 2007, in forum: Python
    Replies:
    5
    Views:
    378
Loading...

Share This Page