pito

mail@pastecode.io avatar
unknown
csharp
19 days ago
6.5 kB
3
Indexable
Never
bool agregarElemento(Lista L, TipoElemento elemento) {
    if (l_es_llena(L)) {
        return false;
    }
    int p = L->libre;
    int q = L->inicio;
    if (l_es_vacia(L)) {
        L->cursor[p].datos = elemento;
        L->libre = L->cursor[p].siguiente;
        L->cursor[p].siguiente = NULO;
        L->inicio = p;
    } else {
        int anteq;
        while (q != NULO) {
            anteq = q;
            q = L->cursor[q].siguiente;
        }
        L->cursor[p].datos = elemento;
        L->cursor[p].siguiente = NULO;
        L->cursor[anteq].siguiente = p;
        L->libre = L->cursor[p].siguiente;
    }
    L->cantidad++;
    return true;
}

// === INSERTAR SEGUN POSICION FISICA ===
// Insertar en una pos fisica del arreglo y retornar pos ordinal
// En caso de no ser posible retornar -1
int insertarPosicionFisica(Lista lista, TipoElemento X, int posFisica) {
    if (l_es_llena(lista)) return -1;
    if (l_es_vacia(lista)) return -1;
    int q, anterior, ordinal = 1, primerLibre;

    q = lista->inicio;
    while (q != NULO) { // itero hasta encontrar posFisica
        if (q == posFisica) {
            primerLibre = lista->libre; // guardo el libre
            lista->libre = lista->cursor[primerLibre].siguiente; // actualizo el libre
            lista->cursor[primerLibre].datos = X; // guardo el elemento en el 1er libre
            if (ordinal == 1) { // si es la pos ordinal 1, cambio el inicio
                lista->cursor[primerLibre].siguiente = lista->inicio;
                lista->inicio = primerLibre;
            } else { // sino, hago el puente
                // primero, el siguiente del elemento a insertar sera el siguiente al anterior
                lista->cursor[primerLibre].siguiente = lista->cursor[anterior].siguiente;
                // segundo, el siguiente del anterior sera nuestro elemento a insertar
                lista->cursor[anterior].siguiente = primerLibre;
            }
            lista->cantidad++;
            return ordinal;
        } else { // en caso de todavia no haber encontrado la posFisica:
            anterior = q; // agarro el anterior al actual
            q = lista->cursor[q].siguiente; // paso al siguiente nodo
            ordinal++;
        }
    }
    return -1;
}
/*
    1. Empiezo con q desde el inicio de la lista y recorro mientras sea diferente a NULO
    2. En el caso de que q NO sea igual a la posFisica, solo se guarda el q en anterior, se
    pase q a su siguiente y se suma el ordinal
    3. Si q es igual a la posFisica, se encontro en donde insertar:
        - guardo el primerLibre
        - actualizo el libre
        - guardo el elemento a insertar en el cursor con posicion primerLibre
        Si el ordinal es 1:
            - el siguiente del elemento a insertar sera el lista->inicio
            - lista->inicio ahora sera primerLibre
        Sino (el ordinal no es 1) hago el puente:
            - el siguiente del elemento a insertar sera el siguiente del anterior
            - el siguiente del anterior sera el primerLibre
        - Se suma lista->cantidad
        - Se retorna el ordinal
    
    Se retorna -1 (solo se llega hasta aca porque no se pudo insertar)
*/


// === ELIMINAR SEGUN POSICION FISICA ===
int eliminarPosicionFisica(Lista lista, int posicionFisica) {
    if (l_es_vacia(lista)) return -1;
    int q, anterior, ordinal = 1;

    q = lista->inicio;
    while (q != NULO) { // se recorre hasta que se encuentra la posicion fisica
        if (q == posicionFisica) { // si encuentro la posicion fisica
            if (ordinal == 1) { // elimino el 1er elemento
                anterior = lista->inicio; // guardo el inicio
                lista->inicio = lista->cursor[anterior].siguiente; // el nuevo inicio sera el sig del previo inicio
                lista->cursor[anterior].siguiente = lista->libre;  // el siguiente del eliminado sera el 1er libre
                lista->libre = anterior; // ahora el 1er libre sera el eliminado
            } else { // elimino el elemento que sea
                lista->cursor[anterior].siguiente = lista->cursor[q].siguiente;
                lista->cursor[q].siguiente = lista->libre;
                lista->libre = q;
            }
            lista->cantidad--;
            return ordinal;
        }
        ordinal++;
        anterior = q; // guardo el valor anterior a q
        q = lista->cursor[q].siguiente; // paso q
    }
    return -1;
}



// Agregar al TAD de listas con cursores una función que permita determinar si
// se trata de una lista ordenada ascendentemente. La función retornara “true”
// si se cumple esa condición, caso contrario “false”. La función se llamará
// “bool listaEstaOrdenada(Lista L)”. La función debe ser lo más eficiente posible.
bool listaEstaOrdenada(Lista L) {
    bool ordenada = true;
    int actual = L->inicio;
    int claveActual, claveProxima, sig;
    while (actual != NULO && ordenada && L->cursor[actual].siguiente != NULO) {
        sig = L->cursor[actual].siguiente;
        claveActual = L->cursor[actual].datos->clave;
        claveProxima = L->cursor[sig].datos->clave;
        if (claveActual > claveProxima) {
            ordenada = false;
        }
        actual = L->cursor[actual].siguiente;
    }
    return ordenada;
}

// Agregar al TAD de listas con cursores una función que elimine un elemento
// según su posición física. La función debe ser lo más eficiente posible.
// En el caso de que la eliminación sea válida, se retornará la posición ordinal,
// caso contrario se retornará -1. La función tendrá la siguiente firma
// “int eliminarPosFisica(Lista lista, int posFisica)”.
int eliminarPosFisica(Lista lista, int posFisica) {
    if (l_es_vacia(lista)) {
        return -1;
    }
    int q, anterior, ordinal = 1;

    q = lista->inicio;
    while (q != NULO) {
        if (q == posFisica) {
            if (ordinal == 1) {
                anterior = lista->inicio;
                lista->inicio = lista->cursor[anterior].siguiente;
                lista->cursor[anterior].siguiente = lista->libre;
                lista->libre = anterior;
            } else {
                lista->cursor[anterior].siguiente = lista->cursor[q].siguiente;
                lista->cursor[q].siguiente = lista->libre;
                lista->libre = q;
            }
            lista->cantidad--;
            return ordinal;
        } else {
            ordinal++;
            anterior = q;
            q = lista->cursor[q].siguiente;
        }
    }
    return -1;
}
Leave a Comment