Actividad de Aprendizaje 10 La lista implementacion dinamica doblemente 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 10. La lista implementación dinámica doblemente ligada 
 
 
 
 
 
 
Alumno: Sandoval Padilla Fernando Cesar 
Docente: Gutiérrez Hernández Alfredo 
Código: 215685409 
Sección: D12 
 
 
 
 
 
 
 
 
 02 de Noviembre de 2019 
Resumen personal: 
Básicamente la realización de esta actividad fue sencilla y solo se tuvo que intercambiar lo lineal 
de la lista anterior y tomar en cuenta que siempre hay un anterior a cada nodo, además la 
sobrecarga es la misma, el programa solo cambia por el encapsulamiento. 
Código fuente: 
main.cpp 
1 #include <iostream> 
2 #include <conio.h> 
3 #include <cstdlib> 
4 #include <cctype> 
5 #include <cstdio> 
6 #include <string> 
7 #include "songs.h" 
8 #include "list.h" 
9 using namespace std; 
10 int main() { 
11 List<Songs> myLista; 
12 Songs c; 
13 List<Songs>::Node* pos; 
14 string myStr; 
15 int op,op2; 
16 char opc,opc2; 
17 do { 
18 cout<<"###Lista de canciones###"<<endl; 
19 cout << myLista.toString() << endl; 
20 cout<<endl; 
21 cout<<"####Bienvenido al menu del album####"<<endl<<endl; 
22 cout<<"1. Insertar cancion"<<endl; 
23 cout<<"2. Eliminar cancion"<<endl; 
24 cout<<"3. Buscar una cancion (lineal)"<<endl; 
25 cout<<"4. Otras opciones" <<endl; 
26 cout<<"5. Salir"<<endl; 
27 cout<<"Seleccione una opcion:"; 
28 cin>>op; 
29 cin.get(); 
30 switch(op) { 
31 case 1: 
32 do { 
33 cout << endl; 
34 cout << " ####INSERTAR CANCION#### "<<endl; 
35 cout << " Nombre de la cancion: "<<endl; 
36 getline(cin,myStr); 
37 c.setSongName(myStr); 
38 cout << "Nombre del interprete:" << endl; 
39 getline(cin, myStr); 
40 c.setSongAutor(myStr); 
41 cout << "Ranking de la cancion (1-10):" << endl; 
42 cin>>myStr; 
43 c.setSongRanking(myStr); 
44 try { 
45 pos = myLista.getLastPos(); 
46 myLista.insertData(pos, c); 
47 } 
48 catch (List<Songs>::Exception ex) { 
49 cout << ex.what() << endl; 
50 break; 
51 } 
52 cout << endl << " cancion insertada exitosamente" << endl << endl; 
53 do { 
54 cout << " Insertar otro? (S/N): "; 
55 cin >> opc; 
56 cin.ignore(); 
57 opc = toupper(opc); 
58 } 
59 while(opc != 'S' and opc != 'N'); 
60 } 
61 while(opc == 'S'); 
62 cout << endl << endl; 
63 system("pause"); 
64 system("cls"); 
65 break; 
66 case 2: 
67 cout << " ####ELIMINAR CANCION#### "<<endl; 
68 cout << "Nombre de la cancion a eliminar:" << endl; 
69 getline(cin, myStr); 
70 c.setSongName(myStr); 
71 pos = myLista.findData(c); 
72 try { 
73 myLista.deleteData(pos); 
74 } 
75 catch (List<Songs>::Exception ex) { 
76 cout << ex.what() << endl; 
77 } 
78 cout << "Cancion Eliminada con exito!!" << endl; 
79 system("pause"); 
80 system("cls"); 
81 break; 
82 case 3: 
83 cout << " ####BUSCAR CANCION (LINEAL)#### "<<endl; 
84 cout << "Nombre de la cancion a buscar:" << endl; 
85 getline(cin,myStr); 
86 c.setSongName(myStr); 
87 pos = myLista.findData(c); 
88 cout<<myLista.retrieve(pos).toString()<<endl; 
89 cout<<endl; 
90 system("pause"); 
91 system("cls"); 
92 break; 
93 case 4: 
94 cout<<"1. Mostrar primera cancion de la lista"<<endl; 
95 cout<<"2. Mostrar ultima cancion de la lista"<<endl; 
96 cout<<"3. Mostrar cancion anterior"<<endl; 
97 cout<<"4. Mostrar cancion siguiente"<<endl; 
98 cout<<"5. Eliminar todo"<<endl; 
99 cout<<"Seleccione una opcion"<<endl; 
100 cin>>op2; 
101 switch (op2) 
102 { 
103 case 1: 
104 cout << " ####PRIMERA CANCION#### "<<endl; 
105 cout << myLista.retrieve(myLista.getFirstPos()).toString() << endl; 
106 cout<<endl; 
107 system("pause"); 
108 system("cls"); 
109 break; 
110 case 2: 
111 cout << " ####ULTIMA CANCION#### "<<endl; 
112 cout <<myLista.retrieve(myLista.getLastPos()).toString() << endl; 
113 cout<<endl; 
114 system("pause"); 
115 system("cls"); 
116 break; 
117 case 3: 
118 cout << " ####CANCION ANTERIOR#### "<<endl; 
119 cout << "Nombre de la cancion para mostrar su anterior:" << endl; 
120 getline(cin, myStr); 
121 c.setSongName(myStr); 
122 pos = myLista.findData(c); 
123 try { 
124 cout << myLista.retrieve(myLista.getPrevPos(pos)).toString() << endl; 
125 cout<<endl; 
126 } 
127 catch (List<Songs>::Exception ex) { 
128 cout << ex.what() << endl; 
129 } 
130 system("pause"); 
131 system("cls"); 
132 break; 
133 case 4: 
134 cout << " ####SIGUIENTE CANCION#### "<<endl; 
135 cout << "Nombre de la cancion para mostrar su siguiente:" << endl; 
136 getline(cin, myStr); 
137 c.setSongName(myStr); 
138 pos = myLista.findData(c); 
139 try { 
140 cout << myLista.retrieve(myLista.getNextPos(pos)).toString()<<endl; 
141 } 
142 catch (List<Songs>::Exception ex) { 
143 cout << ex.what() << endl; 
144 } 
145 cout << endl; 
146 system("pause"); 
147 system("cls"); 
148 break; 
149 
150 case 5: 
151 cout << " ####ELIMINAR TODO#### "<<endl; 
152 do { 
153 cout << " Seguro de que desea eliminar todo? (S/N): "; 
154 cin >> opc2; 
155 cin.ignore(); 
156 opc2 = toupper(opc2); 
157 system("cls"); 
158 } 
159 while(opc2 != 'S' and opc2 != 'N'); 
160 if(opc2 == 'S') { 
161 try { 
162 myLista.deleteAll(); 
163 } 
164 catch (List<Songs>::Exception ex) { 
165 cout << ex.what() << endl; 
166 } 
167 } 
168 cout<<"SE HA ELIMINADO TODO"<<endl; 
169 system("pause"); 
170 system("cls"); 
171 break; 
172 default: 
173 cout<<"Opcion invalida, vuelva a intentarlo!!"<<endl; 
174 } 
175 case 5: 
176 cout<<"Nos vemos!!"<<endl; 
177 break; 
178 default: 
179 cout<<"Opcion invalida, vuelva a intentarlo!!"<<endl; 
180 break; 
181 } 
182 } 
183 while (op!=5); 
184 return 0; 
185 } 
List.h 
1 #ifndef LIST_H_INCLUDED 
2 #define LIST_H_INCLUDED 
3 #include <string> 
4 #include <exception> 
5 ///Definicion 
6 template <class T> 
7 class List 
8 { 
9 public:///Ultima opcion 
10 ///class Node; 
11 class Node 
12 { 
13 private: 
14 T data; 
15 Node* next; 
16 public: 
17 Node(); 
18 Node(const T&); 
19 T& getData(); 
20 Node* getNext() const; 
21 void setData(const T&); 
22 void setNext(Node*); 
23 }; 
24 class Exception: public std::exception 
25 { 
26 private: 
27 std::string msg; 
28 public: 
29 explicit Exception(const char* message) : msg(message) { } 
30 explicit Exception(const std::string& message) : msg(message) { } 
31 virtual ~Exception() throw () { } 
32 virtual const char* what() const throw () { 
33 return msg.c_str(); 
34 } 
35 }; 
36 private: 
37 Node* anchor; 
38 bool isValidPos(Node*); 
39 void copyAll(const List&); 
40 public: 
41 List(); 
42 List(const List&); 
43 ~List(); 
44 bool isEmpty() const; 
45 void insertData(Node*, const T&); 
46 void deleteData(Node*); 
47 Node* getFirstPos() const; 
48 Node* getLastPos() const; 
49 Node* getPrevPos(Node*) const; 
50 Node* getNextPos(Node*) const; 
51 Node* findData(const T&) const; 
52 T& retrieve(Node*); 
53 std::string toString() const; 
54 void deleteAll(); 
55 List& operator = (const List&); 
56 }; 
57 ///Implementacion 
58 using namespace std; 
59 ///Node 
60 template <class T> 
61 List<T>::Node::Node() : next(nullptr) { } 
62 template <class T> 
63 List<T>::Node::Node(const T& e) : data(e), next(nullptr) { } 
64 template <class T> 
65 T& List<T>::Node::getData() 
66 { 
67 return data; 
68 } 
69 template <class T> 
70 typename List<T>::Node* List<T>::Node::getNext() const 
71 { 
72 return next; 
73 } 
74 template <class T> 
75 void List<T>::Node::setData(const T& e) 
76 { 
77 data = e; 
78 } 
79 template <class T> 
80 void List<T>::Node::setNext(List<T>::Node* p) 
81 { 
82 next = p; 
83 } 
84 ///List 
85 template <class T> 
86 bool List<T>::isValidPos(List<T>::Node* p) 
87 { 
88 if(isEmpty()){ 
89 return false; 
90 } 
91 Node* aux(anchor); 
92 do 
93 { 
94 if(aux == p) 
95 { 
96 return true; 
97 } 
98 aux = aux->getNext(); 
99 }while(aux != anchor); 
100 return false;101 } 
102 template <class T> 
103 void List<T>::copyAll(const List<T>& l) 
104 { 
105 if(l.isEmpty()){ 
106 return; 
107 } 
108 Node* aux(l.anchor); 
109 Node* lastInserted(nullptr); 
110 Node* newNode; 
111 do{ 
112 newNode = new Node(aux->getData()); 
113 if(newNode == nullptr) 
114 { 
115 throw Exception("Memoria no disponible, copyAll"); 
116 } 
117 if(lastInserted == nullptr) 
118 { 
119 anchor = newNode; 
120 } 
121 else 
122 { 
123 lastInserted->setNext(newNode); 
124 } 
125 lastInserted = newNode; 
126 aux = aux->getNext(); 
127 }while(aux != l.anchor); 
128 lastInserted->setNext(anchor); 
129 } 
130 template <class T> 
131 List<T>::List() : anchor(nullptr) { } 
132 template <class T> 
133 List<T>::List(const List<T>& l) : anchor(nullptr) 
134 { 
135 copyAll(l); 
136 } 
137 template <class T> 
138 List<T>::~List() 
139 { 
140 deleteAll(); 
141 } 
142 template <class T> 
143 List<T>& List<T>::operator = (const List<T>& l) 
144 { 
145 deleteAll(); 
146 copyAll(l); 
147 return *this; 
148 } 
149 template <class T> 
150 bool List<T>::isEmpty() const 
151 { 
152 return anchor == nullptr; 
153 } 
154 template <class T> 
155 void List<T>::insertData(List<T>::Node* p, const T& e) 
156 { 
157 if(p != nullptr and !isValidPos(p)) 
158 { 
159 throw Exception(" Posicion invalida, insertData"); 
160 } 
161 Node* aux(new Node(e)); 
162 if(aux == nullptr) 
163 { 
164 throw Exception(" Memoria no disponible, insertData"); 
165 } 
166 if(p == nullptr) 
167 {///Insertar al principio 
168 if(isEmpty()){///Inserta el primer elemento 
169 aux->setNext(aux); 
170 } 
171 else{///Hay más de un elemento 
172 aux->setNext(anchor); 
173 getLastPos()->setNext(aux); 
174 } 
175 anchor = aux; 
176 } 
177 else 
178 {///Insertar en cualquier otra posicion 
179 aux->setNext(p->getNext()); 
180 p->setNext(aux); 
181 } 
182 } 
183 template <class T> 
184 void List<T>::deleteData(List<T>::Node* p) 
185 { 
186 if(!isValidPos(p)) 
187 { 
188 throw Exception(" Posicion invalida, deleteData."); 
189 } 
190 if(p == anchor) 
191 {///Eliminar el primero 
192 if(p->getNext() == p){///Esta solito 
193 anchor = nullptr; 
194 } 
195 else{///Hay más de un elemento 
196 getLastPos()->setNext(anchor->getNext()); 
197 } 
198 } 
199 else 
200 {///Eliminar cualquiera otro 
201 getPrevPos(p)->setNext(p->getNext()); 
202 } 
203 delete p; 
204 } 
205 template <class T> 
206 typename List<T>::Node* List<T>::getFirstPos() const 
207 { 
208 return anchor; 
209 } 
210 template <class T> 
211 typename List<T>::Node* List<T>::getLastPos() const 
212 { 
213 if(isEmpty()) 
214 { 
215 return nullptr; 
216 } 
217 Node* aux(anchor); 
218 while(aux->getNext() != anchor) 
219 { 
220 aux = aux->getNext(); 
221 } 
222 return aux; 
223 } 
224 template <class T> 
225 typename List<T>::Node* List<T>::getPrevPos(List<T>::Node* p) const 
226 { 
227 /*if(isEmpty() or p->getNext() == anchor) 
228 { 
229 return nullptr; 
230 }*/ 
231 if(isEmpty()){ 
232 return nullptr; 
233 } 
234 Node* aux(anchor); 
235 do 
236 { 
237 if(aux->getNext() == p){ 
238 return aux; 
239 } 
240 aux = aux->getNext(); 
241 }while(aux != anchor); 
242 return nullptr; 
243 } 
244 template <class T> 
245 typename List<T>::Node* List<T>::getNextPos(List<T>::Node* p) const 
246 { 
247 /*if(!isValidPos(p) or p->getNext() == anchor) 
248 { 
249 return nullptr; 
250 }*/ 
251 return p->getNext(); 
252 } 
253 template <class T> 
254 typename List<T>::Node* List<T>::findData(const T& e) const 
255 { 
256 if(isEmpty()){ 
257 return nullptr; 
258 } 
259 Node* aux(anchor); 
260 do{ 
261 if(aux->getData() == e){ 
262 return aux; 
263 } 
264 aux = aux->getNext(); 
265 }while(aux != anchor); 
266 return nullptr; 
267 } 
268 template <class T> 
269 T& List<T>::retrieve(List<T>::Node* p) 
270 { 
271 if(!isValidPos(p)) 
272 { 
273 throw Exception(" Posicion invalida, retireve"); 
274 } 
275 return p->getData(); 
276 } 
277 template <class T> 
278 std::string List<T>::toString() const 
279 { 
280 std::string result; 
281 if(!isEmpty()){ 
282 Node* aux(anchor); 
283 do{ 
284 result += aux->getData().toString() + "\n"; 
285 aux = aux->getNext(); 
286 }while(aux != anchor); 
287 } 
288 return result; 
289 } 
290 template <class T> 
291 void List<T>::deleteAll() 
292 { 
293 if(isEmpty()){ 
294 return; 
295 } 
296 Node* mark(anchor); 
297 Node* aux; 
298 do{ 
299 aux = anchor; 
300 anchor = anchor->getNext(); 
301 delete aux; 
302 }while(anchor != mark); 
303 anchor = nullptr; 
304 } 
305 
306 #endif // LIST_H_INCLUDED 
307 
Songs.h 
1 #ifndef SONGS_H 
2 #define SONGS_H 
3 #include <iostream> 
4 #include <string> 
5 class Songs { 
6 private: 
7 std::string SongName; 
8 std::string SongAutor; 
9 std::string SongRanking; 
10 public: 
11 void setSongName(const std::string&); 
12 void setSongAutor(const std::string&); 
13 void setSongRanking(const std::string&); 
14 std::string toString() const; 
15 std::string getSongName() const; 
16 std::string getSongAutor() const; 
17 std::string getSongRanking() const; 
18 bool operator == (const Songs&) 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 friend std::ostream& operator << (std::ostream&, Songs&); 
25 friend std::istream& operator >> (std::istream&, Songs&); 
26 }; 
27 
28 #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 
 
Opción 4 
 
Opción 1 
 
Opción 2 
 
Opción 3 
 
Opción 4 
 
Opción 5