Ir ao conteúdo
  • Cadastre-se
Regras do Clube do Hardware

C Fila de Prioridade em C

Lucas LC

Por Lucas LC
em C/C#/C++

 Compartilhar
Ir à solução Resolvido por arfneto,

Posts recomendados

arfneto
 

arfneto

Postado
Postado
1 hora atrás, Lucas LC disse:

Ficou bem mais elegante

 

sim. Quase legível. :)

 

Esse trecho

image.png.256838effe81c1f9ffec8857c8504783.png

é o que invalida os ponteiros e remove um cara. Note o incremento para remover :D 

 

Fazendo assim conserta o problema de tamanho() já que o modelo não tem o óbvio campo. Não tem cabimento percorrer toda a lista a cada vez que consulta o tamanho, e assim


image.png.edea673961481f81098842aab5694dfc.png

 

tamanho() volta a ter uma linha só como é normal. E atribuir maxElementos ao id do excluído invalida o nó para o arranjo porque o modelo estabelece que o maior id é (maxElementos-1). E assim a vida segue e não precisa mais alocar um ELEMENTO para um id que já tenha estado na fila antes, como previsto no enunciado. e não tem chance de leak de memória

Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado
34 minutos atrás, Lucas LC disse:

Posso dar uma olhada no código todo ? pra mim ver essas mudanças

 

As mudanças foram essas que listei:

 

  • ExibirLog() é nova porque a anterior que você escreveu não listava do jeito que eu pretendia, por slot e depois pela fila
  • O modelo, tosco, não tinha previsão para o tamanho, e usei o campo id do registro sentinela
  • Faltavam elementos para salvar os endereços de nodes removidos e criar uma nova lista seria tosco. Então invalidei os ponteiros como mostrei antes
  • Evitei usar tipos que são ponteiros porque acho 1d10t@. Ainda que se chame PONT. Se NUNCA definir um tipo ponteiro NUNCA vou ter que pensar nisso. Se quero um ponteiro uso o operador. E para os tipos uso sempre apenas a primeira letra em maiúscula. É só uma convenção mas é bom ter uma.
  • Coloquei as funções em ordem alfabética porque é muito chato ficar procurando e meu IDE põe uma lista de links para elas e se estão em ordem não preciso procurar. Separei em dois grupos: as do exercício e as helpers, só 2: exibirLog() e trocaPrioridade()
  • as de teste estão claro em main()
    São coisas como essa aqui:
     
  • Citação

     

    int        testaRemoveTodos(FILADEPRIORIDADE* porque)
    {
        // agora remove todos

        printf("\n\n\t==> Atendendo todo mundo: fila vai ficar vazia\n\n\n");
        
        // mostra antes
        exibirLog(porque);

        ELEMENTO* adeus = NULL;
        while (tamanho(porque) > 0)
        {
            adeus = removerElemento(porque);
            if (adeus != NULL)
            {
                printf("Removido elemento com endereco %p\n", adeus);
            }
            else
            {
                printf("Nao removeu elemento (%d,%6.2f)\n",
                    porque->fila->prox->id, porque->fila->prox->prioridade);
            };    // if()
        };

        // mostra depois
        exibirLog(porque);

        return 0;
    };    // testaRemoveTodos()

     


    Que faz o simples: atende todo mundo que está na fila. Naturalmente, ao retornar exibeLog() deve mostrar a fila vazia.

O resto acho que pouco mudou. Escrevi umas funções para ter uns testes mais tranquilos e estão em main().  As outras estão no arquivo normal. Usei um arquivo para main() outro para os headers e outro para as funções, o normal.

 

O sw do forum está com problemas, como deve ter visto nesses dias. Hoje não tenho a opção de publicar código... :) por exemplo. Algumas funções sumiram do editor. Não vou copiar o código aqui porque não compensa o trabalho. Depois talvez, se voltar  o editor.

 

Pode ver

Pode baixar os arquivos e o exemplo da saída aqui

 

Me avise se achar um erro ou senão entender algo. Como eu disse não dá para postar aqui porque algumas funções sumiram do editor por enquanto

image.png.ac71a41c82ea1ac47faca3a40c29be18.png

 

Não entendo porque o forum não usa um editor compatível com MarkDown como o GitHub ou o StackOverflow

 

 

 

 

 

adicionado 3 minutos depois

E agora o genial editor do forum substitui p q por 'porque" mesmo dentro de um programa. Pode? Que bobagem....

 

