Ir al contenido

publicidad

Foto

[Programación] Pequeña orientación para tipos abstractos de datos (aka estructuras avanzadas de dato


Este tema ha sido archivado. Esto significa que no puedes responder en este tema.
8 respuestas en este tema

  • wiyarmir

  • Elder

  • vida restante: 100%
  • Registrado: 27 mar 2009
  • Mensajes: 108
#1

Escrito 03 mayo 2009 - 11:01

Bueno, estaba repasando apuntes, y he decidido compartir esto con vosotros por si os fuera útil.

Ante todo, lo hare en pseudolenguaje castellano (el mio se parece bastante a C++ con toques de Visual Basic :] ) para que sea más general. Simplemente

intentaré recopilar lo que he ido aprendiendo con el tiempo. Doy por sabidos los conceptos puntero, clase y memoria dinámica. Repito que esto no es un "Aprende C++ en 10 minutos"

Usaré Asignar() para asignar memoria dinámica y Liberar() para liberarla. El símbolo del puntero, el clásico de C++: “*”

Luego intentaré esbozar para qué creo yo que valdrían programando un videojuego, por qué merece la pena usarlas.


Contenido:

Tipos Abstractos de Datos:
Listas enlazadas
Pilas
Colas
Listas posicionales
Tablas de dispersión
Árboles Binarios

Conocimientos adicionales:
Clases y Cabeceras
Plantillas


Listas Enlazadas


Es lo más simple de entre lo no tan simple. Nos va a servir para construir el resto de las estructuras.
Es el concepto de una cadena en la que se van engarzando eslabones o quitando según necesidad. A los eslabones los voy a llamar Nodos. En estos nodos

guardaremos un puntero del mismo tipo para apuntar al siguiente.

Imagen Enviada

Voy a definir el tipo TipoNodo (o TNodo para abreviar) que es un registro(struct) tal que así:

[code:1]TIPOS

Registro TipoNodo
TipoDato dato
TipoNodo *sig //Puntero a siguiente nodo
Fin[/code]

//Y el tipo TipoLista (o TLista) como un puntero a nodo (facilita la comprensión)

TipoNodo *TipoLista

¿Qué pasa cuando hacemos que sig apunte a otro registro del tipo TNodo? ¿Y este a su vez a otro? Obtenemos una lista enlazada. Es como engarzar una cadena.

Podeis pensar “Vaya complicación con lo que molan los arrays/vectores”. Bueno, es una complicación necesaria para seguir adelante :D

Para manejarlo, crearemos una clase, la clase TipoLista que como atributos solo necesita un puntero de tipo TNodo, que será nuestra “cabeza de lista”. Desde ese puntero accederemos al resto de la lista, y si lo perdemos, perdemos la lista entera!!

El convenio que hay, es de que valga NULO el puntero siguiente (o el de cabeza) para indicar el fin de la lista. Por tanto, una lista vacía, su cabeza sería

NULO


Queda una cosa así más o menos:

Imagen Enviada


Además la lista puede ser ordenada o no (depende de con qué propósito vaya a usarse)

Cosas que debes de poder hacer con una lista enlazada:

Añadir un nodo

Al principio:
[code:1]ALGORITMO InsertaPrim(E/S TLista lis, E TDato d)
VARIABLES
TNodo *nuevo
INICIO
Asignar(nuevo) //Reservo memoria
nuevo->dato = d //Guardo el dato
nuevo->sig = lis //El primero pasa a ser el siguiente al nuevo
lis = nuevo// y el nuevo al primero
FIN[/code]

Al final:
[code:1]ALGORITMO InsUltimo(E/S TLista lis, E TDato d)
VARIABLES
TNodo *aux = lis, *nuevo
INICIO
Asignar(nuevo) //Reservo memoria
nuevo->dato = d //Guardo el dato
nuevo->sig = NULO //Sabemos que es el último
SI lis != NULO ENTONCES
MIENTRAS aux->sig != NULO HACER //Recorrer la lista hasta el final -1
aux = aux->sig
FIN MIENTRAS
aux->sig = nuevo //El último apunta al nuevo último
SI NO //Entonces la lista está vacía.
lis = nuevo
FIN SI
FIN[/code]

En una ordenada(por el dato):

