Universidad Nacional Mayor de San Marcos “Decana de América”

E.A.P. : Ingeniería de Sistemas

Alumno / Código : Vargas Pablo, Pedro Emilio / 11200123 Torres Avellaneda, Luis / 11200218

Curso : Algorítmica III

Tema : 3er Informe de Laboratorio

Profesor : Carlos A. Ruiz De La Cruz Melo

Implemente las estructuras siguientes:

1. Un arreglo unidimensional.

2. Una lista enlazada simple y doble..

3. Un árbol binario común.

4. Un árbol AVL.

5. Un árbol B

Luego asígnele las siguientes operaciones a cada uno:

Búsqueda de un valor.

Eliminación de un valor.

Mida los tiempos y compare. Comente cual de las estructuras es la mas

rápida, la mas lenta, si hay estructuras que dan tiempos iguales, etc.

Desarrollo:

1. Un arreglo unidimensional: #include <cstdlib> #include <iostream> #include <conio.h> #define MAX 5 #include <stdio.h> #include <windows.h> using namespace std; /* retorna "a - b" en segundos */ double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b) { LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart; } void valores(); void buscar(); void eliminar(); int v[MAX] = {1,4,16,3,8}; int i, x, p; int TOPE=MAX; int main(int argc, char *argv[]){ int op; do{ system("cls"); cout<<"\n\t\t MENU"; cout<<"\n\t 1) Ver valores. "; cout<<"\n\t 2) Buscar valores. "; cout<<"\n\t 3) Eliminar valor. "; cout<<"\n\t 4) Salir. "; cout<<"\n\t Ingrese opcion: "; cin>>op; switch(op){ case 1: valores(); break; case 2: buscar(); break; case 3: eliminar(); break; case 4:

exit(0); } getch(); }while(true); } void eliminar(){ p=0; cout<<"\n\t > Ingrese elemento a eliminar:"; cin>>x; LARGE_INTEGER t_ini, t_fin; double secs; QueryPerformanceCounter(&t_ini); for(i=0; i<MAX; i++){ if(v[i]==x){ cout<<"\n\t\t >Elemento encontrado en la posicion: "<<i+1; p=1; for(int j=i;j<TOPE;j++){ v[i]=v[i+1]; i++; } TOPE--; } } if(p!=1){ cout<<"\n\t\t > No se hallo en el vector, imposible eliminar..."; } cout<<"\n\t >> El proceso ha durado: "; QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); printf("%.16g millisegundos\n", secs * 1000.0); } void buscar(){ p=0; cout<<"\n\t > Ingrese elemento a buscar:"; cin>>x; LARGE_INTEGER t_ini, t_fin; double secs; QueryPerformanceCounter(&t_ini); for(i=0; i<MAX; i++){ if(v[i]==x){ cout<<"\n\t\t >Elemento encontrado en la posicion: "<<i+1; p=1; } } if(p!=1){ cout<<"\n\t\t > No se hallo en el vector..."; } cout<<"\n\t >> El proceso ha durado: "; QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); printf("%.16g millisegundos\n", secs * 1000.0); } void valores(){ cout<<"\n\t > Valores del vector:"; for(i=0; i<TOPE; i++){ cout<<"\n\t\t - Valor["<<i+1<<"] = "<<v[i];

} }

Búsqueda:

Eliminar:

