Inserir ordenado na lista encadeada(ligada)

[otaviohpf]

Olá, estou com um problema: tenho que ler um arquivo de .csv que contem simulações de jogos entre dois times e/ou consultas ao ranking.

Foi especificado que o numero de consultas é muito maior que o numero de simulações de jogos.

Para não ficar muito custoso pensei em sempre inserir os times após cada simulação já de maneira ordenada, e se o time já tiver feito algum outro jogo, eu removo e insiro novamente ordenado.

/****************************    Estruturas    ****************************/
typedef int TipoChave;
typedef struct TipoTime {
char *nome;
int  classificacao;
int  pontos;
}TipoTime;
typedef struct TipoItem{
TipoChave Chave;
TipoTime Time;
}TipoItem;
typedef struct TipoCelula *TipoApontador;
typedef struct TipoCelula{
TipoItem Item;
TipoApontador Prox;
}TipoCelula;
typedef struct TipoLista{
TipoApontador Primeiro, Ultimo;
}TipoLista;

/****************************    Funcoes    ****************************/
void FLVazia (TipoLista *Lista);
int Vazia(TipoLista Lista);
void Insere (TipoItem x, TipoLista *Lista);
void Retira (TipoApontador p, TipoLista *Lista, TipoItem *Item);
void Imprime (TipoLista Lista);
void ImprimeNoArquivoDeSaida (TipoLista Lista);
int pesquisarTime(TipoLista *L , char *nome, TipoCelula *Celula);
void inserirOrdenado(TipoLista Lista , TipoItem *Time);
void atualizaVitoria(TipoLista Lista, TipoItem *Item, TipoApontador p);
void atualizaEmpate(TipoLista Lista, TipoItem *Item, TipoApontador p);

/*Função que faz uma lista vazia*/
void FLVazia (TipoLista *Lista){
Lista -> Primeiro = (TipoApontador) malloc (sizeof(TipoCelula));
Lista -> Ultimo   =  Lista -> Primeiro;
Lista -> Primeiro -> Prox = NULL;
}

int Vazia(TipoLista Lista){
return (Lista.Primeiro == Lista.Ultimo);
}

