C Inserir número em determinada posição de lista duplamente encadeada. Linguagem C

[jcgs98]

Dado o código, como incluir número em determinada posição na LDE criada?

 

Por exemplo, lista criada: 1 2 3 5 6 7 8. Quero incluir o 4 na quarta posição, tornando a lista assim: 1 2 3 4 5 6 7 8.

 

Segue o código:

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

typedef struct No
{
   int valor;
   struct No *prox, *ant;
} TNo;

typedef TNo* TLista;

int inserir (TLista *Lista, TLista *U, int num)
{
	TLista aux = (TLista) malloc (sizeof(TNo));

   		aux->valor = num;
 
  		aux->prox = *Lista;
      	
  		aux->ant = NULL;

	  	(*Lista)?(*Lista)->ant = aux:*U = aux;

      	*Lista = aux;
}

void exibir (TLista Lista)
{
	if(Lista)
	{
		printf ("%d ", Lista->valor);
		exibir (Lista->prox);
	}
}

 

[arfneto]

Sua pergunta é ambígua: você diz que quer inserir na quarta posição, mas sugere que quer também inserir na ordem numérica.
 

3 horas atrás, Comunista.RJ disse:

1 2 3 5 6 7 8. Quero incluir o 4 na quarta posição, tornando a lista assim: 1 2 3 4 5 6 7 8.

 

Se quer inserir na quarta posição é uma coisa, se quer inserir na ordem é outra.

 

Inserir na posição N 

É trivial, apenas tem o caso especial de a lista não ter ao menos (N-1) elementos. Se posiciona no início, conta os avanços, cria o nó e ajusta os ponteiros. É um exercíçio comum para iniciantes, mas pouco útil. Foi discutido aqui dias atrás.

 

Inserir em ordem

É trivial, mas é mais útil. Em geral o que se faz é usar uma função de comparação para manter a inserção genérica e poder classificar por CPF, por nome, por idade, o que tiver dentro do nó ou puder ser determinado a partir dele.

 

É a técnica usada por exemplo no qsort() em
 

void qsort(
	void *base, size_t nitems, 
	size_t size, 
	int (*compar)(const void *, const void*)
);

 

Eis um protótipo de uma solução em uso aqui:

Lista*      _inserir_na_ordem(void*, Lista*, int(*)(void*, void*));
 

E uma implementação com muitos comentários. No fundo não tem 20 linhas. Pode entender a lógica melhor

 

/*
 aqui a ideia e simples: tenho um elemento 'item'
 para inserir. Mas quero inserir na ordem.
 So que nao sei qual o conteudo entao nao sei qual a ordem.

 Se eu tiver que saber o conteudo entao a lista nao sera mais
 generica e o trabalho nao vai poder ser usado depois sem
 alterar o codigo, compilar e tal

 Logico que nao queremos abrir mao disso porque nao queremos
 mexer mais nesse codigo. Uma lista e uma lista afinal

 A solucao e a simples, usada em todas as bibliotecas e
 sistemas desde os '60. So vai mudando o nome. Hook, CallBack
 sei la

 A funcao f() escrita pelo cara que conhece os items compara dois
 itens e devolve -1, 0 ou 1 conforme o primeiro seja menor
 igual ou maior que o segundo Pronto

Se a funcao veio em branco insere no final e pronto

Queremos manter uma propriedade chamada estabilidade, que ocorre
quando os elementos iguais sao inseridos um depois do outro

*/
Lista*      _inserir_na_ordem(void* item, Lista* l, int(*f)(void*, void*))
{
    if (l == NULL) return l; // sem lista
    if (item == NULL) return l; // sem item
    // se nao veio a funcao insere no fim e pronto
    if (f == NULL)
        return _inserir_no_final(item, l);
    // se nao tinha nada insere no final. Ou no inicio
    if (l->quantos == 0)
        return _inserir_no_final(item, l);
    // entao tem mais gente. o caso comum
    // segue a lista e acha a posicao
    Node* p = l->inicio;
    // agora comparamos os itens
    // p->item e item para inserir, claro, na ordem
    do
    {
        int res = f(item, p->item); // -1,0,1
        // se voltou > 0 a posicao e mais pra frente
        // continua na lista
        if (res > 0)
        {
            p = p->proxima;
            continue;
        };  // if()
        // se voltou 0 insere o item depois de p
        if (res == 0)
            // aqui tem uma pegadinha se for inserir depois do ultimo
            if (p == l->fim)
                l->fim = _inserir_node_depois(item, p);
            else
                p = _inserir_node_depois(item, p);
        else
        {
            // aqui tem uma pegadinha se for inserir antes do primeiro
            if (p == l->inicio)
                l->inicio = _inserir_node_antes(item, p);
            else
                p = _inserir_node_antes(item, p);
        };  // if()
        // agora atualiza a quantidade e retorna
        l->quantos = l->quantos + 1;
        return l;
    } while (p != NULL);
    // se nao retornou ainda e porque esse novo item e o maior
    // de todos entao insere no final
    return _inserir_no_final(item, l);
};  // inserir_na_ordem()

 

 