2. Una Lista enlazada simple: #include<iostream.h> #include<stdlib.h> #include<stdio.h> #include<fstream.h> #include<conio.h> #include <windows.h> using namespace std; /* retorna "a - b" en segundos */ double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b) { LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart;

} struct Nodo{ int valor; Nodo *sig; }; struct Lista{ Nodo *cab; Nodo *U; }; Lista inicializar(Lista l){ l.cab=NULL; l.U=NULL; return l; } bool Vacio(Lista l) { if (l.cab==NULL) return true; else return false; } Lista Adiciona(Lista l, int val){ Nodo *n=new Nodo(); n->sig = NULL; n->valor = val; if(Vacio(l)) l.cab = n; else l.U->sig = n; l.U = n; return l; } void Recorre(Lista l){ Nodo *aux = l.cab; int i=0; cout<<"\n\n\t Visualizacion de la Lista\n"; if(Vacio(l)){ cout<<"Lista vacia\n"; } else { while(aux!=NULL){ cout<<"\n\t Valor: "<<aux -> valor<<endl; aux = aux -> sig; i++; } } cout<<"\n\n\t Existen "<<i<<" elementos"; } void Acces_Val(Lista l, int Val) { LARGE_INTEGER t_ini, t_fin; double secs; QueryPerformanceCounter(&t_ini);

Nodo *p; bool encontro = false; if (Vacio(l)) cout<<"\n\n\t Lista se encuentra vacia\n"; else { p = l.cab; if(p -> valor == Val) encontro = true; else { while(p != NULL && p -> valor != Val) { p = p -> sig; } if (p != NULL) encontro = true; } if (encontro) cout<<"\n\n\t Valor encontrado en la direccion "<<p<<endl; else cout<<"\n\n\t Valor no encontrado\n"; } cout<<"\n\n El proceso duro: "; QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); printf("%.16g millisegundos\n", secs * 1000.0); } Lista Insertar_Por_Posicion(Lista l, int Pos, int V) { Nodo *ant, *n1 = l.cab, *n; n = new Nodo(); n -> valor = V; if(Pos==1) { n->sig = l.cab; l.cab = n; } else { int i = 1; while(n1 != NULL && i < Pos){ ant = n1; n1 = n1 -> sig; i++; } if(n1 != NULL) { n -> sig = ant -> sig; ant -> sig = n; } else cout<<"\n\n\t Posicion no encontrada\n"; } return l; } Lista Eliminar_Por_Valor(Lista l, int Val) { LARGE_INTEGER t_ini, t_fin; double secs;

QueryPerformanceCounter(&t_ini); Nodo *n, *ant; n = l.cab; if (Vacio(l)) cout<<"\n\n\t Lista se encuentra vacia\n"; else { bool encontro = false; while(n != NULL && !encontro) { if(n -> valor == Val) encontro = true; else { ant = n; n = n -> sig; } } if(n == NULL) cout<<"\n\n\t Valor no encontrado\n"; else { if(l.cab == n) l.cab = n -> sig; else ant -> sig = n -> sig; delete(n); cout<<"\n\n\t Valor eliminado\n"; } } cout<<"\n\n El proceso duro: "; QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); printf("%.16g millisegundos\n", secs * 1000.0); return l; } void Salvar(Lista l) { ofstream FLista; Nodo *p; int V; cout<<"\n\n\t Guardar Lista\n"; p = l.cab; if (Vacio(l)) cout<<"\n\n\t Lista se encuentra vacia\n"; else { FLista.open("lista.txt", ios::out); while (p != NULL) { V = p -> valor; FLista<<V<<endl; p = p -> sig; } FLista.close(); } cout<<"\n\n\t Lista guardada\n"; } int main(){ int op, numero, pos;

Lista l; l = inicializar(l); do { system("cls"); cout<<"\t=================================================="<<endl; cout<<"\t LISTA DE VALORES \n"; cout<<"\t=================================================="<<endl; cout<<"\t Adicionar al final de la lista [1]\n"; cout<<"\t Recorrer mostrando sus elementos [2]\n"; cout<<"\t Busqueda de un elemento por valor [3]\n"; cout<<"\t Insertar por posicion [4]\n"; cout<<"\t Eliminar por valor [5]\n"; cout<<"\t Salvar Lista en una Fila [6]\n"; cout<<"\t Salir [7]\n"; cout<<"\n\n\t Ingrese su opcion ---> "; cin>>op; switch (op) { case 1: system("cls"); cout<<"\n\n\t Ingrese el valor a insertar al final de la lista: "; cin>>numero; l = Adiciona(l, numero); break; case 2: system("cls"); Recorre(l); break; case 3: system("cls"); cout<<"\n\t Ingrese el valor a buscar: "; cin>>numero; Acces_Val(l, numero); break; case 4: system("cls"); cout<<"\n\t Ingrese el valor a insertar: "; cin>>numero; cout<<"\n\t Ingrese la posicion (entero > 0): "; cin>>pos; l = Insertar_Por_Posicion(l, pos, numero); break; case 5: system("cls"); cout<<"\n\t Ingrese el valor a eliminar: "; cin>>numero; l = Eliminar_Por_Valor(l, numero); break; case 6: system("cls"); Salvar(l); break; case 7: exit(0); break; } getche();

} while (op!= 7); system("PAUSE"); return (0); }

