Linked list question

C

Chapman

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;
}
 
A

Alf P. Steinbach

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.
 
I

Irrwahn Grausewitz

Chapman said:
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 said:
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
 
J

James K

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;
}
 
A

Al Bowers

James said:
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?
 
J

James K

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().
 
C

Chapman

Irrwahn Grausewitz said:
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);

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.
 
B

Barry Schwarz

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>>
 
B

Barry Schwarz

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>>
 
J

James K

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.
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,484
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top