Permuting bottom element with top element in a stack

Question

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

struct node
{
    int data;
    struct node *next;
};
struct node *top;


int count=0;
void push(int n);
void Print();
void permute();

int main()
{
 int no, ch, e;
 printf("\n1 - Push");
 printf("\n4 - Print");
 printf("\n7 - Permute first and last element");
while (1)
    {
        printf("\n Enter choice : ");
        scanf("%d", &ch);
switch (ch)
        {
        case 1:
            printf("Enter data : ");
            scanf("%d", &no);
            push(no);
            break;
        case 4:
            Print();
            break;

        case 7:
            permute();
            break;
        default :
            printf(" Wrong choice, Please enter correct choice  ");
            break;
        }
    }


}
void push(int no)
{
    struct node *temp=(struct node*)malloc(sizeof(struct node));
    temp->data=no;
    temp->next=top;
    top=temp;
    count++;
}
 void Print()
{
    struct node *temp=top;
    printf("List is:");
    while(temp!=NULL)
    {
        printf("%d  ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
void permute()
{
    int i;
    struct node *temp=(struct node*)malloc(sizeof(struct node));
    struct node *temp1=(struct node*)malloc(sizeof(struct node));
    struct node *temp2=(struct node*)malloc(sizeof(struct node));
    temp=top;
    temp1=NULL;
    for(i=0;i<count-1;i++)
    {
        temp1=temp1->next;
    }
    temp1->next=temp2;
    temp2->data=temp1->next->data;
    temp1->next=temp;
    temp->data=top->data;
    temp=NULL;
    temp2->next=top;
    top=temp2;
}

So my implementation of a stack works fine as for pushing and printing the elements in the stack, but when I want to permute the bottom element with the top element the program crashes. I think I am messing something up in my permute function. Thank you for any help before hand.

Unrelated to the problem, but [Don't cast the result of `malloc`](http://stackoverflow.com/questions/605845/do-i-cast-the-result-of-malloc) — Spikatrix, Mar 29 '15 at 11:42
`struct node *temp=(struct node*)malloc(sizeof(struct node));...temp=top;` causes a memory leak. It's not the origin of your problem. — francis, Mar 29 '15 at 11:46
@Module , Are you compiling in C++ instead of C? BTW, *what* is the error? — Spikatrix, Mar 29 '15 at 11:47
@Module Is it enough simply to swap values of data member data of the two nodes? — Vlad from Moscow, Mar 29 '15 at 11:48
`temp1=NULL;...temp1=temp1->next;` : dereferencing NULL pointer is [undefined behavior](http://stackoverflow.com/questions/2727834/c-standard-dereferencing-null-pointer-to-get-a-reference). The program may crash due to a segmentation fault. — francis, Mar 29 '15 at 11:49
@VladfromMoscow I will try just permuting the data members of the two nodes and see if I can get it to work. — Module, Mar 29 '15 at 11:50
"*If I don't cast it then I get an error.*" then you aren't using a Standard conforming C compiler, but most probably a C++ compiler. — alk, Mar 29 '15 at 11:51

score 3 · Accepted Answer · answered Mar 29 '15 at 11:54

3

If I have correctly understood it is enough simply to swap values of data member data of two nodes. The function can be defined the following way

void permute()
{
    if ( top && top->next )
    {
        int data = top->data;

        struct node *last = top->next;

        while ( last->next ) last = last->next;

        top->data = last->data;
        last->data = data;
    }
}

answered Mar 29 '15 at 11:54

Vlad from Moscow

301,070
26
186
335

Thank you! It works perfectly fine now. I was messing the permutations up . – Module Mar 29 '15 at 11:58
The condition in the if statement is the equivalent of just saying that if top is different from NULL and top->next is also different from NULL. If I am not mistaken. – Module Mar 29 '15 at 12:00
@Module You are right. At least two nodes that differ from NULL are required that to make the permutation. – Vlad from Moscow Mar 29 '15 at 12:08

score 1 · Answer 2 · answered Mar 29 '15 at 12:12

If you wish to permute nodes, here is a solution. Since there is no new node in the stack when a permutation is performed, there is no need to allocate memory. It is just pointer handling.

Notice the additional test to treat the case of an empty stack, or a stack with a single element.

A removed the cast of the return of malloc() in push() and tested the return value of malloc(). malloc() may fail if there is not enough memory available.

The following code is compiled by gcc main.c -o main -Wall :

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

struct node
{
    int data;
    struct node *next;
};
struct node *top;


int count=0;
void push(int n);
void Print();
void permute();

int main()
{
    int no, ch;
    printf("\n1 - Push");
    printf("\n4 - Print");
    printf("\n7 - Permute first and last element");
    while (1)
    {
        printf("\n Enter choice : ");
        scanf("%d", &ch);
        switch (ch)
        {
        case 1:
            printf("Enter data : ");
            scanf("%d", &no);
            push(no);
            break;
        case 4:
            Print();
            break;

        case 7:
            permute();
            break;
        default :
            printf(" Wrong choice, Please enter correct choice  ");
            break;
        }
    }


}
void push(int no)
{
    struct node *temp=malloc(sizeof(struct node));
    if(temp==NULL){printf("malloc failed\n");exit(1);}
    temp->data=no;
    temp->next=top;
    top=temp;
    count++;
}
void Print()
{
    struct node *temp=top;
    printf("List is:");
    while(temp!=NULL)
    {
        printf("%d  ",temp->data);
        temp=temp->next;
    }
    printf("\n");
}
void permute()
{
    if(count<2){return;}
    int i;
    struct node *temp1=top;
    struct node *temp2;
    for(i=0;i<count-2;i++)
    {
        temp1=temp1->next;
    }
    temp2=temp1->next;
    temp1->next=top;
    temp2->next=top->next;
    top->next=NULL;
    top=temp2;

}

I would like to ask you: Is Francis a French man's name and Frances a French woman's name? — Vlad from Moscow, Mar 29 '15 at 12:16
@VladfromMoscow : According to wikipedia, Francis is a French and English surname of Latin origin ( Franciscus). I did not know about the English part... France was the scenic name of woman singer [France Gall](http://fr.wikipedia.org/wiki/France_Gall), the name of my country and the name of a [boat](http://fr.wikipedia.org/wiki/France_%28paquebot_de_1912%29). Yet the feminine of Francis is Francine...It's not very common nowadays...Nice to ask ! — francis, Mar 29 '15 at 12:32
I simply know a woman that names herself Frances. It is her real name. In Italian there are Francesco and Francesca. So i have thought that in French there are Francis and Frances. — Vlad from Moscow, Mar 29 '15 at 12:35

Permuting bottom element with top element in a stack

2 Answers2