How to create a function that merges elements from two double-chained circular lists

Question

How to create a function that merges elements from two double-chained circular lists

Navigation

#1 by (1 votes)

1

Well, I would like a hint of how I create the function that gets list1 and list2 and returns a third list with the interleaved elements of list 1 and 2, what would be the logic? my code is like this ...

#include <stdio.h>
#include <stdlib.h>
#define true 1;
#define false 0;


typedef struct _nodo{
    int data;
    struct _nodo *next;
    struct _nodo *prev;
}nodo;


typedef struct _lista{
    nodo *head;
}lista;


lista *criaLista(){
    lista *l = (lista*)malloc(sizeof(lista));
    if (l != NULL){
        l->head = NULL;
        return l;
    }
    return NULL;
}


nodo *criaNodo(int data){
    nodo *n = (nodo*)malloc(sizeof(nodo));
    if (n != NULL){
        n->data = data;
        n->next = NULL;
        n->prev = NULL;
        return n;
    }
    return NULL;
}


int inserirFim(lista *l, int data){
    if (l != NULL){
        nodo *n = criaNodo(data);
        if (l->head == NULL){
            l->head = n;
            n->next = n->prev = n;
            return true;
        }
        else{
            nodo *last = l->head->prev;
            n->next = last->next;
            l->head->prev = n;
            n->prev = last;
            last->next = n;
            return true;
        }
    }
}


void display(lista *l){
    if (l != NULL && l->head != NULL){
        nodo *temp = l->head;
        while (temp->next != l->head){
            printf("%d ", temp->data);
            temp = temp->next;
        }
        printf("%d ", temp->data);
    }
}


lista *intersecao(lista *l, lista *l1){
    if (l != NULL && l->head != NULL && l1 != NULL && l1->head != NULL){
        lista *l2 = criaLista();
        nodo *temp = l->head;
        nodo *temp1 = l1->head;
        while (temp->next != l->head){
            while (temp1->next != l1->head){
                if (temp->data == temp1->data)
                    inserirFim(l2, temp->data);
                temp1 = temp1->next;
            }
            temp = temp->next;
            temp1 = l1->head;
        }
        if (temp->data == temp1->prev->data)
            inserirFim(l2, temp->data);
        return l2;
    }
}


int main()
{
        //desconsidera a main, era só pra testar se tava funcionando.
        // por isso ja inserir os numeros ordenados

    lista *l = criaLista();
    lista *l1 = criaLista();

    inserirFim(l, 100);
    inserirFim(l, 90);
    inserirFim(l, 80);
    inserirFim(l, 70);
    inserirFim(l, 60);
    inserirFim(l, 50);
    inserirFim(l, 40);

    inserirFim(l1, 100);
    inserirFim(l1, 70);
    inserirFim(l1, 50);
    inserirFim(l1, 40);

    lista *l3 = intersecao(l1, l);

    display(l3);

    printf("\n\n");
    system("pause");
    return 0;
}

c

asked by anonymous 02.08.2017 / 06:38

1 answer

Transfer files from server to client ?? [closed] Compare explode array with select option text

score 1 · Answer 1

We should never ignore compiler warnings, which help us understand potential code problems. Starting with these we see that return is missing in some functions, such as inserirFim and intersecao , which if they do not enter if has no return.

Example:

int inserirFim(lista *l, int data){
    if (l != NULL){
        ...
        if (l->head == NULL){
            ...
            return true;
        }
        else{
            ...
            return true;
        }
    }
    return false; //faltava retorno aqui, se não entrar no if não tem valor de retorno!
}

As for intersecao , the problem is in the two cycles, which do not give correct navigation, nor does it include lists of different sizes. For this you can change the function to look like this:

lista *intersecao(lista *l, lista *l1){
    if (l != NULL && l->head != NULL && l1 != NULL && l1->head != NULL){
        lista *l2 = criaLista();
        nodo *temp = l->head->next; //começa no segundo para simplificar o ciclo
        nodo *temp1 = l1->head->next; //começa no segundo para simplificar o ciclo

        //escreve os dois primeiros diretamente ja que começa no segundo
        inserirFim(l2, l->head->data);
        inserirFim(l2, l1->head->data);

        //enquanto uma das listas não chega ao fim escreve um elemento de cada
        while (temp != l->head && temp1 != l1->head){
            inserirFim(l2, temp->data);
            inserirFim(l2, temp1->data);
            temp = temp->next;
            temp1 = temp1->next;
        }

        //se a primeira lista chegou ao fim vai continuar com a segunda, caso contrario
        //vai continuar com a primeira
        if (temp == l->head) {
            temp = temp1;
            l = l1;
        }

        //continuar com os elementos da lista maior
        while (temp != l->head){
            inserirFim(l2, temp->data);
            temp = temp->next;
        }

        return l2; //retornar a nova lista
    }

    return NULL; //estava em falta também este retorno
}

Also inserirFim can be simplified to:

int inserirFim(lista *l, int data){
    if (l == NULL) return false; //o teste de lista NULL logo aqui no topo

    nodo *n = criaNodo(data);

    if (l->head == NULL){
        l->head = n;
        n->next = n->prev = n;
    }
    else{ //sem ponteiro auxiliar last, que é basicamente l->head->prev
        n->next = l->head;
        n->prev = l->head->prev;
        l->head->prev->next = n;
        l->head->prev = n;
    }
    return true; //retorno true so uma vez
}

Example working on Ideone

As an additional note, the #define should not contain ; although some compilers will allow it.