1 | #ifndef TLISTA_H
|
---|
2 | #define TLISTA_H
|
---|
3 |
|
---|
4 |
|
---|
5 |
|
---|
6 | #include <iostream>
|
---|
7 |
|
---|
8 |
|
---|
9 |
|
---|
10 | template<class T>
|
---|
11 | struct dato_enlazado
|
---|
12 | {
|
---|
13 | T dato; // El dato como tipo abstracto
|
---|
14 | float prioridad; // Por si queremos ordenar la lista con prioridad
|
---|
15 | dato_enlazado * sig; // Puntero al siguient
|
---|
16 | dato_enlazado (void); // Constructor por defecto
|
---|
17 | dato_enlazado (const T& a); // Constructor de copia
|
---|
18 | dato_enlazado (const T& a, const float); // Constructor de copia
|
---|
19 | dato_enlazado& operator =(const dato_enlazado& d); // Operador de asignación
|
---|
20 | bool operator ==(const dato_enlazado& d) const; // Operador de igualdad
|
---|
21 | bool operator !=(const dato_enlazado& d) const; // Operador de desigualdad
|
---|
22 | //friend ostream& operator << (ostream& os, T& d);
|
---|
23 | };
|
---|
24 |
|
---|
25 |
|
---|
26 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
27 | // NO LA BORRO PORQUE ES INTERESANTE
|
---|
28 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
29 | /*template<class T>
|
---|
30 | ostream& operator << (ostream& os, T& d)
|
---|
31 | {
|
---|
32 | os << d.dato;
|
---|
33 |
|
---|
34 | return os;
|
---|
35 | }*/
|
---|
36 |
|
---|
37 |
|
---|
38 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
39 | // Constructor por defecto, inicializa el siguiente a nulo
|
---|
40 | // Parámetros : ninguno
|
---|
41 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
42 | template<class T>
|
---|
43 | dato_enlazado<T>::dato_enlazado (void) : sig(NULL), prioridad(0.0f)
|
---|
44 | {
|
---|
45 | }
|
---|
46 |
|
---|
47 |
|
---|
48 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
49 | // Constructor de copia
|
---|
50 | // Parámetros : T& a --> Referencia constante al dato a copiar
|
---|
51 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
52 | template<class T>
|
---|
53 | dato_enlazado<T>::dato_enlazado (const T& a) : dato(a), sig(NULL)
|
---|
54 | {
|
---|
55 | }
|
---|
56 |
|
---|
57 |
|
---|
58 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
59 | // Constructor con dato de prioridad
|
---|
60 | // Parámetros : T& a --> Referencia constante al dato a copiar
|
---|
61 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
62 | template<class T>
|
---|
63 | dato_enlazado<T>::dato_enlazado (const T& a, const float prior) : dato(a), sig(NULL), prioridad(prior)
|
---|
64 | {
|
---|
65 | }
|
---|
66 |
|
---|
67 |
|
---|
68 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
69 | // Operador de asignación
|
---|
70 | // Parámetros : const dato_enlazado& d --> Referencia constante al dato que se va a copiar
|
---|
71 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
72 | template<class T>
|
---|
73 | dato_enlazado<T>& dato_enlazado<T>::operator =(const dato_enlazado& d)
|
---|
74 | {
|
---|
75 | dato = d.dato;
|
---|
76 | sig = NULL;
|
---|
77 | return *this;
|
---|
78 | }
|
---|
79 |
|
---|
80 |
|
---|
81 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
82 | // Operador de igualdad, devuelve true si los datos son iguales y false en caso contrario
|
---|
83 | // Parámetros : const dato_enlazado& d
|
---|
84 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
85 | template<class T>
|
---|
86 | bool dato_enlazado<T>::operator ==(const dato_enlazado<T>& d) const
|
---|
87 | {
|
---|
88 | return dato == d.dato;
|
---|
89 | }
|
---|
90 |
|
---|
91 |
|
---|
92 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
93 | // Operador de desigualdad, devuelve true si los datos son distintos y false si son iguales
|
---|
94 | // Parámetros : const dato_enlazado
|
---|
95 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
96 | template<class T>
|
---|
97 | bool dato_enlazado<T>::operator !=(const dato_enlazado<T>& d) const
|
---|
98 | {
|
---|
99 | return dato != d.dato;
|
---|
100 | }
|
---|
101 |
|
---|
102 |
|
---|
103 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
104 | template<class T> class iterador_lista;
|
---|
105 | template<class T> class iterador_prioridad;
|
---|
106 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
107 |
|
---|
108 | template<class T>
|
---|
109 | class lista
|
---|
110 | {
|
---|
111 | protected :
|
---|
112 | float Prioridad (const unsigned long); // Devuelve la prioridad del elemento seleccionado
|
---|
113 | public :
|
---|
114 | dato_enlazado<T> *cab;
|
---|
115 | //dato_enlazado<T> *cola;
|
---|
116 | dato_enlazado<T> *selec; // Puntero al dato actualmente 'encontrado',
|
---|
117 | // aumenta la eficiencia en la busqueda de datos consecutivos
|
---|
118 | dato_enlazado<T> *cola; // Esto es temporal, hay que borrarlo
|
---|
119 |
|
---|
120 | public:
|
---|
121 | lista (void); // Constructor vacio
|
---|
122 | virtual ~lista (void); // Destructor
|
---|
123 | lista (lista<T>&); // Constructor de copia
|
---|
124 | bool operator == (lista<T>&) const; // Operador de comparación
|
---|
125 | bool operator != (lista<T>&) const; // Idem
|
---|
126 | virtual bool Inserta (const T& a); // Inserta un dato en la lista
|
---|
127 | virtual bool InsertaPrioridad (const T&, const float, const bool); // Inserta manteniendo orden
|
---|
128 | virtual bool Busca (const T& a);
|
---|
129 | virtual bool Borra (const T& a); // Borra a si existe
|
---|
130 | virtual bool BorraLista (void); // Borra todos los elementos de la lista
|
---|
131 | virtual bool Cab (void); // Situa el seleccionado al principio de la lista
|
---|
132 | virtual bool Sig (void);
|
---|
133 | virtual T GetCab (void); // Extrae la cabeza de la lista
|
---|
134 | virtual T GetCola (void);
|
---|
135 | virtual bool BorraCola (void); //borra la cola
|
---|
136 | virtual unsigned long NDatos (void) const; // Devuelve el número de datos en la lista
|
---|
137 | virtual unsigned long NPrioridadDatos (void) const; //
|
---|
138 | friend class iterador_lista<T>;
|
---|
139 | friend class iterador_prioridad<T>;
|
---|
140 | // A partir de aqui las funciones son sólo para depurar el código
|
---|
141 | friend std::ostream& operator << (std::ostream& os, lista<T>& d);
|
---|
142 | };
|
---|
143 |
|
---|
144 |
|
---|
145 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
146 | // PARA DEPURAR EL CÓDIGO, PERO ES INTERESANTE
|
---|
147 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
148 | template<class T>
|
---|
149 | std::ostream& operator << (std::ostream& os, lista<T>& l)
|
---|
150 | {
|
---|
151 | dato_enlazado<T> * tmp = l.cab;
|
---|
152 |
|
---|
153 | while (tmp)
|
---|
154 | {
|
---|
155 | cout << (*tmp).dato;
|
---|
156 | tmp = tmp->sig;
|
---|
157 | }
|
---|
158 |
|
---|
159 | return os;
|
---|
160 | }
|
---|
161 |
|
---|
162 |
|
---|
163 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
164 | // Constructor por defecto
|
---|
165 | // Parámetros : Ninguno
|
---|
166 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
167 | template<class T>
|
---|
168 | lista<T>::lista (void) : cab(NULL), selec(NULL), cola(NULL)
|
---|
169 | {
|
---|
170 | }
|
---|
171 |
|
---|
172 |
|
---|
173 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
174 | // Constructor de copia
|
---|
175 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
176 | template<class T>
|
---|
177 | lista<T>::lista (lista<T>& l) : cab(NULL), selec(NULL), cola(NULL)
|
---|
178 | {
|
---|
179 | dato_enlazado<T> *tmp = l.cab;
|
---|
180 | dato_enlazado<T> *nuevo; // Apuntador a la memoria que se va a reservar
|
---|
181 |
|
---|
182 | while (tmp != NULL)
|
---|
183 | {
|
---|
184 | nuevo = new dato_enlazado<T> (*tmp); // Reservo espacio para el nuevo dato
|
---|
185 | if (cola == NULL) cola = nuevo;
|
---|
186 | nuevo->sig = cab; // El siguiente del nuevo dato será la cabeza de la lista
|
---|
187 | selec = cab = nuevo; // Ahora hago apuntar la cabeza al nuevo dato
|
---|
188 |
|
---|
189 | tmp = tmp->sig;
|
---|
190 | }
|
---|
191 | }
|
---|
192 |
|
---|
193 |
|
---|
194 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
195 | // Destructor por defecto
|
---|
196 | // Parámetros : Ninguno
|
---|
197 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
198 | template<class T>
|
---|
199 | lista<T>::~lista (void)
|
---|
200 | {
|
---|
201 | //BorraLista ();
|
---|
202 | }
|
---|
203 |
|
---|
204 |
|
---|
205 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
206 | // Operador de comparación. Dos listas son iguales si contienen los mismos elementos aunque no estén en el mismo orden
|
---|
207 | // Parámetros --> const lista<T>& l : Lista con la que se compara
|
---|
208 | // Salida --> 'true' si las dos listas contienen los mismos elementos
|
---|
209 | // 'false' en cualquier otro caso
|
---|
210 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
211 | template<class T>
|
---|
212 | bool lista<T>::operator == (lista<T>& l) const
|
---|
213 | {
|
---|
214 | if (NDatos () != l.NDatos ()) return false; // Si no tienen el mismo número de datos no pueden ser iguales
|
---|
215 |
|
---|
216 | //lista<T> tmp = *this;
|
---|
217 | lista<T> tmpl = l;
|
---|
218 | //iterador_lista<T> iterador (tmp); // Creo un iterador sobre esta lista
|
---|
219 | //T* dato;
|
---|
220 |
|
---|
221 | //while (dato = iterador ())
|
---|
222 | //if (!tmpl.Busca(*dato)) return false; // Si uno de los datos de la primera lista no lo encuentro en la segunda no son iguales
|
---|
223 |
|
---|
224 | dato_enlazado<T> *tmpd = cab;
|
---|
225 |
|
---|
226 | while (tmpd != NULL)
|
---|
227 | {
|
---|
228 | if (tmpl.Busca (tmpd->dato) == false) return false;
|
---|
229 | tmpd = tmpd->sig;
|
---|
230 | }
|
---|
231 |
|
---|
232 | return true; // si todos los de la primera están en la segunda y tienen el mismo tamaño es que son iguales
|
---|
233 | }
|
---|
234 |
|
---|
235 |
|
---|
236 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
237 | // Operador de desigualdad
|
---|
238 | // Parámetros --> const lista<T>& l : Lista con la que se compara
|
---|
239 | // Salida --> 'true' si las listas son distintas
|
---|
240 | // 'false' en caso contrario
|
---|
241 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
242 | template<class T>
|
---|
243 | bool lista<T>::operator != (lista<T>& l) const
|
---|
244 | {
|
---|
245 | if (*this == l) return false;
|
---|
246 |
|
---|
247 | return true;
|
---|
248 | }
|
---|
249 |
|
---|
250 |
|
---|
251 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
252 | // Devuelve la prioridad en la posición i-ésima
|
---|
253 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
254 | template<class T>
|
---|
255 | float lista<T>::Prioridad (const unsigned long i)
|
---|
256 | {
|
---|
257 | unsigned long cont = 0L; // Inicializo el contador de posiciones
|
---|
258 |
|
---|
259 | selec = cab; //Inicio la búsqueda desde la cabeza
|
---|
260 | while (i != cont && selec != NULL) // Mientras no haya encontrado la posición y me queden elementos
|
---|
261 | {
|
---|
262 | selec = selec->sig; // Paso al siguiente
|
---|
263 | cont++; // e incremento en uno el contador
|
---|
264 | }
|
---|
265 |
|
---|
266 | return selec->prioridad;
|
---|
267 | }
|
---|
268 |
|
---|
269 |
|
---|
270 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
271 | // Inserta un nuevo elemento en la lista. El nuevo elemento se inserta en la cabeza
|
---|
272 | // Parámetros : a --> el dato que hay que añadir a la lista
|
---|
273 | // Salida : 'true' si el dato se ha podido insertar en la lista
|
---|
274 | // 'false' en caso contrario
|
---|
275 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
276 | template<class T>
|
---|
277 | bool lista<T>::Inserta (const T& a)
|
---|
278 | {
|
---|
279 |
|
---|
280 | if (cola == NULL)
|
---|
281 | {
|
---|
282 | selec = cab = cola = new dato_enlazado<T> (a);
|
---|
283 | return true;
|
---|
284 | }
|
---|
285 | else
|
---|
286 | {
|
---|
287 | if (!(cola->sig = new dato_enlazado<T> (a))) // Reservo espacio para el nuevo dato
|
---|
288 | return false;
|
---|
289 | else
|
---|
290 | {
|
---|
291 | cola = cola->sig;
|
---|
292 | selec = cola; // Ahora hago apuntar la cabeza al nuevo dato
|
---|
293 | return true;
|
---|
294 | }
|
---|
295 | }
|
---|
296 | }
|
---|
297 |
|
---|
298 |
|
---|
299 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
300 | // Inserta manteniendo orden
|
---|
301 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
302 | template<class T>
|
---|
303 | bool lista<T>::InsertaPrioridad (const T& a, const float prior, const bool borra)
|
---|
304 | {
|
---|
305 | dato_enlazado<T>* tmp = cola;
|
---|
306 |
|
---|
307 | selec = new dato_enlazado<T> (a, prior); // Creo el nodo a insertar
|
---|
308 |
|
---|
309 | if (cab == NULL) // No hay ningún dato en la lista
|
---|
310 | {
|
---|
311 | cab = cola = selec;
|
---|
312 | return true;
|
---|
313 | }
|
---|
314 | // Tengo mas de uno en la lista y el que voy a insertar es el menor
|
---|
315 | if (cola->prioridad >= prior)
|
---|
316 | {
|
---|
317 | if (cola->dato != a)
|
---|
318 | {
|
---|
319 | selec->sig = cola;
|
---|
320 | cola = selec;
|
---|
321 | }
|
---|
322 | else if (cola->dato == a && borra)
|
---|
323 | {
|
---|
324 | dato_enlazado<T>* tmp_selec = cola;
|
---|
325 | cola = cola->sig;
|
---|
326 | delete tmp_selec;
|
---|
327 | }
|
---|
328 | else delete selec;
|
---|
329 | return true;
|
---|
330 | }
|
---|
331 | else
|
---|
332 | {
|
---|
333 | while (tmp != cab) // Mientras no llegue a la cabeza
|
---|
334 | {
|
---|
335 | if (tmp->sig->prioridad >= prior) // inserto antes de tmp->sig
|
---|
336 | {
|
---|
337 | if (a != tmp->sig->dato) // Si no está ya presente en la lista
|
---|
338 | {
|
---|
339 | selec->sig = tmp->sig; // lo inserto
|
---|
340 | tmp->sig = selec;
|
---|
341 | }
|
---|
342 | else if (a == tmp->sig->dato && borra) // Si hay que borrarlo
|
---|
343 | {
|
---|
344 | dato_enlazado<T>* tmp_selec = tmp->sig;
|
---|
345 | if (tmp->sig == cab) cab = tmp;
|
---|
346 | tmp->sig = tmp->sig->sig;
|
---|
347 | delete tmp_selec;
|
---|
348 | }
|
---|
349 | else // si está presente
|
---|
350 | {
|
---|
351 | delete selec; // Libero la memoria que había reservado
|
---|
352 | }
|
---|
353 | return true;
|
---|
354 | }
|
---|
355 | tmp = tmp->sig;
|
---|
356 | }
|
---|
357 | if ((tmp == cab) && (a != cab->dato)) // Si llego a la cabeza sin encontrar ninguno en la lista con prioridad mayor
|
---|
358 | { // es porque el que voy a insertar tiene la mayor prioridad
|
---|
359 | cab->sig = selec;
|
---|
360 | cab = selec;
|
---|
361 | return true;
|
---|
362 | }
|
---|
363 | else
|
---|
364 | {
|
---|
365 | delete selec;
|
---|
366 | selec = cab;
|
---|
367 | }
|
---|
368 | }
|
---|
369 | return false;
|
---|
370 | }
|
---|
371 |
|
---|
372 |
|
---|
373 |
|
---|
374 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
375 | // Busca un elemento en la lista y deja el puntero selec apuntando a él si lo encuentra
|
---|
376 | // Parámetros : const T& a --> Referencia al dato que se está buscando
|
---|
377 | // Salida : true si el dato efectivamente es encontrado
|
---|
378 | // false si el dato no está en la lista
|
---|
379 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
380 | template<class T>
|
---|
381 | bool lista<T>::Busca (const T& a)
|
---|
382 | {
|
---|
383 | dato_enlazado<T> *tmp; // Puntero de reserva
|
---|
384 |
|
---|
385 | if (!cab) return false; // Si no hay ningún dato no hay donde buscar
|
---|
386 |
|
---|
387 | if (selec && selec->dato != a)
|
---|
388 | {
|
---|
389 | tmp = selec; // Me guardo el actualmente seleccionado
|
---|
390 | selec = selec->sig; // Iniciaré la búsqueda a partir del dato siguiente
|
---|
391 | }
|
---|
392 | else
|
---|
393 | {
|
---|
394 | selec = cab; // Iniciaré la busqueda desde la cabeza si no
|
---|
395 | //tmp = NULL;
|
---|
396 | }
|
---|
397 |
|
---|
398 | while (selec != NULL && selec->dato != a)
|
---|
399 | selec = selec->sig; // lo busco a partir de la posición original hacia el final
|
---|
400 |
|
---|
401 | if (!selec) // Si antes habia uno seleccionado
|
---|
402 | {
|
---|
403 | selec = cab; // Iniciaré la búsqueda desde la cabeza
|
---|
404 | while (selec != tmp && selec->dato != a) selec = selec->sig;
|
---|
405 | }
|
---|
406 |
|
---|
407 | if (selec && selec->dato == a) return true;
|
---|
408 | return false;
|
---|
409 | }
|
---|
410 |
|
---|
411 |
|
---|
412 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
413 | // Borra el elemento indicado de la lista
|
---|
414 | // Parámetros : const T& a --> Referencia al elemento a borrar
|
---|
415 | // Salida --> true si el elemento ha sido encontrado y borrado
|
---|
416 | // false si no se ha encontrado el elemento
|
---|
417 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
418 | template<class T>
|
---|
419 | bool lista<T>::Borra (const T& a)
|
---|
420 | {
|
---|
421 | dato_enlazado<T> *tmp = cab; // Me guardo la posición de lo que quiero borrar
|
---|
422 |
|
---|
423 | if (!Busca (a)) return false; // Si no lo encuentra devuelve false
|
---|
424 |
|
---|
425 | if (selec == cab) // Si lo que quiero borrar es la cabeza
|
---|
426 | {
|
---|
427 | cab = cab->sig; // Adelanto la cabeza
|
---|
428 | delete selec; // Borro el dato
|
---|
429 | selec = cab; // Hago apuntar el actual a la nueva cabeza
|
---|
430 | }
|
---|
431 | else
|
---|
432 | {
|
---|
433 | while (tmp->sig->dato != a) tmp = tmp->sig; // Encuentro el anterior al que quiero borrar
|
---|
434 | if (tmp->sig == cola) cola = tmp;
|
---|
435 |
|
---|
436 | tmp->sig = selec->sig; // Saco el que voy a borrar fuera de la lista
|
---|
437 | delete selec; // Borro el dato
|
---|
438 | if (!(selec = tmp->sig)) selec = cab; // Si al avanzar el seleccionado llego al final, inicio desde la cabeza
|
---|
439 | }
|
---|
440 |
|
---|
441 | return true;
|
---|
442 | }
|
---|
443 |
|
---|
444 |
|
---|
445 |
|
---|
446 |
|
---|
447 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
448 | // Elimina todos los elementos de lista
|
---|
449 | // Parámetros : ninguno
|
---|
450 | // Salida : Si la lista ha sido efectivamente borrada true
|
---|
451 | // false en caso contrario
|
---|
452 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
453 | template<class T>
|
---|
454 | bool lista<T>::BorraLista (void)
|
---|
455 | {
|
---|
456 | while (cab)
|
---|
457 | {
|
---|
458 | selec = cab;
|
---|
459 | if (!Borra (selec->dato)) return false; // Borro siempre la cabeza
|
---|
460 | }
|
---|
461 | return true;
|
---|
462 | }
|
---|
463 |
|
---|
464 |
|
---|
465 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
466 | // Coloca el seleccionado al inicio de la lista
|
---|
467 | // Parémetros --> ninguno
|
---|
468 | // Salida --> 'true' si efectivamente se ha colocado al inicio de la lista
|
---|
469 | // 'false' si ha habido algún error y el seleccionado no apunta al inicio de la lista
|
---|
470 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
471 | template<class T>
|
---|
472 | bool lista<T>::Cab (void)
|
---|
473 | {
|
---|
474 | if (cab)
|
---|
475 | {
|
---|
476 | selec = cab;
|
---|
477 | return true;
|
---|
478 | }
|
---|
479 | return false;
|
---|
480 | }
|
---|
481 |
|
---|
482 |
|
---|
483 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
484 | // Avanza el seleccionado hasta la siguiente posición, el siguiente del último es de nuevo la cabeza
|
---|
485 | // Parámetros : ninguno
|
---|
486 | // Salida : 'true' si se inicia desde la cabeza al avanzar
|
---|
487 | // 'false' en cualquier otro caso
|
---|
488 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
489 | template<class T>
|
---|
490 | bool lista<T>::Sig (void)
|
---|
491 | {
|
---|
492 | if (!(selec = selec->sig))
|
---|
493 | {
|
---|
494 | selec = cab; // Avanzo el seleccionado hasta el siguiente, y si me paso, lo llevo
|
---|
495 | return true; // de nuevo a la cabeza
|
---|
496 | }
|
---|
497 | return false;
|
---|
498 | }
|
---|
499 |
|
---|
500 |
|
---|
501 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
502 | // Extrae la cabeza de la lista
|
---|
503 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
504 | template<class T>
|
---|
505 | T lista<T>::GetCab (void)
|
---|
506 | {
|
---|
507 | if (cab->dato == NULL) return NULL; // Si no hay nada en la lista devuelve NULL
|
---|
508 |
|
---|
509 | else return cab->dato;
|
---|
510 | }
|
---|
511 |
|
---|
512 |
|
---|
513 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
514 | // Extrae la cola de la lista ///ACABAAAR melon
|
---|
515 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
516 | template<class T>
|
---|
517 | T lista<T>::GetCola (void)
|
---|
518 | {
|
---|
519 |
|
---|
520 | if (cola->dato == NULL) return NULL; // Si no hay nada en la lista devuelve NULL
|
---|
521 |
|
---|
522 | else return cola->dato;
|
---|
523 |
|
---|
524 | }
|
---|
525 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
526 | // Extrae y borra la cola de la lista
|
---|
527 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
528 | template<class T>
|
---|
529 | bool lista<T>::BorraCola (void)
|
---|
530 | {
|
---|
531 | /*dato_enlazado<T>* tmp = cab; // Nos situamos incialmente en la cabeza
|
---|
532 |
|
---|
533 |
|
---|
534 | if (cab == NULL) return false; // Si no hay nada en la lista devuelve NULL
|
---|
535 | if (cab == cola) // Si solo tenemos un elemento
|
---|
536 | {
|
---|
537 | delete cab;
|
---|
538 | cab = cola = selec = NULL;
|
---|
539 | return true;
|
---|
540 | }
|
---|
541 | else
|
---|
542 | {
|
---|
543 | while (tmp->sig != cola)
|
---|
544 | tmp = tmp->sig;
|
---|
545 | delete cola;
|
---|
546 | cola = tmp;
|
---|
547 | cola->sig = NULL;
|
---|
548 | selec = cab;
|
---|
549 | return true;
|
---|
550 | }*/
|
---|
551 | return Borra (cola->dato);
|
---|
552 | }
|
---|
553 |
|
---|
554 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
555 | // Devuelve el número de datos actuales en la lista
|
---|
556 | // Parámetros --> Ninguno
|
---|
557 | // Salida --> int : el número de datos en la lista
|
---|
558 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
559 | template<class T>
|
---|
560 | unsigned long lista<T>::NDatos (void) const
|
---|
561 | {
|
---|
562 | unsigned long nDatos = 0; // Para contar el número de datos de la lista
|
---|
563 | /*lista<T> tmp = *this;
|
---|
564 | /iterador_lista<T> iterador(tmp); // Creo un iterador sobre la lista
|
---|
565 | T * dato;
|
---|
566 |
|
---|
567 | while (dato = iterador ())
|
---|
568 | nDatos++;*/
|
---|
569 |
|
---|
570 | dato_enlazado<T> * tmp = cab;
|
---|
571 |
|
---|
572 | while (tmp != NULL)
|
---|
573 | {
|
---|
574 | tmp = tmp->sig;
|
---|
575 | nDatos++;
|
---|
576 | }
|
---|
577 |
|
---|
578 | return nDatos;
|
---|
579 | }
|
---|
580 |
|
---|
581 |
|
---|
582 | template<class T>
|
---|
583 | unsigned long lista<T>::NPrioridadDatos (void) const
|
---|
584 | {
|
---|
585 | unsigned nDatos = 0;
|
---|
586 |
|
---|
587 | dato_enlazado<T>* tmp = cola;
|
---|
588 |
|
---|
589 | while (tmp != NULL)
|
---|
590 | {
|
---|
591 | tmp = tmp->sig;
|
---|
592 | nDatos++;
|
---|
593 | }
|
---|
594 |
|
---|
595 | return nDatos;
|
---|
596 | }
|
---|
597 |
|
---|
598 |
|
---|
599 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
600 | // Esta es la clase iterador, recorre la lista desde la cabeza a la cola devolviendo punteros a los datos
|
---|
601 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
602 |
|
---|
603 | template<class T>
|
---|
604 | class iterador_lista
|
---|
605 | {
|
---|
606 | private:
|
---|
607 | dato_enlazado<T> *iterador; // Elemento de la lista a devolver
|
---|
608 | lista<T> *lista_iterada; // Puntero a la lista sobre la que se está iterando
|
---|
609 |
|
---|
610 | public:
|
---|
611 | iterador_lista (lista<T>&); // Constructor con una lista
|
---|
612 | T * const operator () (void); // Operador de iteracion
|
---|
613 | T * const IteradorCircular (void); // Igual que el anterior, pero cuando llega al final, recomienza
|
---|
614 | };
|
---|
615 |
|
---|
616 |
|
---|
617 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
618 | // Constructor con un lista
|
---|
619 | // Parámetros --> lista<T>& l : Referencia a la lista sobre la que se iterará
|
---|
620 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
621 | template<class T>
|
---|
622 | iterador_lista<T>::iterador_lista (lista<T>& l) : lista_iterada (&l), iterador(l.cab)
|
---|
623 | {
|
---|
624 | // Hago que el primer elemento de iteración sea la cabeza
|
---|
625 | }
|
---|
626 |
|
---|
627 |
|
---|
628 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
629 | // Operador () que es el que hace las funciones de iterador
|
---|
630 | // Párámetros --> Ninguno
|
---|
631 | // Salida --> T * const : un puntero constante al elemento devuelto por el iterador
|
---|
632 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
633 | template<class T>
|
---|
634 | T * const iterador_lista<T>::operator () (void)
|
---|
635 | {
|
---|
636 | T * tmp = &iterador->dato;
|
---|
637 |
|
---|
638 | if (!iterador) iterador = lista_iterada->cab; // Si llegamos al final de la lista, dejamos el iterador
|
---|
639 | else iterador = iterador->sig; // al inicio de la lista.
|
---|
640 |
|
---|
641 | return tmp;
|
---|
642 | }
|
---|
643 |
|
---|
644 |
|
---|
645 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
646 | // Igual que el anterior, pero cuando llega al final de la lista empieza desde el principio
|
---|
647 | // Parametros --> Ninguno
|
---|
648 | // Salida T * const : un puntero constante al elemento devuelto
|
---|
649 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
650 | template<class T>
|
---|
651 | T * const iterador_lista<T>::IteradorCircular (void)
|
---|
652 | {
|
---|
653 | if (iterador == NULL) return NULL;
|
---|
654 | else
|
---|
655 | {
|
---|
656 | iterador = iterador->sig;
|
---|
657 | if (!iterador) iterador = lista_iterada->cab;
|
---|
658 |
|
---|
659 | return &iterador->dato;
|
---|
660 | }
|
---|
661 | }
|
---|
662 |
|
---|
663 |
|
---|
664 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
665 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
666 | template<class T>
|
---|
667 | class iterador_prioridad
|
---|
668 | {
|
---|
669 | private:
|
---|
670 | dato_enlazado<T> *iterador; // Elemento de la lista a devolver
|
---|
671 | lista<T> *lista_iterada; // Puntero a la lista sobre la que se está iterando
|
---|
672 |
|
---|
673 | public:
|
---|
674 | iterador_prioridad (lista<T>&); // Constructor con una lista
|
---|
675 | T * const operator () (void); // Operador de iteracion
|
---|
676 | };
|
---|
677 |
|
---|
678 |
|
---|
679 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
680 | // Constructor con un lista
|
---|
681 | // Parámetros --> lista<T>& l : Referencia a la lista sobre la que se iterará
|
---|
682 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
683 | template<class T>
|
---|
684 | iterador_prioridad<T>::iterador_prioridad (lista<T>& l) : lista_iterada (&l), iterador(l.cola)
|
---|
685 | {
|
---|
686 | // Hago que el primer elemento de iteración sea la cabeza
|
---|
687 | }
|
---|
688 |
|
---|
689 |
|
---|
690 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
691 | // Operador () que es el que hace las funciones de iterador
|
---|
692 | // Párámetros --> Ninguno
|
---|
693 | // Salida --> T * const : un puntero constante al elemento devuelto por el iterador
|
---|
694 | //------------------------------------------------------------------------------------------------------------------------------
|
---|
695 | template<class T>
|
---|
696 | T * const iterador_prioridad<T>::operator () (void)
|
---|
697 | {
|
---|
698 | T * tmp = &iterador->dato;
|
---|
699 |
|
---|
700 | if (!iterador) iterador = lista_iterada->cola; // Si llegamos al final de la lista, dejamos el iterador
|
---|
701 | else iterador = iterador->sig; // al inicio de la lista.
|
---|
702 |
|
---|
703 | return tmp;
|
---|
704 | }
|
---|
705 |
|
---|
706 |
|
---|
707 |
|
---|
708 |
|
---|
709 | #endif |
---|