Ordenar Pilha Encadeada

[MuriloHB]

Olá galera! Então, estou tendo problemas com o seguinte exercício de Algoritmos e Estrutura de Dados:

 

Escreva um algoritmo para ordenar os elementos de uma pilha durante o processo de inserção - push(x). Após todas as inserções, os elementos da pilha devem estar dispostos em ordem crescente, estando o maior valor no topo da pilha e o menor, na primeira posição válida da pilha.

 

Entrada: Todos os elementos a serem inseridos na pilha separados por espaço, aqui os elementos não estão ordenados.

 

Saída: Elementos na pilha, sendo que o topo da pilha é o primeiro elemento a ser exibido, e assim por diante...

 

Ex de Entrada: 6 1 9 4 3 2 10 22

 

Ex de Saída: 22 10 9 6 4 3 2 1

 

OBS PARA OBTER A ENTRADA: Leia cada linha utilizando a função fgets, utilizando como ponteiro de arquivo stdin. Para obter cada número da linha lida, utilize a função strtok. A conversão de cada número obtido com strtok para seu valor inteiro pode ser feita com a função atoi.

 

 

Então, eu escrevi meu código e na minha cabeça a lógica está completamente correta, no entando quando executo dá erro e o programa para de funcionar...

 

Meu código está assim:

#include <stdio.h>#include <stdlib.h>typedef struct node {    int info;    struct node *ant;}node;typedef struct Pilha{    node *topo;}Pilha;Pilha *P;void cria(Pilha *P){    P->topo = NULL;}void push(Pilha *P, int x){    node *p;    node *aux;    node *proximo;    proximo = NULL;    aux = NULL;    p =(node*)malloc(sizeof(node));    if(p == NULL){        printf("Erro de alocacao!");        exit(1);        }    else{        p->info = x;        if(P->topo == NULL){            p->ant = NULL;            P->topo = p;       }        else{            aux = P->topo;            while(aux != NULL && aux->info > x ){                proximo = aux;                aux = aux->ant;            }            proximo->ant = p;            p->ant = aux;        }    proximo = NULL;    aux = NULL;    }}void converte(char string[], Pilha *P){    char *pch;    int x;    pch = strtok(string," ");    while (pch != NULL){        x = atoi(pch);        push(P, x);        pch = strtok (NULL, " ");    }}void imprime(Pilha *P){    node *p;    if(P->topo == NULL){        printf("A Pilha esta vazia!");        exit(1);    }    else{        p = P->topo;        while(p!=NULL){            printf("%d ", p->info);            p = p->ant;        }    }}void esvazia(Pilha *P){    node *p, *aux;    p = P->topo;    while(p != NULL){        aux = p;        p = p->ant;        free(aux);    }    free(P);}int main(){    char string[6000];    Pilha *P = (Pilha*) malloc (sizeof(Pilha));    cria(P);    printf("Informe os valores da pilha: ");    fgets(string, 6000, stdin);    converte(string, P);    imprime(P);    esvazia(P);    return 0;}

Gostaria de saber o que estou errando, pois realmente não tenho a menor ideia.

 

Agradeço a atenção!

[Detetive Virtual de SSDs]

mostre a parte do DEV que mostra onde foi localizado os erros

[MuriloHB]

mostre a parte do DEV que mostra onde foi localizado os erros

 

Então, eu uso o CodeBlocks pra compilar e quanto eu rodo o programa ele não mostra onde estão os erros, apenas aponta " Exercício.exe parou de funcionar... "

[Detetive Virtual de SSDs]

Então, eu uso o CodeBlocks pra compilar e quanto eu rodo o programa ele não mostra onde estão os erros, apenas aponta " Exercício.exe parou de funcionar... "

se você usa-se o dev eu até saberia responder mais nem conheço esse problem e eu n achei nenhum erro aqui vou tenar achar de novo

[MuriloHB]

se você usa-se o dev eu até saberia responder mais nem conheço esse problem e eu n achei nenhum erro aqui vou tenar achar de novo

 

Eu tenho o DEV C++ aqui também, mas ele dá a mesma coisa. Na hora de compilar ele aponta:

 

Compilation results...

--------

- Errors: 0

- Warnings: 0

- Output Filename: C:\Users\Murilo\Desktop\dev.exe

- Output Size: 130,6328125 KiB

- Compilation Time: 2,81s

 

Mas na hora que eu rodo o programa, informo os elementos da Pilha e dou Enter, o programa também para de funcionar.

