leccion 3.4 listas circulares

8/8/2019 Leccion 3.4 Listas circulares

1/18

ESTRUCTURAS DE DATOS LECCION 3.4 LISTAS CIRCULARES Pgina 1

Leccion 3.4 LISTAS CIRCULARES

Definicin:

Recorrido simplemente despliega los datos almacenados en el arreglo Info, con ayuda de un segundo

arreglo llamado Indice el cual guarda el orden en el que encuentran enlazados cada uno de los datos.

Detalle:

Apuntador toma el valor de Indice[Inicio], despus ve si la condicin cumple para efectuar un Ciclomientras Apuntador sea diferente de Inicio, si cumple lo que hace es que despliega la Info[Apuntador],

despus Apuntador toma el valor de Indice[Apuntador] (El cual nos indica el siguiente nodo que sigue

en la lista) y hace esto hasta que Apuntador sea igual a Inicio (Cuando llega a este punto a llegado al finde la Lista).

Algoritmo:

Recorrido(Inicio, Info, Indice)

Apuntador Indice[Inicio]

Repetir mientras Apuntador Inicio

Imprimir Info[Apuntador]

Apuntador Indice[Apuntador]

Fin del ciclo

Salir

Diagrama:


2/18


Programa:

#include

#include

void Recorrido(char Info[8][2],int Indice[8],int Inicio,int Disp);

void main()