Búsqueda:

Eliminar:

3. Una Lista enlazada doble: #include <iostream.h> #include <stdlib.h> #include <conio.h> #include<conio.h> #include <windows.h> using namespace std; /* retorna "a - b" en segundos */ double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b) {

LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart; } struct nodo{ int info; nodo *sgt; nodo *ant; }; void agrega(nodo **cab, nodo **fin); void muestra(nodo *cab); void buscar(nodo *cab); int main() { nodo *c=NULL,*f=NULL; //puntero de cabecera, y puntero de fin de lista int opcion; do{ system("cls"); cout<<"1) Ingresa un dato (numero entero)."<<endl; cout<<"2) Muestra los datos ingresados."<<endl; cout<<"3) Buscar elemento."; cout<<"\n Ingrese opcion: "; cin>>opcion; switch(opcion){ case 0: exit(0);break; case 1: agrega(&c, &f);break; case 2: muestra(c);break; case 3: buscar(c);break; } } while(opcion!=0); system("PAUSE"); return 0; } void agrega(nodo **cab, nodo **fin){ int num; cout<<"ingrese informacion"<<endl; cin>>num; if((*cab)==NULL){ *cab = new nodo; (*cab)->info =num; (*cab)->sgt=NULL; (*cab)->ant=NULL; (*fin)=(*cab); }else{ (*fin)->sgt=new nodo; (*fin)->sgt->info=num; (*fin)->sgt->ant=(*fin); (*fin)=(*fin)->sgt; (*fin)->sgt=NULL; } } void muestra(nodo *cab){ cout<<"elementos en la lista"<<endl; nodo* temp; temp=cab; while ( temp != NULL){

cout<<temp->info<<" "; temp=temp->sgt; } getche(); } void buscar(nodo *cab){ int x; int z=0; int op=0; cout<<"Ingrese elemento a buscar:"<<endl; cin>>x; LARGE_INTEGER t_ini, t_fin; double secs; QueryPerformanceCounter(&t_ini); nodo* temp; temp=cab; while ( temp != NULL){ if (temp->info==x){ cout<<"Elemento encontrado en la posicion "<<z+1; op=1; } z=z+1; temp=temp->sgt; } if(op!=1){ cout<<"Elemento no hallado..."; } cout<<"\n\n El proceso duro: "; QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); printf("%.16g millisegundos\n", secs * 1000.0); getche(); }

Búsqueda:

4. Un árbol binario común: // crea la clase ABB #include <iostream.h> #include <stdlib.h> #include <conio.h> #include <fstream.h> #include <stdio.h> #include <windows.h> using namespace std; /* retorna "a - b" en segundos */ double performancecounter_diff(LARGE_INTEGER *a, LARGE_INTEGER *b) { LARGE_INTEGER freq; QueryPerformanceFrequency(&freq); return (double)(a->QuadPart - b->QuadPart) / (double)freq.QuadPart; } class Nodo { public: int valor; Nodo *HI; Nodo *HD; }; class ABB { private: Nodo *pos, *posPad, *n, *t, *padre, *hijo, *suc, *padSuc; public: Nodo *raiz; ABB(); bool Vacio(); bool Buscar(int); void Insertar(int); void Eliminar(int); void Eliminar_Caso_A(int, Nodo *, Nodo *); void Eliminar_Caso_B(int, Nodo *, Nodo *); void PreOrden(Nodo *); void InOrden(Nodo *); void PostOrden(Nodo *); void Salvar(); void Salvar_PreOrden(Nodo *); void Recuperar(); }; ABB::ABB() { raiz = NULL; } bool ABB::Vacio() { if (raiz == NULL) return true; else return false; } bool ABB::Buscar(int Val) { LARGE_INTEGER t_ini, t_fin; double secs; QueryPerformanceCounter(&t_ini); bool encontro = false;

