Problema 1: Implemente el tipo de dato abstracto (TDA) lista de doble enlace simple:

Estructura:

typedef ListaDE{
    Item item;
    ListaDE *sig;
    ListaDE *ant;
} ListaDE;

Para la creación de listas de doble enlace, y también para la asignación, se utiliza el siguiente método:

ListaDE *init(Item item){
    ListaDE *elem;

    elem = new ListaDE();
    elem->sig = elem;
    elem->ant = elem;
    elem->item = elem;
    return elem;
}

NOTA: Al crear la lista, el valor de item no interesa, en cambio al asigar si.

Para realizar inserciones:

void insert(ListaDE *lista, ListaDE *elem){
    /* Noten que estoy recibiendo el puntero al elemento */
    elem->sig = lista->sig;
    elem->ant = lista;
    elem->sig->ant = elem;
    elem->ant->sig = elem;
}
 

Para realizar búsquedas:

ListaDE *busqueda(ListaDE *lista, Item target){
    ListaDE *aux = lista;

    while(aux->sig != lista){ /* la condición de salida es que se de la vuelta completa*/
        if (aux->sig->item == target)
            return aux->sig;
        aux = aux->sig;
    }
    return NULL;
}

Para borrar los elementos:

void remove(ListaDE *lista, Item target){
    /* Noten que para borrar, primero verifico que el elemento exista,
       y si existe, lo borro */

    ListaDE *aux = buqueda(lista, target);

    if aux != NULL{
        /* lo desengancho del la lista */
        aux->sig->ant = aux->ant;
        aux->ant->sig = aux->sig;
        /* borro el elemento */
        delete (aux);
    }
}
 
 

Problema 2: Implemente el tipo de dato abstracto (TDA) lista de doble enlace simple con listas ordenadas:

Para esto vamos a respetar que el elemento k >= elemento k-1

Estructura:

typedef ListaDE{
    Item item;
    ListaDE *sig;
    ListaDE *ant;
} ListaDE;

Para la creación de listas de doble enlace se utiliza el siguiente método:

ListaDE *init(){
    ListaDE *elem = new ListaDE();
    elem->sig = elem;
    elem->ant = elem;
    elem->item = -INFINITO /* ojo!! */;
    return elem;
}

Para la asinación de elementos de la lista de doble enlace se utiliza el siguiente método:

ListaDE *asign(Item item){
    ListaDE *elem = init();
    elem->item = item;
    return elem;
}

Para la inserción de elementos en la listas de doble enlace ordenada:
Importante: La inserción debe ser ordenada :)

void insert(ListaDE *lista, ListaDE *elem){
    ListaDE *elem = lista;

    while(aux->sig->item < valor) && (aux->sig != lista){
    /* buscamos hasta encontrar el elemento inmediatamente superior o
     * llegamos al final de la lista */
        aux = aux->sig;
    }

    /* Noten que estoy recibiendo el puntero al elemento */
    elem->sig = aux->sig;
    elem->ant = aux;
    elem->sig->ant = elem;
    elem->ant->sig = elem;
}

Para realizar búsquedas:
Como la lista esta ordenada

ListaDE *busqueda(ListaDE *lista, Item target){
    ListaDE *aux = lista;

    while(aux->sig->item < valor) && (aux->sig != lista){
    /* buscamos hasta encontrar el elemento o encontrar uno
     * inmediatamente superior, que significa que el elemento no
     * esta */
        if (aux->sig->item == target)
            return aux->sig;
        aux = aux->sig;
    }
    return NULL;
}

Para borrar los elementos:
Es igual al anterior, search and destroy (buscar y destruir)

void remove(ListaDE *lista, Item target){
    /* Noten que para borrar, primero verifico que el elemento exista,
       y si existe, lo borro */

    ListaDE *aux = buqueda(lista, target);

    if aux != NULL{
        /* lo desengancho del la lista */
        aux->sig->ant = aux->ant;
        aux->ant->sig = aux->sig;
        /* borro el elemento */
        delete (aux);
    }
}
 

Problema 3: Aplicación de listas: Arboles Generales

Un árbol general es una lista de listas de listas de listas de ...

Estructura:

typedeff ArbolGeneral{
    Item item;
    ArbolGeneral *hermano;
    ListaArbolGeneral *hijo;
} ArbolGeneral;

typedeff ArbolGeneral ListaArbolGeneral;

Noten que ArbolGeneral y ListaArbolGeneral son iguales :), sólo indico la diferencia para enfatizar que el nodo tiene un siguiente hermano y un puntero a su primer hijo.

Para la creación de un árbol general y para asignar el elemento item se utiliza el siguiente método:

ArbolGeneral *init(Item item){
    ArbolGeneral *nood = new ArbolGenral();
    nodo->hermano = NULL;
    nodo->hijo = NULL;
    nodo->item = item;
    return nodo;
}

Para las inserciones y borrados es necesario considerar la aplicación a utilizar.

Para la inserción de hermanos:

void insertaHermano(ArbolGeneral *arbol, ArbolGeneral *nodo){
    nodo->hermano = arbol->hermano;
    arbol->hermano = nodo;
}

Para la inserción de hijos:

void insertaHermano(ArbolGeneral *arbol, ArbolGeneral *nodo){
    nodo->hermano = arbol->hijo;
    arbol->hijo = nodo;
}

Insisto que si se definen criterios como los hijos son menores que el padre, y los hermanos son mayores, cambian los algoritmos.

Para realizar búsquedas:

ArbolGeneral *busqueda(ArbolGeneral * arbol, Item target){
    ArbolGenral *aux = NULL;

    if nodo->item=target
        return nodo;
    else{
        if nodo->hijo != NULL
            aux = busqueda(nodo->hijo);
        if (aux == NULL) && (nodo->hermano != NULL)
            aux = busqueda(nodo->hermano);
    }
    return aux;
}

Para borrar los elementos: depende de la aplicación :), pero lo importante es respetar los criterios considerados