Concatenation of two chained lists in C

Question

Concatenation of two chained lists in C

Asked 9 years, 2 months ago

Viewed 1,882 times

1

Given the TAD LISTA_ENC_NC_ORD, need to implement an operation that takes two lists and returns a list resulting from the concatenation of them, and that cannot have elements with the same value.

Here the TAD:

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

It is chained, ordered crescently and has a header node (the node is a NODE too, but its inf field is the number of elements in the list, and its next 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’t do it at all ^^

What have you tried? What specific problem are you having? With more information it is possible to help without going out doing all the homework for you. :)

– hugomg

2015/05/02 at 21:44
Returning to the subject, given that the lists are ordered, I got the impression that the operation you want to implement is more "merge" than for a concatenation. And I must confess that it is very strange this scheme of storing the size of the list in the first element.

– hugomg

2015/05/02 at 21:46
my problem is I didn’t know what to do so the list wouldn’t have repeated elements

– poirot

2015/05/02 at 22:00
this size storage scheme is so you don’t have to go through the entire list to find the number of elements

– poirot

2015/05/02 at 22:01
1

The reason I find it odd is that, unlike vectors, linked lists don’t need to know their own size to do most things. And storing the number of elements within the list itself makes it super easy for you to make a mistake and treat the number of elements as if it were an element itself. One way to mitigate this problem would be to store the metadata in a second type of data instead of putting it "in-band".

– hugomg

2015/05/02 at 22:07
For insertion, query and removal operations I use to know if the position in which the user wants to insert, query or remove is valid.

– poirot

2015/05/02 at 22:13
If the list is sorted, it makes no sense for the user to pass a position. And even if you did, inserting things in the middle of a linked list is not efficient because you have to go through the list all the time.

– hugomg

2015/05/02 at 23:48
Yes, on an orderly list it doesn’t make any sense at all. The teacher just wanted to complicate.

– poirot

2015/05/05 at 18:47

Show 3 more comments

1 answer

Browser other questions tagged c

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

by Marcelo Shiniti Uchimura • **3,302** points · Answer 1 · 2015-05-02T21:54:48+00:00

If the lists could have repeated values, simply scan one list and then the other, inserting the elements in the new list. As nay can have repeated elements, you scan one of the lists and each element scans the other list completely, checking for repetition. If there is any, pula to the next element of the first list, without inserting it, until the list is finished. Once finished, the second list is scanned, inserting all her elements in the new list.

I will consider the following prototype for list creation:

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;
}