1

Bom, gostaria de uma dica de como crio a função que recebe lista1 e lista2 e retorna uma terceira lista com os elementos intercalados da lista 1 e 2, qual seria a logica? o meu codigo esta assim...

#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;
}
2
  • A lógica seria algo assim: 1. Fazer uma função POP (remover da lista), 2. Fazer uma outra função que recebe 2 listas por parâmetro e enquanto as listas tiverem elemento(s), vc faz o POP (retornando um nodo) e implementando o nodo numa terceira lista, que seria a junção das outras duas. Commented 2/08/2017 às 14:02
  • 1
    Muito obrigado.
    – user86552
    Commented 2/08/2017 às 16:27

1 Resposta 1

1

Nunca devemos ignorar os avisos do compilador, que nos ajudam o perceber potenciais problemas no código. Começando por esses vemos que falta return em algumas funções, tais como no inserirFim e no intersecao que se não entrarem nos if não tem nenhum retorno.

Exemplo:

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

Quanto á intersecao o problema está nos dois ciclos, que não dão a navegação correta, assim como não contempla listas de tamanhos diferentes. Para isso pode-se alterar a função para ficar assim:

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
}

Também o inserirFim pode ser simplificado para:

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
}

Exemplo a funcionar no Ideone

Como nota adicional o #define não deve levar ; embora alguns compiladores o permitam.

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