Actividad de Aprendizaje 05 Métodos de Búsqueda - Fernando Cesar Sandoval Padilla

Vista previa del material en texto

UNIVERSIDAD DE GUADALAJARA 
Centro Universitario de Ciencias Exactas e Ingenierías 
 
Estructura de datos I 
Actividad de Aprendizaje 05. Métodos de búsqueda 
 
 
 
 
 
 
Alumno: Sandoval Padilla Fernando Cesar 
Docente: Gutiérrez Hernández Alfredo 
Código: 215685409 
Sección: D12 
 
 
 
 
 
 
 
 
 21 de Septiembre de 2019 
Resumen personal: 
 
Básicamente la realización de esta actividad fue literalmente sencilla, solo por el 
simple hecho de poder o tener que reutilizar la actividad 3 e implementar los dos 
métodos de búsqueda, el binario y el lineal, en cual sinceramente prefiero el método 
lineal, pues así no es necesario tener en orden alfabético la lista ya que si no estaba 
en orden el binario solo mostraba lo primero que se encontrara según el orden 
alfabético. 
Código fuente: 
main.cpp 
 1 #include <windows.h> 
 2 #include <iostream> 
 3 #include <cstdlib> 
 4 #include "Lista.h" 
 5 
 6 using namespace std; 
 7 int main() 
 8 { 
 9 setlocale(LC_ALL,"spanish"); 
 10 Musicbox pistas; 
 11 char op, op2; 
 12 int Intpos; 
 13 string ncancion, nautor, nraking; 
 14 cout << "Programa, lista de canciones..." << endl ; 
 15 Sleep(500); 
 16 do 
 17 { 
 18 system("cls"); 
 19 if(pistas.getlast() != -1) 
 20 { 
 21 for(int x=0; x <= pistas.getlast(); x++) 
 22 { 
 23 cout<<pistas.seeAll(x)<<endl<<"Posicion: "<<x<<endl<<endl<<endl; 
 24 } 
 25 } 
 26 if(pistas.getlast() == -1) 
 27 { 
 28 cout<<"No se encuentra ninguna cancion en la lista"<<endl<<endl<<endl; 
 29 } 
 30 cout << "----------Menu----------" << endl ; 
 31 cout << "1) Añadir Cancion" << endl; 
 32 cout << "2) Eliminar Cancion" << endl; 
 33 cout << "3) Otras opciones" << endl; 
 34 cout << "4) Buscar cancion" << endl; 
 35 cout << "5) Salir" << endl; 
 36 cin >> op; 
 37 
 38 op = toupper(op); 
 39 
 40 switch (op) { 
 41 case '1': 
 42 cin.ignore(); 
 43 cout << "Ingresa el nombre de la cancion >> "; 
 44 getline(cin,ncancion); 
 45 cout << "Ingresa el nombre del Autor >> "; 
 46 getline(cin,nautor); 
 47 cout << "Ingresa la posicion del ranking >> "; 
 48 cin >> nraking; 
 49 try { 
 50 pistas.insertMusic(ncancion,nautor,nraking); 
 51 } catch(Musicbox::Exception ex) { 
 52 cout << ex.what() << endl; 
 53 } 
 54 cin.ignore(); 
 55 break; 
 56 case '2': 
 57 cout << "Ingresa la posicion de la cancion a borrar : "; 
 58 cin>>Intpos; 
 59 try { 
 60 pistas.deleteMusic(Intpos); 
 61 } catch(Musicbox::Exception ex) { 
 62 cout << ex.what() << endl; 
 63 } 
 64 break; 
 65 case '3': 
 66 int other; 
 67 cout<<"1.-Primer elemento: "<<endl; 
 68 cout<<"2.-Ultimo elemento: "<<endl; 
 69 cout<<"3.-Elemento anterior: "<<endl; 
 70 cout<<"4.-Siguiente elemento: "<<endl; 
 71 cout<<"5.-Eliminar todo: "<<endl; 
 72 cout<<"6.-Recuperar elemento: "<<endl; 
 73 cin>>other; 
 74 if (other==1) 
 75 { 
 76 try { 
 77 cout << pistas.firstMusic() << endl << endl; 
 78 } catch(Musicbox::Exception ex) { 
 79 cout << ex.what() << endl; 
 80 } 
 81 system("pause"); 
 82 } 
 83 else if (other==2) 
 84 { 
 85 try { 
 86 cout<<pistas.lastMusic() << endl << endl; 
 87 } catch(Musicbox::Exception ex) { 
 88 cout << ex.what() << endl; 
 89 } 
 90 system("pause"); 
 91 } 
 92 else if (other==3) 
 93 { 
 94 cout << "Ingresa la posicion para ver el anterior a esta: "; 
 95 cin>>Intpos; 
 96 try { 
 97 cout << pistas.prevMusic(Intpos) << endl << endl; 
 98 } catch(Musicbox::Exception ex) { 
 99 cout << ex. what() << endl << endl << endl; 
100 } 
101 system("pause"); 
102 } 
103 else if (other==4) 
104 { 
105 cout << "Ingresa la posicion para ver la siguiente a esta: "; 
106 cin>>Intpos; 
107 try { 
108 cout << pistas.nextMusic(Intpos) << endl << endl; 
109 } catch(Musicbox::Exception ex) { 
110 cout << ex. what() << endl << endl << endl; 
111 } 
112 system("pause"); 
113 } 
114 else if (other==5) 
115 { 
116 do { 
117 cout<< "Estas seguro? [S/N] >> "; 
118 cin>>op2; 
119 cin.ignore(); 
120 op2 = toupper(op2); 
121 } while(op2 != 'S' and op2!= 'N'); 
122 if (op2 == 'S') 
123 pistas.deleteAll(); 
124 system("pause"); 
125 } 
126 else if (other==6) 
127 { 
128 cout << "Proporciona el nombre de la cancion a recuperar: "; 
129 getline(cin,ncancion); 
130 try { 
131 cout << pistas.recoverMusic(ncancion); 
132 } catch(Musicbox::Exception ex) { 
133 cout << ex.what() << endl; 
134 } 
135 system("pause"); 
136 } 
137 else{ 
138 cout<<"Opcion inexistente"<<endl; 
139 system("pause"); 
140 } 
141 break; 
142 case '4': 
143 do { 
144 cout << "Menú" << endl; 
145 cout << "a) Busqueda binaria" << endl; 
146 cout << "b) Busqueda lineal" << endl; 
147 cout << "c) Regresar" << endl; 
148 cout << "Ingresa una opcion >> "; 
149 cin >> op; 
150 op = toupper(op); 
151 switch(op) { 
152 case 'A': 
153 cin.ignore(); 
154 cout << "Ingrese el nombre a buscar >> "; 
155 getline(cin,ncancion); 
156 try { 
157 Intpos = pistas.FindDataB(ncancion); 
158 } 
159 catch (Musicbox::Exception ex) { 
160 cout << ex.what() << endl; 
161 } 
162 if( Intpos == -1 ) { 
163 cout << "No se encontro la cancion" << endl; 
164 } 
165 else { 
166 cout << pistas.seeAll(Intpos) << endl; 
167 } 
168 break; 
169 case 'B': 
170 cin.ignore(); 
171 cout << "Ingrese la cancion a buscar >> "; 
172 getline(cin,ncancion); 
173 try { 
174 Intpos = pistas.FindDataL(ncancion); 
175 } 
176 catch (Musicbox::Exception ex) { 
177 cout << ex.what() << endl; 
178 } 
179 if( Intpos == -1 ) { 
180 cout << "No se encontro la cancion" << endl; 
181 } 
182 else { 
183 cout << pistas.seeAll(Intpos) << endl; 
184 } 
185 break; 
186 case 'C': 
187 break; 
188 default: 
189 cout << "Se ha ingresado una opcion incorrecta, intente de nuevo" << endl << endl; 
190 } 
191 } 
192 while(op!='C'); 
193 break; 
194 
195 case '5': 
196 cout << "Nos vemos..." << endl; 
197 break; 
198 
199 default: 
200 cout << "Error, opcion invalida o inexistente" << endl << endl ; 
201 } 
202 } while(op!='5'); 
203 system("pause"); 
204 return 0; 
205 } 
Lista.h 
1 #ifndef LISTA_H 
 2 #define LISTA_H 
 3 #include "Musica.h" 
 4 class Musicbox { 
 5 private: 
 6 int Last; 
 7 int Deleted; 
 8 Musica AllMusic[3000]; 
 9 Musica DeletedMusic[3000]; 
10 public: 
11 
12 class Exception : public std::exception { 
13 private: 
14 std::string msg; 
15 public: 
16 explicit Exception(const char* message) : msg(message) { } 
17 
18 explicit Exception(const std::string& message) : msg(message) { } 
19 
20 virtual ~Exception() throw () { } 
21 
22 virtual const char* what() const throw() { 
23 return msg.c_str(); 
24 } 
25 }; 
26 int getlast(); 
27 Musicbox(); 
28 bool isFull(); 
29 bool isEmpty(); 
30 bool isValidPos(const int&); 
31 void insertMusic(const std::string&,const std::string&,const std::string&); 
32 void deleteMusic(const int&); 
33 std::string recoverMusic(std::string&); 
34 int FindDataL(const std::string&); 
35 int FindDataB(const std::string&); 
36 std::string firstMusic(); 
37 std::string lastMusic(); 
38 std::string prevMusic(const int&); 
39 std::string nextMusic(const int&); 
40 std::string seeAll(const int&); 
41 void deleteAll(); 
42 }; 
43 
44 #endif // LISTA_H 
Lista.cpp 
 1 #include "Lista.h" 
 2 Musicbox::Musicbox() { 
 3 Last=-1; 
 4 Deleted=-1; 
 5 } 
 67 bool Musicbox::isFull() { 
 8 return Last==2999; 
 9 } 
 10 
 11 bool Musicbox::isEmpty() { 
 12 return Last==-1; 
 13 } 
 14 
 15 bool Musicbox::isValidPos(const int& Pos) { 
 16 return Pos>-1 and Pos<=Last+1; 
 17 } 
 18 
 19 void Musicbox::insertMusic(const std::string& Name, const std::string& Autor, const 
std::string& Rank) { 
 20 if(isFull()) { 
 21 throw Exception("Desbordamiento de datos, insertMusic"); 
 22 } 
 23 Last++; 
 24 AllMusic[Last].setSongName(Name); 
 25 AllMusic[Last].setSongAutor(Autor); 
 26 AllMusic[Last].setRanking(Rank); 
 27 } 
 28 
 29 void Musicbox::deleteMusic(const int& Pos) { 
 30 if(isEmpty()) { 
 31 throw Exception("Insuficiencia de datos,deleteMusic"); 
 32 } 
 33 if(!isValidPos(Pos)) { 
 34 throw Exception("Posicion invalida,deleteMusic"); 
 35 } 
 36 
 37 if(Deleted<50) { 
 38 Deleted++; 
 39 DeletedMusic[Deleted].setSongName(AllMusic[Pos].getSongName()); 
 40 DeletedMusic[Deleted].setSongAutor(AllMusic[Pos].getSongAutor()); 
 41 DeletedMusic[Deleted].setRanking(AllMusic[Pos].getRanking()); 
 42 } 
 43 int i = Pos; 
 44 while(i<=Last) { 
 45 AllMusic[i].setSongName(AllMusic[i+1].getSongName()); 
 46 AllMusic[i].setSongAutor(AllMusic[i+1].getSongAutor()); 
 47 AllMusic[i].setRanking(AllMusic[i+1].getRanking()); 
 48 i++; 
 49 } 
 50 Last--; 
 51 } 
 52 
 53 std::string Musicbox::recoverMusic(std::string& Name) { 
 54 if(Deleted==-1) { 
 55 throw Exception("Insuficiencia de datos,recoverMusic"); 
 56 } 
 57 int band; 
 58 for(int i=0; i<=Deleted; i++){ 
 59 if(DeletedMusic[i].getSongName() == Name){ 
 60 band=i; 
 61 } 
 62 } 
 63 return DeletedMusic[band].toString(); 
 64 } 
 65 int Musicbox::FindDataB(const std::string& Name) { 
 66 if(isEmpty()) { 
 67 throw Exception("Insuficiencia de datos, FindDataB"); 
 68 } 
 69 int i=0, j=Last, m; 
 70 while(i<=j) { 
 71 m = (i + j) / 2; 
 72 if( AllMusic[m].getSongName() == Name or AllMusic[m].getSongAutor() == Name) { 
 73 return m; 
 74 } 
 75 if( AllMusic[m].getSongName() < Name or AllMusic[m].getSongAutor() < Name ) { 
 76 i= m + 1; 
 77 } 
 78 else { 
 79 j = m - 1; 
 80 } 
 81 } 
 82 return -1; 
 83 } 
 84 int Musicbox::FindDataL(const std::string& Name) { 
 85 if(isEmpty()) { 
 86 throw Exception("Insuficiencia de datos, FindDataL"); 
 87 } 
 88 for(int i = 0 ; i <= Last ; i++) { 
 89 if( AllMusic[i].getSongName() == Name or AllMusic[i].getSongAutor() == Name ) { 
 90 return i; 
 91 } 
 92 } 
 93 return -1; 
 94 } 
 95 
 96 std::string Musicbox::firstMusic() { 
 97 if(isEmpty()){ 
 98 throw Exception("Insuficiencia de datos,firstMusic"); 
 99 } 
100 return AllMusic[0].toString(); 
101 } 
102 
103 std::string Musicbox::lastMusic() { 
104 if(isEmpty()){ 
105 throw Exception ("Insuficiencia de datos,lastMusic"); 
106 } 
107 return AllMusic[Last].toString(); 
108 } 
109 
110 std::string Musicbox::prevMusic(const int& Pos) { 
111 if(isEmpty() or Last==0){ 
112 throw Exception("Insuficiencia de datos,prevMusic"); 
113 } 
114 if(!isValidPos(Pos)){ 
115 throw Exception("Posicion invalida,prevMusic"); 
116 } 
117 return AllMusic[Pos-1].toString(); 
118 } 
119 
120 std::string Musicbox::nextMusic(const int& Pos) { 
121 if(isEmpty()){ 
122 throw Exception("Insuficiencia de datos,nextMusic"); 
123 } 
124 if(!isValidPos(Pos)){ 
125 throw Exception("Posicion invalida,nextMusic"); 
126 } 
127 return AllMusic[Pos+1].toString(); 
128 } 
129 
130 std::string Musicbox::seeAll(const int& Pos){ 
131 return AllMusic[Pos].toString(); 
132 } 
133 
134 void Musicbox::deleteAll() { 
135 if(isEmpty()){ 
136 throw Exception("Insuficiencia de datos,deleteAll"); 
137 } 
138 Last=-1; 
139 Deleted=-1; 
140 } 
141 
142 int Musicbox::getlast(){ 
143 return Last; 
144 } 
Musica.h 
1 #ifndef MUSICA_H 
 2 #define MUSICA_H 
 3 #include <string> 
 4 
 5 class Musica { 
 6 private: 
 7 std::string SongName; 
 8 std::string SongAutor; 
 9 std::string Ranking; 
10 public: 
11 Musica(); 
12 std::string getSongName(); 
13 std::string getSongAutor(); 
14 std::string getRanking(); 
15 void setSongName(const std::string&); 
16 void setSongAutor(const std::string&); 
17 void setRanking(const std::string&);; 
18 std::string toString(); 
19 }; 
20 #endif // MUSICA_H 
Musica.cpp 
1 #include "Musica.h" 
 2 #include <cstdio> 
 3 
 4 Musica::Musica() { 
 5 SongAutor=""; 
 6 SongName=""; 
 7 Ranking=""; 
 8 } 
 9 
10 std::string Musica::getSongName() { 
11 return SongName; 
12 } 
13 
14 std::string Musica::getSongAutor() { 
15 return SongAutor; 
16 } 
17 
18 std::string Musica::getRanking() { 
19 return Ranking; 
20 } 
21 
22 void Musica::setSongName(const std::string& Name) { 
23 SongName = Name; 
24 } 
25 
26 void Musica::setSongAutor(const std::string& Autor) { 
27 SongAutor = Autor; 
28 } 
29 
30 void Musica::setRanking(const std::string& Rank) { 
31 Ranking = Rank; 
32 } 
33 
34 std::string Musica::toString() { 
35 std::string CompleteSong; 
36 CompleteSong+="Nombre : "; 
37 CompleteSong+=SongName; 
38 CompleteSong+="\nAutor : "; 
39 CompleteSong+=SongAutor; 
40 CompleteSong+="\nRanking : "; 
41 CompleteSong+=Ranking; 
42 
43 return CompleteSong; 
44 } 
Capturas de pantalla: