lista ordenada

[Krisofferson 0]

Olá pessoal. Estou fazendo um trabalho da faculdade e travei pois não consegui terminar minha lista. O Programa tem que pegar os dados de um arquivo e ordená-los por ordem de data e hora. Pois bem, se fosse no padrão americano já tava resolvido yyyy/mm/dd mas tem que ser no formato brasileiro e o arquivo origem não pode ser alterado ou seja a ordem tem que ser dd/mm/aaaa vou postar um exemplo do arquivo origem pra ver se algum pode me ajudar, não precisa fazer o código, só quero uma força com a idéia de como fazer!! (pra o cerebro não enferrujar rsrsrs).

Atualmente quando peço pra ordenar ele leva em consideração todos os dias, depois todos os meses e depois todos os anos e não a data com os tres campos. Socorrooo

 

05/01/2009;10:30;Deposito;100.00

09/01/2009;15:30;Compra_debito;30.00

01/11/2008;09:00;Compra_credito;30.00

10/02/2009;11:10;Transferencia;+49.50

11/12/2008;13:20;Pgto_fatura;50.00

10/12/2008;14:25;Compra_credito;30.00

28/12/2008;08:00;Saque;500.00

[VictorCacciari 42]

Se o arquivo vai seguir sempre esse padrão fixo, nos podemos ler ele com:

"%d/%d/%d;%d:%d;%*[^\n]\n"

 

(você pode trocar dia, mes, hora e minuto por um char, afinal você não usará mais de um byte para armazená-los)

 

A parte mais difícil já fizemos!

(obs.: O arquivo será muito grande?

desempenho será levado em conta?

 

Eu primeiro criaria uma struct para armazenar os dados que lemos, de cada linha.

e então faria um vetor com todos os dados do arquivo, ordenaria eles, e depois sobrescreveria o arquivo inical.)

 

 

Para ordenar você começa pelos valores mais significativos, ex:

 

primeiro ordene ano, depois ordene mes, dia, hora e por ultimo minuto.

 

Existem alguns algorítmos para ordenação:

http://en.wikipedia.org/wiki/Sorting_algorithm

 

é só escolher e implementar!

 

 

obs2.:

Se você tiver o valor de, por exemplo: "12/04/1994" em três variáveis: dia, mes e ano

fica fácil converter para o padrão americano.

 

char data_a[11];

 

strcpy(data_a, ano);

strcat(data_a, "\\");

strcat(data_a, mes);

....

 

boa sorte!

[Krisofferson 0]

Cara, sua resposta foi muito boa, mas o nível tá meio alto!! não entendi muito bem! eu teria que pegar o arquivo quebrar as linhas atravez de tokens depois colocar em outra lista ordenar e depois de ordenado colocar as datas sem reordena-las???? Vou postar o código que estou usando para fazer o ordenamento. foi o mais próximo que consegui chegar da resposta!!!

 

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

#define TAM 60

typedef struct no{
	char conteudo[TAM];
	struct no *proximo;
}no;

no *ins(no *lista,char *elemento)
{
	if (lista==NULL){
		if (lista=(no*)malloc(sizeof(no))){
			strcpy(lista -> conteudo, elemento);
			lista -> proximo = NULL;
			return lista;
		}
		else
			printf("Estouro de memoria!\n");
	}
	no *novo;
	if (novo=(no*)malloc(sizeof(no))){
		strcpy(novo->conteudo,elemento);
		if (strcmp(elemento,lista->conteudo)<0)
		{
			novo->proximo=lista;
			lista=novo;
			return lista;
		}
		no *aux=lista;
		while (aux->proximo!=NULL)
		{
			if (strcmp(aux->proximo->conteudo,elemento)>0)
			{
				novo->proximo=aux->proximo;
				aux->proximo=novo;
				return lista;
			}
			aux=aux->proximo;
		}
		novo->proximo=NULL;
		aux->proximo=novo;
		return lista;
	}
	else
		printf("Estouro de memoria!\n");
}

void imprimir(no *lista)
{
	no *aux=lista;
	while (aux!=NULL)
	{
		printf("%s",aux->conteudo);
		aux=aux->proximo;
	}
}

