1. This site uses cookies. By continuing to use this site, you are agreeing to our use of cookies. Learn More.

Problem in Stack Implementation using Linked list

Discussion in 'C' started by back from retirement, Nov 20, 2008.

  1. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    I have some problem regarding my own stack program using linklist....every thing is ok except for the display function....the program while running cannot display....

    Here it is....
    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    
    typedef struct node
    {
    	int data;
    	struct node *link;
    };
    
    void push(node **t, int item)
    {
    	node *temp;
    	temp=(node *)malloc(sizeof(node));
    	temp->data=item;
    	if(*t==NULL)
    		*t=temp;
    	else
    	{
    		temp->link=*t;
    		*t=temp;
    	}
    }
    
    void pop(node **t)
    {
    	node *temp;
    	if(*t==NULL)
    		printf("\nStack Underflow\n");
    	else
    	{
    		temp=*t;
    		(*t)=(*t)->link;
    		free(temp);
    	}
    }
    
    void display(node **t)
    {
    	if(*t==NULL)
    		printf("\nEmpty Stack\n");
    	else
    	{
    		while(*t!=NULL)
    		{
    			printf("\n%d\n", (*t)->data);
    			*t=(*t)->link;
    		}
    	}
    }
    
    void main()
    {
    	node *top;
    	int i,n;
    	char c;
    	printf("\nWelcome\n");
    	do
    	{
    		printf("\nEnter 1 for PUSH, 2 for POP, 3 for DISPLAY\t");
    		scanf("%d", &i);
    		switch(i)
    		{
    			case 1:
    			{
    				printf("\nEnter the value to be pushed=");
    				scanf("%d", &n);
    				push(&top,n);
    				break;
    			}
    
    			case 2:
    			{
    				pop(&top);
    				break;
    			}
    
    			case 3:
    			{
    				display(&top);
    				break;
    			}
    
    			default:
    			{
    				printf("\nYou are given no other choice than 1,2 and 3\n");
    				printf("\nPlease try again\n");
    				break;
    			}
    		}
    		printf("\nDo you wish to continue?[y/n]\t");
    		c=getch();
    		printf("\n");
    	}while(c=='y'||c=='Y');
    	printf("\nThank You, Press Any Key To Exit\n");
    	getch();
    }
    
     
  2. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Re: Stack Implementation using Linked list

    This thread is just for discussing the article at the top. Please start a new thread for anything that is NOT directly about the article (and "I have a similar program that's failing" is about your similar program, not the article).
     
  3. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Re: Stack Implementation using Linked list

    Oh......excuse me.....I haven't seen it....sorry....cannot it be moved??? If possible, then please move it...
     
  4. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Re: Stack Implementation using Linked list

    Just start a new thread; it's easy, go to the relevant forum and click New Thread.
     
  5. shabbir

    shabbir Administrator Staff Member

    Joined:
    Jul 12, 2004
    Messages:
    15,285
    Likes Received:
    364
    Trophy Points:
    83
    Re: Stack Implementation using Linked list

    Moved it for you as of now.
     
  6. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    What exactly does "*t=(*t)->link;" do in display()?
    When display() returns, what will "top" contain?
     
  7. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    By *t=(*t)->link; we actually move the pointer to a pointer t to the next node, in this way, beginning from the top, we traverse the whole list, displaying the data contained in each node...

    When display ends its returning, top contains nothing since it point s NULL....
     
  8. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    > When display ends its returning, top contains nothing since it point s NULL

    Is that what should happen?
     
  9. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    (By the way, these are hints, not me not knowing what's going on.)
     
  10. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Oh...now I guess there must be some error in my concept....
     
  11. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    But xpi0t0s, each time the pointer top moves to the next node as we move down the stack

    Like this:

    Say initially my stack was

    1 <- top
    2
    3
    4
    NULL

    1 printed out...
    Next...

    2 <-top
    3
    4
    NULL

    2 printed out...
    Next....

    3 <- top
    4
    NULL

    3 printed out...
    Next...

    4 <- top
    NULL

    So actually when top is pointing the first element i.e. 4....it is not NULL yet...and in the next step it moves to NULL....and the loop stops iteration.....by the way all the elements of the stack has been printed out...

    So where is the error occuring?? Could you design a bit more conceptual questions for me??
     
    Last edited: Nov 22, 2008
  12. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    OK, so top has moved down the stack to point beyond the end.

    How are future functions going to add to the stack, now that the original value of top has been overwritten?
     
  13. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Since now top -> NULL, according to our push function, any node further inserted will be assigned to top....for example, if we enter the no. 5 now....
    *top=5.

    Thus now the list looks like...

    5 <- top
    NULL

    Is it correct conception???
     
  14. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Well, it depends. Is the print function supposed to obliterate the list? If it is, why don't you free the nodes? Surely if you have a stack of 1,2,3,4, then you print it, then you push 5, should the stack then be just 5 or should it be 1,2,3,4,5?

    There's definitely something wrong with your program so far. Either print wrongly obliterates the list, or you have a memory leak. But I don't know what your design is, principally what I don't know is whether or not printing the stack is supposed to obliterate it. Only you can tell me that; I would have said not, but it's not an assignment that was given to me.
     
  15. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Certainly, the stack will be 1,2,3,4,5. But As I have presented it in the form of a function, whenever it is getting called, it is traversing the entire stack, printing out all its nodes...so printf is not obliterating the list, is it??

    Please tell if there is mistakes in my conceptions....maybe, I'm not getting to the point...if so, then I am exttremely sorry sir...
     
  16. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    You've made me wonder. Ran the code (after fixing some bugs):

    Welcome
    Enter 1 for PUSH, 2 for POP, 3 for DISPLAY, 4 for EXIT 1
    Enter the value to be pushed=1
    Enter 1 for PUSH, 2 for POP, 3 for DISPLAY, 4 for EXIT 1
    Enter the value to be pushed=2
    Enter 1 for PUSH, 2 for POP, 3 for DISPLAY, 4 for EXIT 3
    2
    1
    Enter 1 for PUSH, 2 for POP, 3 for DISPLAY, 4 for EXIT 1
    Enter the value to be pushed=3
    Enter 1 for PUSH, 2 for POP, 3 for DISPLAY, 4 for EXIT 3
    3

    So, yes, I was correct. The display function *does* obliterate the list. As you can see I push 1 and 2, then display it and 1,2 appear as expected, then I push 3 and display, and only 3 is displayed, NOT 1,2,3 as you are expecting.

    The code I have for display is, as originally posted:
    Code:
    void display(node **t)
    {
    	if(*t==NULL)
    		printf("Empty Stack\n");
    	else
    	{
    		while(*t!=NULL)
    		{
    			printf("%d\n", (*t)->data);
    			*t=(*t)->link;
    		}
    	}
    }
    
     
  17. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Excuse me....but in my compiler it is showing for the first display...
    Code:
    2
    1
    
    but further progress, such as the msg "Do you want to continue..." blah blah...is stopped and the running stops as well, showing an error statement given below....

    Code:
    General Protection Exception
    MYSTACK.C 46
    
    MYSTACK(2) 0x23E7:0x00D0 Processor Fault
    
     
  18. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    I have seen your post in the other thread Sir....
    So what I have to do is....

    Code:
    void display(node **top)
    {
                node *t=*top;
    	if(t==NULL)
    		printf("\nEmpty Stack\n");
    	else
    	{
    		while(t!=NULL)
    		{
    			printf("\n%d\n", t->data);
    			t=t->link;
    		}
    	}
    }
    
    I hope it is right now...
     
  19. xpi0t0s

    xpi0t0s Mentor

    Joined:
    Aug 6, 2004
    Messages:
    3,012
    Likes Received:
    203
    Trophy Points:
    0
    Occupation:
    Senior Support Engineer
    Location:
    England
    Yes, you could do it that way, or just use pass-by-value and pass the contents of top into the function.
    Code:
    void display(node *t)
    { // etc
    
    So don't pass the address of top into the function at all, then there is no risk of modifying it.
     
  20. back from retirement

    back from retirement New Member

    Joined:
    Nov 9, 2008
    Messages:
    72
    Likes Received:
    1
    Trophy Points:
    0
    Occupation:
    Student, UG 1st Yr., Jadavpur University
    Location:
    Uttarpara, West Bengal, India
    Hello xpi0t0s....I have written the complete code...for the stack using linked list....
    I used the techniques used by Shabbir for implementing doubly linked list...
    Here it is...

    Code:
    #include<stdio.h>
    #include<conio.h>
    #include<stdlib.h>
    
    typedef struct node
    {
    	int data;
    	struct node *next;
    };
    
    void init(node *top, int value)
    {
    	node *newnode;
    	newnode=(node *)malloc(sizeof(node));
    	newnode->data=value;
    	top->next=newnode;
    	newnode->next=NULL;
    }
    
    void push(node *top, int value)
    {
    	node *newnode;
    	newnode=(node *)malloc(sizeof(node));
    	newnode->data=value;
    	newnode->next=top->next;
    	top->next=newnode;
    }
    
    void pop(node *top)
    {
    	node *del;
    	if(top->next==NULL)
    		printf("\nList is empty....nothing to delete\n");
    	else if((top->next)->next==NULL)
    		printf("\nYou cannot pop out the last node\n");
    	else
    	{
    		del=top->next;
    		top->next=(top->next)->next;
    		free(del);
    		}
    }
    
    void display(node *top)
    {
    	node *move=top->next;
    	if(top->next==NULL)
    		printf("\nList is empty....nothing to display\n");
    	else
    	{
    		while(move->next!=NULL)
    		{
    			printf("\n%5d\n", move->data);
    			move=move->next;
    		}
    		printf("\n%5d\n", move->data);
    	}
    }
    
    void main()
    {
    	node *top;
    	int i,n;
    	static int k=0;
    	char ch;
    	top=(node *)malloc(sizeof(node));
    	top->next=NULL;
    	printf("\nWelcome\n");
    	do
    	{
    		again:
    		printf("\nEnter 1 for INITIALISE, 2 for PUSH, 3 for POP, 4 for DISPLAY\t");
    		scanf("%d", &i);
    		if(k==0 && i!=1)
    		{
    			printf("\nYou must initialise first\n");
    			goto again;
    		}
    		else if(k==0 && i==1)
    			k=1;
    		else if(k==1 && i==1)
    		{
    			printf("\nInitialisation can occur only once....now you can push values\n");
    			goto again;
    		}
    		else
    			goto done;
    
    		done:
    		switch(i)
    		{
    			case 1:
    			{
    				printf("\nEnter the value you want to initialise=");
    				scanf("%d", &n);
    				init(top,n);
    				break;
    			}
    
    			case 2:
    			{
    				printf("\nEnter the value you want to push=");
    				scanf("%d", &n);
    				push(top,n);
    				break;
    			}
    
    			case 3:
    			{
    				pop(top);
    				break;
    			}
    
    			case 4:
    			{
    				display(top);
    				break;
    			}
    
    			default:
    			{
    				printf("\nERROR...please re-enter the code\n");
    				break;
    			}
    		}
    		printf("\nDo you wish to continue?[y/n]\t");
    		ch=getche();
    		printf("\n");
    	}while(ch=='y'||ch=='Y');
    	printf("\nThank you....press any key to exit\n");
    	getch();
    }
    
    :D
     

Share This Page