C Fila de Prioridade em C

Lucas LC · 18 de setembro de 2020

Boa tarde!

Alguém poderia dar uma ajuda no código abaixo, sou novo em C em relação a ponteiros e tá dando muitos erros relacionado.

OBS: não posso mudar as estruturas.

#include <stdlib.h>
#include <stdio.h>
#define true 1
#define false 0

typedef int bool;

typedef struct aux {
  int id;
  float prioridade;
  struct aux* ant;
  struct aux* prox;
} ELEMENTO, * PONT;

typedef struct {
  int maxElementos;
  PONT fila;
  PONT* arranjo;
} FILADEPRIORIDADE, * PFILA;

PFILA criarFila(int max);

int tamanho(PFILA f);

bool inserirElemento(PFILA f, int id, float prioridade);

bool aumentarPrioridade(PFILA f, int id, float novaPrioridade);

bool reduzirPrioridade(PFILA f, int id, float novaPrioridade);

PONT removerElemento(PFILA f);

bool consultarPrioridade(PFILA f, int id, float* resposta);

Fila de Prioridade

#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");
}

//maxElemento é a quantidade máxima que a fila pode ter.
//fila é os elementos que possui uma prioridade para ser inserido no arranjo(endereço).
//arranjo armazena os endereços dos elementos.
//PFILA f é a fila de Prioridade. 

int tamanho(PFILA f){
int tam = 0; //Guarda o número de elemento. 
PONT atual = f->fila; //Recebe o endereço do primeiro registro e guarde no atual. 

while(atual != NULL) {//A cada elemento válido guarde na variável tam.
tam++; //Some mais 1. 
atual = atual->prox;// Recebe o prox elemento da fila.
  
}
return tam; //Quando terminar o laço com o total de elementos, retorne tam com o total.
}

//Função de Busca. 
void buscaSeqExc(PFILA f, float prioridade, PONT* atual, PONT* ant) { 
*ant = f->fila;//Inicio da fila.
*atual = ant->prox;//Próximo elemento da fila.

while(atual->prioridade > prioridade && atual->prioridade != f->fila->prioridade) { 

*ant = prox;
*atual = atual->prox;
}
}

//Função para trocar os elementos.
void troca(float *a, float *b) { 

float k = *a;//Guarda onde o a aponta em k. 
*a = *b; //Guarda onde o b aponta na posição a. 
*b = k;//Guarda onde o a aponta na posição b. 
}

bool inserirElemento(PFILA f, int id, float prioridade){
  bool resposta = false;
  PONT *arranjo;
  PONT novoElemento, ant;
  
  novoElemento = buscaSeqExc(f,prioridade,&atual,&ant);
  /*Se o identificador for menor que 0 ou maior
  max de elementos na fila retorne false */ 
 if(id < 0 || id >= f->maxElementos) return false; 
 //Caso já tenha esse id na fila. 
 if(id == f->fila->id) return false;  
 
 //Caso contrário aloque memória para esse novo elemento que irá inserir. 
 novoElemento = (PONT) malloc(sizeof(ELEMENTO));
 novoElemento->arranjo = arranjo;//Colocando o endereço no arranjo.
 
 //Acertar os ponteiros com o novoElemento usando a prioridade.
 if(f->fila->novoElemento->prioridade > f->fila->prioridade) { 
 novoElemento->prox = f->fila;//O próximo do novoElemento será o primeiro registro da fila. 
 f->fila = novoElemento;//Se torna o novo inicio da lista.
 }
 else { 
  novoElemento->prox = ant->prox;
  ant->prox = novoElemento;
  
  resposta = true;
  return resposta;
}
}


bool aumentarPrioridade(PFILA f, int id, float novaPrioridade){
  bool resposta = false;
  PONT *Arm; //Mesmo struct
  
  if(id < 0 || id >= f->maxElementos) return false; 
 
  if(id == f->fila->id) return false;  

  if(f->fila->prioridade >= novaPrioridade) return false; 
 
  else
       //Chamar a função troca para trocar as prioridades.
      troca(&(novaPrioridade), &(f->fila->prioridade));
 
  resposta = true;
     
  return resposta;
}


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

  if(id < 0 || id >= f->maxElementos) return false;

  if(id != f->fila->id) return false;  

  if(f->fila->prioridade <= novaPrioridade) return false;
  //Trocar sua prioridade, caso a novaPrioridade seja maior que a prioridade na fila. 
  else
  //Chamar a função troca para trocar as prioridades.
      troca(&(novaPrioridade), &(f->fila->prioridade));
  
  resposta = true;
     
  return resposta;
}
//Lista de disponíveis
void devolverNo(PFILA f, PONT j){
     f->arranjo[j].prox = f->fila;
     f->fila = j;
} /* devolverNo */

PONT removerElemento(PFILA f){
  PONT resposta = NULL;
  PONT arranjo; //Armazena endereço de ponteiros.
  PONT elemento; 
  PONT *ant; 
  
  //Verificar se a fila possui algum ponteiro válido. 
  if(f->fila == NULL) return resposta; 
  
  //Retirar o primeiro elemento da lista.
  if(f->fila->ant == NULL) 
      
  f->fila = f->arranjo[elemento].prox; 
  
  else f->arranjo[ant].prox = f->arranjo[elemento].prox;
  
  devolverNo(f,elemento);//Guardar na lista de disponíveis. 
  
  arranjo[elemento] = NULL 
  
   return elemento; 
 }
 

bool consultarPrioridade(PFILA f, int id, float* resposta){
  bool resp = false;

  //Identificador inválido.
   if(f->fila->id < 0 || f->fila->id >= f->maxElementos) return false; 
 //Identificador diferente com os que tem na fila. 
   if(id != f->fila->id) return false;  
   
   else 
       *resposta = &(f->fila->prioridade);//Colocar na memória o valor da prioridade.
  
  resp = true;
  return resp;
}