int main(){
	FILE *entrada;
	char linha[60];

	if ((entrada = fopen("entrada.txt", "rt")) == NULL){
		printf("impossivel abrir arquivo entrada.txt\n\n");
		system("pause");
		return 0;
	}
	else{
		printf("arquivo entrada.txt aberto com sucesso!!!\n\n");
	}

	no *lista=NULL;

   /* for (int i = 0; i < 7; i++){
		printf("digite um nome: ");
		scanf("%s", nome);
		lista = ins(lista, nome);
		//lista = ins(lista,(fgets(linha, 60, entrada)));
	}
*/
	while (!feof(entrada)){
		//printf("%s",linha);
		fgets(linha, 60, entrada);
		lista = ins(lista, linha);
		//lista = ins(lista,(fgets(linha, 60, entrada)));
	}//fim enquanto

	imprimir(lista);
	printf("\n\n");

	free(lista);
//	free(novo);
	system("pause");
}

[VictorCacciari 42]

Vamos por partes então!

 

Se você precisa ordenar os items, temos que ler os dados que nos são fornecidos.

você pode pegar a string do arquivo assim:

char linha[200];

	 fgets(linha, 200, arquivo);

Vamos supor que acabamos de ler a linha número 1, então teriamos:

"05/01/2009;10:30;Deposito;100.00"

 

Agora precisamos quebrar essa string em partes, vamos criar uma estrutura para guardar essas partes,

uma lista encadeada para inserirmos elementos, e uma função que quebrará a string para nós e fará a inserção de elementos:

typedef struct
{
	 int dia, mes, hora, min, ano;
} dados;

typedef struct
{
	 dados data;
	 struct node *prox;
} node;

void parseData(node* last, char* str)
{
node *curr = (node*)malloc(sizeof(node));

	curr->prox = NULL;

	sscanf(str, "%d/%d/%d;%d:%d;%*[^\n]\n", &curr->data.dia, &curr->data.mes, &curr->data.ano, &curr->data.hora, &curr->data.min);
	last->prox = curr;
}

Ok, nossos dados estão organizados!

 

Agora é só fazer a ordenação!

 

 

ps.: não compilei o código, estou no pc da escola e nm tenho compilador aqui....

 

 

abraço

[Krisofferson 0]

VictorCacciari, sua dica ajudou muito, pois agora cheguei a outra conclusão!!!! Não posso fazer a ordenação usando um algoritmo de ordenação, pois se trata de uma lista encadeada ordenada com cabeça. a Dona Maria aí não pode sair da primeira linha. então vou ter que achar um meio de tentar fazer um misto do algoritmo que você me mandou para separar a data com insersão ordenada nesta lista mas sem mover a primeira linha. Acredito que seja isso!!! rsrsrsrsrs vlw amigo. Se tiver sugestões elas serão vem vindas. Obrigado

 

Maria Cristina Ribeiro;123-4;5678-9;1000.00;987654321

05/01/2009;10:30;Deposito;100.00

09/01/2009;15:30;Compra_debito;30.00

01/11/2008;09:00;Compra_credito;30.00

10/02/2009;11:10;Transferencia;+49.50

11/12/2008;13:20;Pgto_fatura;50.00

[VictorCacciari 42]

Se a pergunta for idiota, ignora... hahaha

(não tou na faculdade, não tenho aulas teóricas)

Uma lista com cabeça é uma lista onde o primeiro elemento é "valido", ou seja, possui data.

E uma lista sem cabeça é a lista onde se tem apenas o ponteiro para o próximo elemento.

 

Certo ou errado?

 

você não precisa adicionar a Dona Maria no primeiro lugar, basta preencher a cabeça da lista com zeros, e ignorar ela na hora de mostrar os resultados.

 

E eu estava pensando no assunto, um algoritmo genérico de ordenação não vai dar certo, temos MUITOS dados para ordenar!

Ano, mes, dia, hora e minuto!

Desempenho será levado em conta?

O arquivo terá MUITOS dados??

 

Se bobiar, jogavamos pra uma tabela sql, e mandavamos ela ordenar por data, AEUHAEUHAEUHUAEHUAEHUAEHHAEU

mas ai era gambiarra pura...

 

Vou pensar em qualquer coisa, se descobrir algo, volto a postar!

Abraço e boa sorte!

