LISTAS CIRCULARES: 2007

lunes, 1 de octubre de 2007

NUMERO ELIMINADO

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

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

ELIMINACION POR BUSQUEDA

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

PROGRAMA

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

Regresar Nill

Temp → Indice[Inicio]

Temp2 → Indice[Temp]

Repetir mientras Temp2 ≠ Inicio

Si Elemento <>

Regresar Temp

Temp → Temp2

Temp2 → Indice[Temp2]

Regresar Temp

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<<"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<<<0) temp="Temp2;" temp2="Indice[Temp2];" disp="Indice[Disp];">

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

EJERCICIO

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

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 "<<<" encontrado...";  return Apuntador;  }  Apuntador=Indice[Apuntador];  }  return Apuntador;  }

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

EJEMPLO

#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<<"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<

DIAGRAMA

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

viernes, 28 de septiembre de 2007

OPERACIONES:

CreaNodo.

Descripción: Realiza la solicitud del espacio de almacenamiento para almacenar un nodo.

Datos de ingreso: Apuntador a Nodo.

Datos de salida: Espacio de almacenamiento referenciado por el apuntador a Nodo.

Precondición: Apuntador a Nodo se encuentra inicializado a NULL.

Postcondición: Apuntador a Nodo poseerá una dirección de memoria, si es nula se interpretará como la imposibilidad de obtener espacio de almacenamiento, por lo que el objeto no se creará.

InsertaInicio.

Descripción: Inserta un nodo en la posición referenciada por el apuntador Cabeza.

Datos de ingreso: Apuntador a Nodo.

Datos de salida: Apuntador a Cabeza.

Precondición: True.

Postcondición: Lista poseerá uno o más elementos. Cabeza apuntará a una dirección física.

InsertaAntes.

Descripción: Inserta un nodo en la posición previa a la que posee el carácter de ingreso. Actualiza la estructura Lista.

Datos de ingreso: Apuntador Cabeza, Apuntador a Nodo, Caracter.

Datos de salida: Apuntador a Cabeza, o mensaje de imposibilidad de ingresar el nodo, dada la ausencia en la estructura de aquel nodo que posea como elemento al Carácter buscado.

Precondición: True

Postcondición: Lista podrá poseer un elemento más.

InsertaDespues.

Descripción: Inserta un nodo en la posición posterior a la que posee el carácter de ingreso. Actualiza a estructura Lista.

Datos de ingreso: Apuntador Cabeza, Apuntador a Nodo, Caracter.

Datos de salida: Apuntador a Cabeza, o mensaje de imposibilidad de ingresar el nodo, dada la ausencia en la estructura de aquel nodo que posea como elemento al Carácter buscado.

Precondición: True

Postcondición: Lista podrá poseer un elemento más.

VisualizaLista.

Descripción: Permite verificar los elementos de la Lista, partiendo de la Cabeza

Datos de ingreso: Apuntador a Cabeza.

Datos de salida: Ninguno.

Precondición: El usuario ha seleccionado la cabeza desde la cual hará la visualización.

Postcondición: De ninguna manera la estructura será actualizada.

EliminaNodo.

Descripción: Permite prescindir del nodo que posee el Carácter de ingreso (si existe), actualizando la estructura.

Datos de ingreso: Apuntador Cabeza, Carácter.

Datos de salida: Cabeza con estructura modificada, entero 1: fue eliminado, 0: no eliminado.

Precondición: True

Postcondición: De encontrarse el nodo con el carácter buscado, Lista poseerá un elemento menos, de manera contraria se retornará valor para emitir mensaje de nodo no encontrado.

BuscaNodo.

Descripción: Recorre la estructura hasta alcanzar el nodo que contiene el carácter buscado.

Datos de ingreso: Apuntador Cabeza, Carácter.

Datos de salida: 1 si el nodo ha sido encontrado, 0 de manera contraria.

Precondición: True

Postcondición: De ninguna manera la estructura será actualizada.

OrdenaLista.

Descripción: Actualiza la lista, teniendo en cuenta un orden ascendente según los nodos que se tienen.

Datos de ingreso: Apuntador Cabeza.

Datos de salida: Apuntador a Cabeza y estructura modificada.

Precondición: True

Postcondición: Se contará al término de la operación con todos los nodos que se tenían a su inicio.

CuentaNodos.

Descripción: determina la longitud de la estructura a partir del número de nodos que posee Lista.

Datos de ingreso: Apuntador Cabeza.

Datos de salida: Número entero igual o superior a cero.

Precondición: True

Postcondición: La estructura no será modificada.

Circular

LISTA_CIRCULAR_SIMPLE

OBJETO ABSTRACTO: LISTA

Una lista es la sucesión de espacios de memoria vinculados de tal manera que el último encadenamiento debe apuntar al primero.

Lista es una ED Lineal que puede crecer de manera ilimitada (realmente su límite es la memoria ram) según las pretensiones del cliente en tiempo de ejecución.

INVARIANTE:

Lista será controlada por un solo apuntador: cabeza que referenciará en primera instancia NULL y cuando se posicionen uno o más nodos en la Estructura, siempre cabeza referenciará al primero de ellos a menos que el usuario pretenda actualizarlo.

Toda creación de un nodo implicará poner en nulo su espacio autoreferenciable.

Todo nodo se relacionará hacia delante a lo sumo con un nodo a partir de la dirección de memoria donde se encuentra definido. Para todo nodo debe haber claridad en su sucesor y antecesor.

DOMINIO DE LA ESTRUCTURA:

Lista poseerá tantos nodos como el usuario en tiempo de ejecución desee.

Cada nodo poseerá un carácter y la respectiva referencia.