arfneto · 18 de setembro de 2020

1 hora atrás, Lucas LC disse:

OBS: não posso mudar as estruturas

Acho que já falei isso, mas essas estruturas sequer representam bem um fila de prioridade.

E do modo como foi escrito vai atrapalhar muito ao invés de ajudar a escrever. Sugiro escrever em torno dessas estruturas e usar o nada original conceito de encapsulamento.

E tem coisas folclóricas:

bool aumentarPrioridade(PFILA f, int id, float novaPrioridade);
bool reduzirPrioridade(PFILA f, int id, float novaPrioridade);

Considerando que a prioridade é um número de ponto flutuante e com sinal qual o sentido de ter uma função para aumentar e outra para diminuir a probabilidade?
E considerando o valor e o conceito geral de encapsulamento qual o propósito do enunciado dizer que o valor original não pode ser removido? Porque restringir a implementação?
Um valor de prioridade em float só não é mais estranho que um em radianos

Considerando que uma fila de prioridade em geral se define como uma coleção, um conjunto onde cada elemento tem uma chave e uma prioridade e as operações consideradas são

insert(x,S); insere a chave x no conjunto S --- push()
max(S) retorna o primeiro da fila. Pode ser o menor se a fila for ascendente --- top()
extract(S) retira o primeiro --- pop()
increase(k,x,S) para aumentar a prioridade k do elemento x em S

E uma fila dessas geralmente se implementa usando Heap e não listas, então como eu tinha dito em outra ocasião essa é uma estrutura híbrida de lista ligada e fila de prioridade e só vai te dar mais trabalho para escrever e provavelmente ensinar pouca coisa.

Estruturas de dados abstratas modelam coisas reais, e a prioridade muitas vezes sequer faz parte do node. Imagine um sistema de transporte onde a prioridade de uma caixa depende do destino do caminhão que vai entrar no BOX de carga, e isso só apareça quando ele entrar na vaga e o operador passar o cartão...

De volta aos termos do enunciado e ao seu código

    printf("\nValores do arrajo:\n\[ ");

