Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > C Programming > Stack using Array

Reply
Thread Tools

Stack using Array

 
 
arnuld
Guest
Posts: n/a
 
      10-24-2011
OBJECTIVE: To implement a stack (LIFO) using C array
WHAT I GOT: Segfault

I know there is something wrong with Line 73, where I add an element to
the array but what exactly is wrong I am not sure (except that a pointer
to pointer is being passed in function argument):



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

enum { VAL_FALSE = 0, VAL_TRUE = 1, SIZE_STACK = 10 };

struct myStruct
{
char* title;
};


struct myStack
{
int top;
};


void initialize(struct myStack s);
int stackEmpty(struct myStack s);
void push(struct myStruct* arr[], struct myStack s, const char* ele);


int main(void)
{
struct myStruct* sof[SIZE_STACK+1] = {0};
struct myStack s;

initialize(s);
stackEmpty(s);
push(sof, s, "CLC");

return 0;
}



int stackEmpty(struct myStack s)
{
if(s.top) return VAL_FALSE;

return VAL_TRUE;
}



void initialize(struct myStack s)
{
s.top = 0;
}


void push(struct myStruct* arr[], struct myStack s, const char* ele)
{
if(NULL == arr || NULL == ele)
{
fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
}
else if(SIZE_STACK <= s.top)
{
printf("Stack Full, Can not add anymore elements\n");
}
else
{
struct myStruct* p = malloc( 1 * sizeof *p);
if(NULL == p)
{
fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
}
else
{
strcpy(p->title, ele);
arr[s.top] = p;
s.top += 1;
}
}
}





--
arnuld
http://LispMachine.Wordpress.com
 
Reply With Quote
 
 
 
 
Ike Naar
Guest
Posts: n/a
 
      10-24-2011
On 2011-10-24, arnuld <(E-Mail Removed)> wrote:
> void push(struct myStruct* arr[], struct myStack s, const char* ele)
> {
> if(NULL == arr || NULL == ele)
> {
> fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
> }
> else if(SIZE_STACK <= s.top)
> {
> printf("Stack Full, Can not add anymore elements\n");
> }
> else
> {
> struct myStruct* p = malloc( 1 * sizeof *p);


This allocates memory for a myStruct, but the contents
of that memory is still uninitialized;
In particular, p->title is still an uninitialized pointer.

> if(NULL == p)
> {
> fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
> __LINE__);
> }
> else
> {
> strcpy(p->title, ele);


p->title is still an uninitialized pointer.

> arr[s.top] = p;
> s.top += 1;
> }
> }
> }
>
>
>
>
>



--
http://www.velocityreviews.com/forums/(E-Mail Removed)
SDF Public Access UNIX System - http://sdf.lonestar.org
 
Reply With Quote
 
 
 
 
David RF
Guest
Posts: n/a
 
      10-24-2011
On 24 oct, 10:18, arnuld <(E-Mail Removed)> wrote:
> OBJECTIVE: *To implement a stack (LIFO) using C array
> WHAT I GOT: Segfault
>
> I know there is something wrong with Line 73, where I add an element to
> the array but what exactly is wrong I am not sure (except that a pointer
> to pointer is being passed in function argument):
>
> #include <stdio.h>
> #include <stdlib.h>
> #include <string.h>
>
> enum { VAL_FALSE = 0, VAL_TRUE = 1, SIZE_STACK = 10 };
>
> struct myStruct
> {
> * char* title;
>
> };
>
> struct myStack
> {
> * int top;
>
> };
>
> void initialize(struct myStack s);
> int stackEmpty(struct myStack s);
> void push(struct myStruct* arr[], struct myStack s, const char* ele);
>
> int main(void)
> {
> * struct myStruct* sof[SIZE_STACK+1] = {0};
> * struct myStack s;
>
> * initialize(s);
> * stackEmpty(s);
> * push(sof, s, "CLC");
>
> * return 0;
>
> }
>
> int stackEmpty(struct myStack s)
> {
> * if(s.top) return VAL_FALSE;
>
> * return VAL_TRUE;
>
> }
>
> void initialize(struct myStack s)
> {
> * s.top = 0;
>
> }
>
> void push(struct myStruct* arr[], struct myStack s, const char* ele)
> {
> * if(NULL == arr || NULL == ele)
> * * {
> * * * fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
> * * }
> * else if(SIZE_STACK <= s.top)
> * * {
> * * * printf("Stack Full, Can not add anymore elements\n");
> * * }
> * else
> * * {
> * * * struct myStruct* p = malloc( 1 * sizeof *p);
> * * * if(NULL == p)
> * * * * {
> * * * * * fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
> __LINE__);
> * * * * }
> * * * else
> * * * * {
> * * * * * strcpy(p->title, ele);
> * * * * * arr[s.top] = p;
> * * * * * s.top += 1;
> * * * * }
> * * }
>
> }


