Aplicaciones de las listas ?· Doblemente Enlazadas, Listas Enlazadas Circulares y Listas Enlazadas…

  • View
    212

  • Download
    0

Embed Size (px)

Transcript

  • ING:MSc.ELIOMAR NIEVES

    GUA 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 eliminacin 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 mdulos 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 prctica tiene su origen en el lenguaje de programacin Lisp, donde las listas enlazadas son una estructura de datos primaria (aunque no la nica), y ahora es una caracterstica comn en el estilo de programacin 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 bsqueda equilibrados. Sin embargo, a veces una lista enlazada es dinmicamente creada fuera de un subconjunto propio de nodos semejante a un rbol, y son usadas ms eficientemente para recorrer sta serie de datos

    Listas simples enlazadas

    La lista enlazada bsica 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 vaca, si es el ltimo nodo.

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

  • El siguiente ejercicio muestra como se declara una lista, y a travs de funciones se agregan datos, lo que origina en cada oportunidad la creacin de un nuevo nodo y tambin muestra la forma de mostrar el contenido de una lista. #include #include 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

  • 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; coutsgt=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 direccin }else{

  • (*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 teora dice que todo ltimo nodo debe apuntar a null } } void muestra(nodo *cab){ cout

  • 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 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;

  • 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; };

  • 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 vaca 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

  • anterior = anterior->siguiente; // Creamos un nuevo nodo despus 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

  • anterior->siguiente = nodo->siguiente; delete nodo; } } void lista::Mostrar() { nodo *aux; aux = primero; while(aux) { cout valor siguiente; } cout

  • cin>>a; Lista.Insertar(a); } Lista.Mostrar(); Lista.Primero(); cout

  • departamento, la posicin, el una funcin que nos imprima la informacin de este quedara 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 pblico ( 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 inccesible no slo desde otras clases y otras partes del programa, sino tambin desde sus clases derivadas. Las clases derivadas se explicara posteriormente. Miremos el siguiente programa de ejemplo. Se compone de tres partes: la primera una declaracin 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 }

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

    Las funciones Setombre, SetDepartamento, setPosicion, setSalario, Getombre, GetDepartamento, GetPosicion y GetSalario se denominan funciones intercaladas, que son funciones que se declaran en una sola lnea. 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 pblicas de tal modo que se pueda acceder a ellas desde otras funciones. La definicin de la funcin PrintInfo puede quedar as:

    void Empleado::ImprimirInfo( ) { cout

  • estructura de la clase Empleado. Luego, en las lneas siguientes a la instanciacin 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 mayora de los casos se llaman SetXxx y GetXxx, se llama encapsulacin de datos. Las funciones que necesitan valores de