Entenda que a variável no programa se chama p q como em Priority Qeue, mas o sw do forum trocou isso dentro do programa...

adicionado 4 minutos depois

image.png.882b14f57c21657a16caf4890dffd307.png

 

:D:D sério? 

Link para o comentário
Compartilhar em outros sites
Lucas LC
 

Lucas LC

Postado
  • Autor
Postado
25 minutos atrás, arfneto disse:

O sw do forum está com problemas, como deve ter visto nesses dias. Hoje não tenho a opção de publicar código... :) por exemplo. Algumas funções sumiram do editor. Não vou copiar o código aqui porque não compensa o trabalho. Depois talvez, se voltar  o editor.

Sem problemas, deixei o mais simples possível, acabei com as condições, mas não está inserindo nada 😰

 

 

bool inserirElemento(PFILA f, int id, float prioridade){
  bool resposta = false;
  PONT ant, atual
  ELEMENTO* novoElemento;
  PONT* arranjo;
  PONT prox = ant->prox;
   
 novoElemento = buscaSeqExc(f,prioridade,&atual,&ant);
  
 if(id < 0 || id >= f->maxElementos) return false;
 
 if(f->arranjo[id] == NULL) return false;
 
 novoElemento = (PONT) malloc(sizeof(ELEMENTO));

 f->arranjo[id] = novoElemento;

 

 novoElemento->ant = ant;
 novoElemento->prox = ant->prox;
 ant->prox = novoElemento;
 novoElemento->prox->ant = novoElemento;
 novoElemento->prioridade = prioridade;
 novoElemento->id = id;

  resposta = true;
  return resposta;
}

Link para o comentário
Compartilhar em outros sites
Lucas LC
 

Lucas LC

Postado
  • Autor
Postado
8 horas atrás, arfneto disse:

Você leu o código nos links que eu te mandei? entendeu? baixou os programas?

 

Foi mal acabei não vendo, mas vou dar uma olhada. 

adicionado 44 minutos depois
9 horas atrás, arfneto disse:

Você leu o código nos links que eu te mandei? entendeu? baixou os programas?

 

Entendi o erro do meu código, eu achava que estava incluindo em uma lista circular, mas confundi as interpretações e fiz uma inserção de uma fila normal, ontem a noite eu corrigi essa parte, mas tinha um sinal errado que cancelava toda a minha inclusão. Com seu código consegui perceber isso. 

 

  • A função de busca estava ordenando corretamente, mas parecia que não era muito preciso comparar prioridade seria melhor comparar endereço do elemento. 
  • A função de troca eu tentei implementar no inicio, mas como estava dando erro, acabei deixando de lado. 
adicionado 50 minutos depois
9 horas atrás, arfneto disse:

Você leu o código nos links que eu te mandei? entendeu? baixou os programas?

 

Obrigado pela ajuda, agora está correto e consegui entender o processo. 

 

No começo pareceu confuso, mas aos poucos fui entendendo o ponto chave desse programa, mesmo eu sendo teimoso querendo implementar um código complexo rs, mas o senhor ajudou muito. 

 

Continue assim ajudando as pessoas. 

Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado
1 hora atrás, Lucas LC disse:

A função de busca estava ordenando corretamente, mas parecia que não era muito preciso comparar prioridade seria melhor comparar endereço do elemento

a função de busca não deveria ordenar... E a necessidade é digital ;) ou precisa ou não precisa. Rodou as funções de teste que te mostrei? Elas tem que funcionar igualzinho com as suas funções.

 

Nesse modelo que está usando

  • se está buscando por identificador o acesso é direto pelo --- mal denominado --- arranjo.
  • se está buscando por prioridade apenas pense como uma fila comum: vai entrar atrás do primeiro cara com uma senha menor que a sua. Isso quer dizer que sua fila é estável --- stable --- porque caras com a mesma prioiridade vão ser atendidos por ordem de chegada. Isso evita muita discussão na fila ;) 
    Seu enunciado não exige estabilidade mas também não proíbe e aí seria mais best@ ainda depois de tantos buracos que já tem nele. 
1 hora atrás, Lucas LC disse:

No começo pareceu confuso

 

É confuso. O modelo é cheio de furos. Tem uns nomes b0b0s. Chega ao ponto de ter uma função para aumentar a prioridade, uma para diminuir e outra para consultar.

 

E evite usar typedefs para ponteiros. Sempre cai na sua cabeça..

 

O editor de código não voltou ainda ao menos para mim. Quando voltar poste seu código.

 

Leu o código que escrevi? 

