C lista de prioridade em c

Lucas LC · 12 de setembro de 2020

Olá pessoal!

Estou com muitas dúvidas sobre ponteiros e estou tentando implementar uma função inserir na lista de prioridade duplamente ligada. Alguém poderia me ajudar no código abaixo.

Minhas estruturas:

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

typedef struct {
  int maxElementos; //Armazena os dados 
  PONT fila; //Elementos que fica na fila
  PONT* arranjo; //Armazena os ponteiros
} FILADEPRIORIDADE, * PFILA;

bool inserirElemento(PFILA f, int id, float prioridade){
  bool resposta = false;
  PONT = novoElemento, ant, prox; 

 if(f->novoElemento.id < 0 || f->fila >= maxElementos) return false; 
 
 if(f->novoElemento.id == f->maxElementos->id) return false;  
 PFILA novoELEMENTO = (PONT) malloc(sizeof(ELEMENTO));
 arranjo = &novoElemento;
 
 novoElemento = f->maxElementos-1; //Começar no final do array e vai voltando para encotrar a prioridade. 
 while(novoElemento >= 0 && f->fila[novoElemento].prioridade >= prioridade) {
     f->fila[novoElemento+1] = f->fila[novoElemento];
     novoElemento--;
 }
 f->fila[novoElemento+1].id = id;
 f->fila[novoElemento+1].prioridade = prioridade;
 f->maxElementos++
 resposta = true;
 return resposta;
}

arfneto · 15 de setembro de 2020

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

typedef struct {
  int maxElementos; //Armazena os dados 
  PONT fila; //Elementos que fica na fila
  PONT* arranjo; //Armazena os ponteiros
} FILADEPRIORIDADE, * PFILA;

Do modo como declarou fica muito difícil de ler. Considere que está declarando dois tipos por exemplo, ELEMENTO e PONT, só que um é ponteiro e outro não, para o mesmo tipo de estrutura. Isso é complicado, difícil de ler e arriscado. Mesmo chamando de PONT Em geral não se faz isso, apesar de que a Microsoft tem essa convenção há décadas de usar LP isso e aquilo por exemplo.

Mas compare

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

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

}   NODE;

typedef struct
{
    int     maximo; //Armazena os dados 
    int     size;
    NODE*   inicio;

}   FilaDePrioridade;


int main(void)
{
    FilaDePrioridade    porque = { 500,0,NULL }; // 1

    FilaDePrioridade    fila = // 2
    {
        .inicio = NULL,
        .size = 0,
        .maximo = 1000
    };

    FilaDePrioridade outra; // 3
    outra.inicio = NULL;
    outra.maximo = 50;
    outra.size = 0;
  
    FilaDePrioridade* pFila = &porque;
  
};  // main()

E talvez ache mais fácil de ler: Não há tipos para ponteiros então não há o que procurar ou aprender: se é um ponteiro está na declaração da variável e não na declaração da estrutura ou do tipo ou no nome. Fique a vontade para achar bobagem o que eu expliquei.

De volta a programa: A função

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

tem um grande problema: o que é PFILA? É FILADEPRIORIDADE*. Então o valor entra em inserirElemento() mas não sai nunca mais. E se alterar o inicio da lista ele vai se perder. E se não passar o início da lista não vai achar o lugar para inserir. Então... não funciona.

Por isso o usual é declarar

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

e retornar sempre o endereço de início. Claro, vale o mesmo para apagar ou criar ou qualquer operação.

Outra opção é passar o endereço do ponteiro, declarando

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

É menos flexível, menos legível e provavelmente mais seguro.

Um pouco de formalidade

Entenda que a fila de prioridade é uma estrutura em si. E pode ser implementada usando qualquer coisa, desde que resolva --- encapsulamento é o termo --- e uma lista ligada serve para isso.

Mas uma lista ligada não é uma fila de prioridade. Sua estrutura fica meio híbrida assim: meio lista ligada meio fila de prioridade. A bem da verdade o comum é usar um array e uma estrutura chamada heap para implementar isso.

E em geral os nodes em sua lista ligada seriam algo assim

typedef struct aux
{
    void*       item;
    struct aux* ant;
    struct aux* prox;

}   NODE;

// ou algo como

typedef struct aux
{
    ITEM        item;
    struct aux* ant;
    struct aux* prox;

}   NODE;

Porque? simples: você quer que a lista ligada funcione para qualquer coisa. Então a lista é de item e você põe um endereço apenas. Assim não precisa sequer compilar o código quando usa uma lista ligada.

E como seria com a prioridade?

Você acerta a prioridade na rotina de inserção apenas. Coloca o cara na fila no lugar de acordo com a prioridade, usando uma função de comparação na rotina de inserção para a lista.

Mais um palpite

Poste um código inteiro compilável para ajudar os outros aqui a ajudarem você.

TL;DR

No seu programa o ponteiro para inserir() é uma variável local e não retorna para main() então não vai inserir nada.