C++ função crescente numa fila

[nicholas22]

Alguém me ajuda por favor

Não posso alterar o código já pronto.

Preciso implementar no código abaixo uma função que, dada uma fila de entrada p, retorne uma fila com todos os elementos de p ordenados de maneira crescente. Ao final da execução desta função, p permanecerá com todos os seus elementos.  O protótipo desta função é o seguinte:
 

TFila* ordena (TFila *f)

#include <stdlib.h>

typedef struct lista{
    int info;
    struct lista *prox;
}TLista;

typedef struct fila{
    TLista *ini;
    TLista *fim;
}TFila;

TFila* inicializa(){

    TFila *f = (TFila*) malloc(sizeof(TFila));
 
    f->ini = f->fim = NULL;
    return f;
}

int vazia(TFila *f){
    if(f->ini == NULL)
	    return 1;
    else
	    return 0;

}


void insere(TFila *f, int elem){
   
    TLista *novo = (TLista*)malloc(sizeof(TLista));

    novo->info = elem;

    novo->prox = NULL;

    if(f->fim){
        
        f->fim->prox = novo;
    }
    f->fim = novo;
   
    if(!f->ini){
        f->ini = novo;
    }
}
int retira(TFila *f){
   
    if(vazia(f))
        return;
    

    int elem = f->ini->info;

  
    TLista *aux = f->ini;


    f->ini = f->ini->prox;

 
    if(f->ini == NULL){
        f->fim = NULL;
    }

    free(aux);
    return elem;
}

void libera(TFila *f){

    TLista *q = f->ini;
    TLista *aux;
    while(q){
      
        aux = q;
       
        q = q->prox;
       
        free(aux);
    }
    free(f);
}

 

[arfneto]

9 minutos atrás, nicholas22 disse:

Não posso alterar o código já pronto.

Preciso implementar no código abaixo uma função que, dada uma fila de entrada p, retorne uma fila com todos os elementos de p ordenados de maneira crescente. Ao final da execução desta função, p permanecerá com todos os seus elementos

 

Pena não poder mudar o código oferecido, porque ele poderia ficar bem melhor...

 

Como seu compromisso é apenas com a função 

 

    TFila* ordena (TFila *f)

 

pode escrever isso do modo como achar melhor.
 

É claro que p vai ficar com todos seus elementos, já que vai criar outra fila. Não entendi o porque da observação no enunciado já que é mais fácil criar outra pilha do que classificar a fila original e o objetivo é exatamente criar outra. Seria um exercício mais complexo classificar in-line a mesma fila.

 

De volta ao enunciado:

 

Sugiro duas opções:

• como são apenas int os dados da fila, apenas criar um vetor com eles em ordem. É trivial porque vai ler um por um mesmo, usando retira() e aí coloca claro no vetor já na ordem porque afinal repito vem 1 a 1. Ao final da fila tem o vetor ordenado e cria a nova fila num único loop usando insere()
   
• uma opção talvez mais elegante seria SOMAR ao código fornecido uma rotina "insere_na_ordem()" que faz advinha o que? Insere na ordem. É simples, e nesse caso você em um único loop retira da fila original usando retira() e insere na nova usando sua nova função. Claro que ela já deveria fazer parte do código oferecido, assim como uma rotina para inserir no fim e outra para inserir no início, ao invés de uma singela insere()

          void insere_na_ordem(TFila* fila, int elemento);

 

 

 

[nicholas22]

@arfneto não entendi direito, como eu crio um vetor com eles em ordem? isso ficaria na função?

[herbertbahia]

pra ordenar não é dureza mais é melhor inserir ordenado 

int somaPositivo(TFila *f){
	int vetor[100],i=0,j=0,aux=0,num;
    //Checa e a fila está vazia.
    	int soma=0;
    if(fila_vazia(f)) exit(1);
    else{
        TFila *tmp=inicializa();
        while(f->inicio!=NULL){
        	++i;
             insere(tmp, f->inicio->info);
            vetor[i]=f->inicio->info;
            retira(f);
        }
        while(tmp->inicio!=NULL){
            insere(f, tmp->inicio->info);
            retira(tmp);
        }
    }

    for ( j=1;j<=i;j++){
    		 for( int k=j+1; k<=i; k++ ){
    		 	if( vetor[j] > vetor[k] ){
    		 		aux = vetor[j];
    		 		vetor[j] = vetor[k];
    		 		vetor[k] = aux;
    }
}
}
           for(j=1;j<=i;j++)
            printf("%d ",vetor[j]);
            
}

 

[arfneto]

1 minuto atrás, nicholas22 disse:

não entendi direito, como eu crio um vetor com eles em ordem? isso ficaria na função?

 

Sim, claro. Se optar por esse caminho o vetor fica dentro de ordena(). Depois de coletar os int que estão na fila você cria a nova a partir do vetor ordenado. Para ordenar o trivial é usar insertion sort já que vai pegar um por um mesmo

 

Eu não tinha lido com atenção o código e o enunciado. Como precisa preservar a fila p e não foram fornecidas funções de percurso simplesmente, a única coisa que tem lá é retira(), fica complicado percorrer a fila usando o código que está lá sem mudar nada... Nem sei se foi de propósito que o enunciado acabou assim.

 

O fato é que você precisa retirar para poder ver o que tem lá e precisa repor na ordem. Nada especial, mas um pouco chato. Você pode retirar os nós e colocar de volta no fim, marcando o endereço de onde começou para evitar um loop. e assim poderia ficar só com as rotinas fornecidas.

 

Confirme se entendeu isso. Continuam válidas as duas opções que sugeri, apenas com esse cuidado de preservar as coisas. Veja isso com papel e caneta antes e vai entender, eu creio.

[arfneto]

1 hora atrás, arfneto disse:

marcando o endereço de onde começou para evitar um loop

 

Claro, o endereço de onde começou é o fim da lista e foi fornecido: p.fim. E insere() insere sempre no fim...

 

O conteúdo da lista vai ser preservado em termos de ponteiros, mas a lista toda vai ser redefinida, apenas copiada para o fim dela mesma.

 

2 horas atrás, nicholas22 disse:

Ao final da execução desta função, p permanecerá com todos os seus elementos

 

É verdade, mas não devia ser preciso todo esse trabalho de recriar a lista toda com os mesmos ponteiros se vai só extrair uma cópia em ordem... Meio bobinho o enunciado. Podia só varrer a lista P e criar uma lista Q com os ponteiros em ordem de classificação, uma lista de referência. Só que aí não usaria o código fornecido, só a estrutura já na memória

 

@herbertbahia considerando seu vetor int v[]

 

pense nessa função

int   insere_na_ordem(int N, int V[], int T)
{	// insere N em V[], V com T elementos
	int pos = 0;
	for (pos = T; pos > 0; pos = pos - 1)
	{	if (V[pos - 1] > N)
			V[pos] = V[pos - 1];
		else break;
	};	// for()
	V[pos] = N; // pos = posicao certa
	return T + 1;
};

que já insere o valor extraído da fila no vetor, só que na ordem. Acabou acabou: não precisa ler tudo de novo e classificar: apenas aproveita a oportunidade de vir um por um, como eu falei. Ela retorna o total: atenção

 

 

[nicholas22]

@arfneto Realmente, dá forma que você falou seria muito melhor porém infelizmente tenho que fazer como o professor quer kkkk. Eu consegui fazer aqui obrigadoo

adicionado 3 minutos depois

@herbertbahia obrigadoo

[arfneto]

a função é o insertion sort apenas. Só escrevi meio que ao contrário porque achei mais legível. E é claro que podia passar o endereço de T e não o valor.