/*Insere na lista*/
void Insere (TipoItem x, TipoLista *Lista){
Lista -> Ultimo -> Prox = (TipoApontador) malloc (sizeof (TipoCelula));
Lista -> Ultimo = Lista -> Ultimo -> Prox;
Lista -> Ultimo -> Item = x;
Lista -> Ultimo -> Prox = NULL;
}
/*Remove da lista*/
void Retira (TipoApontador p, TipoLista *Lista, TipoItem *Item){
TipoApontador q;
if ( (Vazia(*Lista)) || (p == NULL) || (p -> Prox == NULL) ){
 printf ("\nErro: lista vazia ou posicao nao existe!!\n");
 return;
}

q = p -> Prox;
*Item = q -> Item;
p -> Prox = q -> Prox;
if (p -> Prox == NULL){
 Lista -> Ultimo = p;
}
free (q);
}
/*Imprime a lista*/
void Imprime (TipoLista Lista){
TipoApontador Aux;
Aux = Lista.Primeiro -> Prox;
while (Aux != NULL){
 printf ("%d \n" , Aux -> Item.Chave);
 Aux = Aux -> Prox;
}
}
/*void ImprimeNoArquivoDeSaida (TipoLista Lista){
TipoApontador Aux;
Aux = Lista.Primeiro -> Prox;
while (Aux != NULL){
 fprintf (ArqSaida,"%d, \n" , Aux -> Item.Chave);
 Aux = Aux -> Prox;
}
}*/
//pesquisa se já existem o time na lista.
int pesquisarTime(tlista *L,char *nome, TipoCelula *Celula){
   TipoCelula *p;
   TipoTime *Time;
  while (p !=NULL){
        Time = L->nome;
        if (strcmp(nome,Time->nome)==0){
           return 1;
        }
   }
   return 0;
}
/*Esta função faz a inserção na lista de maneira ordenada*/
void inserirOrdenado(TipoLista Lista **p, *Time)
{
   lista *atual, *novo, *anterior;
   int num;
   novo = (lista *) malloc(sizeof(lista));
   atual = *p;
   anterior = NULL;
   novo->valor = Time;
   if(atual == NULL){
       novo->prox = NULL;
       *p = novo;
   } else{
       while(atual != NULL && atual->valor < num){
           anterior = atual;
           atual = atual->prox;
       }
       novo->prox = atual;
       if(anterior == NULL){
           *p = novo;
       } else{
           anterior->prox = novo;
       }
   }
}
/*A função recebe o time vitorioso, copia para um time temporário.
chama a função Retira, para remover o item da lista
soma os 3 pontos da vitória e insere novamente de maneira ordenada*/
void atualizaVitoria(TipoLista Lista, TipoTime Time, TipoApontador p){
TipoItem ItemTemp;
//Copia o time para um TipoTime temporário.
ItemTemp.Time.nome = Item.Time.nome;
ItemTemp.Time.classificacao = Item.Time.classificacao;
ItemTemp.Time.pontos = Item.Time.pontos+3;//Ponteiro ou conteudo ?
Retira ( p, *Lista, *Item);
inserirOrdenado( Lista **p, *ItemTemp);

}
/*A função recebe os times que empataram(um por vez), copia para um time temporário.
chama a função Retira, para remover o item da lista
soma o 1 ponto da vitória e insere novamente de maneira ordenada*/
void atualizaEmpate(TipoLista Lista, TipoItem *Item, TipoApontador p){
TipoItem ItemTemp;
ItemTemp.Time.nome = Item.Time.nome;
ItemTemp.Time.classificacao = Item.Time.classificacao;
ItemTemp.Time.pontos = Item.Time.pontos+3;//Ponteiro ou conteudo ?
Retira ( p, *Lista, *Item);
inserirOrdenado( Lista **p, *ItemTemp);

}