You forgot to assign space for title:

struct myStruct* p = malloc( 1 * sizeof *p);
p->title = malloc(4);
p->title[0] = '\0'; /* strcpy needs a terminating null character
*/

or just declare title with fixed length

struct myStruct
{
char title[4];

};
 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      10-24-2011
> On Mon, 24 Oct 2011 09:16:32 +0000, Ike Naar wrote:

>> On 2011-10-24, arnuld <(E-Mail Removed)> wrote:


>> else
>> {
>> struct myStruct* p = malloc( 1 * sizeof *p);


> This allocates memory for a myStruct, but the contents of that memory is
> still uninitialized; In particular, p->title is still an uninitialized
> pointer.


I already know this.


>> else
>> {
>> strcpy(p->title, ele);


> p->title is still an uninitialized pointer.


How does it matter to strcpy ? strpcy(dest, src) will overwrite all the
characters, whether its garbage or not. 'src' does contain '\0' in the
(as its a character string), which will be written to ..... Oh.. wait a
minute.. I got it. p->title must be an array rather than a dangling
pointer.







--
arnuld
http://LispMachine.Wordpress.com
 
Reply With Quote
 
David RF
Guest
Posts: n/a
 
      10-24-2011
On 24 oct, 11:19, David RF <(E-Mail Removed)> wrote:
> On 24 oct, 10:18, arnuld <(E-Mail Removed)> wrote:
>
>
>
> > OBJECTIVE: *To implement a stack (LIFO) using C array
> > WHAT I GOT: Segfault

>
> > I know there is something wrong with Line 73, where I add an element to
> > the array but what exactly is wrong I am not sure (except that a pointer
> > to pointer is being passed in function argument):

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

>
> > enum { VAL_FALSE = 0, VAL_TRUE = 1, SIZE_STACK = 10 };

>
> > struct myStruct
> > {
> > * char* title;

>
> > };

>
> > struct myStack
> > {
> > * int top;

>
> > };

>
> > void initialize(struct myStack s);
> > int stackEmpty(struct myStack s);
> > void push(struct myStruct* arr[], struct myStack s, const char* ele);

>
> > int main(void)
> > {
> > * struct myStruct* sof[SIZE_STACK+1] = {0};
> > * struct myStack s;

>
> > * initialize(s);
> > * stackEmpty(s);
> > * push(sof, s, "CLC");

>
> > * return 0;

>
> > }

>
> > int stackEmpty(struct myStack s)
> > {
> > * if(s.top) return VAL_FALSE;

>
> > * return VAL_TRUE;

>
> > }

>
> > void initialize(struct myStack s)
> > {
> > * s.top = 0;

>
> > }

>
> > void push(struct myStruct* arr[], struct myStack s, const char* ele)
> > {
> > * if(NULL == arr || NULL == ele)
> > * * {
> > * * * fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
> > * * }
> > * else if(SIZE_STACK <= s.top)
> > * * {
> > * * * printf("Stack Full, Can not add anymore elements\n");
> > * * }
> > * else
> > * * {
> > * * * struct myStruct* p = malloc( 1 * sizeof *p);
> > * * * if(NULL == p)
> > * * * * {
> > * * * * * fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
> > __LINE__);
> > * * * * }
> > * * * else
> > * * * * {
> > * * * * * strcpy(p->title, ele);
> > * * * * * arr[s.top] = p;
> > * * * * * s.top += 1;
> > * * * * }
> > * * }

>
> > }

>
> You forgot to assign space for title:
>
> * * * struct myStruct* p = malloc( 1 * sizeof *p);
> * * * p->title = malloc(4);
> * * * p->title[0] = '\0'; /* strcpy needs a terminating null character
> */
>
> or just declare title with fixed length
>
> struct myStruct
> {
> * char title[4];
>
> };
>
>


Please, forget this: /* strcpy needs a terminating null character */
 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      10-24-2011

Here is the code that works. I just wrote it with whatever half-brain I
have . Is it really a stack implementation using array ?



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

enum { VAL_FALSE = 0, VAL_TRUE = 1, SIZE_STACK = 10, SIZE_TITLE = 10 };

struct myStruct
{
char title[SIZE_TITLE+1];
};


struct myStack
{
int top;
};


void initialize(struct myStack** s);
int stackEmpty(struct myStack* s);
void push(struct myStruct* arr[], struct myStack* s, const char* ele);
struct myStruct* pop(struct myStruct* arr[], struct myStack* s);
void stackDel(struct myStruct** arr, struct myStack* s);
void stackPrint(struct myStruct** arr, const struct myStack* s);
void stackPrintUsingPointers(struct myStruct** arr);


int main(void)
{
int is_empty;
struct myStruct* sof[SIZE_STACK+1] = {0};
struct myStack* s;
initialize(&s);
is_empty = stackEmpty(s);
printf("is_empty = %d\n", is_empty);

push(sof, s, "A");
push(sof, s, "B");
push(sof, s, "C");
is_empty = stackEmpty(s);
printf("is_empty = %d\n", is_empty);

push(sof, s, "C");
push(sof, s, "C");
push(sof, s, "A");
pop(sof, s);
is_empty = stackEmpty(s);
printf("is_empty = %d\n", is_empty);

printf("\n----------\n");
stackPrintUsingPointers(sof);
stackDel(sof, s);
is_empty = stackEmpty(s);
printf("is_empty = %d\n", is_empty);

return 0;
}



int stackEmpty(struct myStack* s)
{
if(s->top) return VAL_FALSE;

return VAL_TRUE;
}



void initialize(struct myStack** s)
{
*s = malloc(1 * sizeof *s);
if(NULL == *s)
{
fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__, __LINE__);
}
else
{
(*s)->top = 0;
}
}