[code:1]ALGORITMO InsertarOrden(E/S TLista lis, E TDato d)
VARIABLES
TNodo *nuevo, *aux = lis//guardo copia del puntero lis en aux para no perder referencia
TNodo *anterior = NULO
INICIO
Asignar(nuevo)
nuevo->dato = d
MIENTRAS aux != NULO Y aux->dato < d HACER //Lista ordenada ascendentemente
anterior = aux
aux = aux->sig //Paso al siguiente nodo
FIN MIENTRAS
SI anterior == NULO ENTONCES //Entonces es el primero(anterior no se ha actualizado), así que hacemos lo de antes
nuevo->sig = lis //El primero pasa a ser el siguiente al nuevo
lis = nuevo// y el nuevo al primero
SINO //Si no, está por ahí en medio (o al final)
nuevo->sig = aux //Apunta al siguiente
anterior->sig = nuevo //y el anterior deja de apuntar a aux para apuntar a nuevo
FINSI //Insertado : )
FIN
[/code]

Consultar numero de elementos de la lista

[code:1]ALGORITMO Natural numElem(E TLista lis)
VARIABLES
TNodo *aux = lis
Natural n = 0
INICIO
MIENTRAS aux != NULO HACER
aux=aux->sig
n++
FIN MIENTRAS
DEVOLVER n
FIN
[/code]
Eliminar un nodo de valor x

[code:1]ALGORITMO ElimNodo (E/S TLista lis, E TDato d) //Si está repetido, solo elimina la primera repetición
VARIABLES
TNodo *aux = lis, *anterior = NULO, *borrar
INICIO
MIENTRAS(aux != NULO Y aux->dato != d) HACER
anterior = aux
aux=aux->sig
FIN MIENTRAS
SI aux != NULO ENTONCES //Si el elemento está
SI anterior == NULO ENTONCES //El elemento es el primero
borrar = aux
lis = borrar->sig
SINO
borrar = aux //Guardo aux para borrarlo despues
anterior->sig = aux->sig //Me 'como' aux en la lista
FIN SI
Liberar(borrar)
FIN SI
FIN
[/code]

Por último, es buena práctica el liberar toda la memoria reservada a lo largo del programa:

[code:1]ALGORITMO vaciaLista(E/S TLista lis)
VARIABLES
TNodo *aux
INICIO
MIENTRAS lis != NULO HACER
aux = lis
lis = lis->sig
Liberar(aux)
FIN MIENTRAS
FIN
[/code]

Se puede rizar el rizo aún más. Si en el registro TNodo añades un puntero al nodo anterior (y en el primero es nulo) tienes una lista doblemente enlazada. Si haces que el último apunte al primero, tienes una lista circular. Y para rematar la faena, se puede tener una lista doblemente enlazada circular. Si quereis que amplie sobre alguno de esos temas, ya sabeis :)

Implementación usando clases y plantillas:
CLista.hpp
[code:1]#ifndef _CLISTA_HPP_
#define _CLISTA_HPP_

#include

template class CLista{
private:
struct TNodo{
TElem elem;
TNodo *sig;
};
TNodo *lis, *fin;
int nEl;

public:
CLista();
~CLista();
void insertar(TElem el);
TElem extraer(int pos);
void borrar(int pos);
bool esVacia();
int nElem();
};

#include "CLista.cpp"
#endif
[/code]

CLista.cpp
[code:1]template
CLista::CLista(){
lis = fin = NULL;
nEl = 0;
}
template
CLista::~CLista(){
TNodo *aux;
while(!esVacia()){
aux = lis;
lis = lis->sig;
delete aux;
}
}
template
void CLista::insertar(TElem el){
TNodo *nuevo = new TNodo;
nuevo->elem = el;
nuevo->sig = NULL;
if(esVacia()){
fin = lis = nuevo;
} else {
fin->sig = nuevo;
fin = nuevo;
}
nEl++;
}
template
TElem CLista::extraer(int pos){
TElem ret;
int p = 0;
TNodo *aux = lis;
while(!esVacia() && p aux = aux->sig;
p++;
}
if(p == pos){
ret = aux->elem;
}
return ret;
}

template
void CLista::borrar(int pos){
int p = 0;
TNodo *aux = lis, *ante = NULL;
while(!esVacia() && p ante = aux;
aux = aux->sig;
p++;
}
if(p == pos){
if(ante == NULL){
lis = lis->sig;
} else {
ante->sig = aux->sig;
}
delete aux;
nEl--;
}
}

template
bool CLista::esVacia(){
return (lis == NULL);
}

template
int CLista::nElem(){
return nEl;
}[/code]

Muy bonito, pero, ¿para qué me sirve a mi esto en mi “Baterfi Milnovesiento y pico”?

Puedes llevar una lista de enemigos, de balas, de cualquier objeto que vayas creando y destruyendo a lo largo del juego y quieras llevar un orden (o no)

Una vez que conocemos las listas enlazadas, se puede entrar a trapo con las estructuras avanzadas de datos propiamente dichas.