int main(){
/************************** VARIAVEIS *****************************/
   char buffer[100];
   int i = 0;
   int flag = 1;
   TipoLista Campeonato;
   TipoItem ItemAux;
   char *Acao;
   char *TipoDaAcao;
   char *NomeDoTime1;
   char *NomeDoTime2;
/************************ LEITURA ARQUIVOS *******************************/

   FILE *ArqEntrada; // leitura dos comandos
   FILE *ArqSaida;   // resultado dos comandos
   FILE *ArqRanking; // arquivo do ranking ordenado
   ArqEntrada = fopen("entrada.csv","r");
   ArqSaida   = fopen("saida.csv", "w");
   ArqRanking = fopen("ranking.csv","r");

   if (ArqEntrada == NULL)    {
           printf ("\nERRO: Arquivo de entrada incorreto!");
   }
   if (ArqSaida == NULL){
       printf("\nERRO: Arquivo de saida incorreto!");
   }

   if (ArqRanking == NULL){
       printf("\nERRO: Ranking nao encontrado. Sera gerado um novo.");
       ArqRanking = fopen("ranking.csv","w");
       flag = 0;
   }
/************************ CARREGANDO SIMULAÇÕES ANTERIORES *******************************/
   if (flag==1){
   fgets (buffer, 100, ArqRanking);
       while (!feof(ArqRanking)){
           printf ("\n");
           ItemAux.Time.nome = atoi (strtok (buffer, ","));
           printf ("\nNome: %s", ItemAux.Time.nome);
           ItemAux.Time.classificacao = atoi (strtok (buffer, ","));
           printf ("\nClassificacao: %d", ItemAux.Time.classificacao );
           ItemAux.Time.pontos = atoi(strtok (NULL, ","));
           printf ("\nPontuacao: %d", ItemAux.Time.pontos);
           fgets (buffer, 100, ArqRanking);
       }
  }
/************************ LEITURA DA ENTRADA *******************************/
  while (!feof(ArqEntrada)){
          Acao = strtok (NULL, ",");
          if       (strcmp("CONSULTA", Acao)==0){
                   TipoDaAcao = atoi (strtok (buffer, ","));
                   NomeDoTime1 = atoi (strtok (buffer, ","));
                   //if (pesquisarTime(&Campeonato, *NomeDoTime1, ItemAux )==0){
                   if (1){
        printf("/nERRO: Time nao encontrado para consulta.");
                   }
                   if (strcmp("PONTUACAO", Acao)==0){
                       fprintf(ArqSaida, "%s,%s,%d", TipoDaAcao, NomeDoTime1, ItemAux.Time.pontos);
                   }
                   else if (strcmp("RANKING", Acao)==0){
                       fprintf(ArqSaida, "%s,%s,%d", TipoDaAcao, NomeDoTime1, ItemAux.Time.classificacao);
                   }
                   }
           else if(strcmp("VITORIA", Acao)==0){
                   NomeDoTime1 = atoi (strtok (buffer, ","));
                   NomeDoTime2 = atoi (strtok (buffer, ","));
                   if (1){//*pesquisarTime(*NomeDoTime1, Campeonato, ItemAux )*/){
                       atualizaVitoria(Campeonato, *Item, p);
                       }
                   else if(1){ //(pesquisarTime(*NomeDoTime1, Campeonato, ItemAux )==0){
                       //Como somar os 3 pontos para inserir ordenado?
                       inserirOrdenado(Campeonato p, *Time);
                   }
                   if (1){ //(pesquisarTime(*NomeDoTime2, Campeonato, ItemAux )==0){
                       inserirOrdenado(Campeonato p, *Time);
                   }
          /* else if(strcmp("EMPATE", Acao)==0){
                   NomeDoTime1 = atoi (strtok (buffer, ","));
                   NomeDoTime2 = atoi (strtok (buffer, ","));
                   /* pesquisarTime retorna 1 se o time for encontrado e 0 se não.
                   if (pesquisarTime(*NomeDoTime1, Campeonato, ItemAux )){
                       atualizaEmpate(Campeonato, *Item, p);
                       }
                   /* pesquisarTime retorna 1 se o time for encontrado e 0 se não.
                   else if (pesquisarTime(*NomeDoTime1, Campeonato, ItemAux )==0){
                       //Como somar o 1 ponto para inserir ordenado?
                       inserirOrdenado(Campeonato p, *Time);
                   }
                   /* pesquisarTime retorna 1 se o time for encontrado e 0 se não.
                   if (pesquisarTime(NomeDoTime2, Campeonato, ItemAux )){
                       atualizaEmpate(Campeonato, *Item, p);
                       }
                   /* pesquisarTime retorna 1 se o time for encontrado e 0 se não.
                   else if (pesquisarTime(*NomeDoTime2, Campeonato, ItemAux )==0){
                       //Como somar o 1 ponto para inserir ordenado?
                       inserirOrdenado(Campeonato p, *Time);
                   }
                 */
               }
           else{
               printf("/nErro: Primeiro argumento invalido.");
           }
  }
/************************ IMPRIME RANKING *******************************/
  ImprimeNoArquivoDeSaida(Campeonato);

   fclose(ArqEntrada);
   fclose(ArqSaida);
   fclose(ArqRanking);

   return 0;
}

Fiz o código desta maneira porém estou com muitas duvidas quanto as passagens dos parâmetros para as funções. Vocês podem me ajudar ? Obrigado

Edited November 25, 2015 at 11:12 PM by thoga31
GeSHi

[HappyHippyHippo]

podes ser mais concreto na tua dúvida ?

[otaviohpf]

podes ser mais concreto na tua dúvida ?