Link para o comentário
Compartilhar em outros sites
Lucas LC
 

Lucas LC

Postado
  • Autor
Postado
6 horas atrás, arfneto disse:

Leu o código que escrevi?

Olhei sim 

adicionado 1 minuto depois
6 horas atrás, arfneto disse:

O editor de código não voltou ainda ao menos para mim. Quando voltar poste seu código.

Estou fazendo alguns ajustes, quando eu terminar eu posto aqui. 

Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado

Parece que o botão de código está de volta ao forum. Teste seu programa com aquelas funções de teste. Como essa

  

int		testaCriaUns(FILADEPRIORIDADE* porque)
{
	printf("\n\n\t==> Criando alguns registros\n\n\n");

	for (int id = 0; id < 30; id += 3)
	{
		int res = inserirElemento(porque, id, (float)(rand() % 2000) / 100.f);
		if (res < 0)
		{
			printf("Erro ao inserir %d\n", id);
			return 0;
		};
	};	// if()
	return 0;
};	// testaCriaUns()

 Note que o nome da fila é p q :) e o forum vem alterando por canta deles

 

Ou essa
  

int		testaMudaPrioridade(FILADEPRIORIDADE* f)
{
	printf("\n\n\t==> Teste:\n\
\t\tsoma 1 em todas as prioridades para ID pares\n\
\t\te diminui 1 em todas as impares\n\n\n");

	// mostra antes
	exibirLog(f);

	int ix = tamanho(f);
	ELEMENTO* p = f->fila->prox; // primeiro 
	while (ix > 0)
	{
		if (p->id % 2 == 0)
			aumentarPrioridade(f, p->id, (float)(p->prioridade + 1.0f));
		else
			reduzirPrioridade(f, p->id, (float)(p->prioridade - 1.0f));

		p = p->prox;
		ix -= 1;
	};	// while()

	// mostra depois
	exibirLog(f);

	return 0;
};	// testaMudaPrioridade()

 

Não acredito que alguém seriamente especificou essas duas rotina,s aumentar e reduzirPrioridade, mas tudo bem :D :D 

 

Ou essa que atende todo mundo que está na fila...
  

int		testaRemoveTodos(FILADEPRIORIDADE* porque)
{
	// agora remove todos

	printf("\n\n\t==> Atendendo todo mundo: fila vai ficar vazia\n\n\n");
	
	// mostra antes
	exibirLog(porque);

	ELEMENTO* adeus = NULL;
	while (tamanho(porque) > 0)
	{
		adeus = removerElemento(porque);
		if (adeus != NULL)
		{
			printf("Removido elemento com endereco %p\n", adeus);
		}
		else
		{
			printf("Nao removeu elemento (%d,%6.2f)\n",
				porque->fila->prox->id, porque->fila->prox->prioridade);
		};	// if()
	};

	// mostra depois
	exibirLog(porque);

	return 0;
};	// testaRemoveTodos()

 

adicionado 0 minutos depois

Note que o software novo do forum continua fazendo aquela bobagem....

adicionado 10 minutos depois

:D 

adicionado 27 minutos depois

Mudei um pouco exibirLog()
  


exibirLog(): Fila tem  30 lugares.  10 ocupados

        Listagem por identificador:

   1/  30: [ id:    0 P:  12.21 ]
   2/  30: [ id:    3 P:   4.93 ]
   3/  30: [ id:    6 P:  12.17 ]
   4/  30: [ id:    9 P:   6.74 ]
   5/  30: [ id:   12 P:  18.49 ]
   6/  30: [ id:   15 P:   9.51 ]
   7/  30: [ id:   18 P:   6.06 ]
   8/  30: [ id:   21 P:   5.77 ]
   9/  30: [ id:   24 P:   4.21 ]
  10/  30: [ id:   27 P: -56.00 ]

        Listagem por prioridade: [ inicio: 0x00A55900 ]

   1/  10: [ id:   12 p:  18.49 ] [ 0x00A58A10, ant:0x00A55900, prox: 0x00A4FE48]
   2/  10: [ id:    0 p:  12.21 ] [ 0x00A4FE48, ant:0x00A58A10, prox: 0x00A53B00]
   3/  10: [ id:    6 p:  12.17 ] [ 0x00A53B00, ant:0x00A4FE48, prox: 0x00A58C50]
   4/  10: [ id:   15 p:   9.51 ] [ 0x00A58C50, ant:0x00A53B00, prox: 0x00A53B40]
   5/  10: [ id:    9 p:   6.74 ] [ 0x00A53B40, ant:0x00A58C50, prox: 0x00A58B50]
   6/  10: [ id:   18 p:   6.06 ] [ 0x00A58B50, ant:0x00A53B40, prox: 0x00A58810]
   7/  10: [ id:   21 p:   5.77 ] [ 0x00A58810, ant:0x00A58B50, prox: 0x00A4F9A0]
   8/  10: [ id:    3 p:   4.93 ] [ 0x00A4F9A0, ant:0x00A58810, prox: 0x00A58E50]
   9/  10: [ id:   24 p:   4.21 ] [ 0x00A58E50, ant:0x00A4F9A0, prox: 0x00A58E10]
  10/  10: [ id:   27 p: -56.00 ] [ 0x00A58E10, ant:0x00A58E50, prox: 0x00A55900]

