Ir ao conteúdo
  • Cadastre-se
MuriloHB

RESOLVIDO Ordenar Pilha Encadeada

Recommended Posts

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!

Compartilhar este post


Link para o post
Compartilhar em outros sites

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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... "

Compartilhar este post


Link para o post
Compartilhar em outros sites

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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.

Compartilhar este post


Link para o post
Compartilhar em outros sites

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

Compartilhar este post


Link para o post
Compartilhar em outros sites

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!

Compartilhar este post


Link para o post
Compartilhar em outros sites

// 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;
}

Compartilhar este post


Link para o post
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisar ser um membro para fazer um comentário

Criar uma conta

Crie uma nova conta em nossa comunidade. É fácil!

Crie uma nova conta

Entrar

Já tem uma conta? Faça o login.

Entrar agora





Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas publicações sobre tecnologia do Brasil. Leia mais

Direitos autorais

Não permitimos a cópia ou reprodução do conteúdo do nosso site, fórum, newsletters e redes sociais, mesmo citando-se a fonte. Leia mais

×