Leccion 3.5 Listas dobles

8/8/2019 Leccion 3.5 Listas dobles

http://slidepdf.com/reader/full/leccion-35-listas-dobles 1/17

ESTRUCTURAS DE DATOS – LECCION 3.5 LISTAS DOBLES Página 1

Leccion 3.5 LISTAS DOBLES

Definición:

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

arreglo llamado Indice1 o Indice2 el cual guarda el orden en el que encuentran enlazados cada uno de

los datos. Estos datos se pueden recorrer de Arriba hacia Abajo o de Abajo hacia Arriba.

Explicación:

Dependiendo de la forma en la que se desea recorrer el Arreglo, la variable Apuntador tomara el valor

de Indice1[Inicio], o de Fin. Después recorrerá el Arreglo mientras la condición no se rompa (Dicha

condición será diferente dependiendo el caso).

Diagrama:

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

búsqueda es mas efectiva ya que compara el dato de la mitad y dependiendo el resultado, empezara la búsqueda por el Final o Inicio.




Explicación:

Primeramente usaremos un contador y la cabecera, esto nos permitirá determinar cual es dato de la

mitad. Para esto se utiliza el Recorrido el cual al encontrar el Dato de la mitad lo copia ese dato a la

cabecera con la cual se comparara para determinar por donde empezar (Inicio y Fin).

Diagrama:

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.

Explicación:

Esta Inserción ordenada es similar a las anteriores aunque en este caso consta de mas comparación y

movimientos de variables, esto se debe a que tenemos 2 arreglos que nos indican los movimientos y al

insertar un dato ambos arreglos deben direccionar nuevamente.

Diagrama:




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.

Explicación:

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”

Diagrama:




Corrida:

PROGRAMA CLICK HERE




#include <stdio.h>

#include <conio.h>

#include <iomanip.h>

#include <iostream.h>

class Alumno

{

private:

char Nombre[10][30];

int N_control[10],Edad[10],Indice1[10],Indice2[10],Inicio,Fin,Disp;

public:

//Constructor

Alumno()

{

int i,j;

Inicio=0;

Fin=0;

Disp=1;

Indice1[Inicio]=-999;

Indice2[Fin]=-999;

for(i=1,j=2;i<9;i++,j++)

Indice1[i]=j;

Indice1[9]=-999;

}

//Funcion de Recorrido

void Recorrido(int op)

{

int i=0,Temp;

if(op==1)

{




Temp=Indice1[Inicio];

if(Temp!=-999)

{

cout<<"Numero de Control"<<setw(19)<<"Nombre del Alumno"<<setw(5)<<"Edad"<<endl;

while(Temp!=-999)

{

if(i==(int(Edad[Inicio]/2)))

{

N_control[Inicio]=N_control[i];

strcpy(Nombre[Inicio],Nombre[i]);

}

cout<<setw(9)<<N_control[Temp]<<setw(22)<<Nombre[Temp]<<setw(9)<<Edad[Temp]<<endl;

Temp=Indice1[Temp];

i++;

}

}

else

cout<<"Lista Vacia...";

}

if(op==2)

{

Temp=Fin;

if(Edad[Inicio]!=0)

{


while(Temp!=-999&&i<Edad[Inicio])

{

if(i==(int(Edad[Inicio]/2)))




{

N_control[Inicio]=N_control[i];

strcpy(Nombre[Inicio],Nombre[i]);

}


Temp=Indice2[Temp];

i++;

}

}

else

cout<<"Lista Vacia...";

}

}

//Funcion Sobrecargada de Busqueda para Enteros

int Busqueda(int Elem)

{

if(Elem<N_control[Inicio])

{

int Temp=Indice1[Inicio];

while(Temp!=-999)

{

if(Elem==N_control[Temp])

{

gotoxy(1,10);



return Temp;

}

else




Temp=Indice1[Temp];

}

}

else

{

int Temp=Fin;

while(Temp!=-999)

{


{

gotoxy(1,10);



return Temp;

}

else

Temp=Indice2[Temp];

}

}

return -999;

}

//Funcion Sobrecargada de Busqueda de Cadenas de Caracteres

int Busqueda(char Elem[30])

{

if((strcmp(Elem,Nombre[Inicio]))<0)

{

int Temp=Indice1[Inicio];

while(Temp!=-999)




{

if((strcmp(Elem,Nombre[Temp]))==0)

{

gotoxy(1,10);



return Temp;

}

else

Temp=Indice1[Temp];

}

}

else

{

int Temp=Fin;

while(Temp!=-999)

{


{

gotoxy(1,10);



return Temp;

}

else

Temp=Indice2[Temp];

}

}

return -999;




}

//Funcion Sobrecargada de Orden para Numeros Enteros

int Enca(int E_nc)

{

int Temp=Indice1[Inicio],Temp2;

if(Temp==-999||E_nc<N_control[Temp])

return -999;

Temp2=Indice1[Indice1[Inicio]];

while(Temp2!=-999)

{

if(E_nc<N_control[Temp2])

return Temp;

Temp=Temp2;

Temp2=Indice1[Temp2];

}

return Temp;

}

//Funcion Sobrecargada de Orden para Cadena de Caracteres

int Enca(char E_nom[30])

{

int Temp=Indice1[Inicio],Temp2;

if(Temp==-999)

return -999;

if((strcmp(E_nom,Nombre[Temp]))<0)

return Temp;

Temp2=Indice1[Indice1[Inicio]];

while(Temp2!=-999)

{




Indice2[Indice1[Inicio]]=Temp;

}

Indice1[Inicio]=Temp;

}

else

{

Indice1[Temp]=Indice1[Npos];

if(Fin==Npos)

{

Indice2[Temp]=Fin;

Fin=Temp;

}

else

{

Indice2[Temp]=Npos;

Indice2[Indice1[Npos]]=Temp;

}

Indice1[Npos]=Temp;

}

}

