EDD 202009925 - LLS Insercción Eliminación Búsqueda y recursividad

#include <iostream>

/**
¿qué haremos hoy?
- Revisaremos:
    - retornar la cantidad de nodos que tiene una lista
    - retornar la suma de los nodos
  resumen: profesor
- Tarea: mostrar sólo los elementos impares



- función insertarAlInicio (esta es la forma fácil)
- función insertarAlFinal (tenemos que recorrer hasta el nodo final)
- Eliminar el primer nodo (fácil)
- Eliminar el último nodo (fácil)
- Eliminar nodo X

--Ejercicios: Crear función mayorElemento de la lista
--Contar si el primer dígito es igual a K
--retornar el mayor elemento
--retornar el menor elemento INT_MAX
**/
using namespace std;

//como construir un nodo
struct Nodo {
    int info;
    struct Nodo *link;
};
//Lista es un tipo de variable de tipo puntero
typedef Nodo *Lista;

//función que muestra una lista
void mostrarLista(Lista aux){
    cout <<"Mostrando lista"<<endl;
    while(aux != NULL) {
        cout << "valor: "<< aux->info<<endl;
        aux = aux->link;
    }
}

int cantidadNodos(Lista aux){
    int cantidad = 0;
    while(aux != NULL) {
        cantidad ++;
        aux = aux->link;
    }
    return cantidad;
}

int sumarNodos(Lista aux){
    int suma = 0;
    while(aux != NULL) {
        suma += aux->info;
        aux = aux->link;
    }
    return suma;
}

void mostrarImpares(Lista aux){
    cout <<"Mostrando Impares"<<endl;
    while(aux != NULL) {
        if(aux->info % 2 == 1)
            cout << "valor: "<< aux->info<<endl;
        aux = aux->link;
    }
}



void insertarAlInicio(Lista &l, int valor) {
    Lista nuevoNodo = new(Nodo);
    nuevoNodo->info = valor;
    nuevoNodo->link = l;
    l = nuevoNodo;
}

void insertarAlFinal2(Lista &l, int valor) {
    //1 creamos el nuevo nodo
    Lista nuevoNodo = new(Nodo);
    nuevoNodo->info = valor;
    nuevoNodo->link = NULL;
    //caso particular l es null
    if(l == NULL)
        l = nuevoNodo;

    else //si sólo tiene un nodo
        if(l->link == NULL)
            l->link = nuevoNodo;
    else {
        Lista aux = l;
        //recorremos hasta el final
        while (aux->link != NULL)
            aux = aux->link;

        aux->link = nuevoNodo;
    }
}


void insertarAlFinal(Lista &l, int valor) {
    //1 creamos el nuevo nodo
    Lista nuevoNodo = new(Nodo);
    nuevoNodo->info = valor;
    nuevoNodo->link = NULL;
    //caso particular l es null
    if(l == NULL)
        l = nuevoNodo;

    else {
        Lista aux = l;
        //recorremos hasta el final
        /***recorro a->link, para saber si es el ultimo elemento de la lista **/
        /**Si lo hago con aux != NULL, sólo llegaré al último nodo**/
        while (aux->link != NULL)
            aux = aux->link;

        aux->link = nuevoNodo;
    }
}

//insertar un nodo según posicion (se podría considerar como un indice)
void insertarNodoOrdenado(Lista &l, int valor){
    //preparamos el nodo
    Lista nuevoNodo = new(Nodo);
    nuevoNodo->info = valor;
    nuevoNodo->link = NULL;

    //Si la lista es vacia
    if(l == NULL) {
        l = nuevoNodo;

    } else if(l->info >= valor) { //revisamos el primer caso
            nuevoNodo->link = l;
            l = nuevoNodo;
    } else {
        Lista aux = l;
        Lista siguiente = l;
        while(aux->link != NULL){
            siguiente = aux->link;
            if(siguiente != NULL && siguiente->info >= valor) {
                aux->link = nuevoNodo;
                nuevoNodo->link = siguiente;
                break; //termina la ejecución
            }
            aux=aux->link;
        }
        //si no lo encontró lo agregamos al final
        aux->link = nuevoNodo;
    }
}

//Eliminar ultimo nodo
void eliminarPrimerNodo(Lista &p) {
    if(p != NULL) {
        Lista nodoEliminar = p;
        p = p->link;
        delete(nodoEliminar);
    }
}

//eliminar el último nodo
void eliminarUltimoNodo(Lista &l){
    if(l == NULL)
        return ;

    if (l->link == NULL) {//caso particular sólo 1 nodo
        cout <<"[x]"<< l->info<<endl;
        delete(l);
        l = NULL;
        return;
    } else { //tiene por lo menos un nodo
        //vamos hasta el último
        Lista aux = l;
        Lista penultimo = l;
        while(aux->link != NULL) {
            penultimo = aux;
            aux= aux->link;
        }
        //aux tiene el último nodo
        cout <<"[x]"<< aux->info<<endl;
        delete (aux);
        penultimo->link = NULL;
    }
}

void eliminarNodoIgualaK(Lista &l, int k){
    if(l == NULL)
        return ;

    //revisamos el primer elemento
    if (l != NULL && l->info == k) {//caso particular sólo 1 nodo
        cout <<"Eliminó el primero igual a "<<l->info<<endl;
        Lista nodoEliminar = l;
        l = l->link;
        delete(nodoEliminar);
        return ;
    } else { //tiene por lo menos un nodo
        //vamos hasta el último
        Lista aux = l;
        Lista siguiente = l;
        while(aux != NULL) {
            siguiente = aux->link;
            cout <<"\t Revisando "<<aux->info<<endl;
            if(siguiente != NULL && siguiente->info == k){
                cout <<"Eliminó el primero igual a "<<aux->info<<endl;
                Lista nodoEliminar = siguiente;
                aux->link = siguiente->link;
                delete(nodoEliminar);
                //break;
            }
            aux= aux->link;
        }
    }
}

