Linked list question

Discussion in 'C Programming' started by Chapman, Sep 21, 2003.

  1. Chapman

    Chapman Guest

    I tried to run this code after compiling it but it always gives me the stack
    dump...Anyone can give me advice? Thanks

    #include <stdio.h>

    typedef struct stack {
    int data;
    struct stack *next;
    } stack;

    void push(stack *s, int x);
    int pop(stack *s);
    int empty(stack **s);

    int main() {

    int m, n, result;
    stack *st = NULL;

    push(st, 2);
    push(st, 3);
    m = pop(st);
    n = pop(st);
    result = m + n;
    printf("The result is %d\n", result);

    return 0;
    }

    int empty(stack **s) {

    return ((*s == NULL) ? 1 : 0);
    }

    void push(stack *s, int x) {

    stack *ptr;
    ptr = (stack *)malloc(sizeof(stack));
    ptr->data = x;
    ptr->next = s->data;
    s->data = ptr;
    }

    int pop(stack *s) {

    int p;
    stack *ptr;

    if (s->data != NULL) {
    ptr = s->data;
    p = ptr->data;
    s->data = ptr->next;
    }

    return p;
    }
     
    Chapman, Sep 21, 2003
    #1
    1. Advertising

  2. On Sun, 21 Sep 2003 16:59:19 GMT, "Chapman" <> wrote:

    >I tried to run this code after compiling it but it always gives me the stack
    >dump...Anyone can give me advice? Thanks
    >
    >#include <stdio.h>
    >
    >typedef struct stack {
    > int data;
    > struct stack *next;
    >} stack;
    >
    >void push(stack *s, int x);


    Cannot change the actual first argument, does not return a result.



    >int pop(stack *s);
    >int empty(stack **s);


    Use descriptive names like 'isEmpty' (pure 'empty' can also be a verb).



    >int main() {
    >
    > int m, n, result;
    > stack *st = NULL;
    >
    > push(st, 2);


    Can not affect 'st', which therefore remains 'NULL'.



    > push(st, 3);
    > m = pop(st);


    So here you're trying to pop an item via a 'NULL' pointer.


    > n = pop(st);
    > result = m + n;
    > printf("The result is %d\n", result);
    >
    > return 0;
    >}
    >
    >int empty(stack **s) {
    >
    > return ((*s == NULL) ? 1 : 0);
    >}
    >
    >void push(stack *s, int x) {
    >
    > stack *ptr;
    > ptr = (stack *)malloc(sizeof(stack));
    > ptr->data = x;
    > ptr->next = s->data;
    > s->data = ptr;
    >}
    >
    >int pop(stack *s) {
    >
    > int p;
    > stack *ptr;
    >
    > if (s->data != NULL) {
    > ptr = s->data;
    > p = ptr->data;
    > s->data = ptr->next;
    > }
    >
    > return p;
    >}
     
    Alf P. Steinbach, Sep 21, 2003
    #2
    1. Advertising

  3. "Chapman" <> wrote:

    >I tried to run this code after compiling it but it always gives me the stack
    >dump...Anyone can give me advice? Thanks
    >
    >#include <stdio.h>

    #include <stdlib.h>
    >
    >typedef struct stack {
    > int data;
    > struct stack *next;
    >} stack;

    The name of this type is confusing, it describes not a stack but merely
    an element of a stack.

    >
    >void push(stack *s, int x);

    void push(stack **s, int x);

    >int pop(stack *s);

    int pop(stack **s);

    >int empty(stack **s);
    >
    >int main() {
    >
    > int m, n, result;
    > stack *st = NULL;
    >
    > push(st, 2);

    push( &st, 2);

    > push(st, 3);

    push( &st, 3);

    > m = pop(st);

    m = pop( &st);

    > n = pop(st);

    n = pop( &st);

    > result = m + n;
    > printf("The result is %d\n", result);
    >
    > return 0;
    >}
    >
    >int empty(stack **s) {
    >
    > return ((*s == NULL) ? 1 : 0);
    >}
    >
    >void push(stack *s, int x) {

    void push(stack **s, int x) {
    >
    > stack *ptr;
    > ptr = (stack *)malloc(sizeof(stack));

    Drop the cast, id did hide the fact that you failed to provide a
    prototype for malloc by including stdlib.h.
    Check the return value of malloc().

    > ptr->data = x;
    > ptr->next = s->data;

    Change this to:
    ptr->next = *s;

    > s->data = ptr;

    and this to:
    *s = ptr.
    >}
    >
    >int pop(stack *s) {

    int pop(stack **s) {
    >
    > int p;

    p is a strange name for non-pointer variable.

    > stack *ptr;
    >
    > if (s->data != NULL) {

    Make this:
    if ( *s != NULL) {

    > ptr = s->data;

    Make this:
    ptr = *s;

    > p = ptr->data;
    > s->data = ptr->next;

    Make this:
    *s = ptr->next;
    > }


    What if your stack was empty?

    > return p;
    >}
    >

    Remark: you may drop the variable ptr in pop().

    All corrections applied we get:


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

    typedef struct stack {
    int data;
    struct stack *next;
    } stack;

    void push(stack **s, int x);
    int pop(stack **s);
    int empty(stack **s);

    int main()
    {
    int m, n, result;
    stack *st = NULL;

    push( &st, 2);
    push( &st, 3);
    m = pop( &st);
    n = pop( &st);

    result = m + n;
    printf("The result is %d\n", result);
    getchar();
    return EXIT_SUCCESS;
    }

    int empty(stack **s)
    {
    return ((*s == NULL) ? 1 : 0);
    }

    void push(stack **s, int x)
    {
    stack *ptr;

    ptr = malloc(sizeof(stack));
    if ( ptr == NULL )
    {
    fprintf( stderr, "push(): memory allocation failed." );
    exit( EXIT_FAILURE );
    }
    ptr->data = x;
    ptr->next = *s;

    *s = ptr;
    }

    int pop(stack **s)
    {
    int x;

    if ( *s != NULL)
    {
    x = (*s)->data;
    *s = (*s)->next;
    }
    else
    {
    fprintf( stderr, "Attempt to pop() from empty stack." );
    exit( EXIT_FAILURE );
    }

    return x;
    }


    Regards

    Irrwahn
    --
    My other computer is a abacus.
     
    Irrwahn Grausewitz, Sep 21, 2003
    #3
  4. Chapman

    James K Guest

    On Sun, 21 Sep 2003 16:59:19 +0000, Chapman wrote:

    > I tried to run this code after compiling it but it always gives me the stack
    > dump...Anyone can give me advice? Thanks
    >
    > #include <stdio.h>
    >
    > typedef struct stack {
    > int data;
    > struct stack *next;
    > } stack;

    ....
    > void push(stack *s, int x) {
    >
    > stack *ptr;
    > ptr = (stack *)malloc(sizeof(stack));
    > ptr->data = x;
    > ptr->next = s->data;


    You are assigning a field intended to store an address with the integer
    stored in s->data. In fact, you seem to be doing a lot of this in both
    directions:

    > s->data = ptr;
    > if (s->data != NULL) {
    > ptr = s->data;
    > p = ptr->data;
    > s->data = ptr->next;


    I made a few quick changes, though this certainly has its own issues as
    well:

    #include <stdio.h>

    typedef struct list
    {
    int data;
    struct list *next;
    } list;

    typedef struct stack
    {
    struct list* top;
    } stack;

    void push(stack *s, int x);
    int pop(stack *s);
    int empty(stack *s);

    int main() {

    int m, n, result;
    stack * st;

    st = malloc (sizeof(stack));

    if (st == NULL)
    {
    fprintf (stderr, "Allocation error\n");
    exit (1);
    }


    push(st, 2);
    push(st, 3);
    if (!(empty (st)))
    m = pop(st);
    else
    fprintf (stderr, "Stack error: m has no known value\n");
    if (!(empty(st)))
    n = pop(st);
    else
    fprintf (stderr, "Stack error: n has no known value\n");
    result = m + n;
    printf("The result is %d\n", result);

    return 0;
    }

    int empty(stack *s) {

    return ((s->top == NULL) ? 1 : 0);
    }

    void push(stack *s, int x) {

    list *ptr;
    ptr = (list *)malloc(sizeof(list));
    ptr->data = x;
    if (s->top)
    ptr->next = s->top;
    s->top = ptr;
    }

    int pop(stack *s) {

    int p;
    list *ptr;

    if (s->top != NULL) {
    ptr = s->top;
    p = ptr->data;
    s->top = ptr->next;
    free (ptr);
    }

    return p;
    }
     
    James K, Sep 21, 2003
    #4
  5. Chapman

    Al Bowers Guest

    James K wrote:

    >
    > I made a few quick changes, though this certainly has its own issues as
    > well:
    >
    > #include <stdio.h>
    >
    > typedef struct list
    > {
    > int data;
    > struct list *next;
    > } list;
    >
    > typedef struct stack
    > {
    > struct list* top;
    > } stack;
    >
    > void push(stack *s, int x);
    > int pop(stack *s);
    > int empty(stack *s);
    >
    > int main() {
    >
    > int m, n, result;
    > stack * st;
    >
    > st = malloc (sizeof(stack));
    >
    > if (st == NULL)
    > {
    > fprintf (stderr, "Allocation error\n");
    > exit (1);
    > }
    >
    >
    > push(st, 2);


    There is no initialization or assignment.
    What value to you thing st->top will have when you
    call function push?

    > void push(stack *s, int x) {
    >
    > list *ptr;
    > ptr = (list *)malloc(sizeof(list));
    > ptr->data = x;
    > if (s->top)
    > ptr->next = s->top;
    > s->top = ptr;
    > }
    >


    --
    Al Bowers
    Tampa, Fl USA
    mailto: (remove the x)
    http://www.geocities.com/abowers822/
     
    Al Bowers, Sep 21, 2003
    #5
  6. Chapman

    James K Guest

    On Sun, 21 Sep 2003 18:16:45 -0400, Al Bowers wrote:

    > James K wrote:
    >
    >>
    >> I made a few quick changes, though this certainly has its own issues as
    >> well:

    >
    > There is no initialization or assignment.
    > What value to you thing st->top will have when you
    > call function push?


    On my system: 0. On the systems that I typically develop for: pick a
    number. For the record, I also didn't give a proto for malloc or check
    that it actually assigned me any heap space in push().

    >> void push(stack *s, int x) {
    >>
    >> list *ptr;
    >> ptr = (list *)malloc(sizeof(list));
    >> ptr->data = x;
    >> if (s->top)
    >> ptr->next = s->top;
    >> s->top = ptr;
    >> }
     
    James K, Sep 22, 2003
    #6
  7. Chapman

    Chapman Guest

    "Irrwahn Grausewitz" <> wrote in message
    news:...
    > "Chapman" <> wrote:
    >
    > >I tried to run this code after compiling it but it always gives me the

    stack
    > >dump...Anyone can give me advice? Thanks
    > >
    > >#include <stdio.h>

    > #include <stdlib.h>
    > >
    > >typedef struct stack {
    > > int data;
    > > struct stack *next;
    > >} stack;

    > The name of this type is confusing, it describes not a stack but merely
    > an element of a stack.
    >
    > >
    > >void push(stack *s, int x);

    > void push(stack **s, int x);
    >


    Thanks Irrwhan for the comments and advice. Why do I need to make the
    prototype to 'stack **s' instead of 'stack *s'
    Is it because I declare stack *st in the main function. Yes, it only defines
    the node, not the whole stack.
     
    Chapman, Sep 22, 2003
    #7
  8. On Mon, 22 Sep 2003 03:40:54 GMT, "Chapman" <> wrote:

    >
    >"Irrwahn Grausewitz" <> wrote in message
    >news:...
    >> "Chapman" <> wrote:
    >>
    >> >I tried to run this code after compiling it but it always gives me the

    >stack
    >> >dump...Anyone can give me advice? Thanks
    >> >
    >> >#include <stdio.h>

    >> #include <stdlib.h>
    >> >
    >> >typedef struct stack {
    >> > int data;
    >> > struct stack *next;
    >> >} stack;

    >> The name of this type is confusing, it describes not a stack but merely
    >> an element of a stack.
    >>
    >> >
    >> >void push(stack *s, int x);

    >> void push(stack **s, int x);
    >>

    >
    >Thanks Irrwhan for the comments and advice. Why do I need to make the
    >prototype to 'stack **s' instead of 'stack *s'
    >Is it because I declare stack *st in the main function. Yes, it only defines
    >the node, not the whole stack.


    No, it because since p passes by value, any changes you make to s when
    it is a stack * are local to push and are lost when push exits. Since
    you call push several times to place multiple elements on the stack,
    you obviously want subsequent calls to be aware of what changed on
    previous calls.

    By using stack** and passing the address of a pointer, push can use *s
    to dereference the address and actually update the pointer in the
    calling function directly.


    <<Remove the del for email>>
     
    Barry Schwarz, Sep 22, 2003
    #8
  9. On Sun, 21 Sep 2003 20:01:29 -0700, James K
    <1.we.attbi.com> wrote:

    >On Sun, 21 Sep 2003 18:16:45 -0400, Al Bowers wrote:
    >
    >> James K wrote:
    >>
    >>>
    >>> I made a few quick changes, though this certainly has its own issues as
    >>> well:

    >>
    >> There is no initialization or assignment.
    >> What value to you thing st->top will have when you
    >> call function push?

    >
    >On my system: 0. On the systems that I typically develop for: pick a
    >number. For the record, I also didn't give a proto for malloc or check
    >that it actually assigned me any heap space in push().


    Technically, it is indeterminate and attempting to evaluate an
    indeterminate value invokes undefined behavior. This is the standard
    for the language.

    If you want to address the characteristics of your specific system(s),
    you would do better to post in newsgroup(s) devoted to them.


    <<Remove the del for email>>
     
    Barry Schwarz, Sep 22, 2003
    #9
  10. Chapman

    James K Guest

    On Mon, 22 Sep 2003 06:31:20 +0000, Barry Schwarz wrote:
    >>>> I made a few quick changes, though this certainly has its own issues as
    >>>> well:
    >>>
    >>> There is no initialization or assignment.
    >>> What value to you thing st->top will have when you
    >>> call function push?

    >>
    >>On my system: 0. On the systems that I typically develop for: pick a
    >>number. For the record, I also didn't give a proto for malloc or check
    >>that it actually assigned me any heap space in push().

    >
    > Technically, it is indeterminate and attempting to evaluate an
    > indeterminate value invokes undefined behavior. This is the standard
    > for the language.
    >
    > If you want to address the characteristics of your specific system(s),
    > you would do better to post in newsgroup(s) devoted to them.


    Easy, tiger. I was _agreeing_ with you that my quick little hack had
    problems (like the disclaimer at the top says) and acknowledging, by
    mentioning the different behaviour on different systems (which I never
    named), that I was invoking non-std behaviour.

    Disclaimer: I have also, unintentionally, used spelling which is
    nonstandard for the US, which is where both this post and this poster are
    from. This message may self-destruct as a result.
     
    James K, Sep 23, 2003
    #10
    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. Chris Ritchey
    Replies:
    7
    Views:
    511
    emerth
    Jul 10, 2003
  2. Chris Ritchey

    Generating a char* from a linked list of linked lists

    Chris Ritchey, Jul 9, 2003, in forum: C Programming
    Replies:
    7
    Views:
    501
    emerth
    Jul 10, 2003
  3. fool
    Replies:
    14
    Views:
    542
    Barry Schwarz
    Jul 3, 2006
  4. joshd
    Replies:
    12
    Views:
    701
    John Carson
    Oct 2, 2006
  5. jawdoc
    Replies:
    9
    Views:
    804
    Chris Thomasson
    Mar 10, 2008
Loading...

Share This Page