Fim da listagem

 

Assim fica mais obvio para seguir os links: o endereço do registro sentinela está explícito em  "inicio:". Claro que ele vem  antes do primeiro e depois do último, mas fica mais claro assim. E muda só uma linha de código afinal. Não sei porque não tinha isso desde antes.

  • Curtir 1
Link para o comentário
Compartilhar em outros sites
Lucas LC
 

Lucas LC

Postado
  • Autor
Postado

Concluído!!! 

#include "filaDePrioridade.h"

PFILA criarFila(int max){
  PFILA res = (PFILA) malloc(sizeof(FILADEPRIORIDADE));
  res->maxElementos = max;
  res->arranjo = (PONT*) malloc(sizeof(PONT)*max);
  int i;
  for (i=0;i<max;i++) res->arranjo[i] = NULL;
  PONT cabeca = (PONT) malloc(sizeof(ELEMENTO));
  res->fila = cabeca;
  cabeca->ant = cabeca;
  cabeca->prox = cabeca;
  cabeca->id = -1;
  cabeca->prioridade = 1000000;
  return res;
}

void exibirLog(PFILA f){
  printf("Log [elementos: %i (alem do no cabeca)]\n", tamanho(f));
  PONT atual = f->fila;
  printf("%p[%i;%f;%p]%p ", atual->ant, atual->id, atual->prioridade, atual, atual->prox);
  atual = atual->prox;
  while (atual != f->fila){
  printf("%p[%i;%f;%p]%p ", atual->ant, atual->id, atual->prioridade, atual, atual->prox);
  atual = atual->prox;
  }
  printf("\nElementos validos: ");
  atual = atual->prox;
  while (atual != f->fila){
    printf("[%i;%f;%p] ", atual->id, atual->prioridade, atual);
    atual = atual->prox;
  }

  printf("\nValores do arrajo:\n\[ ");
  int x;
  for (x=0;x<f->maxElementos;x++) printf("%p ",f->arranjo[x]);
  printf("]\n\n");
}


int tamanho(PFILA f){
int tam = 0; 
PONT atual = f->fila->prox; 

while(atual != f->fila) {
tam++; 
atual = atual->prox;
 
}
return tam; 
}


ELEMENTO* buscaSeqExc(PFILA f, float prioridade,PONT* atual, PONT* ant) {
*ant = f->fila;
*atual = (*ant)->prox;

while((*atual)->prioridade > prioridade && (*atual) != f->fila) {
*ant = *atual;
*atual =(*atual)->prox;

}
}

bool trocar(PFILA f, int id, float prioridade){
 
(f->arranjo[id]->ant)->prox = f->arranjo[id]->prox;
(f->arranjo[id]->prox)->ant = f->arranjo[id]->ant;

ELEMENTO* novo = f->fila->prox; 
while (novo != f->fila){
if (prioridade >= novo->prioridade) break;
    novo = novo->prox;
    } 
novo->ant->prox = f->arranjo[id];
f->arranjo[id]->ant = novo->ant;
novo->ant = f->arranjo[id];
f->arranjo[id]->prox = novo;
f->arranjo[id]->prioridade = prioridade;

   return true;
}

bool inserirElemento(PFILA f, int id, float prioridade){
  bool resposta = false;
  PONT ant, atual;
  ELEMENTO* novoElemento;
  PONT* arranjo;
   
 novoElemento=buscaSeqExc(f,prioridade,&atual,&ant);
 if(f->arranjo[id] != NULL) return false;
 
 if(id < 0 || id >= f->maxElementos) return false;
 
 novoElemento = (PONT) malloc(sizeof(ELEMENTO));

 f->arranjo[id] = novoElemento;

 novoElemento->ant = ant;
 novoElemento->prox = ant->prox;
 ant->prox = novoElemento;
 novoElemento->prox->ant = novoElemento;
 novoElemento->prioridade = prioridade;
 novoElemento->id = id;

  resposta = true;
  return resposta;
}