Próximamente: PILAS

Conocimientos adicionales



AVISO: Hasta ahora, creo que casi todo (si no todo) lo dicho vale casi cualquier lenguaje de programación. Hasta ahora, ya que clases y plantillas no están presentes, por ejemplo, en C


Clases y cabeceras de C++



Tener todo tu código en un mismo archivo... ya puedes tenerlo por orden alfabético, que cuando lleves 1000 líneas o así (no es tan difícil) te las vas a ver canutas para encontrar cualquier cosa.

Bueno, pues resulta que podemos utilizar la Programación Orientada a Objetos y darle un pelín de sentido semántico y orden al código. C++ lo implementa de manera bastante forzada (se nota la obligada compatibilidad con C), pero potente.

Una clase, visto desde el que la usa, es una caja negra. No sabes lo que hay ahí dentro, puesto que solo ves la fachada, la interfaz, pero la utilizas mediante métodos. Te da igual cómo esté hecho, puesto que funciona. Y si por casualidad cambiara la manera en la que se hace, no lo notarías siempre y cuando se mantengan los mismos métodos.

A nivel de programador, tenemos que desarrollar las tripas de la caja negra, la implementación, y podemos tener variables no visibles hacia fuera pero sí por los métodos de la clase: los atributos. (Suena un poco a juego de Rol, ¿verdad?)

Luego, obtendríamos la clase propiamente dicha, el molde con el que podemos crear las copias o instancias que queramos. Cada instancia tiene sus propios atributos que pueden ser iguales o no, pero mantienen comunes todos los métodos. Esto es así tanto desde el punto de vista teórico como desde el de mapeo de memoria del sistema.

En la práctica podemos hacer clases sobre, como, y con lo que nos de la gana, pero el propósito de las clases es de agrupar funciones y variables para darles un sentido completo. Por ejemplo, podemos tener nuestra clase CLista. O nuestra clase CPersona.

Según reza la Programación Orientada a Objetos, se pueden hacer muchísimas cosas con las clases, como Herencia y Polimorfismo, pero no pretendo llegar hasta ahí.

Absolutamente todas las clases tienen en común dos métodos básicos: El constructor y el destructor.

El constructor es un método que se llama automáticamente cada vez que se crea una nueva instancia de una clase. En C++ se escribe como el nombre de la clase. Puedes usarlo para muchas cosas, ya que acepta argumentos. No devuelve ningún resultado (es un procedimiento, no una función). Utilidad: dar valor inicial a las variables (en las clases la mayoría de lenguajes no dejan), reservar memoria dinámica...

El destructor, como habréis deducido, se llama cuando se elimina la instancia de la clase de memoria. Básicamente se usa para liberar memoria dinámica reservada durante el uso de la clase, y no acepta argumento alguno. En C++ se denota por el nombre de la clase precedido por un '~'

Ambos métodos pueden estar vacíos, pero (dependiendo del lenguaje) es obligatoria o muy recomendada su presencia.

Pasando a C++, para declarar una clase nueva se utiliza la palabra reservada class seguida del nombre de la clase. También se utilizan public: para diferenciar la parte pública, la interfaz, de la privada, la implementación, con private:. Todo lo que haya debajo de una de éstas etiquetas será público o privado, hasta el fin de la clase o hasta encontrar otra que lo contradiga.

Un ejemplo de clase podría ser éste:
[code:1]class CPersona{
public:
CPersona(int e, string n, string ap, char s);
~CPersona();
int dimeEdad();
string comoTeLlamas();
private:
int edad;
string nombre;
string apellidos;
char sexo;
};[/code]

¡¡ATENTOS AL PUNTO Y COMA AL FINAL!!

¿Tenemos con ésto ya nuestra clase? No, daos cuenta de que ahí sólo hemos definido los métodos, hay que implementarlos. Esto se hace fuera de las llaves, y tienes que indicar que esa función es un método de tu clase y no una cualquiera que haya por ahí, con el nombre de la clase y el operador de ámbito ::

Ejemplo:
int CPersona::dimeEdad(){
    return edad;
}[code]

Una vez implementada, puedes hacer instancias de tu clase más o menos como si fueran variables. Si el constructor acepta parámetros, has de pasarlos.

Para acceder a la parte pública de una clase, se hace como en los registros ([b]struct[/b]):
[code]CPersona primo(23, "Benito", "Poncela", 'M');
cout << primo.edad() << endl;[/code]

Con todo esto hemos conseguido darle un poco más de sentido a nuestro código pero... sigue igual de "por en medio".

