Actividad de Aprendizaje 09 Lista simplemente ligada - 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 09. Lista simplemente ligada 
 
 
 
 
 
 
Alumno: Sandoval Padilla Fernando Cesar 
Docente: Gutiérrez Hernández Alfredo 
Código: 215685409 
Sección: D12 
 
 
 
 
 
 
 
 
 20 de Octubre de 2019 
Resumen personal: 
La realización de esta actividad fue bastante sencilla, ya que gran parte del modelo de la lista 
fue tomado de lo que se vio en clase, entonces realmente no fue difícil implementarla al main 
pues estaba bastante sencilla por lo que el único inconveniente fue el tener que hacer tantos 
recorridos por las condicionales y por los tipos de métodos a implementar. 
Código fuente: 
main.cpp 
1 #include <iostream> 
2 #include <stdlib.h> 
3 #include <string> 
4 #include "List.h" 
5 #include "Songs.h" 
6 using namespace std; 
7 int main() { 
8 setlocale(LC_ALL,"spanish"); 
9 List<Songs> myList; 
10 Songs mySong; 
11 Songs aux; 
12 string myStr; 
13 List<Songs>::Node* pos; 
14 char op; 
15 cout << "Bienvenido al programa" << endl; 
16 do { 
17 system("cls"); 
18 if(!myList.isEmpty()){ 
19 cout << myList.toString() << endl; 
20 } 
21 cout << "----------------Menu----------------" << endl; 
22 cout << "1) Añadir cancion" << endl; 
23 cout << "2) Eliminar cancion" << endl; 
24 cout << "3) Buscar cancion" <<endl; 
25 cout << "4) Otras opciones" << endl; 
26 cout << "5) Salir" << endl; 
27 cout << "Ingresa una opcion" << endl; 
28 cin >> op; 
29 op = toupper(op); 
30 switch(op) { 
31 case '1': 
32 cout << "Ingresa el nombre de la cancion" << endl << ">> "; 
33 cin.ignore(); 
34 getline(cin,myStr); 
35 mySong.setSongName(myStr); 
36 cout << "Ingresa el nombre del autor" << endl << ">> "; 
37 getline(cin,myStr); 
38 mySong.setSongAutor(myStr); 
39 cout << "Ingresa la posicion en el ranking" << endl << ">> "; 
40 getline(cin,myStr); 
41 mySong.setSongRanking(myStr); 
42 try { 
43 pos = myList.getFirstPos(); 
44 myList.insertData(pos,mySong); 
45 } 
46 catch(List<Songs>::Exception ex) { 
47 cout << ex.what() << endl; 
48 } 
49 break; 
50 case '2': 
51 cout << "Ingresa el nombre de la cancion " << endl << ">> "; 
52 cin.ignore(); 
53 getline(cin,myStr); 
54 aux.setSongName(myStr); 
55 pos = myList.findData(aux); 
56 try{ 
57 myList.deleteData(pos); 
58 } 
59 catch(List<Songs>::Exception ex){ 
60 cout << ex.what() << endl; 
61 } 
62 system("pause"); 
63 break; 
64 
65 case '3': 
66 cout << "Ingresa el nombre de la cancion " << endl << ">> "; 
67 cin.ignore(); 
68 getline(cin,myStr); 
69 aux.setSongName(myStr); 
70 pos = myList.findData(aux); 
71 if( pos != nullptr ){ 
72 cout << myList.retrieve(pos); 
73 } 
74 else{ 
75 cout << "No se encontro la cancion..." << endl; 
76 } 
77 system("pause"); 
78 break; 
79 system("pause"); 
80 
81 case '4': 
82 int other; 
83 cout<<"1.-Primer elemento: "<<endl; 
84 cout<<"2.-Ultimo elemento: "<<endl; 
85 cout<<"3.-Elemento anterior: "<<endl; 
86 cout<<"4.-Siguiente elemento: "<<endl; 
87 cout<<"5.-Eliminar todo: "<<endl; 
88 cin>>other; 
89 if (other==1) 
90 { 
91 if(myList.isEmpty()){ 
92 cout << "La lista esta vacia" << endl; 
93 } 
94 else{ 
95 cout << myList.retrieve(myList.getFirstPos()); 
96 } 
97 system("pause"); 
98 } 
99 if (other==2) 
100 { 
101 if(myList.isEmpty()){ 
102 cout << "La lista esta vacia" << endl; 
103 } 
104 else{ 
105 cout << myList.retrieve(myList.getLastPos()); 
106 } 
107 system("pause"); 
108 } 
109 
110 if (other==3) 
111 { 
112 if(!myList.isEmpty()){ 
113 cout << "Ingresa el nombre de la cancion " << endl; 
114 cin.ignore(); 
115 getline(cin,myStr); 
116 aux.setSongName(myStr); 
117 pos = myList.findData(aux); 
118 cout << myList.retrieve(myList.getPrevPos(pos)); 
119 } 
120 else{ 
121 cout << "La lista esta vacia" << endl; 
122 } 
123 system("pause"); 
124 } 
125 if (other==4) 
126 { 
127 if(!myList.isEmpty()){ 
128 cout << "Ingresa el nombre de la cancion " << endl; 
129 cin.ignore(); 
130 getline(cin,myStr); 
131 aux.setSongName(myStr); 
132 pos = myList.findData(aux); 
133 cout << myList.retrieve(myList.getNextPos(pos)); 
134 } 
135 else{ 
136 cout << "La lista esta vacia" << endl; 
137 } 
138 system("pause"); 
139 } 
140 if (other==5) 
141 { 
142 char myAux; 
143 cout << "Estas seguro de eliminar todo? [S/N] "<< endl << ">> "; 
144 do{ 
145 cin >> myAux; 
146 myAux = toupper(myAux); 
147 if(myAux == 'S'){ 
148 myList.deleteAll(); 
149 } 
150 } while( myAux != 'S' and myAux != 'N' ); 
151 break; 
152 case '5': 
153 cout << "Nos vemos..." << endl; 
154 } 
155 break; 
156 default: 
157 cout << "Ingresaste una opcion incorrecta " << endl << endl; 
158 break; 
159 } 
160 } 
161 while( op != '5' ); 
162 return 0; 
163 } 
List.h 
1 #ifndef LIST_H_INCLUDED 
2 #define LIST_H_INCLUDED 
3 
4 #include <string> 
5 #include <exception> 
6 
7 ///Definicion 
8 
9 template <class T> 
10 class List 
11 { 
12 public:///Ultima opcion 
13 ///class Node; 
14 class Node 
15 { 
16 private: 
17 T data; 
18 Node* next; 
19 
20 public: 
21 Node(); 
22 Node(const T&); 
23 
24 T& getData(); 
25 Node* getNext() const; 
26 
27 void setData(const T&); 
28 void setNext(Node*); 
29 }; 
30 
31 class Exception: public std::exception 
32 { 
33 private: 
34 std::string msg; 
35 
36 public: 
37 explicit Exception(const char* message) : msg(message) { } 
38 
39 explicit Exception(const std::string& message) : msg(message) { } 
40 
41 virtual ~Exception() throw () { } 
42 
43 virtual const char* what() const throw () { 
44 return msg.c_str(); 
45 } 
46 }; 
47 
48 private: 
49 Node* anchor; 
50 
51 bool isValidPos(Node*); 
52 
53 void copyAll(const List&); 
54 
55 public: 
56 
57 List(); 
58 List(const List&); 
59 
60 ~List(); 
61 
62 bool isEmpty() const; 
63 
64 void insertData(Node*, const T&); 
65 void deleteData(Node*); 
66 
67 Node* getFirstPos() const; 
68 Node* getLastPos() const; 
69 Node* getPrevPos(Node*) const; 
70 Node* getNextPos(Node*) const; 
71 
72 Node* findData(const T&) const; 
73 
74 T& retrieve(Node*); 
75 
76 std::string toString() const; 
77 
78 void deleteAll(); 
79 
80 List& operator = (const List&); 
81 }; 
82 
83 ///Implementacion 
84 
85 using namespace std; 
86 
87 ///Node 
88 
89 template <class T> 
90 List<T>::Node::Node() : next(nullptr) { } 
91 
92 template <class T> 
93 List<T>::Node::Node(const T& e) : data(e), next(nullptr) { } 
94 
95 template <class T> 
96 T& List<T>::Node::getData() 
97 { 
98 return data; 
99 } 
100 
101 template <class T> 
102 typename List<T>::Node* List<T>::Node::getNext() const 
103 { 
104 return next; 
105 } 
106 
107 template <class T> 
108 void List<T>::Node::setData(const T& e) 
109 { 
110 data = e; 
111 } 
112 
113 template <class T> 
114 void List<T>::Node::setNext(List<T>::Node* p) 
115 { 
116 next = p; 
117 } 
118 
119 ///List 
120 
121 template <class T> 
122 bool List<T>::isValidPos(List<T>::Node* p) 
123 { 
124 if(isEmpty()){ 
125 return false; 
126 } 
127 
128 Node* aux(anchor); 
129 
130 do 
131 { 
132 if(aux == p) 
133 { 
134 return true; 
135 } 
136 
137 aux = aux->getNext(); 
138 }while(aux != anchor); 
139 
140 return false; 
141 } 
142 
143 template <class T> 
144 void List<T>::copyAll(const List<T>& l) 
145 { 
146 if(l.isEmpty()){ 
147 return; 
148 } 
149 
150 Node* aux(l.anchor); 
151 Node* lastInserted(nullptr); 
152 Node* newNode; 
153 do{ 
154 newNode = new Node(aux->getData()); 
155 
156 if(newNode == nullptr) 
157 { 
158 throw Exception("Memoria no disponible, copyAll"); 
159 } 
160 
161 if(lastInserted == nullptr) 
162 { 
163 anchor = newNode; 
164 } 
165 else 
166 { 
167 lastInserted->setNext(newNode); 
168 } 
169 
170 lastInserted = newNode; 
171 
172 aux = aux->getNext(); 
173 }while(aux!= l.anchor); 
174 
175 lastInserted->setNext(anchor); 
176 } 
177 
178 template <class T> 
179 List<T>::List() : anchor(nullptr) { } 
180 
181 template <class T> 
182 List<T>::List(const List<T>& l) : anchor(nullptr) 
183 { 
184 copyAll(l); 
185 } 
186 
187 template <class T> 
188 List<T>::~List() 
189 { 
190 deleteAll(); 
191 } 
192 
193 template <class T> 
194 List<T>& List<T>::operator = (const List<T>& l) 
195 { 
196 deleteAll(); 
197 
198 copyAll(l); 
199 
200 return *this; 
201 } 
202 
203 template <class T> 
204 bool List<T>::isEmpty() const 
205 { 
206 return anchor == nullptr; 
207 } 
208 
209 template <class T> 
210 void List<T>::insertData(List<T>::Node* p, const T& e) 
211 { 
212 if(p != nullptr and !isValidPos(p)) 
213 { 
214 throw Exception(" Posicion invalida, insertData"); 
215 } 
216 
217 Node* aux(new Node(e)); 
218 
219 if(aux == nullptr) 
220 { 
221 throw Exception(" Memoria no disponible, insertData"); 
222 } 
223 
224 if(p == nullptr) 
225 {///Insertar al principio 
226 if(isEmpty()){///Inserta el primer elemento 
227 aux->setNext(aux); 
228 } 
229 else{///Hay más de un elemento 
230 aux->setNext(anchor); 
231 
232 getLastPos()->setNext(aux); 
233 } 
234 
235 anchor = aux; 
236 } 
237 else 
238 {///Insertar en cualquier otra posicion 
239 aux->setNext(p->getNext()); 
240 
241 p->setNext(aux); 
242 } 
243 } 
244 
245 template <class T> 
246 void List<T>::deleteData(List<T>::Node* p) 
247 { 
248 if(!isValidPos(p)) 
249 { 
250 throw Exception(" Posicion invalida, deleteData."); 
251 } 
252 
253 if(p == anchor) 
254 {///Eliminar el primero 
255 if(p->getNext() == p){///Esta solito 
256 anchor = nullptr; 
257 } 
258 else{///Hay más de un elemento 
259 getLastPos()->setNext(anchor->getNext()); 
260 } 
261 } 
262 else 
263 {///Eliminar cualquiera otro 
264 getPrevPos(p)->setNext(p->getNext()); 
265 } 
266 
267 delete p; 
268 } 
269 
270 template <class T> 
271 typename List<T>::Node* List<T>::getFirstPos() const 
272 { 
273 return anchor; 
274 } 
275 
276 template <class T> 
277 typename List<T>::Node* List<T>::getLastPos() const 
278 { 
279 if(isEmpty()) 
280 { 
281 return nullptr; 
282 } 
283 
284 Node* aux(anchor); 
285 
286 while(aux->getNext() != anchor) 
287 { 
288 aux = aux->getNext(); 
289 } 
290 
291 return aux; 
292 } 
293 
294 template <class T> 
295 typename List<T>::Node* List<T>::getPrevPos(List<T>::Node* p) const 
296 { 
297 /*if(isEmpty() or p->getNext() == anchor) 
298 { 
299 return nullptr; 
300 }*/ 
301 if(isEmpty()){ 
302 return nullptr; 
303 } 
304 
305 Node* aux(anchor); 
306 
307 do 
308 { 
309 if(aux->getNext() == p){ 
310 return aux; 
311 } 
312 
313 aux = aux->getNext(); 
314 }while(aux != anchor); 
315 
316 return nullptr; 
317 } 
318 
319 template <class T> 
320 typename List<T>::Node* List<T>::getNextPos(List<T>::Node* p) const 
321 { 
322 /*if(!isValidPos(p) or p->getNext() == anchor) 
323 { 
324 return nullptr; 
325 }*/ 
326 
327 return p->getNext(); 
328 } 
329 
330 template <class T> 
331 typename List<T>::Node* List<T>::findData(const T& e) const 
332 { 
333 if(isEmpty()){ 
334 return nullptr; 
335 } 
336 
337 Node* aux(anchor); 
338 do{ 
339 if(aux->getData() == e){ 
340 return aux; 
341 } 
342 
343 aux = aux->getNext(); 
344 }while(aux != anchor); 
345 
346 return nullptr; 
347 } 
348 
349 template <class T> 
350 T& List<T>::retrieve(List<T>::Node* p) 
351 { 
352 if(!isValidPos(p)) 
353 { 
354 throw Exception(" Posicion invalida, retireve"); 
355 } 
356 
357 return p->getData(); 
358 } 
359 
360 template <class T> 
361 std::string List<T>::toString() const 
362 { 
363 
364 std::string result; 
365 
366 if(!isEmpty()){ 
367 Node* aux(anchor); 
368 do{ 
369 result += aux->getData().toString() + "\n"; 
370 
371 aux = aux->getNext(); 
372 }while(aux != anchor); 
373 } 
374 
375 return result; 
376 } 
377 
378 template <class T> 
379 void List<T>::deleteAll() 
380 { 
381 if(isEmpty()){ 
382 return; 
383 } 
384 
385 Node* mark(anchor); 
386 Node* aux; 
387 
388 do{ 
389 aux = anchor; 
390 
391 anchor = anchor->getNext(); 
392 
393 delete aux; 
394 }while(anchor != mark); 
395 
396 anchor = nullptr; 
397 } 
398 
399 #endif // LIST_H_INCLUDED 
400 
Songs.h 
1 #ifndef SONGS_H 
2 #define SONGS_H 
3 
4 #include <iostream> 
5 #include <string> 
6 class Songs { 
7 private: 
8 std::string SongName; 
9 std::string SongAutor; 
10 std::string SongRanking; 
11 public: 
12 void setSongName(const std::string&); 
13 void setSongAutor(const std::string&); 
14 void setSongRanking(const std::string&); 
15 std::string toString() const; 
16 std::string getSongName() const; 
17 std::string getSongAutor() const; 
18 std::string getSongRanking() const; 
19 bool operator == (const Songs&) const; 
20 bool operator != (const Songs&) const; 
21 bool operator >= (const Songs&) const; 
22 bool operator > (const Songs&) const; 
23 bool operator <= (const Songs&) const; 
24 bool operator < (const Songs&) const; 
25 friend std::ostream& operator << (std::ostream&, Songs&); 
26 friend std::istream& operator >> (std::istream&, Songs&); 
27 }; 
28 
29 #endif // SONGS_H 
Songs.cpp 
1 #include "songs.h" 
2 void Songs::setSongName(const std::string& Name) { 
3 SongName = Name; 
4 } 
5 void Songs::setSongAutor(const std::string& Autor) { 
6 SongAutor = Autor; 
7 } 
8 void Songs::setSongRanking(const std::string& Ranking) { 
9 SongRanking = Ranking; 
10 } 
11 std::string Songs::toString() const { 
12 std::string AllSong; 
13 AllSong += SongName; 
14 AllSong += " | "; 
15 AllSong += SongAutor; 
16 AllSong += " | "; 
17 AllSong += SongRanking; 
18 return AllSong; 
19 } 
20 std::string Songs::getSongName() const { 
21 return SongName; 
22 } 
23 std::string Songs::getSongAutor() const { 
24 return SongAutor; 
25 } 
26 std::string Songs::getSongRanking() const { 
27 return SongRanking; 
28 } 
29 bool Songs::operator == (const Songs& Song) const { 
30 return SongName == Song.SongName or SongAutor == Song.SongAutor; 
31 } 
32 bool Songs::operator != (const Songs& Song) const { 
33 return SongName != Song.SongName or SongAutor != Song.SongAutor; 
34 } 
35 bool Songs::operator >= (const Songs& Song) const { 
36 return SongName >= Song.SongName or SongAutor >= Song.SongAutor; 
37 } 
38 bool Songs::operator > (const Songs& Song) const { 
39 return SongName > Song.SongName or SongAutor > Song.SongAutor; 
40 } 
41 bool Songs::operator <= (const Songs& Song) const { 
42 return SongName <= Song.SongName or SongAutor <= Song.SongAutor; 
43 } 
44 bool Songs::operator < (const Songs& Song) const { 
45 return SongName < Song.SongName or SongAutor < Song.SongAutor; 
46 } 
47 std::ostream& operator << (std::ostream& os, Songs& s){ 
48 std::string aux; 
49 aux = s.SongName + " | " + s.SongAutor + " | " + s.SongRanking + "\n"; 
50 os << aux; 
51 return os; 
52 } 
53 std::istream& operator >> (std::istream& is, Songs& s){ 
54 is >> s.SongAutor; 
55 is >> s.SongAutor; 
56 is >> s.SongRanking; 
57 return is; 
58 } 
 
Capturas de pantalla: 
Menu
 
Opción 1 
 
Opción 2 
 
 
Opción 3 
 
Opcion 4 
 
Opción 1 
 
Opción 2 
 
Opción 3 
 
Opción 4 
 
Opcion 5