bool aumentarPrioridade(PFILA f, int id, float novaPrioridade){
  bool resposta = false;
 
 if (f == NULL)  return false; 
 if (id < 0)     return false; 
 if (id >= (f->maxElementos)) return false; 
 if ((f->arranjo[id] == NULL) || (f->arranjo[id]->ant == NULL))
   return false;

 
 if ((f->arranjo[id] == NULL) || (f->arranjo[id]->ant == NULL)) return false;

 if (f->arranjo[id]->prioridade  >= novaPrioridade) return false;
 
  
   trocar(f, id, novaPrioridade);
 
  resposta = true;
  return resposta;
}

bool reduzirPrioridade(PFILA f, int id, float novaPrioridade){
  bool resposta = false;

   if (f == NULL) return false; 
   if (id < 0) return false; 
   if (id >= (f->maxElementos)) return false;
   if ((f->arranjo[id] == NULL) || (f->arranjo[id]->ant == NULL))
   return false;

    
   if ((f->arranjo[id] == NULL) || (f->arranjo[id]->ant == NULL)) return false;

   if (f->arranjo[id]->prioridade <= novaPrioridade) return false;

   
   trocar(f, id, novaPrioridade);

 
  resposta = true;

  return resposta;
}

PONT removerElemento(PFILA f){
  PONT resposta = NULL;
  PONT ant;
  PONT* arranjo;
  int id;
 
  if (f->fila->prox == f->fila) return resposta;
   
ELEMENTO* apagar = f->fila->prox;
    int idApagar = apagar->id;
    
    f->fila->prox = apagar->prox;
    apagar->prox->ant = f->fila;
    f->arranjo[idApagar] = NULL;
 
resposta = apagar;
    return resposta;
}
 
bool consultarPrioridade(PFILA f, int id, float* resposta){
  bool resp = false;

  if (f == NULL) return false; 
  if (id < 0) return false; 
  if (id >= (f->maxElementos)) return false; 
  if ((f->arranjo[id] == NULL) || (f->arranjo[id]->ant == NULL)) return false;

  *resposta = f->arranjo[id]->prioridade;
 
  resp = true;
  return resp;
}

 

  • Curtir 1
Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado
13 horas atrás, Lucas LC disse:

Concluído!!!

 

exibirLog() não pode cancelar só porque a fila não foi criada ainda. É uma rotina de diagnóstico e em geral é escrita antes mesmo da que cria a fila. Para teste. Uma rotina de teste não deve cancelar só porque o ponteiro não é válido

 

A saída de exibirLog() está um pouco ruim de ler, para uma rotina que serve justamente para certificar que a estrutura está ok e os ponteiros estão certinhos. Talvez deva rever.

Link para o comentário
Compartilhar em outros sites
arfneto
 

arfneto

Postado
Postado

 

Essa é a saída da versão atual de exibirLog()

 

image.thumb.png.8114c17329280acb2a0f8ef866cc7c89.png

 

Que está lá na versão que eu escrevi. Pode usar algo assim. tem a lista dos slots ocupados na fila, o total deles, o ponteiro para o sentinela e todos os ponteiros para os registros na listagem por prioridade, que é a fila propriamente dita

  • Curtir 1
Link para o comentário
Compartilhar em outros sites
Lucas LC
 

Lucas LC

Postado
  • Autor
Postado
Em 23/09/2020 às 17:52, arfneto disse:

Que está lá na versão que eu escrevi. Pode usar algo assim. tem a lista dos slots ocupados na fila, o total deles, o ponteiro para o sentinela e todos os ponteiros para os registros na listagem por prioridade, que é a fila propriamente dita

Perfeito arfneto, agradeço sua ajuda. 

Link para o comentário
Compartilhar em outros sites

Crie uma conta ou entre para comentar

Você precisa ser um usuário 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
 Compartilhar
Ir à lista de tópicos

Sobre o Clube do Hardware

No ar desde 1996, o Clube do Hardware é uma das maiores, mais antigas e mais respeitadas comunidades 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

Mais

×
×
  • Criar novo...

 

GRÁTIS: ebook Redes Wi-Fi – 2ª Edição

EBOOK GRÁTIS!

CLIQUE AQUI E BAIXE AGORA MESMO!