Listas C++

INSTITUTO TECNOLÓGICO DE DURANGO ESTRUCTURAS DE DATOS

Practica ED 5 Listas

Nombre(s): Bustamante Hernández Rubén Ángel 11041245 Edith Pamela Ontiveros Romero 11040421

Maestro: Zúñiga Rodríguez Marco Antonio

Grupo: 3ZZ

Fecha: 21/Noviembre/2012

Marco Teórico
Una lista doblemente enlazada es una lista lineal en la que cada nodo tiene dos enlaces, uno al nodo siguiente, y otro alanterior. 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 cualquier nodo 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 otropuntero al nodo anterior:
struct nodo \{ int dato; struct nodo *siguiente; struct nodo *anterior; };

Las listas doblemente enlazadas son estructuras de datos semejantes a las listas enlazadas simples. La asignación de memoria es hecha al momento de la ejecución. En cambio, en relación a la listas enlazada simple el enlace entre los elementos se hace gracias a dos punteros (uno que apunta hacia elelemento anterior y otro que apunta hacia el elemento siguiente).

El puntero anterior del primer elemento debe apuntar hacia NULL (el inicio de la lista). El puntero siguiente del último elemento debe apuntar hacia NULL (el fin de la lista). Para acceder a un elemento, la lista puede ser recorrida en ambos sentidos: *comenzando por el inicio, el puntero desplazamiento hacia el próximo elemento.*comenzando por el final, el puntero desplazamiento hacia el elemento anterior. siguiente anterior permite permite el el

Resumiendo, el desplazamiento se hace en ambas direcciones, del primer al último elemento y/o del último al primer elemento. Las operaciones que podemos realizar sobre una lista enlazada son las siguientes:

Recorrido. Esta operación consiste en visitar cada uno de losnodos que forman la lista . Para recorrer todos los nodos de la lista, se

comienza con el primero, se toma el valor del campo liga para avanzar al segundo nodo, el campo liga de este nodo nos dará la dirección del tercer nodo, y así sucesivamente. Inserción. Esta operación consiste en agregar un nuevo nodo a la lista. Para esta operación se pueden considerar tres casos: Insertar un nodo alinicio. Insertar un nodo antes o después de cierto nodo. Insertar un nodo al final. Borrado. La operación de borrado consiste en quitar un nodo de la lista, redefiniendo las ligas que correspondan. Se pueden presentar cuatro casos: Eliminar el primer nodo. Eliminar el último nodo. Eliminar un nodo con cierta información. Eliminar el nodo anterior o posterior al nodo cierta con información. Búsqueda.Esta operación consiste en visitar cada uno de los nodos, tomando al campo liga como puntero al siguiente nodo a visitar.

CODIGO

#include #include #include #include

struct nodo{ char elemento; //Tipo de dato a insertar struct nodo* siguiente; struct nodo* ante;

};

struct nodo* lista = NULL; //Apuntador para la lista siempre NULL struct nodo* nodos; struct nodo* ultimo; //Siempresera la ultima direccion

void insertar(); void eliminar(); void mostrar();

char buscar; //Esta variable sera para buscar los elementos

int opcion; // variable para menu

//Creacion de la funcion menu void menu() { system("cls"); printf("----------MENU--------------\n\n"); printf(" printf(" printf(" printf(" 1.-Insertar\n "); 2.-Eliminar\n "); 3.-Mostrar\n "); 4.-Salir\n ");

printf(": ");

scanf("%d",&opcion); }//Fin menu

//Funcion Principal main

main() { menu(); //mandamos llamar funcion menu

switch(opcion) { case 1: insertar(); main();

case 2: eliminar(); main();

case 3: mostrar(); main();

case 4: printf("Adios"); }//Fin funcion switch

getche();

}//Fin main

//Funcion Para Insertar elementos

void insertar() {

if(lista == NULL) {...