if (Vacio()) { pos = NULL; posPad = NULL; } else { n = raiz; if (n -> valor == Val) { pos = raiz; posPad = NULL; encontro = true; } else { if (Val > n -> valor) n = n -> HD; else n = n -> HI; padre = raiz; while (n != NULL && !encontro) { if (n -> valor == Val) { pos = n; posPad = padre; encontro = true; } else { padre = n; if (Val < n -> valor) n = n -> HI; else n = n -> HD; } } if (!encontro) { pos = NULL; posPad = padre; } } } cout<<"\n\t >> El proceso ha durado: "; QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); printf("%.16g millisegundos\n", secs * 1000.0); return encontro; } void ABB::Insertar(int Val) { pos = NULL; posPad = NULL; Buscar(Val); if (pos != NULL) cout<<"\n\n\t "<<Val<<" duplicado"; else { n = new Nodo; n -> valor = Val; n -> HI = NULL; n -> HD = NULL; if (posPad == NULL) raiz = n; else if (Val < posPad -> valor) posPad -> HI = n; else

posPad -> HD = n; } } void ABB::Eliminar(int Val) { LARGE_INTEGER t_ini, t_fin; double secs; QueryPerformanceCounter(&t_ini); Buscar(Val); if(pos == NULL) cout<<"\n\n\t "<<Val<<" no existe en el arbol"; else { if(pos -> HI != NULL && pos -> HD != NULL) Eliminar_Caso_B(Val, pos, posPad); else Eliminar_Caso_A(Val, pos, posPad); cout<<"\n\n\t "<<Val<<" eliminado"; } cout<<"\n\t >> El proceso ha durado: "; QueryPerformanceCounter(&t_fin); secs = performancecounter_diff(&t_fin, &t_ini); printf("%.16g millisegundos\n", secs * 1000.0); } void ABB::Eliminar_Caso_A(int Val, Nodo *posi, Nodo *posiPad) { if(posi -> HI == NULL && posi -> HD == NULL) hijo = NULL; else if(posi -> HI != NULL) hijo = posi -> HI; else hijo = posi -> HD; if (posiPad != NULL) { if(posi == posiPad -> HI) posiPad -> HI = hijo; else posiPad -> HD = hijo; } else raiz = hijo; } void ABB::Eliminar_Caso_B(int Val, Nodo *posi, Nodo *posiPad) { t = posi; n = posi -> HD; while(n -> HI != NULL) { t = n; n = n -> HI; } suc = n; padSuc = t; Eliminar_Caso_A(Val, suc, padSuc); if (posiPad != NULL) { if(posi == posiPad -> HI) posiPad -> HI = suc; else posiPad -> HD = suc; } else raiz = suc;

suc -> HI = posi -> HI; suc -> HD = posi -> HD; } void ABB::PreOrden(Nodo *r) { if(r != NULL) { cout<<"\t "<<r -> valor; PreOrden(r -> HI); PreOrden(r -> HD); } } void ABB::InOrden(Nodo *r) { if(r != NULL) { InOrden(r -> HI); cout<<"\t "<<r -> valor; InOrden(r -> HD); } } void ABB::PostOrden(Nodo *r) { if(r != NULL) { PostOrden(r -> HI); PostOrden(r -> HD); cout<<"\t "<<r -> valor; } } void ABB::Salvar() { cout<<"\n\n\t Salvar Arbol\n"; if (Vacio()) cout<<"\n\n\t Arbol se encuentra vacio\n"; else { Salvar_PreOrden(raiz); cout<<"\n\n\t Arbol salvado\n"; } } void ABB::Salvar_PreOrden(Nodo *r) { ofstream FArbol; if(r != NULL) { FArbol.open("arbol.txt", ios::app); FArbol<<r -> valor<<endl; Salvar_PreOrden(r -> HI); Salvar_PreOrden(r -> HD); FArbol.close(); } } void ABB::Recuperar() { ifstream FArbol; int V; cout<<"\n\n\t Recuperar Arbol\n"; FArbol.open("arbol.txt", ios::in); FArbol>>V; raiz = NULL; while(!FArbol.eof()) { Insertar(V); FArbol>>V; } FArbol.close();

cout<<"\n\n\t Arbol recuperado\n"; } int main() { int op, numero, pos; ABB A; do { system("cls"); cout<<"\t=================================================="<<endl; cout<<"\t ARBOL BINARIO DE BUSQUEDA \n"; cout<<"\t=================================================="<<endl; cout<<"\t Insertar valores [1]\n"; cout<<"\t Buscar valor [2]\n"; cout<<"\t Eliminar valor [3]\n"; cout<<"\t Recorrer en PreOrden [4]\n"; cout<<"\t Recorrer en InOrden [5]\n"; cout<<"\t Recorrer en PostOrden [6]\n"; cout<<"\t Salvar Arbol en un Archivo [7]\n"; cout<<"\t Recuperar Arbol de un Archivo [8]\n"; cout<<"\t Salir [9]\n"; cout<<"\n\n\t Ingrese su opcion ---> "; cin>>op; switch (op) { case 1: system("cls"); cout<<"\n\n\t Ingrese el entero a insertar en el arbol: "; cin>>numero; A.Insertar(numero); break; case 2: system("cls"); cout<<"\n\t Ingrese el entero a buscar: "; cin>>numero; if (A.Buscar(numero)) cout<<"\n\t El numero "<<numero<<" esta en el arbol\n"; else cout<<"\n\t El numero "<<numero<<" no esta en el arbol\n"; break; case 3: system("cls"); cout<<"\n\n\t Ingrese el entero a eliminar del arbol: "; cin>>numero; A.Eliminar(numero); break; case 4: system("cls"); cout<<"\n\n\t El Recorrido PreOrden es:\n\n"; A.PreOrden(A.raiz); break; case 5: system("cls"); cout<<"\n\n\t El Recorrido InOrden es:\n\n"; A.InOrden(A.raiz); break; case 6: system("cls"); cout<<"\n\n\t El Recorrido PostOrden es:\n\n"; A.PostOrden(A.raiz);

break; case 7: system("cls"); A.Salvar(); break; case 8: system("cls"); A.Recuperar(); break; case 9: exit(0); break; } getche(); } while (op!= 9); system("PAUSE"); return (0); }