Quando vou compilar o programa ele apresenta vários erros nas passagens das funções, ainda não tenho muita prática com programação, então tenho dificuldade de lidar com tads e estruturas... Gostaria que me ajudassem a tentar achar os erros, porque já estou a algum tempo tentando corrigi-los mas não consigo.

Obrigado.

[HappyHippyHippo]

acabei de ver que fizeste aquilo que nuca se deve fazer:

escreveste +200 linhas de código e nunca te deste ao trabalho de testar uma única até então.

tens tantos erros que não sei por onde pegar.

a única coisa que te posso aconselhar para ter isso correctamente é:

- cria um novo ficheiro de código

- cria a função main só com o return

- define os tipos de dados que pretendes criar

- cria uma função de cada vez e testa para que esta corra como deve ser antes sequer de pensar na próxima

[otaviohpf]

acabei de ver que fizeste aquilo que nuca se deve fazer:

escreveste +200 linhas de código e nunca te deste ao trabalho de testar uma única até então.

tens tantos erros que não sei por onde pegar.

a única coisa que te posso aconselhar para ter isso correctamente é:

- cria um novo ficheiro de código

- cria a função main só com o return

- define os tipos de dados que pretendes criar

- cria uma função de cada vez e testa para que esta corra como deve ser antes sequer de pensar na próxima

Obrigado pela resposta, mas este semestre da faculdade foi muito corrido, e este trabalho deve ser entregue amanhã de noite. Não sei se conseguirei começar tudo de novo.

Mas obrigado pela atenção.

[HappyHippyHippo]

eu não estou a dizer para começar de novo, estou a dizer para testar e corrigir uma coisa de cada vez, porque o que não faltam ai são coisas para corrigir

[otaviohpf]

eu não estou a dizer para começar de novo, estou a dizer para testar e corrigir uma coisa de cada vez, porque o que não faltam ai são coisas para corrigir

A sim, havia entendido errado...

Este é o meu problema:

1 Introdução

O objetivo deste trabalho e simular o ranking de times em um torneio de futebol com base em

confrontos diretos. Seu programa devera contemplar dois aspectos: (1) armazenar a atualizar

a pontuação e a posição no ranking de cada time a cada resultado de jogo obtido e (2) como o

sistema pode ser acessado por jornalistas e seguidores dos times, a qualquer momento, podem

ser solicitadas consultas ao programa. A nalidade dessa simulação e prover aos usuarios um

sistema de ranking baseado em confrontos diretos que possa ser consultado em tempo real.

2 O Problema

Dene-se para este trabalho que a pontuação de um time s~ao os pontos que o time ganhou ate

o momento, e seu ranking e a posicao relativa do time (1, 2, 3 lugar, etc.). Na simulação,

o resultado dos confrontos entre os times so podera ser vitoria ou empate. Dene-se que, a

cada rodada, o time vitorioso ganha 3 pontos e o perdedor ganha 0, sendo que, no caso de

empate, ambos os times ganham 1 ponto. No incio, a ordem dos times e indenida (todos

têm 0 pontos). Conforme eles vão jogando, a ordenação muda.

Ao escolher seus algoritmos, leve em consideração as propriedades do problema. Por

exemplo, como a alteração do ranking dos times decorrente de um so jogo e muito pequena,

considere utilizar uma forma de reordenar o vetor que leve isso em consideração. Alem disso,

como e esperado que o numero de consultas seja vastamente superior ao numero de jogos,

priorize a otimização do processo de consultar os dados de pontuação e ranking referentes a

um time, em detrimento do processo de adicionar novos times. Explicitamente, o custo de

uma operação de consulta devera ser estritamente menor que O(n), onde n e o numero de

times. Sua nota tambem levara em consideração a forma com que você reordena o vetor de

