Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente...

18

Click here to load reader

Transcript of Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente...

Page 1: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

ING:MSc.ELIOMAR NIEVES

GUÌA DE LISTAS EN C++

Una lista enlazada es un tipo de dato auto-referenciado porque contienen un puntero o link a otro dato del mismo tipo. Las listas enlazadas permiten inserciones y eliminación de nodos en cualquier punto de la lista en tiempo constante (suponiendo que dicho punto está previamente identificado o localizado), pero no permiten un acceso aleatorio. Existen diferentes tipos de listas enlazadas: Lista Enlazadas Simples, Listas Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares.

Aplicaciones de las listas enlazadas

Las listas enlazadas son usadas como módulos para otras muchas estructuras de datos, tales como pilas, colas y sus variaciones.

El campo de datos de un nodo puede ser otra lista enlazada. Mediante este mecanismo, podemos construir muchas estructuras de datos enlazadas con listas; esta práctica tiene su origen en el lenguaje de programación Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la única), y ahora es una característica común en el estilo de programación funcional.

A veces, las listas enlazadas son usadas para implementar arrays asociativos, y estas en el contexto de las llamadas listas asociativas. Hay pocas ventajas en este uso de las listas enlazadas; hay mejores formas de implementar éstas estructuras, por ejemplo con árboles binarios de búsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinámicamente creada fuera de un subconjunto propio de nodos semejante a un árbol, y son usadas más eficientemente para recorrer ésta serie de datos

Listas simples enlazadas

La lista enlazada básica es la lista enlazada simple la cual tiene un enlace por nodo. Este enlace apunta al siguiente nodo en la lista, o al valor NULL o a la lista vacía, si es el último nodo.

Una lista enlazada simple contiene dos valores: el valor actual del nodo y un enlace al siguiente nodo

Page 2: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

El siguiente ejercicio muestra como se declara una lista, y a través de funciones se agregan datos, lo que origina en cada oportunidad la creación de un nuevo nodo y también muestra la forma de mostrar el contenido de una lista. #include <iostream> #include <stdlib.h> using namespace std; struct nodo{ int info; //parte de datos en el nodo nodo *sgt; //puntero siguiente, vea que sgt es de tipo nodo }; void agrega(nodo **cab, nodo **fin); void muestra(nodo *cab); int main() { nodo *c=NULL,*f=NULL; //puntero de cabecera, y puntero de fin de lista int opcion; do{ cout<<"1) Ingresa un dato (numero entero)."<<endl; cout<<"2) Muestra los datos ingresados."<<endl; cout<<"Pulse cero para terminar"<<endl; cout<<"Pulse cero para terminar"<<endl; cout<<"ingrese opcion"<<endl;

Page 3: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

