3

Eu precisava trocar dois nós consecutivos ou não numa lista duplamente encadeada, mas eu não consigo. Alguém pode me ajudar? Já até fiz no papel mas não executa. Qual o problema do código?

void swap(no_teste* A, no_teste* B) {

    no_teste* proximoA = A->prox;
    no_teste* anteriorB = B->ant;

    A->prox = B->prox;
    B->ant = A->ant;

    A->ant = anteriorB;
    anteriorB->prox = A;
    B->prox = proximoA;
    proximoA->ant = B;

}

Eu me perco com essa troca de ponteiros, se fosse lista simplesmente encadeada eu conseguiria. Alguém consegue me ajudar?

Essas últimas eu tentei no papel mas não consegui nem usá-las:

void init(no_teste* aA, no_teste* A, no_teste* bA, no_teste* aB, no_teste* B, no_teste* bB) {
    aA = A->ant;
    bA = A->prox;
    aB = B->ant;
    bB = B->prox;
}

void Disconect_Geral_Node(no_teste* aA, no_teste* A, no_teste* bA) {

    aA->prox = NULL;
    A->ant = NULL;
    A->prox = NULL;
    bA->ant = NULL;

}

void Geral_Conect(no_teste* aA, no_teste* B, no_teste* bA) {
    aA->prox = B;
    B->ant = aA;
    B->prox = bA;
    bA->ant = B;
}
1
  • Trocar os ponteiros prox e ant ou trocar o conteúdo basta? Commented 13/12/2017 às 23:39

1 Resposta 1

3

No seu código as alterações ao B->prox e A->ant não estão corretas:

A->ant = anteriorB;
B->prox = proximoA;

Pois o anterior de A vai passar a ser o B, e o próximo de B vai passar a ser o A. Para além disso não precisa das variáveis temporárias se fizer as trocas na ordem correta.

Como primeira abordagem pode fazer assim:

void swap(no_teste* A, no_teste* B) {
    A->ant->prox = B;
    B->prox->ant = A;
    A->prox = B->prox;
    B->ant = A->ant;
    B->prox = A;
    A->ant = B;
}

Nesta versão de swap alterei primeiro anterior ao A e depois o próximo do B e por isso não foi necessário guardar valores em variáveis temporárias.

Esta solução não irá funcionar se a troca for no fim da lista ou no inicio da lista pois A->ant ou B->prox serão NULL, o que irá resultar num segmentation fault. Para resolver temos que testar o NULL antes de alterar:

void swap(no_teste* A, no_teste* B) {
    if (A->ant != NULL){
        A->ant->prox = B;
    }

    if (B->prox != NULL){
        B->prox->ant = A;
    }

    A->prox = B->prox;
    B->ant = A->ant;
    B->prox = A;
    A->ant = B;
}

Agora apesar de não dar erro a troca no inicio da lista também não irá ficar correta pois seria necessário alterar a cabeça da lista, algo que não contemplou no próprio cabeçalho da função:

void swap(no_teste** lista, no_teste* A, no_teste* B) {
    if (A->ant != NULL){
        A->ant->prox = B;
    }
    else {
        *lista = B; //se A->ant é NULL, A é a cabeça e B passa agora a ser a cabeça
    }

    if (B->prox != NULL){
        B->prox->ant = A;
    }

    A->prox = B->prox;
    B->ant = A->ant;
    B->prox = A;
    A->ant = B;
}

Exemplo dos swaps no Ideone

Nos exemplos do ideone utilizei duas funções de mostrar para ser fácil de ver que tanto os ponteiros ant como prox estão corretos.

Também considerei que era uma lista duplamente ligada não circular.

Você deve fazer log-in para responder a esta pergunta.

Esta não é a resposta que você está procurando? Pesquise outras perguntas com a tag .