[osbornehell 0]

stLista* CriaSubListaContaOrdenada(stLista* pListaConta, stConta *pConta, stData pDataInicial, stData pDataFinal, char psNomeArquivo[])
{

	 //Declara um ponteiro para a estrutura de um arquivo
	FILE *prArquivoEntrada = NULL;

	//Declara uma string para a leitura da linha
	char sLinha[TAM_STRING];

	//Declara um ponteiro para transaçao
	stTransacao *prTransacao = NULL;

	//Faz as inicializaçoes das estruturas lista
	pListaConta->prInicio = NULL;
	pListaConta->prFim = NULL;


	//Faz as inicializações da estrutura conta
	pConta->fSaldoAnterior = 0.0f;
	pConta->fSaldoAtual = 0.0f;

	//Faz a abertura do arquivo
	prArquivoEntrada = fopen(psNomeArquivo,"r");

	//Testa se o arquivo foi aberto com sucesso
	if (!prArquivoEntrada)
	{
		printf("Nao foi possivel abrir o arquivo de entrada");
		return(0);
	}

	//Le a primeira linha do arquivo (cabecalho)
	fgets(sLinha,TAM_STRING,prArquivoEntrada);

	//Invoca a função que separa as informaçoes do cabeçalho
	LerCabecalho(pConta,sLinha);

	//Enquanto existirem transasões a serem lidas
	while (!feof(prArquivoEntrada))
	{
			//Faz a leitura de uma linha no arquivo contendo os dados da transação
		fgets(sLinha,TAM_STRING,prArquivoEntrada);
		
		//Testa se não é linha em branco
		if (sLinha[0]=='\n')
		{
				continue;
			}
	 		//Aloca memória para uma nova transação
		prTransacao = (stTransacao*)malloc(sizeof(stTransacao));

			//Quebra os dados da transação e preenche as estruturas
		PreencheTransacao(prTransacao,sLinha);

			//Verifica o tipo da operação e insere na lista do cartão ou da conta corrente:
			//código 1 a 4: operações de conta corrente
			//código 5 e 6: operações do cartão de crédito
		if (prTransacao->iOperacao < 4)
		{
			InsereTransacao(pListaConta,prTransacao);
		}

	}

	 // comparar datas entrada usuario com arquivo
		 
 	  if(stTransacao.sData.iDia == sDataInicial.iDia, // erro
		&& stTransacao.sData.iMes == sDataInicial.iMes,
		&& stTransacao.sData.iAno == DataInicial.iAno); 
	  
		 if(stTransacao.sData.iDia == sDataFinal.iDia,
		&& stTransacao.sData.iMes == sDataFinal.iMes,
		&& stTransacao.sData.iAno == sDataFinal.iAno); 
			
	 //Cria um ponteiro para o nó inicial de uma lista
	  
	  stLista* prSubLista  = NULL;
	  stLista* prSubLista = (stLista*)malloc(sizeof(stLista));
	  
	 if (sListaConta==NULL)
   {
	 printf("Erro de alocacao\n");
	 return 0;
   }

   //sListaConta->sDataInicial = sConta;
   //sListaConta->sDataFinal = NULL;

   if (prSubLista==NULL)
	  prSubLista = sListaConta;
   else {
	  //sListaConta->sDataFinal = prSubLista;
	  //prSubLista  = sListaConta;
	}

	   //Implemente aqui
	
	  //Retorna a lista ordenada
	  return prSubLista;
	

}

 

esta muito errado essa linha de raciocinio

[Krisofferson 0]

VictorCacciari, nesse link tem um breve relato sobre as listas com e sem cabeça. http://www.ime.usp.br/~pf/algoritmos/aulas/lista.html

O sistema não leva em consideração o tempo gasto e eu não posso mudar o restante das funções que foram disponibilizadas pelos professores, ou seja não posso usar sql ou outros meios que não sejam os expostos pelos professores! meu trabalho é o mesmo do amigo osbornehell da resposta acima, mas eu não postei da mesma forma pois ainda estou aprendendo. Vou postar exatamente o que a função deve fazer:

 

stLista* CriaSubListaContaOrdenada(stLista* pListaConta, stConta *pConta,

stData pDataInicial, stData pDataFinal): esta função deverá retornar uma sublista