cin>>opcion; switch(opcion){ case 0: exit(0);break; case 1: agrega(&c, &f);break; case 2: muestra(c);break; } } while(opcion!=0); system("PAUSE"); return 0; } void agrega(nodo **cab, nodo **fin){ int num; cout<<"ingrese informacion"<<endl; cin>>num; if((*cab)==NULL){ *cab = new nodo; //se asigna la dirección de nodo a cab (*cab)->info =num; //se guarda num dentro del nodo (*cab)->sgt=NULL; // apuntador siguiente se apunta a nulo porque es un solo nodo (*fin)=(*cab); // como hay un solo nodo principio y fin apuntan a la misma dirección }else{

Page 4: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

(*fin)->sgt=new nodo; //este es un nodo nuevo por eso fin se apunta a siguiente (*fin)->sgt->info=num; //se guarda num dentro del nodo nuevo (*fin)=(*fin)->sgt; //como hay un nuevo nodo se actualiza el puntero fin (*fin)->sgt=NULL; //la teoría dice que todo último nodo debe apuntar a null } } void muestra(nodo *cab){ cout<<"elementos en la lista"<<endl; nodo* temp; temp=cab; while ( temp != NULL){ cout<<temp->info<<" "; //se hace referencia al contenido del nodo temp=temp->sgt; // se le da la dirección en memoria del siguiente nodo } } Explicaciòn de funciòn agrega

Cuando ingresas el dato, llamado num, verifica si la cabeza (cab) es nula, si es nula se crea new nodo, que será el primero y será apuntado por cab, indicando el inicio de la lista, y el fin tambien a la vez. Si no es nulo, entonces solo se toma al puntero fin, ingresa a su campo sgt, y se crea new nodo, stg está apuntando al siguiente nodo, y se puede ingresar a su campo info haciendo (*fin)->sgt->info=num; y de paso se iguala con num para agregar el nuevo valor. ahora el fin es otro, porque hay uno nuevo, entonces se hace (*fin)=(*fin)->sgt;

Page 5: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

EJEMPLO II

El programa permite Insertar, Borrar, Mostrar y Muestra el primer nodo. Se emplea el uso de la clase nodo y la clase lista, donde lista es una clase amiga dentro de la clase nodo. #include <iostream> using namespace std; class nodo { public: nodo(int v, nodo *sig = NULL) { valor = v; siguiente = sig; } private: int valor; nodo *siguiente; friend class lista; }; typedef nodo *pnodo;

Page 6: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

class lista { public: lista() { primero = actual = NULL; } ~lista(); void Insertar(int v); void Borrar(int v); bool ListaVacia() { return primero == NULL; } void Mostrar(); void Siguiente() { if(actual) actual = actual->siguiente; } void Primero() { actual = primero; } void Ultimo() { Primero(); if(!ListaVacia()) while(actual->siguiente) Siguiente(); } bool Actual() { return actual != NULL; } int ValorActual() { return actual->valor; } private: pnodo primero; pnodo actual; };

Page 7: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

lista::~lista() { pnodo aux; while(primero) { aux = primero; primero = primero->siguiente; delete aux; } actual = NULL; } void lista::Insertar(int v) { pnodo anterior; // Si la lista está vacía if(ListaVacia() || primero->valor > v) { // Asignamos a lista un nuevo nodo de valor v y primero = new nodo(v, primero); // cuyo siguiente elemento es la lista actual } else { anterior = primero; // Buscar el nodo de valor menor a v // Avanzamos hasta el último elemento o hasta que el siguiente tenga // un valor mayor que v while(anterior->siguiente && anterior->siguiente->valor <= v)

Page 8: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

anterior = anterior->siguiente; // Creamos un nuevo nodo después del nodo anterior, y cuyo siguiente // es el siguiente del anterior anterior->siguiente = new nodo(v, anterior->siguiente); } } void lista::Borrar(int v) { pnodo anterior, nodo; nodo = primero; anterior = NULL; while(nodo && nodo->valor < v) { anterior = nodo; nodo = nodo->siguiente; } if(!nodo || nodo->valor != v) return; else { // Borrar el nodo if(!anterior) // Primer elemento primero = nodo->siguiente; else // un elemento cualquiera

Page 9: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

anterior->siguiente = nodo->siguiente; delete nodo; } } void lista::Mostrar() { nodo *aux; aux = primero; while(aux) { cout << aux->valor << "-> "; aux = aux->siguiente; } cout << endl; } int main() { lista Lista; int a,i; for(i=0;i<4;i++){ cout<<"Ingrese Numero:";

Page 10: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

cin>>a; Lista.Insertar(a); } Lista.Mostrar(); Lista.Primero(); cout<<"Primer Valor: "<<Lista.ValorActual()<<"\n"; cout<<"Ingrese Numero a borrar:"; cin>>a; Lista.Borrar(a); Lista.Mostrar(); cin.get(); return 0; }

CLASES EN C++

En escencia, una clase en C++ es una estructura en el estilo de C con algunas ventajas sencillas pero muy potentes.

Declaración de clases

Para declarar una clase, todo lo que se necesita es escribir una definición de estructura y sustituir la palabra reservada struct por class. Por ejemplo, una clase empleado con campos como el nombre, el

Page 11: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

departamento, la posición, el una función que nos imprima la información de este quedaría así:

class Empleado { char* m_nombre; char* m_departamento; char* m_posicion; long m_salario; void Imprimir( Empleado infoEmpleado); } Cuando usted declara una clase en C++, no se reserva memoria para la clase hasta que usted crea un objeto de la clase. Crear un objeto de una clase se llama instanciar un objeto. Un objeto creado de una clase de denomina instancia de una clase. Por ejemplo, yo puedo tener una instancia de empleado con el valor en m_nombre=Jose, m_departamento=Sistemas, m_posicion=programador y m_salario=3000000 por ejemplo.

Especificadores de acceso

C++ utiliza especificadores de acceso para permitir controlar a una clase el acceso a las variables de datos de esa clase. Los especificadores de acceso permiten acceder a algunos miembros de la clase y restringir el acceso a otros. Hay tres especificadores de acceso en C++: public, private y protected. Cuando usted declara público ( public) un miembro de una clase, usted permite el acceso a tal miembro desde dentro y fuera de la clase. Los miembros de datos que son declarados protegidos ( protected ) son únicamente accesibles por funciones miembro de la clase, pero no se pueden acceder a ellos desde otras clases. Cuando un miembro de una clase es declarado privado ( private ) es ináccesible no sólo desde otras clases y otras partes del programa, sino también desde sus clases derivadas. Las clases derivadas se explicara posteriormente. Miremos el siguiente programa de ejemplo. Se compone de tres partes: la primera una declaración de una clase llamada Empleado:

class Empleado { private: char* m_nombre; char* m_departamento; char* m_posicion; long m_salario; public: void ImprimirInfo(); void SetNombre( char* nombre ) { m_nombre = nombre } void SetDepartamento( char * departamento) { m_departamento = departamento } void SetPosicion ( char* posicion ) { m_posicion = posicion } void SetSalario ( long salario ) { m_salario = salario } const char* GetNombre( ){ return m_nombre }

Page 12: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

const char* GetDepartamento( ){ return m_departamento } const char* GetPosicion( ){ return m_posicion } const char* GetSalario( ){ return m_salario } };

Las funciones Set�ombre, SetDepartamento, setPosicion, setSalario, Get�ombre, GetDepartamento,

GetPosicion y GetSalario se denominan funciones intercaladas, que son funciones que se declaran en una sola línea. Las variables de miembro son declaradas privadas para que funciones de miembro de otras funciones no tengan acceso a ellas sino a travez de la correspondiente funcion Get o Set. Las funciones de miembro si son declaradas públicas de tal modo que se pueda acceder a ellas desde otras funciones. La definición de la función PrintInfo puede quedar así:

void Empleado::ImprimirInfo( ) { cout << "Nombre: " << m_nombre << '\n'; cout << "Departamento: " << m_departamento << '\n'; cout << "Puesto: " << m_posicion << '\n'; cout << "Salario: " << m_salario << '\n'; } Los dos dos puntos ( :: ) se denomina operador de resolución de ambito. Nos indica que la función que estamos definiendo que en este caso es ImprimirInfo, pertenece a la clase Empleado. La tercera parte es la función main. Veamos como podría ser:

void main() { //creacion de un objeto de la clase Empleado Empleado empleado12; //asignacion de valores a las variables miembro empleado12.SetNombre("Jose"); empleado12.SetDepartamento("Sistemas"); empleado12.SetPosicion("Programador"); empleado12.SetSalario(3000000); //impresion de los datos empleado12.ImprimirInfo(); }

Entonces, primero en : Empleado empleado12; Se instancia un objeto de la clase Empleado con nombre empleado12. Entonces empleado12 tiene la

Page 13: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

estructura de la clase Empleado. Luego, en las líneas siguientes a la instanciación del objeto, se le asignan los valores iniciales a sus variables: //asignacion de valores a las variables miembro empleado12.SetNombre("Jose"); empleado12.SetDepartamento("Sistemas"); empleado12.SetPosicion("Programador"); empleado12.SetSalario(3000000); Finalmente se llama ImprimirInfo para imprimir el contenido de las variables: //impresion de los datos empleado12.ImprimirInfo(); que lo que hará es imprimir el valor de las varibles en la pantalla. Permitir el acceso a las variables solo a travez de funciones, que en la mayoría de los casos se llaman SetXxx y GetXxx, se llama encapsulación de datos. Las funciones que necesitan valores de otra clase, llaman a las funciones que les dan acceso y obtienen estos datos sin conocimiento de detalles específicos de como se manipulan los datos.

Operador de resolución de ambito

El operador de ambito permíte acceder de otra manera funciones de miembro y variables de miembro de una clase. Cuando aparece el operador de resolución de ámbito entre el nombre de la clase y el nombre de la función en un programa significa que la función especificada es un miembro de la clase especificada:

Empleado::ImprimirInfo();

El operador de resolución de ambito se suele utilizar para llamar funciones que se encuentran fuera del ambito de la función de llamada. Entonces, para llamar la función ImprimirInfo() de la clase Empleado se fuera de su ambito se debe utilizar este operador.

La principal diferencia entre este operador y los operadores punto y flecha es que el operador de resolución de ambito se utiliza para acceder a miembros de clases, y el operador punto y flecha para acceder a miembros de objetos específicos.

Veamos el siguiente código:

::MessageBox("Prueba del operador de resolucion");

Si el operador de resolución de ambito aparece sin un nombre de clase delante, significa que la función que esta llamando ( MessageBox ) no es miembro de ninguna clase.

Page 14: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

El apuntador this

Este apuntador lo tiene todo objeto en C++, apuntando a sí mismo. Se puede utilizar este apuntador en cualquier lado para acceder a todos los miembros del objeto al cual esta apuntando este apuntador this. Veamos el siguiente código:

#include <iostream.h>

class Miclase { public: Miclase() {} //constructor por defecto ~Miclase() {} //destructor void yoMismo() { return this } };

int main() { void* pClase; Miclase unObjeto; pClase = unObjeto.yoMismo(); cout<< "El puntero pClase es " << pClase <<'\n.'; return 0; }

En este ejemplo la clase yoMismo() devuelve un apuntador al objeto que lo posee de la clase Miclase. El main() crea un objeto de la clase Miclase y luego llama a yoMismo(). Lo almacena en pClase y luego enseña el contenido, que en este caso es el valor de la referencia. Entonces este apuntador nos permitira realizar muchas cosas sobre los propios objetos con esta referencia.

CONSTRUCTORES

Los constructores son funciones miembro especiales que sirven para inicializar un objeto de una determinada clase al mismo tiempo que se declara.

Los constructores son especiales por varios motivos:

• Tienen el mismo nombre que la clase a la que pertenecen.

• No tienen tipo de retorno, y por lo tanto no retornan ningún valor.

• No pueden ser heredados.

• Por último, deben ser públicos, no tendría ningún sentido declarar un constructor como privado, ya que siempre se usan desde el exterior de la clase, ni tampoco como protegido, ya que no puede ser heredado.

Sintaxis: class <identificador de clase> { public: <identificador de clase>(<lista de parámetr os>) [: <lista de constructores>] {

Page 15: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

<código del constructor> } ... }

Añadamos un constructor a nuestra clase pareja:

#include <iostream> using namespace std; class pareja { public: // Constructor pareja(int a2, int b2); // Funciones miembro de la clase "pareja" void Lee(int &a2, int &b2); void Guarda(int a2, int b2); private: // Datos miembro de la clase "pareja" int a, b; }; pareja::pareja(int a2, int b2) { a = a2; b = b2; } void pareja::Lee(int &a2, int &b2) { a2 = a; b2 = b; } void pareja::Guarda(int a2, int b2) { a = a2; b = b2; } int main() { pareja par1(12, 32); int x, y; par1.Lee(x, y); cout << "Valor de par1.a: " << x << endl; cout << "Valor de par1.b: " << y << endl; return 0; }

Si no definimos un contructor el compilador creará uno por defecto, sin parámetros, que no hará absolutamente nada. Los datos miembros del los objetos declarados en el programa contendrán basura.

Si una clase posee constructor, será llamado siempre que se declare un objeto de esa clase. Si ese constructor requiere argumentos, como en este caso, es obligatorio suministrarlos.

Por ejemplo, las siguientes declaraciones son ilegales:

pareja par1; pareja par1();

La primera porque el constructor de "pareja" requiere dos parámetros, y no se suministran.

Page 16: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

La segunda es ilegal por otro motivo más complejo. Aunque existiese un constructor sin parámetros, no se debe usar esta forma para declarar el objeto, ya que el compilador lo considera como la declaración de un prototipo de una función que devuelve un objeto de tipo "pareja" y no admite parámetros.

Cuando se use un constructor sin parámetros para declarar un objeto no se deben escribir los paréntesis.

Y las siguientes declaraciones son válidas:

pareja par1(12,43); pareja par2(45,34);

Constructor por defecto

^

Cuando no especifiquemos un constructor para una clase, el compilador crea uno por defecto sin argumentos. Por eso el ejemplo del capítulo anterior funcionaba correctamente. Cuando se crean objetos locales, los datos miembros no se inicializarían, contendrían la "basura" que hubiese en la memoria asignada al objeto. Si se trata de objetos globales, los datos miembros se inicializan a cero.

Para declarar objetos usando el constructor por defecto o un constructor que hayamos declarado sin parámetros no se debe usar el paréntesis:

pareja par2();

Se trata de un error frecuente cuando se empiezan a usar clases, lo correcto es declarar el objeto sin usar los paréntesis:

pareja par2;

Destructores

Sinopsis

Los destructores son un tipo especial de función miembro, estrechamente relacionados con los constructores. Son también funciones que no devuelven nada (ni siquiera void). Tampoco aceptan ningún parámetro, ya que la destrucción de un objeto no acepta ningún tipo de opción o especificación particular y es idéntica para todos los objetos de la clase. Los destructores no pueden ser heredados, aunque una clase derivada puede llamar a los destructores de su superclase si no han sido declarados privados (son públicos o protegidos). Lo mismo que ocurre con los constructores, tampoco puede obtenerse su dirección, por lo que no es posible establecer punteros a este tipo de funciones.

La misión más común de los destructores es liberar la memoria asignada por los constructores, aunque también puede consistir en desasignar y/o liberar determinados recursos asignados por estos. Por ejemplo, cerrar un fichero o desbloquear un recurso compartido previamente bloqueado por el constructor.

Se ha señalado que, si el programador no define uno explícitamente, el compilador C++ proporciona un destructor de oficio, que es declarado público y puede ser invocado sin argumentos. Por lo general en la mayoría de los casos este destructor de oficio es suficiente, por lo que el programador no necesita definir uno por sí mismo, a no ser que la clase incluya la inicialización de objetos persistentes . Por ejemplo, matrices que necesiten del operador new en el constructor para su inicialización, en cuyo caso es responsabilidad del programador definir un destructor adecuado (ver ejemplo).

Page 17: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones

Los destructores son invocados automáticamente (de forma implícita) por el programa en multitud de ocasiones; de hecho es muy raro que sea necesario invocarlos explícitamente. Su misión es limpiar los miembros del objeto antes que el propio objeto se auto-destruya.

Declaración

Los destructores se distinguen porque tienen el mismo nombre que la clase a que pertenecen precedido por la tilde ~ para simbolizar su estrecha relación con los constructores que utilizan el mismo nombre (son el "complemento" de aquellos). Ejemplo:

class X { public: ~X(); // destructor de la clase X }; ... X::~X() { // definición (off-line) del destructo r ... }

Ejemplo:

La clase Punto definida en el epígrafe anterior sería un buen exponente del caso en que es necesario definir un destructor explícito que se encargue de las correcta destrucción de los miembros. En efecto, manteniendo aquella definición, una sentencia del tipo:

{ ... Punto p1(2,3); ... }

provoca la creación de un objeto en memoria dinámica. El miembro coord es un puntero-a-int que señala un área en el montón capaz para albergar dos enteros. Cuando la ejecución sale del ámbito del bloque en que se ha creado el objeto, es invocado el destructor de oficio y el objeto es destruido, incluyendo su único componente, el puntero coord ; sin embargo el área señalada por este permanece reservada en el montón, y por tanto irremediablemente perdida.

La forma sensata de utilizar tales objetos sería modificando la definición de la clase para añadirle un destructor adecuado. La versión correcta tendría el siguiente aspecto:

class Punto { public: int* coord; Punto(int x = 0, int y = 0) { // construtor coord = new int[2]; coord[0] = x; coord[1] = y; } ~Punto() { // destructor delete [] coord; // L.8: };

En este caso, la sentencia de la línea 8 provoca que al ser invocado el destructor del objeto, se desasigne el área del montón señalada por el puntero (recuerde que, al igual que el resto de las funciones-miembro, los destructores también tienen un argumento oculto this, por lo que la función sabe sobre que objeto tiene que operar en cada caso).

Page 18: Aplicaciones de las listas enlazadasingeliomar.webcindario.com/guialista.pdf · Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas Doblemente Circulares. Aplicaciones