Programación iii
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)...
Regístrate para leer el documento completo.