ordenada de transações, criada a partir da lista pListaConta, passada como parâmetro,

contendo somente as transações da conta corrente lidas do arquivo de entrada. O

conjunto de transações da sublista a ser retornada deverá ser delimitado pela data

inicial e final escolhida pelo usuário. Além de criar a sublista, a função deve calcular o

saldo anterior e atual da conta. O saldo anterior corresponde ao saldo da conta lido do

cabeçalho do arquivo de entrada, levando em consideração todas as transações

ocorridas até um dia antes da data inicial especificada pelo usuário. O saldo atual

corresponde ao valor do saldo anterior calculado descontando-se todas as transações

ocorridas no período escolhido pelo usuário. Os valores calculados para o saldo

anterior e o saldo atual devem ser atribuídos para os respectivos campos da estrutura

stConta.

 

Eu estou tentando implementar outro programa paralelo para depois de conseguir ordenar a lista de forma correta usar a mesma solução no problema original fazendo as devidas adaptações, pois assim acredito fixar melhor os conhecimentos!

 

E por enquanto a única coisa que consegui foi criar a bendita lista com cabeça e ordena, só que ainda está de forma incorreta. Por isso vou aproveitar o trecho de código postado pelo VictorCacciari para tentar fazer a ordenação com base na data de forma correta. Vou aproveitar e postar todo o conteúdo do arquivo entrada.txt que não é grande pra vcs verem que são poucos os dados do arquivo

 

Maria Cristina Ribeiro;123-4;5678-9;1000.00;987654321

05/01/2009;10:30;Deposito;100.00

09/01/2009;15:30;Compra_debito;30.00

01/11/2008;09:00;Compra_credito;30.00

10/02/2009;11:10;Transferencia;+49.50

11/12/2008;13:20;Pgto_fatura;50.00

10/12/2008;14:25;Compra_credito;30.00

28/12/2008;08:00;Saque;500.00

07/02/2009;11:20;Pgto_fatura;100.00

25/01/2009;08:00;Saque;200.00

18/10/2008;12:04;Compra_debito;500.00

09/01/2009;18:30;Compra_debito;55.00

02/01/2009;18:25;Compra_credito;150.00

17/02/2009;09:55;Compra_credito;25.45

15/11/2008;12:40;Compra_debito;500.00

18/01/2009;13:40;Deposito;500.00

05/01/2009;10:20;Pgto_fatura;50.00

10/01/2009;16:30;Transferencia;-90.50

05/01/2009;20:35;Transferencia;+100.25

21/11/2008;09:10;Compra_credito;90.00

25/12/2008;12:40;Compra_debito;70.45

13/01/2009;11:45;Deposito;50.10

05/12/2008;10:30;Deposito;200.00

05/12/2008;14:25;Compra_credito;20.00

25/10/2008;09:30;Compra_debito;130.00

07/02/2009;11:55;Compra_credito;175.45

25/12/2008;11:30;Compra_debito;200.45

15/02/2009;10:30;Deposito;300.00

15/01/2009;10:25;Compra_credito;220.00

07/11/2008;11:20;Pgto_fatura;100.00

05/01/2009;10:55;Compra_credito;35.45

20/02/2009;17:20;Pgto_fatura;400.00

 

então é isso!!!!!

[José Enésio 4]

Cara pensei em uma solução maluca para você ordenar essa lista:

Pois é, como é para ordenar a lista pelo tempo, e se for ordenar por cada campo ali, vai piorar a performance por ter que realizar o código de ordenação para todos os campos que são ordenados, por que não inventa uma forma de juntar todos os números em um só código especial, e ordenar por ele apenas? Você já está conseguindo popular a lista com os dados do arquivo? Se sim, ótimo. Siga uma lógica para a criação de um número: o ano é o que tem maior importância, portanto ele irá ser multiplicado por uma potência maior de 10, efetivamente aparecendo "à esquerda" no número final que será uma adição de todos os números codificados. Os minutos tem menos importância, portanto continuarão como estão, apenas fazendo difereça quando todos os outros números são iguais a outro elemento. As horas valem mais que os minutos, portante deverão ser multiplicados por 100, fazendo com que 22:35 se torne um número 2235 (já que 22 * 100 = 2200, + 35 = 2235).

 