{

char Info[8][2]={{" "},{"I"},{" "},{"T"},{"O"},{"A"},

{"G"},{"T"}};

int Indice[8]={6,7,-999,1,0,3,5,4};

int Inicio=0,Disp=2;

cout


3/18


int Apuntador=Indice[Inicio];

while(Apuntador!=Inicio)

{

cout


4/18


Imprimir Info[Apuntador]

Regresa Apuntador

Apuntador Indice[Apuntador]

Fin del ciclo

Regresar Apuntador

Diagrama:

Programa:

#include

#include

int Busqueda(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento);

void main()

{

int Info[8]={0,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,0,3,-999,4};


5/18


int Inicio=0,Disp=2,Elemento,Res;

coutElemento;

Res=Busqueda(Info,Indice,Inicio,Disp,Elemento);

if(Res==-999)

cout


6/18


Insercin al Principio

Definicin:

La Insercin al Principio bsicamente busca si existe algn lugar disponible en el arreglo Info y loagrega como primer Nodo si es que es posible.

Detalle:

Hace una comparacin para ver si es posible insertar otro Elemento al arreglo Info, para esto checa siDisp es Diferente de Nulo. Si no cumple con la condicin se desplegar Sobre Carga ya que no se

puede insertar un Nuevo Elemento. Si es cierto Apuntador toma el valor de Inicio, Disp cambia a

Indice[Disp] ya que el primer Disp tomara el valor del Nuevo Elemento, despus de esto solo copia la

informacin de Elemento al arreglo Info en la posicin que guarda Apuntador, Indice[Apuntador] tomael valor de Indice[Inicio] y finalmente Indice[Inicio] toma el valor de Apuntador.

Algoritmo:

InsPr(Inicio, Disp, Info, Indice, Elemento)

Si Disp Nill entonces:

Apuntador Disp

Disp Indice[Disp]

Info[Apuntador] Elemento

Indice[Apuntador] Indice[Inicio]

Indice[Inicio] Apuntador

Si no:


7/18


Imprimir Sobre Carga

Salir

Diagrama:

Programa:

#include

#include

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp);

void InsPr(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento);

void main()

{

int Info[8]={0,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,0,3,-999,4};


cout


8/18


Recorrido(Info,Indice,Inicio,Disp);

coutElemento;

InsPr(Info,Indice,Inicio,Disp,Elemento);

getch();

}

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp)

{



{

cout


9/18


Insercin despus de un NodoDeterminado

Definicin:

La Insercin despus de un Nodo Determinado bsicamente hace lo mismo que la insercin al principio,

la nica diferencia es que este recibe la posicin del nodo en la que ser Insertada. Este Algoritmo se usa

para Insercin Ordenada que mas adelante explicaremos.

Detalle:

Primero confirma que sea posible insertar el Dato, si no es posible solo desplegara Sobre Carga. Si es

posible insertar un dato nuevo lo posiciona en la primer posicin Disponible en el arreglo Info, despuscompara la Nueva Posicin (Npos) que le mandamos con Nill si cumple la condicin el dato es insertadoen la primer posicin, de otra forma se posicionara en la posicin que guarde Npos.

Algoritmo:


10/18


InsOrd(Inicio, Disp, Info, Indice, Elemento, Npos)

Si Disp Nill entonces:

Apuntador Disp

Disp Indice[Disp]

Info [Apuntador] Elemento

Si Npos = Nill entonces:

Indice[Apuntador] Indice[Inicio]

Indice[Inicio] Apuntador

Si no:

Indice[Apuntador] Indice[Npos]

Indice[Npos] Apuntador

Si no:

Imprimir Sobre Carga

Salir

Insercin Ordenada

Definicin:

La Insercin Ordenada busca la posicin en donde ser Insertado el Elemento y la posicin anteriordonde ser Insertado, despus de encontrar la posicin en la que ser Insertado el Elemento nos regresa

ese valor y lo mandamos al mtodo de la Insercin despus de un Nodo.

Detalle:

En esta ocasin usaremos dos variables para determinar la posicin deseada, comparamos siIndice[Inicio] es igual a Inicio si Elemento es menor al dato que se encuentra en Info[Inicio], si alguna

de las dos cumple regresamos Nill, de esta manera Indicamos que el Elemento ser el primero de todo el

Arreglo Info, si no es as Temp tomara el valor de Inicio y Temp2 de la posicin que le sigue a Inicio.


11/18


Hace un ciclo hasta encontrar la posicin en donde se insertara el Nuevo Elemento y va movindose de

posicin con las variables Temp y Temp2 para as determinar que posicin debe de regresar.

Algoritmo:

InsOrd(Inicio, Info, Indice, Elemento)

Si Inicio = Indice[Inicio] Elemento < Info[Inicio] entonces:

Regresar Nill

Temp Indice[Inicio]

Temp2 Indice[Temp]

Repetir mientras Temp2 Inicio

Si Elemento < Info[Temp2]

Regresar Temp

Temp Temp2

Temp2 Indice[Temp2]

Regresar Temp

Diagrama:


12/18


Programa:

#include

#include

#include

void Recorrido(char Info[8][10],int Indice[8],int Inicio,int Disp);

void InsPr(char Info[8][10],int Indice[8],int Inicio,int Disp,char Elemento[10]);

void InsOrd(char Info[8][10],int Indice[8],int Inicio,int Disp,char Elemento[10]);

void main()

{

char Info[8][10]={{"Cabeza"},{"e"},{" "},{"c"},{"i"},{"a"},{" "},{"g"}};

char Elemento[10];

int Indice[8]={5,7,6,1,0,3,-999,4};

int Inicio=0,Disp=2,Res;

cout


13/18


gets(Elemento);

InsOrd(Info,Indice,Inicio,Disp,Elemento);

getch();

}

void Recorrido(char Info[8][10],int Indice[8],int Inicio,int Disp)

{



{

cout


14/18


return;

}

int Temp=Indice[Inicio],Temp2=Indice[Temp];

while(Temp2!=Inicio)

{

if((strcmp(Elemento,Info[Temp2]))


15/18


Algoritmo:

EliBusq(Inicio, Info, Indice, Elemento)

Temp Indice[Inicio]

Si Temp = Inicio

Imprimir Lista Vacia Imposible Eliminar y Retornar

Repetir mientras Temp Inicio

Si Elemento = Info[Temp] entonces:

Si Temp = Indice[Inicio] entonces:

Indice[Inicio] Indice[Indice[Inicio]]

Si no:

Indice[Temp2] Indice[Temp]

Indice[Temp] Disp

Disp Temp

Recorrido(Inicio, Info, Indice) y Retornar

Si no:

Temp2 Temp

Temp Indice[Temp]

Imprimir Dato no encontrado Imposible Eliminar y Retornar

Diagrama:


16/18


Programa:

#include

#include

void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp);

void EliBusq(int Info[8],int Indice[8],int Inicio,int Disp,int Elemento);

void main()

{

int Info[8]={0,10,0,9,5,3,0,20};

int Indice[8]={5,7,6,1,0,3,-999,4};


cout


17/18


void Recorrido(int Info[8],int Indice[8],int Inicio,int Disp)

{



{

cout


18/18


return;

}

else

{

Temp2=Temp;

Temp=Indice[Temp];

}

}

cout

leccion 3.4 listas circulares

Documents