Bueno, otra cosa de las clases es que se suelen repartir en dos ficheros, un .h con la cabecera y la interfaz, y un .cpp con la implementación. La relación se consigue de la siguiente manera: el archivo .cpp tiene al principio un [code]#include "mifichero.h"[/code], y se compila junto con el resto del código. El .h no se compila, y debe de hacerse un pequeño truco para evitar inclusiones mútliples:
[code]#ifndef _MIARCHIVO_H_
#define _MIARCHIVO_H_

.
.
.
Todo tu código del .h
.
.
.

#endif[/code]

Con esa directiva conseguimos que si no hemos incluido antes el .h, _MIARCHIVO_H_ (nombre que debe de ser diferente para cada .h y suele ser el nombre de archivo) no esté definido, y "ifndef" devuelva verdadero (if not defined). Nada más saber que no está definido, lo definimos con el "define", y así conseguimos sólo incluir una vez el archivo. Al final, hacemos un "endif".
Todo ésto tiene antepuesto un '#' porque son directivas del preprocesador, una de las distintas fases por las que pasa nuestro programa al compilarse.

Luego en nuestro programa sólo tendremos que incluir la cabecera (.h) como incluimos la iostream u otras bibliotecas)

[anchor]plant[/anchor]
[b][center]Plantillas en C++[/center][/b]
Ya hemos vencido la batalla a los punteros, y exhaustos nos ponemos a usar nuestro bonito y personalizado nuevo tipo. Pero... vaya, cada vez que lo uses con un tipo de dato distinto, vas a tener que reescribir un montón de código... [b]o no[/b]

Para eso creó el [inserte deidad venerada aquí] las plantillas, con algo de ayuda de [inserte némesis, y por ende mala persona, de la deidad anterior aquí] 

las plantillas. ¿Por qué la última parte de la frase anterior? Pues porque si bien nos ayudan a obtener unos tipos muy versátiles que nada tiene que envidiar a la STL en cuanto a aplicación, su forma de declarar es un tanto... "especial". Y fea de cojones.

Si tenemos hecha ya nuestra [u]clase[/u] del tipo, las modificaciones serán las siguientes:

Al declarar la clase, añadimos template<typename TipoGenerico1, typename TipoGenerico2....> según los que necesitemos. A partir de ahí, en la declaración de 

la clase los TipoGenérico[i]n[/i] son tipos totalmente válidos.
[code]template <typename TElem> class ClaseEjem{
	private:
.
.
        public:
.
.
};
[/code]

Cosa fea: en la implementación, tendremos que poner template<typename TipoGenerico1, typename TipoGenerico2....> arriba de [b]todas [/b]y cada una de las 

implementaciones particulares de cada método. Además, después tenemos que añadir antes del operador de ámbito( :: ) <TipoGenerico1, TipoGenerico2...>
Para la clase ejemplo anterior:
[code]CLista<TElem>::ClaseEjem(){
  .
  .
  .

}

template <typename TElem>
CLista<TElem>::~ClaseEjem(){
  .
  .
  .
}
.
.
.[/code]

Si se te olvidara algo, o lo pusieras mal, los mensajes de error del compilador van a ser los más raros que hayas visto hasta ahora.

Además, vas a tener que reordenar tu código.

Si tienes todo en un mismo fichero, mientras no cambies el orden habitual (interfaz/cabecera antes que implementación) no habrá problema.

Sin embargo, si eres mas ordenado y pulcro con tu código y lo tienes separado en un .h con la cabecera y un .cpp con la implementación, no te va a compilar (no debe xD). Tienes dos opciones:

[list][b]Pasar todo a un .hpp[/b], formato nuevo de C++, que básicamente representa a un .h pero con la implementación ya incluida. El .hpp no se compila, se incluye como un .h normal.

[b]Convertir tu .h a un .hpp[/b], para lo cual tendrás que hacer un pequeño cambio. Para lulz general, ahora no es el .cpp el que incluye al .h, sino que [b]el .hpp es el que incluye al .cpp[/b], y no se compila ninguno de los dos. Se incluye el .hpp y punto.[/list]

Ahora que ya habrás pensado en varias ocasiones "por qué me metería yo en estos berenjenales con lo bien que me iba a mi sin plantillas" y por fin has acabado, veamos como usarlas.

Hay que incluir, obviamente, el .hpp, da igual cómo esté implementada la plantilla. Después, cuando creemos una instancia de esa clase, lo haremos como de costumbre pero concretando los n TipoGenérico que hubiéramos especificado en la plantilla, de la siguiente manera:
[code]ClaseEjem<int, char*, float, double...> miClasePlantilla;[/code]

O para los más dinámicos:
[code]ClaseEjem<int, char*, float, double...> *miClasePlantillaMasGuay = new ClasePlantilla();