void push(struct myStruct* arr[], struct myStack* s, const char* ele)
{
if(NULL == arr || NULL == s || NULL == ele)
{
fprintf(stderr, "IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
}
else if(SIZE_STACK <= s->top)
{
printf("Stack Full, top = %d, Can not add anymore elements\n", s-
>top);

}
else
{
struct myStruct* p = malloc( 1 * sizeof *p);
if(NULL == p)
{
fprintf(stderr, "IN: %s @%d: Out of Memory\n", __FILE__,
__LINE__);
}
else
{
strcpy(p->title, ele);
arr[s->top] = p;
s->top += 1;
printf("Adding %s, top = %d\n", ele, s->top);
}
}
}


struct myStruct* pop(struct myStruct* arr[], struct myStack* s)
{
struct myStruct* ele;

if(NULL == arr || NULL == s)
{
fprintf(stderr,"IN: %s @%d: Invalid Args\n", __FILE__, __LINE__);
ele = NULL;
}
else
{
ele = arr[s->top - 1];
printf("Removing: %s\n", ele->title);
arr[s->top - 1] = '\0';
s->top -= 1;
}

return ele;
}


void stackDel(struct myStruct** arr, struct myStack* s)
{
if(arr && s)
{
int i;
struct myStruct* ele;
for(i = s->top - 1; i >= 0; --i)
{
ele = arr[i];
free(ele);
arr[i] = NULL;
s->top -= 1;
}
}
}


void stackPrint(struct myStruct** arr, const struct myStack* s)
{
if(arr)
{
int i = s->top - 1;
for(; i >= 0; --i)
{
struct myStruct* ele = arr[i];
printf("title = %s\n", ele->title);
}
}
}



void stackPrintUsingPointers(struct myStruct** arr)
{
if(arr)
{
for(; *arr; ++arr)
{
struct myStruct* ele = *arr;
printf("title = %s\n", ele->title);
}
}
}
===================== OUTPUT ==========================
[arnuld@dune C]$ gcc -ansi -pedantic -Wall -Wextra stack-using-array.c
[arnuld@dune C]$ ./a.out
is_empty = 1
Adding A, top = 1
Adding B, top = 2
Adding C, top = 3
is_empty = 0
Adding C, top = 4
Adding C, top = 5
Adding A, top = 6
Removing: A
is_empty = 0

----------
title = A
title = B
title = C
title = C
title = C
is_empty = 1



--
arnuld
http://LispMachine.Wordpress.com
 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      10-24-2011
"arnuld" <(E-Mail Removed)> wrote in message
news:4ea54970$0$287$(E-Mail Removed)...

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


> struct myStack
> {
> int top;
> };


> void initialize(struct myStack** s);


> void initialize(struct myStack** s)
> {
> *s = malloc(1 * sizeof *s);


You are good at making code far more complicated than is necessary!

Anyway, here, I'm not sure what's going on, as I'm not too adept at
following all these **s, but you seem to be allocating space for a pointer
which doesn't quite seem right.

Presumably you want to allocate space for an instance of myStack? Then
perhaps you want sizeof **s. (If you add some dummy elements to myStack so
that it's size doesn't coincide with both pointer width, and int width, then
it makes it easier to see if these numbers make sense when you print them
out..)

--
Bartc

 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      10-24-2011
> On Mon, 24 Oct 2011 12:51:05 +0100, BartC wrote:

>> "arnuld" <(E-Mail Removed)> wrote in message


>> void initialize(struct myStack** s)
>> {
>> *s = malloc(1 * sizeof *s);

>
> You are good at making code far more complicated than is necessary!


ouch! ..



> Anyway, here, I'm not sure what's going on, as I'm not too adept at
> following all these **s, but you seem to be allocating space for a
> pointer which doesn't quite seem right.


> Presumably you want to allocate space for an instance of myStack? Then
> perhaps you want sizeof **s.


Ah.. you are right. I needed this.


> (If you add some dummy elements to myStack
> so that it's size doesn't coincide with both pointer width, and int
> width, then it makes it easier to see if these numbers make sense when
> you print them out..)


I am not sure what you meant but I my best guess is: you want me to add
more elements to myStack structure so that I can see garbage printing out
because of the mistake I did. Right ?




--
arnuld
http://LispMachine.Wordpress.com
 
Reply With Quote
 
BartC
Guest
Posts: n/a
 
      10-24-2011
"arnuld" <(E-Mail Removed)> wrote in message
news:4ea55bc7$0$287$(E-Mail Removed)...
>> On Mon, 24 Oct 2011 12:51:05 +0100, BartC wrote:


>> You are good at making code far more complicated than is necessary!

>
> ouch! ..


That just means I couldn't follow your code and resorted to nit-picking
fragments.

Which reminds me of this bit that was slightly puzzling:

struct myStack* s;

Even disregarding myStack only having four bytes or so, I wasn't sure why
this struct wasn't just statically allocated. Assuming you are only going to
have a small number of distinct stacks.

>> (If you add some dummy elements to myStack
>> so that it's size doesn't coincide with both pointer width, and int
>> width, then it makes it easier to see if these numbers make sense when
>> you print them out..)

>
> I am not sure what you meant but I my best guess is: you want me to add
> more elements to myStack structure so that I can see garbage printing out
> because of the mistake I did. Right ?


When I added this debug code, I just kept getting 4s, until I made myStack a
bit bigger. Then one of these gave the right answer!

printf("SIZE*s %d\n",1*sizeof *s);
printf("SIZE**s %d\n",1*sizeof **s);

--
bartc

 
Reply With Quote
 
arnuld
Guest
Posts: n/a
 
      10-24-2011
> > On Mon, 24 Oct 2011 14:16:30 +0100, BartC wrote:


> struct myStack* s;
>
> Even disregarding myStack only having four bytes or so, I wasn't sure
> why this struct wasn't just statically allocated. Assuming you are only
> going to have a small number of distinct stacks.


Even after working for 2 years in C (not exclusively) my brain is still
clunky when it comes to C basics. This struct definition:


struct myStack
{
int top;
};


can be allocated statically ? I don't have the exact code (function
definition of initialize is 100% same as the code I posted) but I tried
using:

struct myStack s;
initialize(&s);

And all I got was garbage value in s.top.


>> I am not sure what you meant but I my best guess is: you want me to
>> add more elements to myStack structure so that I can see garbage
>> printing out because of the mistake I did. Right ?


> When I added this debug code, I just kept getting 4s, until I made
> myStack a bit bigger. Then one of these gave the right answer!


> printf("SIZE*s %d\n",1*sizeof *s);
> printf("SIZE**s %d\n",1*sizeof **s);


Let me ask again, you make myStack bigger by adding more elements to this
structure ? I still wonder what these 2 printf()s giving debug
information.

P.S. May be my mind is too much full of office work right now that I
can't understand anything. Will surely re-read it tomorrow.





--
arnuld
http://LispMachine.Wordpress.com
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Why does std::stack::pop() not throw an exception if the stack is empty? Debajit Adhikary C++ 36 02-10-2011 08:54 PM
C/C++ compilers have one stack for local variables and return addresses and then another stack for array allocations on the stack. Casey Hawthorne C Programming 3 11-01-2009 08:23 PM
stack frame size on linux/solaris of a running application stack Surinder Singh C Programming 1 12-20-2007 01:16 PM
Why stack overflow with such a small stack? Kenneth McDonald Ruby 7 09-01-2007 04:21 AM
"stack level too deep"... because Threads keep their "starting" stack Sam Roberts Ruby 1 02-11-2005 04:25 AM



Advertisments