Estrutura de Dados 2 - Listas Duplamente

/*#########################################
*                                         *
*    NOME: MARCIO HENRIQUE LIMA OLIVEIRA  *
*                                         *
*    CURSO: ENGENHARIA DA COMPUTACAO      *
*    4° PERIODO - NOTURNO                *
*                                         *
*    MATERIA: ESTRUTURA DE DADOS 2        *
*    PROF(a): Edna Y. S.                  *
*                                         *
*#########################################*/

// EXERCICIO A ) INSERIR NO FIM DA LISTA

void insereFim(int x, listadup *inicio, listadup *fim){
    listadup novo;

    if(inicio == NULL) return;//lista existe?
    if((*inicio) == NULL){//lista vazia?
        return;
    }else{
        novo = getNode();

        if(novo == NULL){//não alocou memoria
            printf("\nnoh nao pode ser alocado\n");
            system("pause");
            return;
        }else{//recebeu um endereço valido de memoria
            novo -> info = x;
            novo -> prox = NULL;
            (*fim) -> prox = novo;
            novo -> ant = *fim;
            *fim = novo;
        }
    }
    return;
}

// EXERCICIO B ) CONCATENAR 2 LISTAS

void concatenaLista(listadup *inicio, listadup *fim, listadup *inicio1, listadup *fim1){

    //fazer as verificações

    listadup aux;
    aux = *inicio;

    while(aux != NULL){
        aux = aux -> prox;
    }

    aux -> prox = *inicio1;
    free(inicio1);
    *fim = *fim1;
    free(fim1);

    return;
}


// EXERCICIO C ) LIBERAR TODOS OS NOHS DE UMA LISTA

void liberaLista(listadup *inicio){
    if(inicio == NULL){
        printf("\nLista Vazia\n");
        system("pause");
    }else{

        listadup aux;

        while((*inicio) != NULL){
            aux = *inicio;
            *inicio = (*inicio) -> prox;
            free(aux);
        }
        *fim = *inicio;
    }
    return;
}

// EXERCICIO D) INVERTER LISTA
void inverteLista(listadup *inicio, listadup *fim, listadup *inicio1, listadup *fim1){

    if(inicio == NULL) return; //lista nao existe nao existe endereço de inicio
    if((*inicio) == NULL) return; // não existe nada sendo apontado para o inicio

    while((*inicio) != NULL){
        insereFim((*inicio) -> info,inicio1,fim1);
        *inicio = (*inicio) -> prox;
    }

    *fim = *inicio;

    return;
}

// EXERCICIO E ) REMOVER ULTIMO ELEMENTO DA LISTA

void removerUltimo(listadup *inicio)
{
    listadup aux;

    if(inicio == NULL) return; //lista existe?
    if((*inicio) == NULL) return;//lista vazia?

    aux = *inicio;

    while(aux -> prox == NULL){//enquanto existir mais elementos na lista
        aux = aux -> prox;
    }

    if(aux -> ant == NULL){//é o primeiro noh?
        *inicio = aux -> prox;//vou apontar o inicio para o prox, que na vdd é o NULL
    }else{
        aux -> ant -> prox = NULL;//se nao for o primeiro noh,
    }

    free(aux);
    return;
}

// EXERCICIO F ) REMOVER ENESIMO ELEMENTO DA LISTA