tem erros simples como esse que além do erro de grafia tem um \[ e claro que o compilador vai reclamar.

Agora tem coisas para pensar como isso

void    buscaSeqExc(PFILA f, float prioridade, PONT* atual, PONT* ant);

PONT é struct aux*, um ponteiro. Então PONT* é struct aux** e você tem que tratar de acordo, como em

    *atual = ant->prox;//Próximo elemento da fila.

já que *atual é PONT e então NÃO pode escrever

    *atual = ant->prox;//Próximo elemento da fila.

No comentário pode escrever o que quiser, mas PONT não tem um campo chamado prox

*ant tem... Pense nisso. Assim estaria certo:

    *atual = (*ant)->prox;//Próximo elemento da fila.

Por isso eu disse aqui que não é esperto declarar typedef para ponteiros e estruturas ao mesmo tempo. Declare apenas para estruturas e não vai errar como aqui...

Lucas LC · 19 de setembro de 2020

arfneto eu entendi o conceito de uma fila de prioridade, mas essa atividade que estou desenvolvendo não está relacionada apenas com fila de prioridade, a sua dedução que é lista ligada junto com fila de prioridade está correto.

Meus ponteiros atual e prox está dando erro dentro da função inserir e na função busca.

Um ponteiro não pode apontar para uma variável do tipo float ? será que é isso problema de semântica ?

arfneto · 19 de setembro de 2020

1 hora atrás, Lucas LC disse:

Meus ponteiros atual e prox está dando erro dentro da função inserir e na função busca

você entendeu o que eu te expliquei? eu mostrei a linha, a razão e as variáveis.

De novo:

1 hora atrás, Lucas LC disse:

eu entendi o conceito de uma fila de prioridade, mas essa atividade que estou desenvolvendo não está relacionada apenas com fila de prioridade, a sua dedução que é lista ligada junto com fila de prioridade está correto

O que eu tentei de explicar, mais de uma vez, vou tentar resumir de outro modo: uma fila de prioridade pode ser implementada de qualquer maneira. Qualquer uma. Esse conceito de colocar a implementação toda dentro da estrutura é o tal de encapsulamento.

Quando você lê as chamadas das funções que tratam a lista de prioridade não consegue ver como ela foi implementada.

Se você abre seu programa nas funções que tratam a lista ligada não vê o que ela está ligando, não vê a fila de prioridade. E esse é o valor real dessas coisas: ADT. Você abstrai o modelo real e esconde nessas estruturas de estruturas de estruturas.

Esse modelo que você recebeu é muito ruim. Não mostra o valor dos modelos. Não ajuda na implementação e ainda fica no seu caminho. Exatamente o que eu te disse que dá problema está dificultando a simples compilação de um algoritmo que já está torto na própria declaração.

Mas assim é. Se deve fazer assim use suas variáveis e tipos e conserte o que der.

Veja se entende a linha de código que te mostrei de novo e a questão dos tipos.

A culpa não é sua de ficar confuso se está confuso. O modelo é ruim demais.

1 hora atrás, Lucas LC disse:

Um ponteiro não pode apontar para uma variável do tipo float ? será que é isso problema de semântica

Não, não é. Um ponteiro é só isso: uma variável de 4 ou 8 bytes nesse caso e que tem um endereço. Esse endereço pode apontar para qualquer coisa.

Corrija o que te expliquei ou pergunte de novo se não entendeu.

adicionado 9 minutos depois

Um exemplo do seu modelo:

PFILA é um ponteiro para FILADEPRIORIDADE, e aponta para um endereço onde tem uma estrutura arranjo que aponta para um ponteiro para struct aux, onde tem um ponteiro ant para uma outra struct aux.

Você acha que um exercício introdutório como esse justifica esse nível de redirecionamento? Eu acho que não.

adicionado 19 minutos depois

novoElemento é PONT, que é struct aux*

typedef struct aux
{
    int id;
    float prioridade;
    struct aux* ant;
    struct aux* prox;

} ELEMENTO, * PONT;

E lá não tem esse campo arranjo. Ele está em f, que é FILADEPRIORIDADE*, onde tem um campo arranjo que é struct aux** que é PONT* sinistro. Estou quase aprendendo seu modelo.

Lucas LC · 19 de setembro de 2020

Agradeço as respostas e novamente obrigado, estou corrigindo aos poucos e entendendo também.

Lucas LC · 19 de setembro de 2020

arfneto consegui corrigi a minha função de busca, usei um número inteiro que é o id(identificador) em vez de um tipo float que não é o usual quando se usa operadores como == e !=, o ponteiro atual recebe o primeiro elemento válido da lista, fiz um laço enquanto o identificador apontado pelo atual for menor que o elemento buscado ele passa para o próximo elemento da fila, quando ele sair do laço vai para minha condição if para ter certeza q o elemento foi encontrado, o elemento atual tem q ser diferente do elemento que está no inicio da minha fila q é o nó cabeça e o atual ser igual ao id buscado, caso não encontre retorna NULL. Faz sentido ?

22 horas atrás, arfneto disse:


   //Função de Busca. 
PONT buscaSeqExc(PFILA f, int id, PONT* ant) { 
*ant = f->fila;
PONT atual = f->fila->prox;//Primeiro elemento válido.

while(atual->id < id) { 
*ant = atual;
atual =atual->prox;
}
if(atual != f->fila && atual->id == id) return atual; 
return NULL;//Não encontrou. 
}

Mas agora estou com problema nessa função excluir elemento, os métodos abaixo são remover elementos que retorna NULL se não tiver nenhum elemento válido na fila e caso contrário, retira o primeiro elemento válido da lista, coloquei o valor NULL na posição correspondente desse elemento no ponteiro arranjo e retornei o endereço do respectivo elemento.

Como não posso liberar a memória do elemento eu fiz uma função devolverNó para colocar no inicio da minha fila, caso o usuário precise usar. Mas nesse método eu posso colocar ele no inicio da minha lista f ou f->fila ou só coloco NULL na posição que ele foi retirado e não libero a memória dele ? nesse método fiquei em dúvida.

22 horas atrás, arfneto disse:


//Lista de disponíveis
void devolverNo(PFILA f, int j){
     f->arranjo[j]->prox = f->fila;//Colocar no inicio da fila.
     f->fila = j;
} /* devolverNo */


PONT removerElemento(PFILA f){
  PONT resposta = NULL;
  PONT* arranjo; //Armazena endereço de ponteiros.
  int elemento;
  PONT *ant;
 
  //Verificar se a fila possui algum ponteiro válido.
  if(f->fila == NULL) return resposta;
 
  //Retirar o primeiro elemento da lista.
  if(f->fila->ant == NULL)
 
  f->fila = f->arranjo[elemento]->prox;
 
  else f->arranjo[ant]->prox = f->arranjo[elemento]->prox;
 
  devolverNo(f,elemento);//Guardar na lista de disponíveis no inicio da fila.
 
  arranjo[elemento] = NULL;
 
   return elemento;
 }

adicionado 3 minutos depois

E consegui arrumar alguns erros básicos de ponteiros no código.

arfneto · 19 de setembro de 2020

15 minutos atrás, Lucas LC disse:

Faz sentido ?

Sim. Faz total sentido

16 minutos atrás, Lucas LC disse:

Como não posso liberar a memória do elemento eu fiz uma função devolverNó para colocar no inicio da minha fila

Quando mais seu modelo se afasta da realidade simples de uma fila de prioridade, implementada através de uma lista ligada que não deveria estar aparecendo, usando uma prioridade que está fora do dado e não como atributo dele, declarada como float, o trabalho vai ficando mais e mais difícil a toa.

Agora chega a ponto de ter um alocador híbrido, com um estoque de nós vazios pré alocados para o caso de necessidade. Imagino que agora vá implementar uma lista ligada de nós apagados e prontos para reuso...

Não por acaso não terminou isso no mesmo dia em que começou.

Fuja disso. Use o próprio conceito de encapsulamento e redefina o USO desse modelo absurdo que recebeu. E escreva as funções de um modo convencional.

Porque não pode liberar a memória?

Lucas LC · 19 de setembro de 2020

37 minutos atrás, arfneto disse:

Sim. Faz total sentido

Ufa que bom.

adicionado 2 minutos depois

De acordo com o enunciado não posso liberar, porque o usuário pode querer usar o elemento excluído.

adicionado 3 minutos depois

40 minutos atrás, arfneto disse:

Fuja disso. Use o próprio conceito de encapsulamento e redefina o USO desse modelo absurdo que recebeu. E escreva as funções de um modo convencional.

kkkk não tenho permissão de mudar.

adicionado 24 minutos depois

56 minutos atrás, arfneto disse:

Quando mais seu modelo se afasta da realidade simples de uma fila de prioridade, implementada através de uma lista ligada que não deveria estar aparecendo, usando uma prioridade que está fora do dado e não como atributo dele, declarada como float, o trabalho vai ficando mais e mais difícil a toa.

Vamos esquecer o devolverNó, e se eu fosse interpretar dessa forma:

Primeiro eu busco o elemento para excluir, o if significa q o elemento não existe e retorno NULL, mas se existe o elemento i vai da para excluir, eu faço o anterior apontar para o próximo dele para a minha lista não ficar "quebrada" e colocar NULL na posição dele no arranjo[i] e retornar o endereço. Faz sentido com esse código ?

arfneto · 19 de setembro de 2020

Poste o enunciado completo

Entendo que não pode mudar. O que eu te disse é ainda assim pode usar a estrutura de um modo mais sadio. Por isso falei em encapsulamento.

Se precisa manter os nós disponíveis faça o simples e crie uma lista ligada deles, apenas acessível em insererElemento(). Não é algo novo. Se faz isso em muitos casos onde a alocação é cara ou lenta ou impossível: entra com uma estrutura maior com uma certa folga

58 minutos atrás, Lucas LC disse:

Primeiro eu busco o elemento para excluir, o if significa q o elemento não existe e retorno NULL, mas se existe o elemento i vai da para excluir, eu faço o anterior apontar para o próximo dele para a minha lista não ficar "quebrada" e colocar NULL na posição dele no arranjo[i] e retornar o endereço. Faz sentido com esse código ?

Faz sentido. Mas acho que arranjo é desnecessário. Pode tratar apenas início e uma função tipo

ELEMENTO* buscaPorId(PFILA f, int id)

que devolve o endereço se ele está na fila

e outra

ELEMENTO* buscaPorPrioridade(PFILA f, float p)

que devolve o elemento anterior ao que entraria com essa prioridade. Há um conceito chamado estabilidade, não sei se o enunciado fala nisso: em tendo vários elementos com a mesma prioridade eles devem estar por ordem de criação na fila. Então essa função te daria o lugar onde vai entrar o cara novo na fila: depois do endereço que ela retornar

Para apagar alguém ou mudar de lugar em geral tem que olhar 3 nós para a origem e 3 para o destino. E tratar os casos limite de operar no início e no fim da lista

Lucas LC · 19 de setembro de 2020

1 hora atrás, arfneto disse:

Poste o enunciado completo

adicionado 1 minuto depois

1 hora atrás, arfneto disse:

que devolve o elemento anterior ao que entraria com essa prioridade. Há um conceito chamado estabilidade, não sei se o enunciado fala nisso: em tendo vários elementos com a mesma prioridade eles devem estar por ordem de criação na fila. Então essa função te daria o lugar onde vai entrar o cara novo na fila: depois do endereço que ela retornar

Para apagar alguém ou mudar de lugar em geral tem que olhar 3 nós para a origem e 3 para o destino. E tratar os casos limite de operar no início e no fim da lista

De acordo com o enunciado não precisa se preocupar com elementos com a mesma prioridade.

adicionado 2 minutos depois

1 hora atrás, arfneto disse:

Faz sentido. Mas acho que arranjo é desnecessário. Pode tratar apenas início e uma função tipo

Sem usar o arranjo como faço para colocar NULL na posição que eu tirei ?

adicionado 5 minutos depois

1 hora atrás, arfneto disse:

Entendo que não pode mudar. O que eu te disse é ainda assim pode usar a estrutura de um modo mais sadio. Por isso falei em encapsulamento.

OK.

adicionado 42 minutos depois

#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");
}