times apos cada jogo { soluções usando algoritmos triviais como o BubbleSort e Selection

Sort serão penalizadas. Considere tambem que, dado que o simulador pode ser usado em

qualquer torneio de futebol, o numero de times e desconhecido.

A sada do seu sistema sera um relatorio contendo os resultados de cada consulta, seguido

de um resumo no nal que lista os times em ordem do melhor ao pior colocado. No caso de

empate, os resultados serão apresentados em ordem alfabetica.

3 Formato de Entrada e Saída

Segue a denição dos arquivos de entrada e saída. Observe que os CSVs não possuem uma

virgula ao final da linha.

3.1 Entrada

O arquivo de entrada contem uma informação ou requisição por linha em formato csv (arquivo

separado por virgulas), como no primeiro TP, observando que o ultimo atributo vem seguido

de uma quebra de linha ('\n'). As requisições podem ter um dos seguintes formatos:

VITORIA,[NOME TIME A],[NOME TIME B]: Define uma vitoria do time A sobre o time

B. Nesse caso, a pontuação do time vencedor (A) deve ser acrescida de 3 pontos, e a

do perdedor (B) devera permanecer inalterada

.

EMPATE,[NOME TIME A],[NOME TIME B]: Define um empate entre os times A e B, caso

em que a pontuação de ambos os times deve ser acrescida em um ponto.

CONSULTA,PONTUACAO,[NOME TIME]: Requisita a pontuac~ao do time no torneio. Times

que ainda não jogaram deverão ter pontuação 0.

CONSULTA,RANKING,[NOME TIME]: Requisita o ranking do time no torneio. Esse valor

e um inteiro entre 1 e N, onde N e o numero total de times que ja jogaram. Times que

ainda não jogaram deverão ter ranking N+1.

Um exemplo de um possível arquivo de entrada e o seguinte:

VITORIA,LEOES LEAIS,POMBOS POTENTES

CONSULTA,RANKING,LEOES LEAIS

CONSULTA,PONTUACAO,POMBOS POTENTES

CONSULTA,PONTUACAO,FOCAS FORTES

CONSULTA,RANKING,FOCAS FORTES

CONSULTA,RANKING,TIGRES TENAZES

EMPATE,LEOES LEAIS,FOCAS FORTES

VITORIA,POMBOS POTENTES,JACUS JUSTOS

CONSULTA,RANKING,LEOES LEAIS

CONSULTA,RANKING,JACUS JUSTOS

CONSULTA,PONTUACAO,IGUANAS IMBATIVEIS

VITORIA,JACUS JUSTOS,POMBOS POTENTES

3.2 Saída

O arquivo de saída tambem é um csv, e contem as saidas das requisições na ordem em que

aparecem na entrada, em adição a uma listagem dos times e seus pontos em ordem de ranking.

As saídas das requisições devem obedecer o seguinte formato:

RANKING,[NOME TIME],[RANKING INTEIRO]: Expressa o ranking do time como um inteiro

entre 1 e N (ou N+1 se o time nunca foi visto antes).

PONTUACAO,[NOME TIME],[PONTUACAO INTEIRA]: Expressa a pontuação que o time

obteve ate o momento da requisição (ou 0 se o time nunca foi visto antes).

O arquivo de saída esperado referente ao exemplo dado na entrada seria o seguinte:

RANKING,LEOES LEAIS,1

PONTUACAO,POMBOS POTENTES,0

PONTUACAO,FOCAS FORTES,0

RANKING,FOCAS FORTES,3

RANKING,TIGRES TENAZES,3

RANKING,LEOES LEAIS,1

RANKING,JACUS JUSTOS,4

PONTUACAO,IGUANAS IMBATIVEIS,0

1,LEOES LEAIS,4

2,JACUS JUSTOS,3

3,POMBOS POTENTES,3

4,FOCAS FORTES,1

Este é o meu problema a ser resolvido, você consegue enxergar alguma solução que seja mais fácil de implementar ? Obrigado.