A partir de ahí, todo es igual que sin plantillas. Pero nos hemos ahorrado el tener que escribir una para cada tipo de dato.

MUCHO OJO con el tipo char* (cadena de texto), ya que no se comporta como los demás tipos, y algunas operaciones fallarán. Recomiendo en las plantillas usar el tipo string de la biblioteca cstring o string.h o el equivalente en tu lenguaje de programación.

  • joce

  • Mascarón Rojo

  • vida restante: 100%
  • Registrado: 14 jun 2005
  • Mensajes: 559
#2

Escrito 03 mayo 2009 - 11:01

(Quoteadme por favor, que no tengo 100 mensajes todavía :? )

Bueno, estaba repasando apuntes, y he decidido compartir esto con vosotros por si os fuera útil.

Ante todo, lo hare en pseudolenguaje castellano (el mio se parece bastante a C++ con toques de Visual Basic :] ) para que sea más general. Simplemente intentaré recopilar lo que he ido aprendiendo con el tiempo. Doy por sabidos los conceptos puntero, clase y memoria dinámica. Repito que esto no es un "Aprende C++ en 10 minutos"

Usaré Asignar() para asignar memoria dinámica y Liberar() para liberarla. El símbolo del puntero, el clásico de C++: “*”

Luego intentaré esbozar para qué creo yo que valdrían programando un videojuego, por qué merece la pena usarlas.


Contenido:

Listas enlazadas
Pilas
Colas
Listas posicionales
Tablas de dispersión
Árboles Binarios



Listas Enlazadas

Es lo más simple de entre lo no tan simple. Nos va a servir para construir el resto de las estructuras.
Es el concepto de una cadena en la que se van engarzando eslabones o quitando según necesidad. A los eslabones los voy a llamar Nodos. En estos nodos guardaremos un puntero del mismo tipo para apuntar al siguiente.

Imagen Enviada

Voy a definir el tipo TipoNodo (o TNodo para abreviar) que es un registro(struct) tal que así:

[code:1]TIPOS

Registro TipoNodo
TipoDato dato
TipoNodo *sig //Puntero a siguiente nodo
Fin[/code]

//Y el tipo TipoLista (o TLista) como un puntero a nodo (facilita la comprensión)

TipoNodo *TipoLista

¿Qué pasa cuando hacemos que sig apunte a otro registro del tipo TNodo? ¿Y este a su vez a otro? Obtenemos una lista enlazada. Es como engarzar una cadena. Podeis pensar “Vaya complicación con lo que molan los arrays/vectores”. Bueno, es una complicación necesaria para seguir adelante :D

Para manejarlo, crearemos una clase, la clase TipoLista que como atributos solo necesita un puntero de tipo TNodo, que será nuestra “cabeza de lista”. Desde ese puntero accederemos al resto de la lista, y si lo perdemos, perdemos la lista entera!!

El convenio que hay, es de que valga NULO el puntero siguiente (o el de cabeza) para indicar el fin de la lista. Por tanto, una lista vacía, su cabeza sería NULO


Queda una cosa así más o menos:

Imagen Enviada


Además la lista puede ser ordenada o no (depende de con qué propósito vaya a usarse)

Cosas que debes de poder hacer con una lista enlazada:

Añadir un nodo

Al principio:
[code:1]ALGORITMO InsertaPrim(E/S TLista lis, E TDato d)
VARIABLES
TNodo *nuevo
INICIO
Asignar(nuevo) //Reservo memoria
nuevo->dato = d //Guardo el dato
nuevo->sig = lis //El primero pasa a ser el siguiente al nuevo
lis = nuevo// y el nuevo al primero
FIN[/code]

Al final:
[code:1]ALGORITMO InsUltimo(E/S TLista lis, E TDato d)
VARIABLES
TNodo *aux = lis, *nuevo
INICIO
Asignar(nuevo) //Reservo memoria
nuevo->dato = d //Guardo el dato
nuevo->sig = NULO //Sabemos que es el último
SI lis != NULO ENTONCES
MIENTRAS aux->sig != NULO HACER //Recorrer la lista hasta el final -1
aux = aux->sig
FIN MIENTRAS
aux->sig = nuevo //El último apunta al nuevo último
SI NO //Entonces la lista está vacía.
lis = nuevo
FIN SI
FIN[/code]

En una ordenada(por el dato):