//maxElemento é a quantidade máxima que a fila pode ter;
//fila é os elementos que possui uma prioridade para ser inserido no arranjo(endereço);
//arranjo armazena os endereços dos elementos;
//PFILA f é a fila de Prioridade;
//f->fila é o inicio da fila;
//cabeça é o primeiro elemento da fila, com id -1 e prioridade 1000000.


int tamanho(PFILA f){
int tam = 0; //Guarda o número de elemento.
PONT atual = f->fila; //Recebe o endereço do primeiro registro e guarde no atual.

while(atual != NULL) {//A cada elemento válido guarde na variável tam.
tam++; //Some mais 1.
atual = atual->prox;// Recebe o prox elemento da fila.
 
}
return tam; //Quando terminar o laço com o total de elementos, retorne tam com o total.
}

//Função de Busca.
PONT buscaSeqExc(PFILA f, int id, PONT* ant) {
*ant = f->fila;
PONT atual = f->fila->prox;//Primeiro elemento válido.

while(atual->id < id) {
*ant = atual;
atual =atual->prox;
}
if(atual != f->fila && atual->id == id) return atual;//Encontrou
return NULL;//Não encontrou.
}

bool inserirElemento(PFILA f, int id, float prioridade){
  bool resposta = false;
  PONT novoElemento, ant;
  PONT* arranjo;
 
  novoElemento = buscaSeqExc(f,id,&ant);
  /*Se o identificador for menor que 0 ou maior
  max de elementos na fila retorne false */
 if(id < 0 || id >= f->maxElementos) return false;
 //Caso já tenha esse id na fila.
 if(id == f->fila->id) return false;  
 
 //Caso contrário aloque memória para esse novo elemento que irá inserir.
 novoElemento = (PONT) malloc(sizeof(ELEMENTO));
 arranjo = &novoElemento;//Colocando o endereço no arranjo.
 
 //Acertar os ponteiros com o novoElemento usando a prioridade.
 if(novoElemento->prioridade > f->fila->prioridade) {
 novoElemento->prox = f->fila;//O próximo do novoElemento será o primeiro registro da fila.
 f->fila = novoElemento;//Se torna o novo inicio da lista.
 }
 else {
  novoElemento->prox = ant->prox;
  ant->prox = novoElemento;
 
  resposta = true;
  return resposta;
}
}


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

  if(f->fila->prioridade >= novaPrioridade) return false;
 
  else //Trocar a prioridade.
      for (id=0;id<f->maxElementos;id++) {
 f->arranjo[id]->prioridade = novaPrioridade;
      }
  resposta = true;

  return resposta;
}


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

  if(id < 0 || id >= f->maxElementos) return false;

  if(id != f->fila->id) return false;  

  if(f->fila->prioridade <= novaPrioridade) return false;
  //Trocar sua prioridade, caso a novaPrioridade seja maior que a prioridade na fila.
  else //Trocar a prioridade.
      for (id=0;id<f->maxElementos;id++) {
 f->arranjo[id]->prioridade = novaPrioridade;
 }
  resposta = true;

  return resposta;
}