else

cout<<"Overflow..."<<endl;

}

//Funcion Sobrecargada para Borrar un Dato que sea Entero

void Borrar(int Elem)

{

int Temp2,Temp=Indice1[Inicio];

if(Temp==-999)




{

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

return;

}

while(Temp!=-999)

{


{

Edad[Inicio]--;

if(Temp==Indice1[Inicio])

{

Indice1[Inicio]=Indice1[Indice1[Inicio]];

Indice2[Indice1[Inicio]]=Inicio;

}

else if(Temp==Fin)

{

Indice1[Temp2]=Indice1[Temp];

Fin=Indice2[Fin];

}

else

{


Indice2[Indice1[Temp2]]=Temp2;

}

Indice1[Temp]=Disp;

Disp=Temp;

return;

}

else




{

Temp2=Temp;

Temp=Indice1[Temp];

}

}

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

return;

}

//Funcion Sobrecargada para Borrar una Cadena de Caracteres

void Borrar(char Elem[30])

{

int Temp2,Temp=Indice1[Inicio];

if(Temp==Inicio)

{

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

return;

}

while(Temp!=Inicio)

{


{

Edad[Inicio]--;

if(Temp==Indice1[Inicio])

{

Indice1[Inicio]=Indice1[Indice1[Inicio]];

Indice2[Indice1[Inicio]]=Inicio;

}

else if(Temp==Fin)




{


Fin=Indice2[Fin];

}

else

{


Indice2[Indice1[Temp2]]=Temp2;

}

Indice1[Temp]=Disp;

Disp=Temp;

return;

}

else

{

Temp2=Temp;

Temp=Indice1[Temp];

}

}

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

return;

}

}tec;

main()

{

int op=0,res;

char inom[30];

int in_c,iedad;

while(op!=6)




{

clrscr();

cout<<"\n1) Recorrido por Inicio\n2) Recorrido por Final\n3) Busqueda\n";

cout<<"4) Insercion\n5) Eliminar un Dato\n6) Salir"<<endl;

gotoxy(1,1);

cout<<"Que deseas hacer: ";

cin>>op;

gotoxy(1,10);

switch (op)

{

case 1:

tec.Recorrido(1);

break;

case 2:

tec.Recorrido(2);

break;

case 3:

cout<<"Que Numero de Control deseas buscar?"<<endl;

cin>>res;

res=tec.Busqueda(res);

if(res==-999)

cout<<"Dato no encontrado";

break;

case 4:

cout<<"Que nombre quieres Insertar?"<<endl;

gets(inom);

cout<<"Cual es su Numero de Control?"<<endl;

cin>>in_c;




cout<<"Cual es su Edad?"<<endl;

cin>>iedad;

res=tec.Enca(in_c);

tec.InsLug(inom,in_c,iedad,res);

break;

case 5:

cout<<"Que Numero de Control deseas eliminar?"<<endl;

cin>>res;

tec.Borrar(res);

break;

case 6:

cout<<"Salida...";

break;

default:

cout<<"Opcion Erronea"<<endl;

break;

}

getch();

}

}

Leccion 3.5 Listas dobles

Documents

Transcript of Leccion 3.5 Listas dobles