[jcgs98]

3 horas atrás, arfneto disse:

Sua pergunta é ambígua: você diz que quer inserir na quarta posição, mas sugere que quer também inserir na ordem numérica.
 

 

Se quer inserir na quarta posição é uma coisa, se quer inserir na ordem é outra.

 

Inserir na posição N 

É trivial, apenas tem o caso especial de a lista não ter ao menos (N-1) elementos. Se posiciona no início, conta os avanços, cria o nó e ajusta os ponteiros. É um exercíçio comum para iniciantes, mas pouco útil. Foi discutido aqui dias atrás.

 

Inserir em ordem

É trivial, mas é mais útil. Em geral o que se faz é usar uma função de comparação para manter a inserção genérica e poder classificar por CPF, por nome, por idade, o que tiver dentro do nó ou puder ser determinado a partir dele.

 

É a técnica usada por exemplo no qsort() em
 

void qsort(
	void *base, size_t nitems, 
	size_t size, 
	int (*compar)(const void *, const void*)
);

 

Eis um protótipo de uma solução em uso aqui:

Lista*      _inserir_na_ordem(void*, Lista*, int(*)(void*, void*));
 

E uma implementação com muitos comentários. No fundo não tem 20 linhas. Pode entender a lógica melhor

 

/*
 aqui a ideia e simples: tenho um elemento 'item'
 para inserir. Mas quero inserir na ordem.
 So que nao sei qual o conteudo entao nao sei qual a ordem.

 Se eu tiver que saber o conteudo entao a lista nao sera mais
 generica e o trabalho nao vai poder ser usado depois sem
 alterar o codigo, compilar e tal

 Logico que nao queremos abrir mao disso porque nao queremos
 mexer mais nesse codigo. Uma lista e uma lista afinal

 A solucao e a simples, usada em todas as bibliotecas e
 sistemas desde os '60. So vai mudando o nome. Hook, CallBack
 sei la

 A funcao f() escrita pelo cara que conhece os items compara dois
 itens e devolve -1, 0 ou 1 conforme o primeiro seja menor
 igual ou maior que o segundo Pronto

Se a funcao veio em branco insere no final e pronto

Queremos manter uma propriedade chamada estabilidade, que ocorre
quando os elementos iguais sao inseridos um depois do outro

*/
Lista*      _inserir_na_ordem(void* item, Lista* l, int(*f)(void*, void*))
{
    if (l == NULL) return l; // sem lista
    if (item == NULL) return l; // sem item
    // se nao veio a funcao insere no fim e pronto
    if (f == NULL)
        return _inserir_no_final(item, l);
    // se nao tinha nada insere no final. Ou no inicio
    if (l->quantos == 0)
        return _inserir_no_final(item, l);
    // entao tem mais gente. o caso comum
    // segue a lista e acha a posicao
    Node* p = l->inicio;
    // agora comparamos os itens
    // p->item e item para inserir, claro, na ordem
    do
    {
        int res = f(item, p->item); // -1,0,1
        // se voltou > 0 a posicao e mais pra frente
        // continua na lista
        if (res > 0)
        {
            p = p->proxima;
            continue;
        };  // if()
        // se voltou 0 insere o item depois de p
        if (res == 0)
            // aqui tem uma pegadinha se for inserir depois do ultimo
            if (p == l->fim)
                l->fim = _inserir_node_depois(item, p);
            else
                p = _inserir_node_depois(item, p);
        else
        {
            // aqui tem uma pegadinha se for inserir antes do primeiro
            if (p == l->inicio)
                l->inicio = _inserir_node_antes(item, p);
            else
                p = _inserir_node_antes(item, p);
        };  // if()
        // agora atualiza a quantidade e retorna
        l->quantos = l->quantos + 1;
        return l;
    } while (p != NULL);
    // se nao retornou ainda e porque esse novo item e o maior
    // de todos entao insere no final
    return _inserir_no_final(item, l);
};  // inserir_na_ordem()

 

 