[code:1]ALGORITMO InsertarOrden(E/S TLista lis, E TDato d)
VARIABLES
TNodo *nuevo, *aux = lis//guardo copia del puntero lis en aux para no perder referencia
TNodo *anterior = NULO
INICIO
Asignar(nuevo)
nuevo->dato = d
MIENTRAS aux != NULO Y aux->dato < d HACER //Lista ordenada ascendentemente
anterior = aux
aux = aux->sig //Paso al siguiente nodo
FIN MIENTRAS
SI anterior == NULO ENTONCES //Entonces es el primero(anterior no se ha actualizado), así que hacemos lo de antes
nuevo->sig = lis //El primero pasa a ser el siguiente al nuevo
lis = nuevo// y el nuevo al primero
SINO //Si no, está por ahí en medio (o al final)
nuevo->sig = aux //Apunta al siguiente
anterior->sig = nuevo //y el anterior deja de apuntar a aux para apuntar a nuevo
FINSI //Insertado : )
FIN
[/code]

Consultar numero de elementos de la lista

[code:1]ALGORITMO Natural numElem(E TLista lis)
VARIABLES
TNodo *aux = lis
Natural n = 0
INICIO
MIENTRAS aux != NULO HACER
aux=aux->sig
n++
FIN MIENTRAS
DEVOLVER n
FIN
[/code]
Eliminar un nodo de valor x

[code:1]ALGORITMO ElimNodo (E/S TLista lis, E TDato d) //Si está repetido, solo elimina la primera repetición
VARIABLES
TNodo *aux = lis, *anterior = NULO, *borrar
INICIO
MIENTRAS(aux != NULO Y aux->dato != d) HACER
anterior = aux
aux=aux->sig
FIN MIENTRAS
SI aux != NULO ENTONCES //Si el elemento está
SI anterior == NULO ENTONCES //El elemento es el primero
borrar = aux
lis = borrar->sig
SINO
borrar = aux //Guardo aux para borrarlo despues
anterior->sig = aux->sig //Me 'como' aux en la lista
FIN SI
Liberar(borrar)
FIN SI
FIN
[/code]

Se puede rizar el rizo aún más. Si en el registro TNodo añades un puntero al nodo anterior (y en el primero es nulo) tienes una lista doblemente enlazada. Si haces que el último apunte al primero, tienes una lista circular. Y para rematar la faena, se puede tener una lista doblemente enlazada circular. Si quereis que amplie sobre alguno de esos temas, ya sabeis :)

Muy bonito, pero, ¿para qué me sirve a mi esto en mi “Baterfi Milnovesiento y pico”?

Puedes llevar una lista de enemigos, de balas, de cualquier objeto que vayas creando y destruyendo a lo largo del juego y quieras llevar un orden (o no)

Una vez que conocemos las listas enlazadas, se puede entrar a trapo con las estructuras avanzadas de datos propiamente dichas.

Próximamente: PILAS


Quoteado, compañero de piso ;)

  • IsGreen

  • Neonate

  • vida restante: 100%
  • Registrado: 12 ene 2009
  • Mensajes: 73
#3

Escrito 03 mayo 2009 - 20:15

Me ha parecido interesante tu ejercicio y he intentado resolver el entuerto 8O . Este es el código:


[code:1]

Nuevo código en el siguiente post.

[/code]

He añadido la función 'DevolverValorLista' para obtener los valores de la lista, pero en el bucle del bloque principal 'main' la función 'numElem' devuelve 0 y no llega realizar ninguna sentencia del bucle.

También he sustituido en dicho bucle numElem(Lista) por un valor numérico, y la función DevolverValorLista que he creado devuelve siempre 0.

Seguramente el código no es correcto aunque no presenta errores de compilación.

Sólo una apreciación. Al declarar las variables dentro de una función, entiendo que son variables locales que son eliminadas o dejan de ser visibles al salir de dicha función.

Saludos.

  • wiyarmir

  • Elder

  • vida restante: 100%
  • Registrado: 27 mar 2009
  • Mensajes: 108
#4

Escrito 03 mayo 2009 - 22:46

Seguramente el código no es correcto aunque no presenta errores de compilación.


Esa es la gracia de trabajar con punteros, todo perfecto hasta que ejecutas y BUM! segmentation fault XD

Pequeños detalles:
-Con punteros se suele trabajar con while y no con for. No por nada, sino porque al haber más de una condición (al igual que con cadenas de caracteres, tengo que comprobar que no he llegado al final) un for queda mucho más guarrete.

EDITO: Se me olvido ponerte tu devolver valor lista actualizado.... que cabeza la mia! 8O
[code:1]int DevolverValorLista (TNodo *lis, int situacion) {
if ((situacion==0) || (situacion > numElem(lis))) return 0;
TNodo *aux = lis;
int pos = 0;
while(aux != NULL && pos < situacion){//mientras no haya llegado al final y no haya llegado a la posición...
aux = aux->sig;
pos++;
}
if(aux != NULL){//aux sera NULO si ha llegado al final
return aux->dato;
}
return 0;//por ejemplo
}[/code]