void removerQualquer(int x, listadup *inicio){
    listadup aux;

    if(inicio == NULL) return; //lista existe?
    if((*inicio) == NULL) return;//lista vazia?

    aux = *inicio;

    while(aux != NULL && aux -> info != x){//enquanto nao encontrar o elemento
        aux = aux -> prox;//caminho na lista até bater na regra
    }

    if(aux == NULL){//leu toda lista e chegou em null
        printf("Elemento nao encontrado\n");
        return;
    }
    if(aux -> ant == NULL{//eh o primeiro elemento?
        *inicio = aux -> prox;
    }else{//tem mais de um elemento?
        aux -> ant -> prox = aux -> prox;
    }

    if(aux -> prox != NULL){
        aux -> prox -> ant = aux -> ant;
    }

    free(aux);
    return;
}

// EXERCICIO G ) COMBINAR LISTAS

void combinarListas(listadup inicio, listadup inicio1, listadup inicio2, listadup *inicio2, listadup *fim2){
    //considerando ja que as 2 listas estao ordenadas

    inicio2 = inicio;

    listadup aux = inicio;

    while(aux != NULL){
        aux = aux -> prox;
    }

    aux -> ant -> prox = inicio1;
    fim = fim1;
    fim2 = fim;

    return;
}

// EXERCICIO H ) UNIAO DOS ELEMENTOS DE DUAS LISTAS

void uniaoListas(listadup inicio, listadup inicio2, listadup *inicio3, listadup *fim3){

    listadup aux = *inicio;
    listadup aux2 = *inicio2;

    *inicio3 = concatenaLista()

    exibeLista(inicio);
    exibeLista(inicio2);
    exibeLista(inicio3);
}

// EXERCICIO I ) INTERSECCAO DOS ELEMENTOS DE DUAS LISTAS

void interseccaoListas(listadup inicio, listadup inicio2, listadup *inicio3, listadup *fim3){

    listadup aux = *inicio;
    listadup aux2 = *inicio2;

    while(aux != NULL){
        while(aux2 != NULL){
            if(aux -> info != aux2 -> info){
                if((*inicio3) == NULL){
                    insereInicio(aux->info,inicio3,fim3);
                }else{
                    insereFim(aux->info,inicio3,fim3);
                }
            }else{
                aux2 = aux2 -> prox;
            }
        }
        aux = aux -> prox;
    }

    printf("\n");
    exibeLista(inicio);
    printf("\n");
    exibeLista(inicio2);
    printf("\n");
    exibeLista(inicio3);
    printf("\n");

    return;
}

// EXERCICIO J ) INSERIR ELEMENTO APOS ENESIMO TERMO

void insereApos(int x, int y, listadup *inicio, listadup *fim)
{
    listadup novo,aux,aux2;

    if((*inicio) == NULL){
        printf("Lista Vazia\n");
        system("pause");
    }else{
        if((*fim) -> info == y ){
            insereFim(x,inicio,fim);
        }else{
            aux = *inicio;
            while(aux != NULL && aux -> info != y){
                aux = aux -> prox;
            }
            if(aux == NULL){
                printf("Elemento nao encontrado\n");
                system("pause");
            }else{
                novo = getNode();
                if(novo == NULL){
                    printf("noh nao alocado\n");
                    system("pause");
                }else{
                    novo -> info = x;
                    novo -> ant = aux;
                    novo -> prox = aux -> prox;
                    aux -> prox = novo;
                    aux -> prox -> ant = novo
                }
            }
        }
    }
    return;
}

// EXERCICIO K ) REMOVER CADA SEGUNDO ELEMENTO

void segundoE(listadup *inicio, listadup *fim){

    if(inicio == NULL) return; //lista existe?
    if((*inicio) == NULL) return;//lista vazia?

    listadup aux,aux2;
    aux = *inicio;

    int x = 0;

    while(aux -> prox != NULL){
        if(x % 2 == 0){
            aux2 = aux -> prox;
            aux -> prox = aux2 -> prox;
            aux -> prox -> ant = aux2 -> ant;
            free(aux2);
        }else{
            aux = aux -> prox;
        }
        x++;
    }
    *fim = aux;
    return;
}

// EXERCICIO L ) ORDENAR ASCENDENTE

void ordena(listadup *inicio){

    if(inicio == NULL) return; //lista existe?
    if((*inicio) == NULL) return;//lista vazia?

    int x;

    listadup aux;

    aux = (*inicio) -> prox;

    for (inicio; inicio -> prox != NULL; *inicio = (*inicio) -> prox){
        for (aux; aux != NULL; aux = aux -> prox){
            if ((*inicio) -> info > aux -> info){
                x = (*inicio) -> info;
                (*inicio) -> info = aux -> info;
                aux -> info = x;
            }
        }
    }
    return;
}

// EXERCICIO M ) RETORNAR A SOMA DOS ELEMENTOS

void somaL(listadup inicio){
    if(inicio == NULL) return;//lista existe?
    if((*inicio) == NULL) return;//lista vazia?

    int s = 0;

    listadup aux = *inicio;

    while(aux != NULL){
        s += aux->info;
        aux = aux-> prox;
    }

    system("pause");
    system("cls");
    return s;
}

// EXERCICIO N ) EXIBE OS ELEMENTOS DE UMA LISTA

void exibeLista(listadup inicio, listadup fim){

    if(inicio == NULL) return; //lista existe?
    if((*inicio) == NULL) return;//lista vazia?

    int opt;

    aux = inicio;
    aux2 = fim;

    printf("\n[1] - Deseja exibir apartir do Inicio\n[2] - Deseja exibir apartir do fim?:");
    scanf("%d",&opt);

    switch(opt){
        case 1:
            while(aux != NULL){
                printf("[%d] ",aux -> info);
                aux = aux -> prox;
            }
            system("pause");
            break;
        case 2:
            while(aux2 != NULL){
                printf("[%d] ",aux -> info);
                aux2 = aux2 -> ant;
            }
            system("pause");
            break;
        default:
            printf("\nPor favor, escolha uma opcao valida.\n");
            break;
    }
    return;
}

// EXERCICIO N ) RETORNAR O NUMERO DE ELEMENTOS DE UMA LISTA

int exibeTam(listadup inicio){

    if(inicio == NULL) return; //lista existe?
    if((*inicio) == NULL) return;//lista vazia?

    listadup aux = *inicio;

    while ((*inicio) != NULL){
        i++;
        *inicio = (*inicio) -> prox;
    }

    return i;
}

// EXERCICIO O ) MOVE UM NOH (N) TERMOS A FRENTE

void moveLista(listadup *inicio){
    int x,y,opt;
    listadup aux,novo;

    if(inicio == NULL) return;//lista existe? Existe endereço de memoria da lista?
    if((*inicio) == NULL) return;//lista vazia? Inicio aponta para algum noh?

    exibeLista(inicio);

    printf("\nQual elemento deseja Mover: ");
    scanf("%d",&x);

    //usuario informa qual elemento ele quer mover
    //removo o noh, e insiro de acordo com que o usuario quiser
    removerQualquer(x,inicio);

    printf("\nDeseja inserir\n[1] - Antes\n[2] - Apos?: ");
    scanf("%d",&opt);

    switch(opt){
        case 1:
            printf("\nDeseja inserir antes de que elemento?: ");
            scanf("%d",&y);
            insereAntes(x,y,inicio,fim);
            break;
        case 2:
            printf("\nDeseja inserir Apos que elemento?: ");
            scanf("%d",&y);
            insereApos(x,y,inicio,fim);
            break;
        default:
            printf("\n[+] Opcao Invalida, por favor, escolha uma opcao\n");
            break;
    }

    exibeLista(inicio);
    return;
}

// EXERCICIO P) CRIAR COPIA DE UMA LISTA

void criaCP(listadup inicio, listadup *inicioCP, listadup *fimCP)
{
    listadup aux;

    if(inicio == NULL) return;//lista existe?
    if((*inicio) == NULL) return;//lista vazia?

    aux = *inicio;

    while(aux != NULL){
        if(inicioCP == NULL){
            insereInicio(aux->info,inicioCP);
        }else{
            insereFim(aux->info,inicioCP,fimCP);
        }
        aux = aux -> prox;
    }
    return;
}