"Sua pergunta é ambígua: você diz que quer inserir na quarta posição, mas sugere que quer também inserir na ordem numérica.
 

 

Se quer inserir na quarta posição é uma coisa, se quer inserir na ordem é outra."

 

1. Aí, tu forçou a barra...momento algum escrevi "BOTAR EM ORDEM"

2. No início eu escrevi "Por exemplo, "...chegou a ver?

3. aiai...

[arfneto]

1 minuto atrás, Comunista.RJ disse:

1. Aí, tu forçou a barra...momento algum escrevi "BOTAR EM ORDEM"

2. No início eu escrevi "Por exemplo, "...chegou a ver?

3. aiai...

 

Você sabe o que é ambiguidade? Um tópico que fala em inserir na ordem o número 4 na quarta posição e a série é 1 2 3 5 6 7 8 não é ambíguo pra você?

 

 

Sério?

 

Você não quer ajuda? Leia o que as pessoas de boa vontade escrevem para te ajudar 

 

Entendeu o código que eu postei?

 

Se quer apenas inserir na posição N, o que é inútil, basta contar os avanços a partir da raiz. E contornar o caso da lista não ter ao menos N-1 elementos.

 

 

[jcgs98]

@arfneto

6 minutos atrás, arfneto disse:

 

Você sabe o que é ambiguidade? Um tópico que fala em inserir na ordem o número 4 na quarta posição e a série é 1 2 3 5 6 7 8 não é ambíguo pra você?

 

 

Sério?

 

Você não quer ajuda? Leia o que as pessoas de boa vontade escrevem para te ajudar 

 

Entendeu o código que eu postei?

 

Se quer apenas inserir na posição N, o que é inútil, basta contar os avanços a partir da raiz. E contornar o caso da lista não ter ao menos N-1 elementos.

 

 

"Você sabe o que é ambiguidade? Um tópico que fala em inserir na ordem o número 4 na quarta posição e a série é 1 2 3 5 6 7 8 não é ambíguo pra você?"
Não... qualquer pessoa teria lido a expressão "por exemplo" e saberia que se tratava apenas de um exemplo!

Ajudar é bem diferente disso aí.

Retiro o convite. Obrigado!

[arfneto]

3 horas atrás, arfneto disse:

Inserir na posição N 

É trivial, apenas tem o caso especial de a lista não ter ao menos (N-1) elementos. Se posiciona no início, conta os avanços, cria o nó e ajusta os ponteiros. É um exercíçio comum para iniciantes, mas pouco útil. Foi discutido aqui dias atrás.

 

4 minutos atrás, Comunista.RJ disse:

Ajudar é bem diferente disso aí.

 

Isso aí é o algoritmo  tarde demais pra eu retirar a ajuda. já expliquei 3 vezes. É só isso. 

 

Mas vou repetir:
 

13 minutos atrás, arfneto disse:

Se quer apenas inserir na posição N, o que é inútil, basta contar os avanços a partir da raiz. E contornar o caso da lista não ter ao menos N-1 elementos