-En realidad aqui

[code:1]void ElimNodo(TNodo *lis, int d) { //Si está repetido, solo elimina la primera repetición
TNodo *aux = lis, *anterior = NULL, *borrar;
while ((aux != NULL) && (aux->dato != d)) {
anterior = aux;
aux=aux->sig;
}
if (aux != NULL) { //Si el elemento está
if (anterior == NULL) { //El elemento es el primero
borrar = aux;
lis = borrar->sig;
}
else {
borrar = aux; //Guardo aux para borrarlo despues
anterior->sig = aux->sig; //Me 'como' aux en la lista
}
// Liberar borrar sería: delete borrar; pero borrar no ha sido declarada como variable puntero de memoria dinámica.
}
}
[/code]

Sí has declarado memoria dinámica: lo has hecho con el operador new hace tan sólo unas líneas :) así que puedes escribir

[code:1]delete borrar;[/code]

sin miedo. Quizás te referías a que no es el mismo puntero que has usado para crearlo: bueno, eso da igual, ya que apunta a una zona que hemos creado anteriormente.

Después, no se si se me ha pasado ponerlo en el post, pero la lista no es global. De hecho las variables globales son bastante peligrosas. La lista se declararía como
[code:1]typedef TNodo *TLista;[/code]

Y después, en el main:

[code:1]TLista Lista = NULL;[/code]

Muy importante ese NULL porque si no falla todo al suponer que la lista no está vacía. Tu programa podría fallar porque al declarar Lista arriba, aunque está como puntero, no está a NULO, que es el valor con el que decimos que está vacía. No falla porque has usado insertaPrim() para el primero Nodo.

Pero tu insertaPrim() tiene un fallo, y es que no has considerado que he puesto el parámetro Lista como E/S -> Entrada/Salida. Estoy modificando el puntero inicial, por tanto, para que quede constancia de los cambios debo pasar el puntero por referencia. Sale una cosa así de fea:
[code:1]void InsertaPrim(TNodo* &lis, int d) {[/code]
Pero cuando se implementa con clases no hace falta al ser un atributo.

Otra cosa que creo que se me olvidó comentar (voy a hacer un edit de los buenos en cuanto postee esto XD):
Si se reserva memoria dinámica en un programa, es normal liberarla al final, ya que si no se libera esa memoria no se puede utilizar hasta el próximo reinicio. Para ello añado:
[code:1]void vaciaLista(TLista l){
TNodo *aux;
while( l != NULL){
aux = l;
l = l->sig;
delete aux;
}
}[/code]
y lo llamo al final.

Quisquillosería:
[code:1]for (int i=1; i cout << "Posicion: " << i << "\t" << DevolverValorLista (Lista,i) << endl;
}[/code]

Ahí, suponiendo que tengas una lista larga, estás llamando a numElem() en cada iteración, y estás recorriéndola enterita... quizás con 7 nodos no se note pero... jajaja soy un quisquilloso XD

Por lo demás, no había mucho que hacer, pero sin tu respuesta no me habría dado cuenta de mis fallos :P

Saludos

  • Gagle

  • Sheikah

  • vida restante: 100%
  • Registrado: 22 mar 2008
  • Mensajes: 9.856
#5

Escrito 04 mayo 2009 - 09:09

No seria mejor hacerlo con clases? :-/

"640KB tendrían que ser suficientes para cualquiera."


Bill Gates, 1981.
¿Será cierto?



  • wiyarmir

  • Elder

  • vida restante: 100%
  • Registrado: 27 mar 2009
  • Mensajes: 108
#6

Escrito 04 mayo 2009 - 09:25

No seria mejor hacerlo con clases? :-/

"640KB tendrían que ser suficientes para cualquiera."


Bill Gates, 1981.
¿Será cierto?



Sí, pero el ha preferido hacerlo sin clases. Totalmente válido.

  • IsGreen

  • Neonate

  • vida restante: 100%
  • Registrado: 12 ene 2009
  • Mensajes: 73
#7

Escrito 05 mayo 2009 - 00:15

[quote name="Gagle"]
No seria mejor hacerlo con clases? :-/

[/quote]

Sí, pero el ha preferido hacerlo sin clases. Totalmente válido.
[/quote]

He intentado desarrollar una clase o una estructura pero no he podido, O:) , si alguien pudiera enviarla le estaría muy agradecido.

