Unidad 3: LISTAS CIRCULARES

Recorrido

Definición:

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], después ve si la condición cumple para efectuar un Ciclo mientras Apuntador sea diferente de Inicio, si cumple lo que hace es que despliega la Info[Apuntador], después 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 fin de 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:

image534.jpg

Programa:


#include <conio.h>

#include <iostream.h>

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<<"El Recorrido es:\n";

Recorrido(Info,Indice,Inicio,Disp);

getch();

}

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

{

int Apuntador=Indice[Inicio];

while(Apuntador!=Inicio)

{

cout<<Info[Apuntador];

Apuntador=Indice[Apuntador];

}

}

image514.jpg

Búsqueda

Definición:

La Búsqueda su objetivo es encontrar un dato en el arreglo Info, si lo encuentra lo desplegara en la pantalla, si no lo encuentra no desplegara nada ya que el dato no se encuentra en el arreglo Info.

Detalle:

Apuntador toma el valor de Inicio, después ve si la condición cumple para efectuar un Ciclo mientras Apuntador sea diferente de 0, si cumple lo que hace a continuación es la comparación de Elemento (El dato que vamos a buscar) con Info[Apuntador], cuando lo encuentre lo despliega y sale del método. Si no, regresa el valor de Apuntador para así saber que no se encontró el dato.

Algoritmo:


Recorrido(Inicio, Info, Indice, Elemento)

Apuntador → Indice[Inicio]

Repetir mientras Apuntador ≠ Inicio

Si Elemento = Info[Apuntador] entonces:

Imprimir Info[Apuntador]

Regresa Apuntador

Apuntador → Indice[Apuntador]

Fin del ciclo

Regresar Apuntador


Diagrama:

image535.jpg

Programa:


#include <conio.h>

#include <iostream.h>

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};

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

cout<<"Que Numero deseas buscar?";

cin>>Elemento;

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

if(Res==-999)

cout<<"Dato No Encontrado...";

getch();

}

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

{

int Apuntador=Indice[Inicio];

while(Apuntador!=Inicio)

{

if(Elemento==Info[Apuntador])

{

cout<<"Numero "<<Info[Apuntador]<<" encontrado...";

return Apuntador;

}

Apuntador=Indice[Apuntador];

}

return Apuntador;

}

image516.jpg

image517.jpg

Inserción al Principio

Definición:

La Inserción al Principio básicamente busca si existe algún lugar disponible en el arreglo Info y lo agrega como primer Nodo si es que es posible.

Detalle:

Hace una comparación para ver si es posible insertar otro Elemento al arreglo Info, para esto checa si Disp es Diferente de Nulo. Si no cumple con la condición 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, después de esto solo copia la información de Elemento al arreglo Info en la posición que guarda Apuntador, Indice[Apuntador] toma el 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:

Imprimir “Sobre Carga”

Salir


Diagrama:

image536.jpg

Programa:


#include <conio.h>

#include <iostream.h>

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};

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

cout<<"Lista Original\n";

Recorrido(Info,Indice,Inicio,Disp);

cout<<"Que Numero deseas Insertar?";

cin>>Elemento;

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

getch();

}

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

{

int Apuntador=Indice[Inicio];

while(Apuntador!=Inicio)

{

cout<<Info[Apuntador]<<endl;

Apuntador=Indice[Apuntador];

}

}

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

{

if(Disp!=-999)

{

int Apuntador=Disp;

Disp=Indice[Disp];

Info[Apuntador]=Elemento;

Indice[Apuntador]=Indice[Inicio];

Indice[Inicio]=Apuntador;

Recorrido(Info,Indice,Inicio,Disp);

}

else

cout<<"Overflow...";

}

image519.jpg

image520.jpg

Inserción después de un Nodo Determinado

Definición:

La Inserción después de un Nodo Determinado básicamente hace lo mismo que la inserción al principio, la única diferencia es que este recibe la posición del nodo en la que será Insertada. Este Algoritmo se usa para Inserción 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 posición Disponible en el arreglo Info, después compara la Nueva Posición (Npos) que le mandamos con Nill si cumple la condición el dato es insertado en la primer posición, de otra forma se posicionara en la posición que guarde Npos.

