Listas

Índice.



Marco teórico…………………………………………………………………….2

Nodos Centinelas
Listas Doblemente Circulares.



Desarrollo. ……………………………………………………………………………3

Declaración de la estructura…………………………………………….3
Función getnodo…………………………………………………………...3
Función Buscar……………………………………………………………...3
Función Insertar……………………………………………………………..4



Ejemplo de Lista Doblemente Circular.………………………………………..5



Referencias. …………………………………………………………………………13



















Marco teórico.

Definición.

Listas Doblemente Circulares.

Una lista doble circular es una estructura donde el último elemento tiene como referencia siguiente al primer elemento y la referencia al anterior del primer elemento de la lista también es el último.

Cada elemento esta doblemente enlazado

A través del usode listas dobles podemos acceder a los datos recorriendo los hacia delante hasta el final o hacia atrás hasta el inicio.


En una lista enlazada doblemente circular, cada nodo tiene dos enlaces, similares a los de la lista doblemente enlazada, excepto que el enlace anterior del primer nodo apunta al último y el enlace siguiente del último nodo, apunta al primero. Como en una lista doblementeenlazada, las inserciones y eliminaciones pueden ser hechas desde cualquier punto con acceso a algún nodo cercano. Aunque estructuralmente una lista circular doblemente enlazada no tiene ni principio ni fin, un puntero de acceso externo puede establecer el nodo apuntado que está en la cabeza y así mantener el orden tan bien como en una lista doblemente enlazada.

Nodos Centinelas

A veces laslistas enlazadas tienen un nodo centinela (también llamado falso nodo, nodo ficticio o nodo cabeza) al principio y/o al final de la lista, el cual no es usado para guardar datos. Su propósito es simplificar o agilizar algunas operaciones, asegurando que cualquier nodo tiene otro anterior o posterior, y que toda la lista (incluso alguna que no contenga datos) siempre tenga un “primer y último” nodo.Desarrollo.

Declaración de la estructura
Typedef struct celda{
Int elemento;
Struct nodo*sig;
Struct nodo* ant;
}tipo celda;

Función getnodo
tLista getnodo()
{
tLista L;
L=(tLista)malloc(sizeof(tipocelda));
If(L==NULL)
Printf("ERROR: Memoria Insuficiente\a\n");
L->sig=L->ant=L;
Return L;}

Función Buscar
Esta función recibe como argumento un dato a buscar,dentro de la lista y devuelve el nodo que contenga dicho dato.
tPosicion buscar (int x, tLista L)
{
tPosicion p;
int ban=0;
p=L->sig;
while((p!=L) && (!ban))
if(p->elemento==x)
ban=1;
else
p=p->sig;
return p;}


Función Insertar
Algoritmo:
1. Crear el nuevo nodo
2. Guardar el dato en el nuevo nodo
3. Hacer que el nuevo nodo, en su parte de siguiente apunte al nodo anterior (queestá siendo apuntado por p)
4. Luego copiar en nuevo->ant, lo que hay en p->ant
5. hacer que en la parte de siguiente del nodo anterior apuntado por p, contenga la dirección del nuevo nodo
6. hacer que p->ant apunte anuevo
7. guardar la dirección de nuevo en p
void insertar (int x, tPosicion p)
{
tPosicion nuevo; //Declaración nuevo nodo
nuevo=(tPosicion)malloc(sizeof(tipocelda));//Creación de espacio en la memoria para el nuevo nodo
if(nuevo==NULL)
printf("ERROR: memoria insuficiente\a\n");
nuevo->elemento=x;
nuevo->sig=p;
nuevo->ant=p->ant;
p->ant->sig=nuevo;
p->ant=nuevo;
p=nuevo;
}

















Ejemplo de Lista Doblemente Circular.

#include
#include
#include
#include
#define N 100

struct dclinklist

{
struct dclinklist*prev;
int roll_no;
char name[N];
float marks;
struct dclinklist *next;
};


typedef struct dclinklist node;void init(node*);
void ins_aft(node*);
node* ins_bef(node*);
node* del(node*);
void search(node*);
void disp(node*);
void rollsrch(node*);
void namesrch(node*);
void...