//Função de Busca de id.
ELEMENTO* buscaPorID(PFILA f, int id) {
PONT* ant;
*ant = f->fila;
PONT atual = f->fila->prox;//Primeiro elemento válido.

while(atual->id < id) {
*ant = atual;
atual =atual->prox;
}
if(atual != f->fila && atual->id == id) return atual;//Encontrou
return NULL;//Não encontrou.
}

PONT removerElemento(PFILA f){
  PONT resposta = NULL;
  PONT i,ant;
  int id;
 //Devolve o endereço se ele está na fila.
  i=buscaPorID(f,id);//Busca pelo elemento.
  //Verificar se a fila possui algum ponteiro válido.
  if(i == NULL) return resposta;
 
  //Caso contrário da para excluir.
  ant->prox = i->prox;//Anterior dele apontar para o próximo.
  
  i = NULL;//Colocar NULL na posição que o elemento foi retirado.
  
  resposta = i;
  
  return resposta;
 }


bool consultarPrioridade(PFILA f, int id, float* resposta){
  bool resp = false;

  //Identificador inválido.
   if(f->fila->id < 0 || f->fila->id >= f->maxElementos) return false;
 //Identificador diferente com os que tem na fila.
   if(id != f->fila->id) return false;  
   
   else
  resposta = &(f->fila->prioridade);//Colocar na memória o valor da prioridade.
 
  resp = true;
  return resp;
}

adicionado 43 minutos depois

Os erros sumiram, só preciso verificar agora se as interações estão corretas.

arfneto · 19 de setembro de 2020

56 minutos atrás, Lucas LC disse:

De acordo com o enunciado não precisa se preocupar com elementos com a mesma prioridade

Isso quer dizer que essa fila não é estável.

Lendo o enunciado isso fica mais estranho ainda. Isso de lista circular com nó cabeça é conhecido em outros lugares como buffer circular com registro sentinela, se é assim que se escreve em português.

Mas agora entendi o porque do arranjo e o lance dos id

A lista é pré-formatada e o id é a identificação da célula no buffer, como se fosse uma sala de espera com poltronas numeradas. Isso ajuda a entender o porque do tal arranjo, que em inglês seria array . E lembra que em C++ por exemplo o container padrão para uma porque fila de prioridade é um vetor, que é um array chique em C++. E em C um vetor seria o normal, com a lista em torno dos índices, que são os id. E a performance seria ignorante já que as células seriam pré-alocadas e os ponteiros não seriam para a memória e sim para os índices. Já escrevi algo assim para buffers de transmissão tempos atrás.

Mas fica cada vez mais difícil entender onde entrou uma lista ligada aqui, e antes de a matéria introduzir filas. Não consigo entender para que escrever assim

Lucas LC · 20 de setembro de 2020

6 minutos atrás, arfneto disse:

A lista é pré-formatada e o id é a identificação da célula no buffer, como se fosse uma sala de espera com poltronas numeradas. Isso ajuda a entender o porque do tal arranjo, que em inglês seria array . E lembra que em C++ por exemplo o container padrão para uma porque fila de prioridade é um vetor, que é um array chique em C++. E em C um vetor seria o normal, com a lista em torno dos índices, que são os id. E a performance seria ignorante já que as células seriam pré-alocadas e os ponteiros não seriam para a memória e sim para os índices. Já escrevi algo assim para buffers de transmissão tempos atrás.

Exatamente uma sala de espera que é minha fila e o arranjo para guardar o endereço de cada elemento da fila e o nó cabeça como primeiro elemento, mas não sei como usar esse nó cabeça, porque sempre q uso da uns erros,

1 hora atrás, Lucas LC disse:

PONT atual = f->fila; //Recebe o endereço do primeiro registro e guarde no atual.

exemplo aqui, o primeiro endereço da minha fila é o nó cabeça, então seria f->fila->cabeca e adiciono elementos depois dele, mas da erro e substitui pela f->fila q é o inicio.

arfneto · 20 de setembro de 2020

3 horas atrás, Lucas LC disse:

exemplo aqui, o primeiro endereço da minha fila é o nó cabeça, então seria f->fila->cabeca e adiciono elementos depois dele, mas da erro e substitui pela f->fila q é o inicio

Esse registro é chamado sentinela --- sentinel record --- e é intocável. Existe o sentinela e de 0 a MAX registros. Não se misturam. É um jeito de implementar um buffer circular. O outro é usar um ponteiro para o início.

Muitas vezes não se usa isso porque o sentinela ocupa o espaço de um registro comum, ELEMENTO no seu caso. E se imagina que usa isso porque os registros são caros e importantes, como em buffers em áudio por exemplo: se tem um buffer de 300 o que chegar sempre entra. E se não tiver lugar vai apagar algum antigo que não reproduziu ainda e vai ter uma perda. E se espera que não dê pra notar na reprodução. Então se são poucos ter um sentinela pode ser um desperdício grande. Se usar MAX 19 no seu caso vai usar 20 e perder 1 para o sentinela, 5% de perda.

Lucas LC · 20 de setembro de 2020

8 horas atrás, arfneto disse:

Esse registro é chamado sentinela --- sentinel record --- e é intocável. Existe o sentinela e de 0 a MAX registros. Não se misturam. É um jeito de implementar um buffer circular. O outro é usar um ponteiro para o início.