Algoritmo:


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


Inserción Ordenada

Definición:

La Inserción Ordenada busca la posición en donde será Insertado el Elemento y la posición anterior donde será Insertado, después de encontrar la posición en la que será Insertado el Elemento nos regresa ese valor y lo mandamos al método de la Inserción después de un Nodo.

Detalle:


En esta ocasión usaremos dos variables para determinar la posición deseada, comparamos si Indice[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 posición que le sigue a Inicio. Hace un ciclo hasta encontrar la posición en donde se insertara el Nuevo Elemento y va moviéndose de posición con las variables Temp y Temp2 para así determinar que posición 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:

image537.jpg

Programa:


#include <stdio.h>

#include <conio.h>

#include <iostream.h>

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<<"Lista Original\n";

Recorrido(Info,Indice,Inicio,Disp);

cout<<"Que Numero deseas Insertar?";

gets(Elemento);

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

getch();

}

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

{

int Apuntador=Indice[Inicio];

while(Apuntador!=Inicio)

{

cout<<Info[Apuntador]<<endl;

Apuntador=Indice[Apuntador];

}

}

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

{

if(Disp!=-999)

{

strcpy(Info[Disp],Elemento);

Indice[Disp]=Indice[Inicio];

Indice[Inicio]=Disp;

Disp=Indice[Disp];

}

Recorrido(Info,Indice,Inicio,Disp);

}

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

{

if(Inicio==Indice[Inicio]||(strcmp(Elemento,Info[Indice[Inicio]]))==0)

{

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

return;

}

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

while(Temp2!=Inicio)

{

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

break;

Temp=Temp2;

Temp2=Indice[Temp2];

}

strcpy(Info[Disp],Elemento);

Indice[Disp]=Indice[Temp];

Indice[Temp]=Disp;

Disp=Indice[Disp];

Recorrido(Info,Indice,Inicio,Disp);

}

image538.jpg

Eliminación por Búsqueda

Definición:

La Eliminación simplemente cambia los nodos para que el dato que se desea eliminar sea el primer disponible, de esta forma ya no estará en el Arreglo de Info.

Detalle:

Lo primero que hace es ver si existe algún dato en la lista para eliminar, si Indice[Inicio] es igual a Inicio entonces solo desplegara “Imposible Eliminar”. De otra formas cambiar de Posición en Posición hasta encontrar el Elemento que sea desea Eliminar con ayudar de dos variables que guardan la Posición actual y la anterior en donde se encuentre el dato. Ya que lo encuentra cambia ese dato como la primera posición Disponible y lo apunta al siguiente nodo disponible. Si no encuentra el dato simplemente desplegara “Dato no encontrado”

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:

image539.jpg

Programa:


#include <conio.h>

#include <iostream.h>

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};

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

cout<<"Lista Original\n";

Recorrido(Info,Indice,Inicio,Disp);

cout<<"Que Numero deseas Eliminar?";

cin>>Elemento;

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

getch();

}

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

{

int Apuntador=Indice[Inicio];

while(Apuntador!=Inicio)

{

cout<<Info[Apuntador]<<endl;

Apuntador=Indice[Apuntador];

}

}

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

{

int Temp=Indice[Inicio],Temp2;

if(Temp==Inicio)

{

cout<<"Lista Vacia... Imposible Eliminar";

return;

}

while(Temp!=Inicio)

{

if(Elemento==Info[Temp])

{

if(Temp==Inicio)

Inicio=Indice[Inicio];

else

Indice[Temp2]=Indice[Temp];

Indice[Temp]=Disp;

Disp=Temp;

Recorrido(Info,Indice,Inicio,Disp);

return;

}

else

{

Temp2=Temp;

Temp=Indice[Temp];

}

}

cout<<"Dato no encontrado... Imposible Eliminar";

return;

}

image524.jpg

Proyecto Final:

 


 


Driven by DokuWiki

Politica de Privacidad