[Detetive Virtual de SSDs]

Eu tenho o DEV C++ aqui também, mas ele dá a mesma coisa. Na hora de compilar ele aponta:

 

Compilation results...

--------

- Errors: 0

- Warnings: 0

- Output Filename: C:\Users\Murilo\Desktop\dev.exe

- Output Size: 130,6328125 KiB

- Compilation Time: 2,81s

 

Mas na hora que eu rodo o programa, informo os elementos da Pilha e dou Enter, o programa também para de funcionar.

nossa n era pra acontecer isso porque eu n achei nenhum erro no programa oxi

[MuriloHB]

Caso alguem tenha alguma dúvida, o problema se encontrava na função push, especificamenten o trecho:

aux = P->topo;            while(aux != NULL && aux->info > x ){                proximo = aux;                aux = aux->ant;            }            proximo->ant = p;            p->ant = aux;        }    proximo = NULL;    aux = NULL;    }

Realizei a seguinte alteração:

aux = P->topo;            //vai procurar o lugar correto pra inserir o elemento            while(aux != NULL && aux->info > x ){                proximo = aux;                aux = aux->ant;            }            // se tiver que inserir no começo            if (aux == P->topo) {            	p->ant = P->topo;            	P->topo = p;            }            // se for no final            else if (aux == NULL) {            	proximo->ant = p;            	p->ant = NULL;            }            // se for no meio            else {	            p->ant = aux;    	        proximo->ant = p;    	    }        }    proximo = NULL;    aux = NULL;    }

Agora o programa roda normalmente!

[carlosliminha]

// pilhaordena.cpp: Define o ponto de entrada para a aplicação de console.
// ta ai um codigo que ordena

#include "stdafx.h"
#include <iostream>
using namespace std;

struct No {
    int conteudo;
    No* prox;
};
struct Pilha {
    No* topo;
    int size;
};

void push(Pilha* p, int valor) {
    No* aux = (No*)malloc(sizeof(No));
    aux->conteudo = valor;
    aux->prox = p->topo;
    p->topo = aux;
    p->size++;
}

//funcao para desempilhar 
int pop(Pilha *pilha) {
    char valor; // cria para receber o valor da pilha enquanto faz o desempilhamento
    No *aux = NULL; //auxilo para receber o endereço da pilha excluida
    if (pilha->size == 0) {
        cout << "pilha vazia para retirar" << endl;
        return -1;
    }    
    else if((pilha->topo) != NULL) { //testa primeiramente se a pilha esta vazia
        aux = pilha->topo->prox; //aux recebe o end da pilha
        valor = pilha->topo->conteudo; //valor recebe o conteudo da pilha
        free(pilha->topo); //exclui a pilha
        pilha->topo = aux; // a pilha que estava embaixo recebeu o "aux" q recebeu o end do topo da pilha;
        pilha->size--;
        return valor; //retorna o valor desempilhado
    }

}

Pilha* criaPilha() {
    Pilha* p = (Pilha*)malloc(sizeof(Pilha));
    p->topo = NULL;
    p->size = 0;
    return p;
}

void imprimiPilha(Pilha* p) {
    No* aux;
    aux = p->topo;
    while (aux != NULL) {
        cout << aux->conteudo << endl;
        aux = aux->prox;
    }

}
bool empty(Pilha* p) {
    if (p->size == 0) {
        return true;
    }
    else {
        return false;
    }
}

Pilha* ordenaPilha(Pilha* p, Pilha* p2) {
    int elemento;
    int max;
    int aux = NULL; int c = 0, x = 0;

    while (p->topo != NULL) {
        max = NULL;
        while (p->topo != NULL) {
            elemento = pop(p);

            if (elemento > max) {
                max = elemento;
            }
            push(p2, elemento);

        }
        while (p2->size != 0) {
            elemento = pop(p2);
            //cout << elemento;
            if (elemento == max) {            
                aux = elemento;
            }    
            else {
                push(p, elemento);
            }
        }

        push(p2, aux);
        p2->size--;

        max = aux;
    }
    return p2;

}

int main()
{
    Pilha* p1 = criaPilha();
    Pilha* p2 = criaPilha();
    push(p1, 2);
    push(p1, 1);
    push(p1, 4);
    push(p1, 3);
    imprimiPilha(p1);

    cout << endl;

    p1 = ordenaPilha(p1, p2);

    cout << endl;

    imprimiPilha(p1);

    system("pause");
    return 0;
}