Velocity Reviews

Velocity Reviews (http://www.velocityreviews.com/forums/index.php)
-   C Programming (http://www.velocityreviews.com/forums/f42-c-programming.html)
-   -   Stack using Array (http://www.velocityreviews.com/forums/t755073-stack-using-array.html)

arnuld 10-24-2011 08:18 AM

Stack using Array
 
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

Ike Naar 10-24-2011 09:16 AM

Re: Stack using Array
 
On 2011-10-24, arnuld <sunrise@invalid.address> 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;
> }
> }
> }
>
>
>
>
>



--
ike@sdf.lonestar.org
SDF Public Access UNIX System - http://sdf.lonestar.org

David RF 10-24-2011 09:19 AM

Re: Stack using Array
 
On 24 oct, 10:18, arnuld <sunr...@invalid.address> 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];

};

arnuld 10-24-2011 09:45 AM

Re: Stack using Array
 
> On Mon, 24 Oct 2011 09:16:32 +0000, Ike Naar wrote:

>> On 2011-10-24, arnuld <sunrise@invalid.address> 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

David RF 10-24-2011 09:54 AM

Re: Stack using Array
 
On 24 oct, 11:19, David RF <davran...@gmail.com> wrote:
> On 24 oct, 10:18, arnuld <sunr...@invalid.address> 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 */

arnuld 10-24-2011 11:18 AM

Re: Stack using Array
 

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

BartC 10-24-2011 11:51 AM

Re: Stack using Array
 
"arnuld" <sunrise@invalid.address> wrote in message
news:4ea54970$0$287$14726298@news.sunsite.dk...

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


arnuld 10-24-2011 12:36 PM

Re: Stack using Array
 
> On Mon, 24 Oct 2011 12:51:05 +0100, BartC wrote:

>> "arnuld" <sunrise@invalid.address> 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

BartC 10-24-2011 01:16 PM

Re: Stack using Array
 
"arnuld" <sunrise@invalid.address> wrote in message
news:4ea55bc7$0$287$14726298@news.sunsite.dk...
>> 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


arnuld 10-24-2011 02:42 PM

Re: Stack using Array
 
> > 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


All times are GMT. The time now is 04:45 PM.

Powered by vBulletin®. Copyright ©2000 - 2014, vBulletin Solutions, Inc.
SEO by vBSEO ©2010, Crawlability, Inc.