• Author / Uploaded
• solartejoseluis

Citation preview

Listas circulares. • En las listas lineales simples o dobles siempre hay un primer nodo y un último nodo que tiene el campo de enlace a nulo. Esto, porque se delimita el comienzo y el término de la misma. Una lista circular, por su naturaleza cíclica, no tiene ni principio ni fin. No obstante, es útil y recomendable establecer un nodo de referencia a partir del cual se acceda a la lista y así poder conocer la posición inicial y acceder a sus operaciones insertar, borrar etc.

Listas circulares. Listas enlazadas circulares • En una lista enlazada circular, los nodos último y primero están unidos por un enlace (no apuntan a NULL). Esto es posible tanto para listas enlazadas simples como para las doblemente enlazadas. Para recorrer un lista enlazada circular se puede comenzar por cualquier nodo y seguir la lista en cualquier dirección hasta que se regrese hasta el nodo original. • Las listas enlazadas circulares pueden ser vistas como listas sin comienzo ni fin si no hay un punto que lo indique. • Este tipo de listas es el más usado para dirigir buffers para “ingerir” datos, y para visitar todos los nodos de una lista a partir de uno dado.

Listas circulares.

Listas circulares. Listas enlazadas circulares simples • Cada nodo tiene un enlace, análogo al de las listas enlazadas simples, la diferencia está en que el siguiente nodo del último apunta al primero. • Como en una lista enlazada simple, los nuevos nodos pueden ser solo eficientemente insertados después de uno que ya tengamos referenciado (recordemos que aquí no hay inicio ni fin). • Lo usual es quedarse con una referencia solamente al último elemento en una lista enlazada circular simple, esto nos permite rápidas inserciones al principio, y también permite accesos al primer nodo desde el puntero del último nodo.

Listas circulares. Lista Doblemente Enlazada Circular • En una lista circular doblemente enlazada, cada nodo tiene dos enlaces, análogamente a la lista doblemente enlazada lineal, el cambio radica en que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. • Como en una lista doblemente enlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo contiguo. • Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo (centinela) puede establecer el nodo apuntado que está en la cabeza o al nodo final, y así mantener el orden como en una lista doblemente enlazada.

Listas circulares. Nodos Centinelas o cabecera (header nodes) • La búsqueda y los algoritmos de ordenación se simplifican si se usan los llamados Nodos Centinelas o cabecera, donde cada elemento apunta a otro elemento y nunca a nulo. El Nodo Centinela o Puntero Cabeza contiene, como otro, un puntero siguiente que apunta al que se considera como primer elemento de la lista . También contiene un puntero previo que hace lo mismo con el último elemento. • El Nodo Centinela es definido como otro nodo en una lista doblemente enlazada. Si los punteros anterior y siguiente apuntan al Nodo Centinela la lista se considera vacía. En otro caso, si a la lista se le añaden elementos ambos puntero apuntarán a otros nodos. Estos Nodos Centinelas simplifican muchos las operaciones pero hay que asegurarse de que los punteros anterior y siguiente existen en cada momento. • Como ventaja eliminan la necesidad de guardar la referencia al puntero del principio de la lista y la posibilidad de asignaciones accidentales. Por el contrario, usan demasiado almacenamiento extra y resultan complicados en algunas operaciones.

Listas circulares. Inserción de un elemento en una lista circular El algoritmo empleado para añadir o insertar un elemento en una lista circular varia dependiendo de la posición en que se desea insertar el

elemento que inserta el nodo en la lista circular. En todo caso hay que seguir los siguientes pasos: • Asignar memoria a nuevo nodo nuevo y almacenar el dato. • Si la lista esta vacía, enlazar el campo sig del nuevo nodo nuevo con el propio nuevo nodo, nuevo y poner el puntero de la lista circular en el nuevo nodo nuevo. • Si la lista no esta vacía se debe decidir el lugar donde colocar el nuevo nodo nuevo, quedándose con la dirección del nodo inmediatamente anterior ant. Enlazar el campo sig del nuevo nodo nuevo con el campo sig del nodo anterior ant. Enlazar el campo sig del nodo anterior ant con el nuevo nodo nuevo. Si se pretende que el nuevo nodo nuevo ya insertado sea el primero de la lista circular, mover el puntero de la lista circular al nuevo nodo nuevo. En otro caso no hacer nada.

Listas circulares. Ejemplo 1. Inserción en la lista circular nuevo = (Nodo*) malloc (sizeof(Nodo)); nuevo->dato = el; if (primero==NULL) { nuevo->sig = nuevo; primero = nuevo; } else { nuevo->sig = antanterior->sig; anterior->sig = nuevo; }

Listas circulares. Eliminación de un elemento en una lista circular El algoritmo para eliminar un nodo de una lista circular es el siguiente:

Buscar el nodo que contiene el dato quedándose con el nodo anterior ant. Se enlaza el campo sig del nodo anterior ant con el campo siguiente sig del nodo a borrar. Si la lista contenía un solo nodo se pone a NULL la lista. En caso de que el nodo a eliminar sea el referenciado por el puntero de acceso a la lista, Lc y contenga mas de un nodo se modifica Lc para que tenga la dirección del nodo anterior ant o bien el campo sig de Lc. (Si la lista se quedara vacía hacer que Lc tome el valor NULL). Por último se libera la memoria ocupada por el nodo.

Listas circulares. Ejemplo 2. Eliminación en lista circular ant->sig = ptrnodo->sig; if (Lc == Lc->sig) Lc=NULL; else if (ptrnodo == Lc) Lc = ant->sig;

Listas circulares. Ejemplo 3 /***lista circular doblemente enlazada, que guarde enteros, y luego permita determinar cuantas veces se encuentra un número ingresado por el usuario.***/ #include #include #include #include /*Version Circular doblememente enlazada*/ typedef struct tipoNodo { int x; struct tipoNodo *adelante; struct tipoNodo *atras; }Nodo;

Listas circulares. /*Declaracion de los sinonimos para referirnos al tipo de dato*/ typedef Nodo *tLista; typedef Nodo *tPosicion; int cont=0; /*Declaración de las funciones que utilizaremos*/ void insertarPrim (tLista cabeza, int entrada); tLista CrearNodo(); void ImprimeLista(Nodo *ptr); int buscar(int busca, Nodo *cabeza, Nodo *ptr);

Listas circulares. main() { /*inicio del programa principal*/ Nodo *ptr; tPosicion cabeza; int entrada, opc, busca; char ban; /*cabeza contiene la dirección del primer nodo creado*/ cabeza=CrearNodo(); ban='S'; printf("\n\tÛÛ PROGRAMA QUE CALCULA LOS VALORES REPETIDOS EN UNA LISTA ÛÛ"); printf("\n\tÛÛ DOBLEMENTE ENLAZADA ÛÛ");

Listas circulares. while(ban=='S' || ban=='s') { printf("\n\n Ingrese un elemento para la lista:\n"); scanf("%d", &entrada); cont++; /*le enviamos a la función de insertar, le enviamos la dirección del primer nodo y el valor que vamos a introducir*/ insertarPrim(cabeza, entrada); printf("¨Desea Introducir un nuevo elemento a la lista? (S/N)\n"); ban=getch(); }

Listas circulares. printf("Los Valores Guardados en la Lista son:\n"); /*la función de imprimir, recibe un puntero hacia el primer nodo para iniciar con la impresión*/ ImprimeLista(cabeza); getch(); printf("\n\t\t¨Que desea Hacer?\n"); printf("\t\t1.Buscar un valor en la lista\n"); printf("\t\t2.Salir\n"); scanf("%d", &op);

Listas circulares. switch(opc) { case 1: printf("Ingrese el valor que desea buscar en la lista:\n"); scanf("%d", &busca); printf("El valor %d se encuentra %d veces en la lista\n\n", busca,buscar(busca,cabeza, cabeza)); break; case 2:exit(1); default:printf("Error, el comando no es válido\n"); break; } getch(); return 0; }

Listas circulares. /*definición de las funciones*/ void insertarPrim(tPosicion cabeza, int entrada) { tPosicion nuevo; /*creamos un nuevo nodo y le asignamos la dirección de memoria*/ nuevo=(tPosicion)malloc(sizeof(Nodo)); if(nuevo==NULL) printf("ERROR\n"); nuevo->x=entrada; /*la parte de adelante del nuevo nodo, apunta al primer nodo*/ nuevo->adelante=cabeza; nuevo->atras=cabeza->atras; cabeza->atras->adelante=nuevo; cabeza->atras=nuevo; }

Listas circulares. tLista CrearNodo() { /*creamos un nuevo nodo, el cual será la "cabeza" de la lista*/ tLista L; L=(tLista)malloc(sizeof(Nodo)); if(L==NULL); printf("Error, memoria Insuciente\n"); L->adelante=L->atras=L; return L; }

Listas circulares. void ImprimeLista(Nodo *ptr) { Nodo *p; int k=0; if(ptr!=NULL) { printf("Lista de N£meros Guardados:\n"); p=ptr->adelante; do{ k++; if(kx);

p=p->adelante; }while(p!=ptr->adelante); } Else { printf("No Hay elementos en la Lista\n"); }

}

Listas circulares. int buscar(int busca, Nodo *cabeza, Nodo *ptr) { int k=0; if(ptr!=NULL) { cabeza=ptr->adelante; do{ if(cabeza->x==busca) k++;

cabeza=cabeza->adelante; }while(cabeza!=ptr->adelante); } else { printf("No Hay elementos en la Lista\n"); } return k; }