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