Concatenation of two lists chained in C

Question

Concatenation of two lists chained in C

Navigation

#1 by (1 votes)

1

Given the TAD LIST_ENC_NC_ORD , I need to implement an operation that takes two lists and returns a list resulting from their concatenation, and can not have elements of same value.

Here the TAD:

typedef struct nodo
{
    int inf;
    struct nodo * next;
}NODO;
typedef NODO * LISTA_ENC_NC_ORD;

It is chained, ordered incrementally, and has a header node (the node is a NODO too, but the inf field is the number of elements in the list, and the next one is the first element). >

The operation:

LISTA_ENC_NC_ORD concatenar (LISTA_ENC_NC_ORD l1, LISTA_ENC_NC_ORD l2)

Insert operation:

void ins (LISTA_ENC_NC_ORD l, int val)
{
    NODO *novo, *aux;
    novo=(NODO *)malloc(sizeof(NODO));
if (!novo)
{
    printf ("erro! memoria insuficiente");
    exit(2);
}

for (aux=l; aux->next!=NULL && val>(aux->next)->inf; aux=aux->next);
novo->inf = val;
novo->next = aux->next;
aux->next = novo;
l->inf++;
}

I can not do it at all, if someone helps me I'll be very grateful ^^

c

asked by anonymous 02.05.2015 / 22:44

1 answer

JavaScript - Return image dimensions Simulate mouse click

score 1 · Accepted Answer

If lists could have repeated values, you would simply scan one list and then another by inserting the elements in the new list. Since no can have repeated elements, you scan one of the lists and each element scans the other list completely, checking for repetition. If one exists, jump to the next element in the first list, without inserting it, until the list is finished. Once it is finished, the second list is scanned, inserting all elements in the new list.

I'll consider the following prototype for list building:

LISTA_ENC_NC_ORD criar();

The following code is an attempt to resolve the exercise:

#define TRUE  1
#define FALSE 0

LISTA_ENC_NC_ORD concatenar(LISTA_ENC_NC_ORD l1, LISTA_ENC_NC_ORD l2)
{
    LISTA_ENC_NC_ORD nova;
    LISTA_ENC_NC_ORD v;
    LISTA_ENC_NC_ORD w;
    int pode_inserir;

    // criando a lista nova que sera retornada
    nova = criar();

    // laco para varrer a primeira lista
    for (v = l1; v != NULL; v = v->next)
    {
        pode_inserir = TRUE;

        // varrendo a segunda lista em busca de elementos comuns
        for (w = l2; w != NULL; w = w->next)
        {
            if (v->inf == w->inf)
            {
                // nao pode inserir
                pode_inserir = FALSE;
                break;
            }
        }

        if (pode_inserir)
        {
            ins(nova, v->inf);
        }
    }

    // laco para varrer a segunda lista,
    // inserindo todos os elementos da lista 2 na lista nova
    for (w = l2; w != NULL; w = w->next)
    {
        ins(nova, w->inf);
    }

    // fim de operacao, retorna o valor desejado
    return nova;
}