Programación iii

REPUBLICA BOLIVARIANA DE VENEZUELA
MINISTERIO DEL PODER POPULAR PARA LA DEFENSA
UNIVERSIDAD NACIONAL EXPERIMENTAL DE LA FUERZA ARMADA
BARQUISIMETO ESTADO LARA

Asignación Virtual III Corte

NOMBRE:
RUBÉN CARREÑO
SECCIÓN:
6M3IS

BARQUISIMETO, 25 DE ENERO DE 2011
Listasdoblemente enlazadas:

Definición:

Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro al anterior.

Las listas doblemente enlazadas no necesitan un nodo especial para acceder a ellas, pueden recorrerse en ambos sentidos a partir de cualquier nodo, esto es porque a partir de cualquier nodo, siempre es posible alcanzar cualquiernodo de la lista, hasta que se llega a uno de los extremos.

El nodo típico es el mismo que para construir las listas que hemos visto, salvo que tienen otro puntero al nodo anterior:

struct nodo {
int dato;
struct nodo *siguiente;
struct nodo *anterior;
};

Ejemplo:

#include <stdio.h>

#define ASCENDENTE 1#define DESCENDENTE 0

typedef struct _nodo {
int valor;
struct _nodo *siguiente;
struct _nodo *anterior;
} tipoNodo;

typedef tipoNodo *pNodo;
typedef tipoNodo *Lista;

/* Funciones con listas:*/
void Insertar(Lista *l, int v);
void Borrar(Lista *l, int v);

void BorrarLista(Lista *);
void MostrarLista(Lista l, int orden);

int main() {
Lista lista = NULL;
pNodo p;

Insertar(&lista, 20);Insertar(&lista, 10);
Insertar(&lista, 40);
Insertar(&lista, 30);

MostrarLista(lista, ASCENDENTE);
MostrarLista(lista, DESCENDENTE);

Borrar(&lista, 10);
Borrar(&lista, 15);Borrar(&lista, 45);
Borrar(&lista, 30);

MostrarLista(lista, ASCENDENTE);
MostrarLista(lista, DESCENDENTE);

BorrarLista(&lista);

getchar();
return 0;
}

voidInsertar(Lista *lista, int v) {
pNodo nuevo, actual;

/* Crear un nodo nuevo */
nuevo = (pNodo)malloc(sizeof(tipoNodo));
nuevo->valor = v;

/* Colocamos actual en la primera posición de la lista */
actual = *lista;
if(actual)while(actual->anterior) actual = actual->anterior;
/* Si la lista está vacía o el primer miembro es mayor que el nuevo */
if(!actual || actual->valor > v) {
/* Añadimos la lista a continuación del nuevo nodo */
nuevo->siguiente = actual;
nuevo->anterior = NULL;if(actual) actual->anterior = nuevo;
if(!*lista) *lista = nuevo;
}
else {
/* Avanzamos hasta el último elemento o hasta que el siguiente tenga
un valor mayor que v */
while(actual->siguiente &&actual->siguiente->valor <= v)...