Buscar:

Eliminar:

Comentario:

Con las implementaciones que se ha podido realizar y tomando en cuenta

los resultados obtenidos al medir el tiempo, puedo concluir que una Lista

Enlazada Simple demora mas para la BUSQUEDA y ELIMINACION.

Esta claro que una Lista enlazada Doble tiene sus ventajas como la

redimensión en tiempo de ejecución, pero resulta un gasto extra en

recursos (tiempo, en este caso).

Para los casos de BUSQUEDA entre el arreglo y Lista enlazada Doble,

se obtienen tiempos similares.

El que ha resultado mas económico en tiempo es el Arbol Binario, al cual

solo le ha tomado 0,04899799 milisegundos, siendo el menor tiempo

obtenido en esta tabla, pero fracasa al ELIMINAR un elemento, puesto

que el ARREGLO UNIDIMENSIONAL es mas veloz.

Hay que aclarar que solo se ha estado trabajando con 5 elementos, por

lo que al trabajar con mayor cantidad de elementos, el tiempo variaría y

colocaría al Arreglo Unidimensional en uno de los peores, puesto que

tanto para ELIMINAR necesita desplazar cierta cantidad de elementos,

mientras un árbol, solo tendría que modificar los punteros, al igual que

una lista enlazada doble y simple.

Estructura Tiempo (milisegundos)

Búsqueda Eliminación

Arreglo Unidimensional 0,08647476 0,08692600

Lista enlazada Simple 0,20769236 0,50284049

Lista enlazada Doble 0,07800723 --

Árbol Binario 0,04899799 0,12542800