He terminado de corregir el anterior código siguiendo las puntualizaciones de wiyarmir ;) .

[code:1]

#include
using namespace std;

struct TNodo {
int dato;
TNodo *sig;
};

typedef TNodo *TLista;

void InsPrimero(TNodo* &lis, int d) {
TNodo *nuevo = new TNodo;
nuevo->dato = d; //Guardo el dato
nuevo->sig = lis; //El primero pasa a ser el siguiente al nuevo
lis = nuevo; // y el nuevo al primero
}

void InsUltimo (TNodo* &lis, int d) {
TNodo *aux = lis;
TNodo *nuevo = new TNodo;
nuevo->dato = d; //Guardo el dato
nuevo->sig = NULL; //Sabemos que es el último
if (lis!= NULL) {
while (aux->sig != NULL) {
aux = aux->sig; //Recorrer la lista hasta el final -1
}
aux->sig = nuevo; //El último apunta al nuevo último
}
else {
lis = nuevo; //Entonces la lista está vacía.
}
}

void InsertarOrden(TNodo* &lis, int d) { // En una ordenada(por el dato)
TNodo *aux = lis; //guardo copia del puntero lis en aux para no perder referencia
TNodo *anterior = NULL;
TNodo *nuevo = new TNodo;
nuevo->dato = d;
while ((aux != NULL) && (aux->dato < d)) { //Lista ordenada ascendentemente
anterior = aux ;
aux = aux->sig; //Paso al siguiente nodo
}
if (anterior == NULL) { //Entonces es el primero(anterior no se ha actualizado), así que hacemos lo de antes
nuevo->sig = lis; //El primero pasa a ser el siguiente al nuevo
lis = nuevo; // y el nuevo al primero
}
else { //Si no, está por ahí en medio (o al final)
nuevo->sig = aux; //Apunta al siguiente
anterior->sig = nuevo; //y el anterior deja de apuntar a aux para apuntar a nuevo
} //Insertado : )
}

int numElem(TNodo *lis) { // Consultar numero de elementos de la lista
TNodo *aux = lis;
int n = 0;
while (aux != NULL) {
aux=aux->sig;
n++;
}
return n;
}

void ElimNodoRepetido(TNodo* &lis, int d) { //Si está repetido, solo elimina la primera repetición
TNodo *aux = lis, *anterior = NULL, *borrar;
while ((aux != NULL) && (aux->dato != d)) {
anterior = aux;
aux=aux->sig;
}
if (aux != NULL) { //Si el elemento está
if (anterior == NULL) { //El elemento es el primero
borrar = aux;
lis = borrar->sig;
}
else {
borrar = aux; //Guardo aux para borrarlo despues
anterior->sig = aux->sig; //Me 'como' aux en la lista
}
delete borrar;
}
}

int DevolverValorLista (TNodo *lis, int pos) {
if ((pos<0) || (pos > numElem(lis))) return 0;
TNodo *aux=lis;
for (int i=0; i aux = aux->sig;
}
return aux->dato;
}

void vaciarLista(TNodo* &lis){
TNodo *aux;
while( lis != NULL){
aux = lis;
lis = lis->sig;
delete aux;
}
}


void main () {

TLista Lista=NULL;

for (int i=1; i<11; i++) {
InsUltimo(Lista,i);
}

int ii=numElem(Lista);
for (int i=0; i cout << "Posicion: " << i << "\t" << DevolverValorLista (Lista,i) << endl;
}

InsUltimo(Lista,100);
InsertarOrden (Lista,21);
ElimNodoRepetido(Lista,5);
cout << endl << endl;

ii=numElem(Lista);
for (int i=0; i cout << "Posicion: " << i << "\t" << DevolverValorLista (Lista,i) << endl;
}

vaciarLista (Lista);
cout << endl << endl;
cout << "Numero de elementos despues de vaciarLista: " << numElem(Lista) << endl << endl;

}
[/code]

Saludos y gracias.

  • Ellolo17

  • Midna

  • vida restante: 100%
  • Registrado: 16 nov 2006
  • Mensajes: 6.208
#8

Escrito 05 mayo 2009 - 12:53

Entrada añadida al indice ;)

  • wiyarmir

  • Elder

  • vida restante: 100%
  • Registrado: 27 mar 2009
  • Mensajes: 108
#9

Escrito 08 mayo 2009 - 21:43

Perdón por el retraso; exámenes, prácticas y todo ese rollo... ya sabeis

Actualizado con la versión con clases y plantillas, y explicación de plantillas

Currandome Pilas

EDITO: También breve introducción a las clases


Este tema ha sido archivado. Esto significa que no puedes responder en este tema.
publicidad