Muitas vezes não se usa isso porque o sentinela ocupa o espaço de um registro comum, ELEMENTO no seu caso. E se imagina que usa isso porque os registros são caros e importantes, como em buffers em áudio por exemplo: se tem um buffer de 300 o que chegar sempre entra. E se não tiver lugar vai apagar algum antigo que não reproduziu ainda e vai ter uma perda. E se espera que não dê pra notar na reprodução. Então se são poucos ter um sentinela pode ser um desperdício grande. Se usar MAX 19 no seu caso vai usar 20 e perder 1 para o sentinela, 5% de perda.

Entendi, então por ser intocável não posso incluir ele nos meus códigos.

adicionado 12 minutos depois

8 horas atrás, arfneto disse:

O outro é usar um ponteiro para o início.

Então, para meu próximo elemento, ele precisa do endereço do meu nó cabeça para minha lista ficar ligada certo ? Logo se o f->cabeca é intocável, usando outro ponteiro tipo f->cabeca->prox eu posso dizer que os elementos válidos começa com f->cabeca->prox.

f->cabeca->prox = f->cabeca;

Ai eu passo o endereço do nó cabeça para o próximo e posso usar o f->cabeca->prox como inicio em vez do f->fila.

arfneto · 20 de setembro de 2020

3 horas atrás, Lucas LC disse:

Entendi, então por ser intocável não posso incluir ele nos meus códigos.

De certo modo. Apenas não pode considerar como um nó comum. Uma vez criado ele não pode mais ser alterado.

3 horas atrás, Lucas LC disse:

Então, para meu próximo elemento, ele precisa do endereço do meu nó cabeça para minha lista ficar ligada certo ? Logo se o f->cabeca é intocável, usando outro ponteiro tipo f->cabeca->prox eu posso dizer que os elementos válidos começa com f->cabeca->prox

Acho que sim, se entendi.

Sua lista sempre começa em f->fila
O primeiro elemento sempre é f->fila->prox
O último elemento sempre é f->fila->ant
Se a lista está vazia f->fila = f->fila->ant = f->fila->prox (veja a função fornecida criarFila())

Afinal a lista é circular

Escrevi uma exibirLog() que pode ser útil para o seu caso. Veja um resultado:



exibirLog(): Fila nao foi criada
inserirElemento(): id = 0 P =   7.98
Sucesso ao inserir 0
inserirElemento(): id = 3 P =   4.90
Sucesso ao inserir 3
inserirElemento(): id = 6 P =   9.20
Sucesso ao inserir 6
inserirElemento(): id = 9 P =   1.04
Sucesso ao inserir 9
inserirElemento(): id = 12 P =   9.87
Sucesso ao inserir 12
inserirElemento(): id = 15 P =  12.27
Sucesso ao inserir 15
inserirElemento(): id = 18 P =  15.09
Sucesso ao inserir 18
inserirElemento(): id = 21 P =   2.79
Sucesso ao inserir 21
inserirElemento(): id = 24 P =  13.14
Sucesso ao inserir 24
inserirElemento(): id = 27 P =   1.39
Sucesso ao inserir 27


exibirLog(): Fila tem  30 lugares.  10 ocupados

        Listagem por identificador:

   1/  30: [ id:    0 P:   7.98 ]
   2/  30: [ id:    3 P:   4.90 ]
   3/  30: [ id:    6 P:   9.20 ]
   4/  30: [ id:    9 P:   1.04 ]
   5/  30: [ id:   12 P:   9.87 ]
   6/  30: [ id:   15 P:  12.27 ]
   7/  30: [ id:   18 P:  15.09 ]
   8/  30: [ id:   21 P:   2.79 ]
   9/  30: [ id:   24 P:  13.14 ]
  10/  30: [ id:   27 P:   1.39 ]

        Listagem por prioridade:

   1/  10: [ id:   18 p:  15.09 ] [Ponteiros este:000002C508B214E0, ant:000002C508B21C00, prox 000002C508B21900]
   2/  10: [ id:   24 p:  13.14 ] [Ponteiros este:000002C508B21900, ant:000002C508B214E0, prox 000002C508B21000]
   3/  10: [ id:   15 p:  12.27 ] [Ponteiros este:000002C508B21000, ant:000002C508B21900, prox 000002C508B21840]
   4/  10: [ id:   12 p:   9.87 ] [Ponteiros este:000002C508B21840, ant:000002C508B21000, prox 000002C508B21960]
   5/  10: [ id:    6 p:   9.20 ] [Ponteiros este:000002C508B21960, ant:000002C508B21840, prox 000002C508B20E80]
   6/  10: [ id:    0 p:   7.98 ] [Ponteiros este:000002C508B20E80, ant:000002C508B21960, prox 000002C508B217E0]
   7/  10: [ id:    3 p:   4.90 ] [Ponteiros este:000002C508B217E0, ant:000002C508B20E80, prox 000002C508B20D00]
   8/  10: [ id:   21 p:   2.79 ] [Ponteiros este:000002C508B20D00, ant:000002C508B217E0, prox 000002C508B20D60]
   9/  10: [ id:   27 p:   1.39 ] [Ponteiros este:000002C508B20D60, ant:000002C508B20D00, prox 000002C508B21360]
  10/  10: [ id:    9 p:   1.04 ] [Ponteiros este:000002C508B21360, ant:000002C508B20D60, prox 000002C508B21C00]

Fim da listagem

Rode no seu código

