Algoritmo e estrutura de dados para clientes/camiões (/serviços anteriores?)

[chalkos]

Assumindo que estes dois são o exemplo de coisas genéricas com que vamos trabalhar (visto que as localizações provavelmente serão implementadas com um grafo), vamos decidir como vamos decidir como vamos fazer as cenas.

A ideia era fazer aqui o brainstorm pois fica registado a ideia de cada um na thread. eu ou alguém actualiza depois a thread inicial. quando estiver decidido passa-se para os brainstorms na wiki. acho que fica mais arrumado.

O que vamos representar:

Camião:

identificação matricula custo por quilómetro em função do combustível e desgaste do veículo; localidade actual

Clientes

número de contribuinte nome morada último serviço

Serviços anteriormente solicitados

identificação do camião contribuinte do cliente custo cidade onde o camiao estava cidade onde o camiao foi carregado cidade de destino do camiao

Como vamos representar

Estruturas de dados

typedef struct sGenerica{
    unsigned long int id; //contribuinte ou identificação do camião
    char *nome; //nome da pessoa ou matricula do camião
    void *outro; //morada (char *) do cliente ou estrutura de consumo do camião
    void *ultimo; /* apontador para o ultimo serviço solicitado por esse cliente
    * ou apontador para a localidade onde o camião ficou (ou será
    * melhor apontador para o ultimo serviço onde esse camião
    * participou? para aceder até possivelmente ao cliente, não
    * perdendo a possibilidade de saber a localização, pois a
    * estrutura dos serviços inclui localização) */
} Generica;

// para depois podermos mudar preços de combustível rapidamente / dinamicamente
typedef enum eCombustivel{
    TIPO1 = 1,
    TIPO2 = 2,
    TIPO3 = 3,
    TIPO4 = 4
} Combustivel;

typedef struct sConsumo{
    unsigned char desgaste; /* valor de 0-255 relativo ao desgaste do camião, ainda
    * não pensei como vou lidar com o valor*/
    Combustivel comb; // tipo de combustivel de acordo com o enum
}

typedef struct sServico{
    unsigned long int camiao; //camiao id
    unsigned long int nif; //contribuinte (numero de identificação fiscal)

    //opcionais
    float custo; /* custo da viagem até ao local de carga e depois até ao destino
    * este serviria para saber o custo, pois se o preço do combustível
    * for alterado, deixa de se conseguir fazer o cálculo de quanto custou */

    //os próximos dependem de como as cidades vão ser definidas
    //provavelmente serão apontadores
    ???? cidadeOrigem;
    ???? cidadeCarga;
    ???? cidadeDestino;
} Servico;

Algoritmos

Clientes e Camiões

aqui vou inserir um esboço da cena de hash com listas skip

[chalkos]

Ainda antes de colocar o esboço: adapto a estrutura generica para conter a estrutura do serviço? assim a ganerica dava tambem para os serviços anteriores

[danielcarvalhopt]

Tu ainda estás a colar o pisto com as estruturas genéricas?

[chalkos]

Como assim? Isto é importante.... não percebi :|

[danielcarvalhopt]

O importante quer-me parecer que não são as estruturas de dados em si, mas sim as funções sobre o mesmo tipo de estruturas, estas é que têm que ser genéricas. E se abusarmos dos apontadores depois podemos meter-nos numa trapalhada pesada.

Para além disso essa estrutura não está muito bem pensada, pelo menos não nos termos que o Nestor pôs nas aulas. O desgaste e combustível serão um valor fixo, temos de criar uma estrutura com as propriedades da carga, meter mais campos para os camiões, etc.

Acho que o importante agora é concentrar-mo-nos no grafo com as localidades e implementar uma tabela de hash nisso, senão vai ser o caralho procurar uma localidade no meio de 20000 linearmente através da lista ligada. Já viste mais sobre listas skip?

Se as listas skip nao funcionarem vamos ter de usar àrvores binárias de procura, uma para NIF, outra para Nome do cliente.

[danielcarvalhopt]

Acabei de fazer uma pesquisa e aparentemente árvores binárias são melhor cena que Listas skip. Procura cenas e diz o que achas.

[chalkos]

Tri-Árvores Binárias FTW!