Siga essa lógica para os outros números também.

Você só vai usar anos a partir de 2000? Diminua o ano por 2000. Assim ele só precisará mesmo ocupar 2 espaços por um bom tempo. Depois você pode inventar seu próprio algoritmo, mas esse aqui é só pra ter uma base. Veja um exemplo:

#include <stdio.h>

int main()
{
	int dia = 0, mes = 0, ano = 0, hora = 0, minuto = 0;
	unsigned int numero_magico = 0;
	char continua;
	
	do
	{
		printf("Digite uma data no formato dia/mes/ano hora:minuto.\n O programa irá calcular um número mágico.\n Só aceita datas a partir de 2000)\n\n");
		scanf("%d/%d/%d %d:%d", &dia, &mes, &ano, &hora, &minuto);
		while(ano < 2000)
		{
			printf("Ano menor que 2000! Redigite o ano.");
			scanf("%d", &ano);
		}
		ano -= 2000;
		
		numero_magico = minuto + (hora * 100) + (dia * 10000) + (mes * 1000000) + (ano * 100000000);
		
		printf("O numero mágico da data %d/%d/%d %d:%d é %u\n\n", dia, mes, (ano + 2000), hora, minuto, numero_magico);
		
		printf("Continuar? (s/n)");
		getchar();
		scanf("%c", &continua);
	} while(continua == 's');
	return 0;
}

Esse aí funciona para datas entre 2000 e 2099, depois de 2100 aí dá problema por causa do tamanho das variáveis. Mas claro, como eu disse, mais tarde você faz outros algoritmos que realizem uma tarefa parecida.

 

Partindo desse princípio, você pode ordenar a sua lista utilizando apenas um campo daí. O algoritmo de ordenação aí é contigo.

[Krisofferson 0]

Boa José Enésio, gostei!!!! Vou tentar!! vlw

[VictorCacciari 42]

José Enésio:

 

ÓTIMA IDÉIA!

[eliseumga 0]

Olá, Krisofferson

 

Conseguiu resolver o problema ? Deu Certo ?

[Krisofferson 0]

eliseumga, a dica ajudou bastante entender melhor o problema, mas ainda não consegui copiar os valores de uma lista pra a outra de forma ordenada o sistema mistura as datas por exemplo pra o sistema 1/11/2008 11/1/2008 é a mesma coisa já que na estrutura stData tenho iDia, iMes e iAno então quando que junto os inteiros ele fica 1112008 e 1112008. Ainda tow meio perdido! Se tiver idéias elas serão bem vindas

[quitZAUMMM 18]

e c no sistema você colocar:

01112008

 

??

[VictorCacciari 42]

Cara, a dica que o José Enésio deu é otima, mas o ano tem que entrar primeiro!!!!

 

o ano é o dado mais significativo, então tem que entrar como algarismo mais significativo...

você pode guardar esses números concatenados em um unsigned long int que concerteza caberá!

 

ex:

data: 12/03/2009

hora: 22:13

 

número mágico: 200903122213

[José Enésio 4]

Nota para o Krisoferson: tem algo errado então no seu algoritmo, porque ele deveria diferenciar o dia e o mês assim:

 

20091101 e 20090111

 

Victor, você conseguiu dar certo desse jeito aí? Porque eu tinha tentado antes de várias formas, com long, com unsigned, etc... mas o número ficava errado, acho que porque o ano multiplicado ficava muito grande... Como não tava com muita paciência pra arrumar direito, fiz uma gambiarra com double, a hora e o minuto foram pra direita da vírgula e deram espaço para o ano ficar completo. Se alguém não tiver conseguindo com uint, tenta assim então! Fica aí a dica!

[VictorCacciari 42]

José,

 

unsigned long int varia de 0 a 4294967295

não cabe o ano, temos que fazer alquer coisa com ele, ou subtrair 2000, ou dividir por qualquer coisa...

 

em alguns compiladores, existe uma diferencça de 4 bytes de unsigned long int e unsigned long long int, mas isso não ocorre em todos.

 

pode ser que em um unsigned long long int caiba.

 

eu não tinha prestado atenção nisso...

Não tive tempo de efetivamente escrever e compilar uma solução.