How to concatenate two chained lists?

Asked

Viewed 4,088 times

1

I created this code by initializing a list, but I need to improve it, creating a function that concatenates two and at the end prints the value of the two concatenates... Yeah, I don’t know how.

Suggested Prototype: no *concatena(no * inicio1, no * inicio2);

Parameters: Pointer to the beginning of the 1st. list (which can be NULL) and pointer to the beginning of the 2nd. list (which can be NULL).

Return: Pointer to the beginning of the list resulting from concatenation

 //Lista encadeada Simples
//Imprimindo a lista

#include <iostream>
using namespace std;

struct No {
    //Variavel Valor
    int valor;
    //Ponteiro para o próximo Nó
    No * ptr;
};
No * inserirInicio(No * lista, int num);

void imprimir(No * lista);
main(){
    //Declara e inicializa a LIsta
    //O Ponteiro chamado de LISTA e é NULO/Vazio
    No * lista = NULL;
    //Recebera as alterações feitas com a função abaixo

    lista = inserirInicio(lista, 10);
    lista = inserirInicio(lista, 20);
    lista = inserirInicio(lista, 30);
    lista = inserirInicio(lista, 40);
    lista = inserirInicio(lista, 50);
    imprimir(lista);


}

No * inserirInicio(No * lista, int num)
{
        //Variavel temporária
        No * tmp;
        //Se esta vazia Eu crio o elemento e aponto a lista para Ele
        //Aponta para o nov nó
        tmp = new No;
        //Configurando o novo valor
        //Guardo na variavel NUM
        tmp -> valor = num;
        //Apontar para o primeiro cara
        tmp -> ptr = lista;
        lista = tmp;
        //Retorna o novo inicio da lista
        return lista;
    }

//Imprimindo os valores
void imprimir(No * lista)
{
    No * atual;
    atual = lista;//atual aponta para lista
    while(atual!= NULL)
    {
        cout << atual -> valor << endl;
        atual = atual -> ptr;
    }
}
c++

  • Because you do not try to do the following creates a function in which you receive both list.In the code you could make the following use your print function only you will have to increase the variables and I think if you leave with one it will be better

  • @user3652472 I’ve thought of all this, but I’m new even in programming, I can’t perform the practical part.

  • In theory, your pointer will never be null. It will only point to p + sizeof(p) in an iteration, which is "valid". You need to know where the end of the list is to do this.

2 answers

1


Concatenation between two lists has a very simple and very interesting solution, which is a property of the list type itself:

To do so, one must first take into account these properties: each No keeps only one pointer for the next item in the list, not the previous one. This therefore means that the last one No of a list does not point to No some (and, in the case of your program, the last No in itself is null). Second, concatenating, by definition, is the union of two sets by their ends. In this case, the end of inicio1 and the beginning of inicio2 in function No *concatena(No * inicio1, No * inicio2);.

Therefore, to realize the concatenation, you must look for the last No of inicio1 and inserí-lo ao início of inicio2.

For example:

No *concatena(No * inicio1, No * inicio2){
    No* fim = NULL;
    No* iterador = inicio1;
    while(iterador->ptr != NULL){
        iterador = iterador->ptr;
    }
    iterador = inserirInicio(inicio2, iterador->valor);
}

-2

Lista* concatList(Lista* a, Lista* b){

    Lista* temp = b;
    while(temp != NULL){
        a = inserirFim(a, temp->item);
        temp = temp->prox;
    }
    return a;
}

Browser other questions tagged c++

You are not signed in. Login or sign up in order to post.