void        exibirLog(PFILA f)
{
    //
    // exibirLog() simples listagem dos elementos da fila a
    // partir do inicio
    //
    // PFILA e um ponteiro para a fila
    // so que em f->arranjo tem uma lista circular a partir
    // da sentinela, unico registro com Id negativa
    if (f == NULL)
    {
        printf("\n\nexibirLog(): Fila nao foi criada\n");
        return;
    };

    printf("\n\nexibirLog(): Fila tem %3d lugares. %3d ocupados\n",
        f->maxElementos, tamanho(f) );

    if (tamanho(f) < 1) return;

    // lista por ID

    printf("\n\tListagem por identificador:\n\n");
    int ix = 1;
    int id = 0;
    while (ix <= tamanho(f))
    {
        if (f->arranjo[id] != NULL)
        {
            printf("%4d/%4d: [ id: %4d P: %6.2f ]\n",
                ix, f->maxElementos, id, f->arranjo[id]->prioridade);
            ix += 1;
        };  // if()  
        id += 1;
    };  // while()

    // lista por prioridade

    printf("\n\tListagem por prioridade:\n\n");
    ELEMENTO*   p = f->fila->prox; // sentinela
    ix = 1; // conta os caras
    while ( ix <= tamanho(f)  )
    {
        printf("\
%4d/%4d: [ id: %4d p: %6.2f ] [Ponteiros este:%p, ant:%p, prox %p] \n",
            ix, tamanho(f), p->id, p->prioridade, p, p->ant, p->prox
        );
        p = p->prox;
        ix += 1;
    };
    printf("\nFim da listagem\n\n");
    return;
};  // exibirLog()

É compatível.

A lógica é simples:

Lista por ID e depois a fila por prioridade

E pode testar suas funções com esse código

