Lista Encadeada - Inserção ordenada

[gRoOvE 0]

Estou com umas dúvidas pra fazer essa função, inserir de forma ordenada os registros em uma lista encadeada. Vou verificar sempre o último registro da lista, não vou ter que percorrer a lista toda na caça do menor correto? Vou ter que tratar 3 situaçãoes diferentes, caso seja o inicio da lista e o root aponte para NULL, caso o valor da entrada seja maior que o da lista e caso o valor da entrada seja menor que o da lista, só quero saber se a forma de pensar está correta pra tentar implementar aqui :D

[_Isis_ 202]

inserir de forma ordenada os registros em uma lista encadeada. Vou verificar sempre o último registro da lista, não vou ter que percorrer a lista toda na caça do menor correto? Vou ter que tratar 3 situaçãoes diferentes, caso seja o inicio da lista e o root aponte para NULL, caso o valor da entrada seja maior que o da lista e caso o valor da entrada seja menor que o da lista, só quero saber se a forma de pensar está correta pra tentar implementar aqui

 

 

Vai ter que pesquisar tudo sim,mas não se pesquisa pelo menor. Use pesquisa binaria após a ordenação.

 

Crie uma estrutura com a quantidade de elementos da lista.

[gRoOvE 0]

Se pesquisa com base em que então? Vou percorrer a lista toda e ir salvando em uma variável o "maior"/"menor" pra saber qual o maior/menor número, mas no caso vo salvar o endereço do nó pra depois inserir naquela posição? Pra que a estrutura com a qtd de elementos?

[_Isis_ 202]

Não precisa salvar nada e você não vai pesquisar nem o maior elemento e nem o menor da lista. você só vai achar o lugar e colocar o elemento lá.

 

 

http://pt.wikipedia.org/wiki/Pesquisa_bin%C3%A1ria

[gRoOvE 0]

Calma, eu preciso inserir de forma ordenada ainda...depois implemento na busca a pesquisa binária. Não entendi, como não vou pesquisar qual o maior e menor? Como vou achar o lugar onde colocar ele se não souber isso?

[_Isis_ 202]

eu preciso inserir de forma ordenada ainda...depois implemento na busca a pesquisa binária

 

você vai usar primeiro a pesquisa binária pra depois inserir.

Leia a implementação do algoritmo.

[gRoOvE 0]

Fiz dessa forma, parece estar funcionando certinho...mas não consegui entender como usar a pesquisa binária "/

void inserirListaOrdem(Celula* inicio, int valor)
{
	Celula* p = inicio;
	Celula* novo;
	Celula* anterior = NULL;

	if(!(novo = (Celula*)malloc(sizeof(Celula))))
		return;

	novo->conteudo = valor;
	novo->proximo = NULL;

	/*procura posicao para insercao*/
	while(p != NULL && p->conteudo < valor)
	{
		anterior = p;
		p = p->proximo;
	}
	/*insere elemeto*/
	if(inicio->proximo == NULL) /*insere no comeco*/
	{
		inicio->proximo = novo;
		novo->proximo = NULL;
	}
	else /*insere no meio/fim*/
	{
		anterior->proximo = novo;
		novo->proximo = p;
	}
	return;
}

[RMontanaro 0]

Esse algoritmo que você fez é o método da Inserção Direta, em que se sai procurando pela posição correta, e ao encontrá-la (posição anterior a um elemento maior que o atual), você insere o elemento e muda os ponteiros.

Já na inserção sugerida pelo import, você realizaria a Busca Binária para encontrar a posição a ser inserido o elemento.

É claro, em ambos os casos supõe-se que a lista já está ordenada.

[gRoOvE 0]

Seria como inserir em um vetor então? Entendi...