void ordenarListaPorBurbuja(Lista &L) {
    Lista actual    = L;
    Lista siguiente = L;

    while (actual != NULL) {
        siguiente =  actual->link;
        while (siguiente != NULL) {
            if(actual->info > siguiente->info) {
                int temp        = siguiente->info;
                siguiente->info = actual->info;
                actual->info    = temp;
            }
            // *siguiente elemento **
            siguiente = siguiente->link;
        }
        actual = actual->link;
    }
}

///recursividad
void mostrarR(Lista l){
    if(l == NULL)
        return;
    cout <<l->info << endl;
    mostrarR(l->link);
}

void mostrarRecursivoInverso(Lista l){
    if(l == NULL)
        return;

    mostrarRecursivoInverso(l->link);
    cout <<l->info << endl;
}

int contarR(Lista l){
    if(l == NULL)
        return 0;
    return 1 + contarR(l->link);
}

int sumarR(Lista l){
    if(l == NULL)
        return 0;
    return l->info + sumarR(l->link);
}

#include <climits>
int mayorR(Lista l) {
    if(l == NULL)
        return INT_MIN;
    int mayor = mayorR(l->link);
    if(l->info > mayor)
        return l->info;
    else
        return mayor;
}

int promedioR(Lista l, int suma, int cantidad) {
    if(l == NULL) {
        if(cantidad > 0)
            return suma / cantidad;
        else {
            cout << "error div X";
            return -1;
        }
    }
    else {
        //si colocamos ++ delante de la variable, realiza la suma antes de la llamada
        promedioR(l->link, suma + l->info, ++cantidad);
    }
} //cout <<promedioR(L, 0,0);

void agregarR(Lista &l, int valor){
    if(l == NULL) {
        Lista nuevoNodo = new(Nodo);
        nuevoNodo->info = valor;
        nuevoNodo->link = NULL;
        l = nuevoNodo;
    } else {
        agregarR(l->link, valor);
    }
}

int main()
{
    /** ¿Porqué es importante inicializar la variable con NULL? **/
    Lista L = NULL;

    //insertamos
    insertarAlInicio(L, 1);
    insertarAlInicio(L, 2);
    insertarAlInicio(L, 3);
    for(int i=0;i<rand()%20; i++)
        insertarAlInicio(L, rand()%100);

    cout << "LLS: lista lineal simple" << endl;
    mostrarLista(L);
    mostrarImpares(L);
    cout <<"Sumar Nodos:"<<sumarNodos(L)<<endl;
    cout <<"Contar Nodos:"<<cantidadNodos(L)<<endl;
    /**ejercicios:
    - retornar la cantidad de nodos que tiene una lista
    - retornar la suma de los nodos
    */

    Lista L2 = NULL;
    for(int i=0;i<10; i++)
        insertarAlFinal(L2, i);
    mostrarLista(L2);

    //Insertar Nodo Ordenado o en posición X
    Lista L3 = NULL;
    insertarNodoOrdenado(L3, 7);
    cout <<"mostrar Ordenado 7"<<endl;;
    mostrarLista(L3);
    insertarNodoOrdenado(L3, 3);
    insertarNodoOrdenado(L3, 15);
    insertarNodoOrdenado(L3, 8);
    insertarNodoOrdenado(L3, 2);
    insertarNodoOrdenado(L3, 20);
    insertarNodoOrdenado(L3, 1);
    cout <<"mostrar Ordenado "<<endl;;
    mostrarLista(L3);

    cout <<"Eliminamos dos primeros nodos";
    eliminarPrimerNodo(L2);
    eliminarPrimerNodo(L2);
    mostrarLista(L2);
    cout <<"Eliminamos dos ultimos nodos"<<endl;
    eliminarUltimoNodo(L2);
    cout <<endl<<"eliminado otra vez "<<endl;
    eliminarUltimoNodo(L2);
    mostrarLista(L2);
    cout <<endl<<"eliminado igual a K = 5 "<<endl;
    eliminarNodoIgualaK(L2, 5);
    cout <<endl<<"eliminado igual a K = 2 "<<endl;
    eliminarNodoIgualaK(L2, 2);
    mostrarLista(L2);

    Lista L4 = NULL;
    insertarAlFinal(L4, 17);
    insertarAlFinal(L4, 4);
    insertarAlFinal(L4, 24);
    insertarAlFinal(L4, 2);
    insertarAlFinal(L4, 1);
    cout <<endl<<"L4 Antes de Ordenar "<<endl;
    mostrarLista(L4);
    ordenarListaPorBurbuja(L4);
    cout <<endl<<"L4 Después de Ordenar "<<endl;
    mostrarLista(L4);

    cout <<"recursividad"<<endl;
    Lista L5 = NULL;
    agregarR(L5, 1);
    agregarR(L5, 2);
    agregarR(L5, 3);
    agregarR(L5, 4);
    cout <<"Mostrar"<<endl;
    mostrarR(L5);
    cout <<"Mostrar"<<endl;
    mostrarR(L5);

    cout <<"Promedio: "<<promedioR(L5, 0, 0);

    return 0;
}