int main(void)
{
	srand(200920);
	int res = 0;
	FILADEPRIORIDADE* porque = NULL;
	exibirLog(porque);
	porque = criarFila(30);

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

Acho que é bem legível: apenas cria a fila e insere uns caras, deixando uns buracos nas id para poder testar e usando prioridade com valores aleatórios mas determinados. Seu programa deve dar exatamente o mesmo resultado...

Lucas LC · 20 de setembro de 2020

2 horas atrás, arfneto disse:

Escrevi uma exibirLog() que pode ser útil para o seu caso. Veja um resultado:

Ajudou bastante, vou fazer algumas correções.

arfneto · 20 de setembro de 2020

5 horas atrás, Lucas LC disse:

Ajudou bastante, vou fazer algumas correções.

Entendeu que essa implementação de main() é compatível com suas funções e exibirLog() também, certo?

Pode usar para testar seu código.

esse modelo é muito ruim. tosco.

Acho que já sabe, mas isso está errado:

São dois problemas: um óbvio e outro nem tanto.

O identificador tem que estar entre 0 e (maxElementos - 1)
a função só deve alocar memória caso alguém que tenha esse ID não tenha já sido atendido, porque nesse caso em algum lugar está a estrutura alocada inicialmente para tal ID. Ao ser atendido alguém sai da fila e em removerFila() o ELEMENTO tem que ser preservado, já que o enunciado diz em negrito que assim deve ser porque "o usuário pode querer utilizar esse elemento para alguma coisa". Só que essa é a única coisa que existe: o arranjo. E se alocar esse vai gerar um leak de memória, porque é o arranjo o único lugar onde tem esse endereço. E se criar por exemplo um pool de ELEMENTO para serem reaproveitados ninguém vai conseguir usar porque não se pode mexer nas sagradas estruturas. A menos que se use uma estrutura global para disfarçar essa bobagem escrevendo outra.

Lucas LC · 21 de setembro de 2020

1 hora atrás, arfneto disse:

esse modelo é muito ruim. tosco.

Claro que não tá me ajudando muito.

O programa tá andando, eu só preciso acertar alguns ponteiros chatinhos que tá dificultando a inserção da prioridade, mudei a função de busca, porque a fila tava ordenada pela prioridade e não pelo id e também eu pensei em reaproveitar os elementos excluídos, mas não estava pedindo então deixei pra lá.

arfneto · 21 de setembro de 2020

28 minutos atrás, Lucas LC disse:

porque a fila tava ordenada pela prioridade e não pelo id e também eu pensei em reaproveitar os elementos excluídos, mas não estava pedindo então deixei pra lá

A fila tem que estar ordenada pela prioridade

Pelo identificador o acesso é direto e óbvio porque é mais uma idiossincrasia do modelo: a estrutura tem o id mas no vetor eles estão indexados pelo próprio id. Colocou a função que te mandei no seu programa? vai ver bem o mecanismo

Não é exatamente que está pedindo, mas se leu o que escrevi já sabe que se gravar NULL naquele vetor ao remover alguém o endereço vazou. Jamais vai por as mãos nele de novo. E não vai poder liberar. Trata-se de um simples erro. Se não pode liberar tem que usar em insere(). Não pode alocar um registro de novo para o mesmo

Não posso imaginar que seu instrutor não espere que ao final você libere a memoria alocada para essas estruturas...

arfneto · 21 de setembro de 2020

4 horas atrás, arfneto disse:

Entendeu que essa implementação de main() é compatível com suas funções e exibirLog() também, certo?

Pode usar para testar seu código.

esse modelo é muito ruim. tosco.

Acho que já sabe, mas isso está errado:

São dois problemas: um óbvio e outro nem tanto.

O identificador tem que estar entre 0 e (maxElementos - 1)

a função só deve alocar memória caso alguém que tenha esse ID não tenha já sido atendido, porque nesse caso em algum lugar está a estrutura alocada inicialmente para tal ID. Ao ser atendido alguém sai da fila e em removerFila() o ELEMENTO tem que ser preservado, já que o enunciado diz em negrito que assim deve ser porque "o usuário pode querer utilizar esse elemento para alguma coisa". Só que essa é a única coisa que existe: o arranjo. E se alocar esse vai gerar um leak de memória, porque é o arranjo o único lugar onde tem esse endereço. E se criar por exemplo um pool de ELEMENTO para serem reaproveitados ninguém vai conseguir usar porque não se pode mexer nas sagradas estruturas. A menos que se use uma estrutura global para disfarçar essa bobagem escrevendo outra.

Eu li errado as letrinhas pequenas do enunciado: está certo quando fala sobre os identificadores inválidos mas a outra parte está mesmo errada. Não é possível alocar memória mais que uma vez para cada identificador ou vai perder acesso à estrutura anterior.

Lucas LC · 21 de setembro de 2020

17 horas atrás, arfneto disse:

Não é exatamente que está pedindo, mas se leu o que escrevi já sabe que se gravar NULL naquele vetor ao remover alguém o endereço vazou. Jamais vai por as mãos nele de novo. E não vai poder liberar. Trata-se de um simples erro. Se não pode liberar tem que usar em insere(). Não pode alocar um registro de novo para o mesmo

Ata beleza.

adicionado 7 minutos depois

Arrumei os ponteiros, fiz 3 condições para inclusão o primeiro é quando a lista está vazia só tem o cabeça, segundo incluir no inicio quando minha prioridade que foi passado como parâmetro for maior que todos na fila e terceiro incluir no final da fila se for menor.

Só tem um erro quando ele vai imprimir ele coloca em ordem que foi adicionado, será que preciso adicionar um código de ordenação ?

bool inserirElemento(PFILA f, int id, float prioridade){
  bool resposta = false;
  PONT novoElemento, ant, atual;
  PONT* arranjo;
  PONT prox = ant->prox;
  PONT* aux;

  novoElemento = buscaSeqExc(f,prioridade,&atual,&ant);

 if(id < 0 || id >= f->maxElementos) return false;
 
 if(id == f->fila->id) return false;  


 novoElemento = (PONT) malloc(sizeof(ELEMENTO));
 f->arranjo[id] = novoElemento;
 
 if(f->fila == f->fila->prox) { 
  novoElemento->prox = ant->prox;
  ant->prox = novoElemento;
  novoElemento->prioridade = prioridade; 
  novoElemento->id = id; 
 }
 
 if(prioridade > f->fila->prioridade) {
 novoElemento->ant = f->fila; 
 novoElemento->prox = f->fila->prox; 
 f->fila->prox = novoElemento; 
 novoElemento->prox->ant = novoElemento; 
 novoElemento->prioridade = prioridade; 
 novoElemento->id = id; 
 }

 if(prioridade < f->fila->prioridade){
 novoElemento->prox = f->fila;
 novoElemento->ant = f->fila->ant;
 f->fila->ant = novoElemento;
 novoElemento->ant->prox = novoElemento;
 novoElemento->prioridade = prioridade; 
 novoElemento->id = id; 
 }
 
      
  resposta = true;
  return resposta;
}

arfneto · 21 de setembro de 2020

11 minutos atrás, Lucas LC disse:

Arrumei os ponteiros, fiz 3 condições para inclusão o primeiro é quando a lista está vazia só tem o cabeça, segundo incluir no inicio quando minha prioridade que foi passado como parâmetro for maior que todos na fila e terceiro incluir no final da fila se for menor

Entendo. É possível, mas você não tem 3 condições: uma só deve ser suficiente porque a lista é circular. Na verdade essa nomenclatura de cabeça é desnecessária.f->arranjo se olhar bem a estrutura e os desenhos fornecidos vai ver que provavelmente o cara devia ter chamado o campo fila de cabeca e o campo arranjo de fila. Outra bob@gem desse enunciado. f->fila devia ser f->head. E f->arranjo devia ser f->slot ou algo assim.

15 minutos atrás, Lucas LC disse:

Só tem um erro quando ele vai imprimir ele coloca em ordem que foi adicionado, será que preciso adicionar um código de ordenação

Rodou a função que te mostrei em seu código? Aquela exibirLog() ? Ela vai mostrar as estruturas como devem estar.

Lucas LC · 21 de setembro de 2020

19 minutos atrás, arfneto disse:

Rodou a função que te mostrei em seu código? Aquela exibirLog() ? Ela vai mostrar as estruturas como devem estar.

Tá em ordem de inclusão mesmo.

arfneto · 21 de setembro de 2020

quando escrevi esse teste e essa função, depois do que você postou sobre o enunciado e essas restrições de não poder mudar essa estrutura ingênua, eis o que mudei para escrever exibirLog():

Usei o campo id da sentinela, que tem o valor (-1) e prioridade 1 milhão, para controlar também o tamanho da fila, porque é muito 1d10t@ ler a lista toda a cada vez que precisa do tamanho. Custava muito ter declarado um campo tamanho do lado de maxElementos?
Como usei? O id usado é mantido como -(N-1) para N elementos, simples e rápido
Para invalidar o ELEMENTO removido, usei os ponteiros e não o valor, porque acho que o autor do enunciado não tinha pensado nisso. Como a lista é circular os ponteiros jamais são NULL, já que apontam inicialmente para o sentinela, isso funciona sem problemas. Por outro lado se gravar NULL no arranjo vai ter um memory leak. Funciona bem e é simples de implementar. E invalidei o id usando o valor maxElementos. Só muda isso na rotina que insere:

bem simples. E funciona. Não precisa usar algo muito complexo nem tratar casos particulares porque a lista é afinal circular e nunca fica vazia. Na hora de remover também é trivial:
a_excluir, claro, é ELEMENTO*. Só 6 linhas de diferença em relação à função que sempre alocava um novo ELEMENTO.
pra por na lista do enunciado bob1nh0: tem uma função para aumentar a prioridade e uma para diminuir, só que o código é o mesmo e só muda um sinal. E tem uma terceira para consultar a prioridade sem alterar. Sério? Sendo que é o mesmo código?