El tad lista



Descargar 33,08 Kb.
Fecha de conversión24.09.2017
Tamaño33,08 Kb.
  • 23/09/17
  • C++
  • C++
  • LISTAS

EL TAD LISTA

  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • C++
  • El Tipo Abstracto de Datos LISTA es un estructura de datos básica que permite crear, insertar, modificar, buscar y eliminar datos o registros a una lista. Una lista en esencia es una secuencia de datos sucesivos.
  • Donde el primer elemento es a1 y el último es an. Adicionalmente su tamaño es n. Una lista es finita y además es flexible porque puede crecer y acortarse a voluntad.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • El gráfico muestra una lista enlazada con tres elementos o nodos donde cada nodo tiene tres componentes: un campo que es una cadena de caracteres, un campo que es un flotante y un tercer campo que es una dirección o link para el siguiente nodo. La lista gráfico puede declararse como sigue:
  • struct listaNodo{ char articulo[15]; float precio; struct listaNodo *sig; // es recursiva } typedef listaNodo *inicio; inicio -> articulo = strcpy(“pollo”,”papas”); inicio -> precio = 0.80;
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Crear Nodo
  • 1) Crear nodo. 2) Insertar nodo. 3) Eliminar nodo. 4) Buscar. 5) Recorrer nodo. 6) Lista vacía.
  • Operaciones básicas con el TDA LISTA
  • Al construir una lista enlazada lo primero que debe hacerse es crear una lista vacia. Esto se logra estableciendo el primer nodo a NULL.
  • Algoritmo crearLista() { inicio=NULL; }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Insertar Nodo
  • Para adicionar un nodo al TAD lista se hará al comienzo de la lista (puede hacerse en cualquier lugar). Los pasos a seguir son:
  • 1) Crear un nuevo nodo. 2) Llenar el nodo con los datos que se va ha almacenar. 3) Hacer que el nuevo nodo apunte al primer nodo de la lista. 4) Hacer que el primer nodo puente al nuevo nodo.
  • Ejemplo grafico:
  • Sea la lista de enteros 5, 15 y se desea insertar el entero 10.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • 1) Crear nuevo nodo.
  • //P es un apuntador temporal a la lista de Nodos.
  • 2) Llenar el nodo.
  • 3)
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • 4)
  • Los 4 pasos anteriores se resumen en el siguiente pseudocódigo
  • Algoritmo Insertar Nodo { p = new Nodo info(p) = Elemento de datos a insertar sig(p) = inicio inicio = p }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • La clase básica es la siguiente:
  • struct Nodo { int info; Nodo *sig; }; class Lista { Nodo *inicio; public: Lista(); ~Lista(); void insertarNodo(int dato); void eliminarNodo(int dato); void recorrerLista(); int listaVacia(); }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • // el constructor de la lista Lista :: Lista() { inicio = NULL; } // destructor de la lista Lista :: ~Lista() { Nodo *p; Nodo *temp; p = inicio; while(p != NULL) /*eliminar nodo a nodo */ { temp = p -> sig; delete p; p = temp; } }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • // operación insertar nodo void Lista :: insertarNodo(int dato) { Nodo *p; p = new Nodo; // paso 1 p -> info = dato; // paso 2 p -> sig = inicio; // paso 3 inicio = p; // paso 4 }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Operación eliminar Nodo
  • El algoritmo básico es el siguiente:
  • EliminarNodo { Buscar en la lista el elemento a eliminar. Ajusta los punteros de la lista para eliminar el nodo que contenga el elemento que se va a eliminar. }
  • Como puede ver; antes de eliminar se debe de buscar.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • La búsqueda de un elemento se realiza Nodo a Nodo, de principio a fin, es decir, es secuencial. El algoritmo para buscar es el siguiente:
  • Buscar { if lista vacia escribir(“lista vacia...”) else // Ubicarse al comienzo de la lista p = inicio antp = NULL encuentra = false //encuentra es una bandera while(NOT encuentra AND p != NULL) { if info(p) == dato encuentra = true else { //continuar busqueda antp = p p = sig(p) } } }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Después de utilizar el algoritmo de la búsqueda, se usan los valores de encuentra p y antp para proceder a eliminar el nodo requerido. El algoritmo es el siguiente:
  • Eliminar { if(encuentra) { if(antp == NULL) //caso del 1er nodo inicio = sig(p) else sig(antp) = sig(p) //eliminacion } else escribir(“No se encuentra en la lista...”) }
  • Ahora se puede ajustar la búsqueda con eliminar para escribir un solo algoritmo: Eliminar Nodo.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • El algoritmo básico es el siguiente:
  • EliminarNodo { Buscar en la lista el elemento a eliminar. Ajusta los punteros de la lista para eliminar el nodo que contenga el elemento que se va a eliminar. }
  • Como puede verse, antes de eliminar se debe de buscar.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • El algoritmo básico es el siguiente:
  • Algoritmo EliminarNodo { Algoritmo Buscar Algoritmo Eliminar }
  • // Operación EliminarNodo() void Lista :: eliminarNodo(int dato) { int encuentra = false; Nodo *p, *antP; p = inicio; antP = NULL;
  • El código:
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • // buscar elemento a eliminar if( listaVacia() ) cout<<“Lista vacia!…”< info == dato) encuentra = true; else { antP = p; p = p-> sig; } } //eliminar nodo si se encuentra if(encuentra) { if(antP == NULL) { inicio = p-> sig; delete p; } else { antP -> sig = p -> sig; delete p; } } else cout<<“El dato”<
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Recorrer Lista
  • El recorrido de la lista es secuencial y se realiza de prinicipio a fin. El objetivo del recorrido es visitar cada nodo y enviar su(s) dato(s) hacia el flujo de salida. El seudocódigo es:
  • RecorrerLista { if(lista No vacia) { p = inicio while( p !== NULL) { mostrar info(p) p= sig(p) //ir al siguiente nodo } } else escribir (“Lista vacia”) }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • El código
  • // Operación recorrer lista() void Lista :: recorrerLista() { Nodo *p; p = inicio; if(!listaVacia()) { while(p!=NULL) { cout<
    info<<“-> “; p = p -> sig; } cout<<“NULO”<else
    cout<<“lista Vacia…!”<
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Lista Vacía
  • Consiste en averiguar si la lista tiene o no elementos. Para ello se devuelve un valor booleano.
  • Lista Vacia { if (inicio = NULL) return TRUE else return FALSE }
  • // código operación listaVacia() int lista :: listaVacia() { if (inicio == NULL) return true; else return false; }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • C++
  • C++
  • PILAS

EL TAD PILA ( STACK)

  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • C++
  • Una pila es una versión restringida de una lista enlazada. A una pila se le pueden añadir y retirar nodos únicamente por su extremo superior. Por esta razón el TDA Pila se le conoce como estructura de datos del tipo LIFO (Last In First Out) esto quiere decir; último en entrar, primero en salir. Una pila se referencia mediante un apuntador al extremo superior de la misma. El último nodo de la pila se define a NULL para indicar que se trata del último elemento de la estructura (parte inferior de la pila).

Representación Gráfica

  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Sea el ingreso de cadena de caracteres “AMOR” los cuales se almacenan uno a uno en una pila.
  • Mediante listas enlazadas se tiene

Operaciones Básicas en una pila

  • Operación Push o Apilar
  • Operación Pop o Desapilar
  • Operación Pila Vacía o Empty
  • Operación Stacktop
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Al puntero al extremo superior de la pila se le denomina también cima o tope

Operaciones Básicas

  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • 1 Operación Push o Apilar. Significa ingresar un nuevo nodo a la pila. Esto se realiza por el extremo superior o tope. Ejm: Insertar el carácter “I” a la pila del gráfico: push (p, carácter)
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • 2 Operación Pop o Desapilar. Significa retirar un nodo de la pila. Esto se realiza también por el extremo superior o tope. Ejm: Retirar un nodo de la pila anterior: pop(p)

Operaciones Básicas

  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • 3 Operación Pila Vacía o Empty. La operación empty(p) devuelve un valor de verdad si la pila p está vacía o no. La operación push se puede aplicar a cualquier pila, pero la operación pop no puede aplicarse a una pila vacía pues no habrían elementos que remover. El intento de aplicar pop a una pila vacía ocasiona un error conocido como “underflow” o “bajo flujo” por ello antes de hacer pop a una pila se debe verificar si ella está vacía o no.
  • 4 Operación Stacktop. Permite averiguar que elemento está en la parte superior de la pila sin removerlo. La operación stacktop(p) consta de dos operaciones en secuencia: 1. Pop(p) y 2. Push(p,i).
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Esto se resume en lo siguiente: i = stacktop(p); lo cual equivale a hacer las dos lineas siguientes: i = pop (p); push(p,i); Al igual que con pop, la operación stacktop también debe evitar el subdesbordamiento o underflow.

IMPLEMENTACION DEL TDA PILA

  • La implementación del TAD pila se puede hacer con:
  • 1) Arreglos
  • 2) Listas enlazadas
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Programa que utiliza una clase llamada stack para almacenar caracteres en un arreglo.
  • #include #include const int TAM = 10;
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • // declaración de la clase stack class stack { char stck[TAM]; //array para guardar caracteres int icp; //indice a la cabeza o tope de la pila public: void inicio(); // inicializa o crea la pila void push(char ch); // meter o insertar carácter char pop(); // retirar carácter }; // inicializar la pila void stack :: inicio() { icp = 0; } // Operación push void stack :: push(char ch) { if (icp == TAM) { cout<<“Pila llena… overflow”<
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • // operación pop char stack::pop() { if(icp == 0) { cout<<“Pila vacía… Underflow”<
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • // sacar de pila // para p1 for (i = 0; i < 4; i++) cout<<“pila1: ”<

IMPLEMENTACIÓN DEL TAD PILA MEDIANTE UNA LISTA ENLAZADA

  • La declaracion básica es:
  • struct pilaNodo { int numero; struct pilaNodo *sig; }
  • typedef struct pilaNodo PILANODO; tipedef PILANODO *PILANODO; // puntero a PILANODO
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Operación Push.
  • Representación gráfica.- Sea la pila con datos: 11, 7. Se desea insertar el 5.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • El código de la operación push
  • void push(PILANODOPTR *cimaPtr, int info) { PILANODOPTR newPtr; // declarar nuevo nodo newPtr = newPILANODO; /* asignar memoria dinamica al nuevo nodo */ if(newPtr != NULL) { newPtr -> numero = info; //guardar info en nuevo nodo (a) newPtr -> sig = *cimaPtr; // (b) *cimaPtr = newPtr; //(c) } else cout<
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Operación Pop.
  • Representación gráfica.- Hacer pop a la pila anterior.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • El código de Pop
  • int pop(PILANODOPTR *cimaPtr) { PILANODOPTR tempPtr; // crear puntero temporal int popValor; // variable que almacena el entero a retirar tempPtr = *cimaPtr; //(a) popValor = (*cimaPtr) -> numero; //valor a retirar *cimaPtr = (*cimaPtr) -> sig; delete(tempPtr); return popValor; } int esVacia(PILANODOPTR *cimaPtr) { if(cimaPtr == NULL) return true; else return false; }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • APLICACIONES PRACTICAS DEL TAD PILA
  • En computación son diversos las aplicaciones del TDA Pila. 1) Validación de expresiones. 2) Evaluación de expresiones en sus formas: infija, prefija y posfija. 3) Modelación de la memoria por parte del sistema operativo. 4) Eliminar la recursividad para lograr una versión iterativa de algunos algoritmos recursivos.

ALGORITMO DE LA PILA PARA COMPROBAR SIGNOS DE COLECCION

  • Antes de evaluar una expresión, el compilador debe examinar si dicha expresión es válida o no. Para hacerlo procede a analizar los símbolos de colección como {, }, [, ], ( y ) o similares.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Sea la expresión: 7-((x*((x+y)/(5-3))+y)/(4-2.5))
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Para comprobar si dicha expresión es correcta se realiza lo siguiente: 1) Averiguar si hay la misma cantidad de paréntesis izquierdos y derechos. 2) Cada paréntesis derecho esta precedido por un paréntesis izquierdo. Volviendo a la expresión: 7 - ( ( x * ( ( x + y ) / ( 5 - 3 ) ) + y ) / ( 4 - 2.5 ) ) 0 0 122 2 34 4 4 4 3344 4 43 2 2 21 1 2 2 2 2 1 0 contador = 0 Por lo que la expresión es correcta!.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Examinar expresion { valido = TRUE // supone que la cadena es válida s = pila vacia while( no hayamos leido toda la cadena) { leer el siguiente simbolo de la cadena if(simbolo ==‘(‘or simbolo==‘[‘or simbolo==‘{‘) push(s,simbolo) if(simbolo ==‘)‘or simbolo==‘]‘or simbolo==‘}‘) { if(empty(s) valido = FALSE else { i = pop(s) if( i no es el correspondiente simbolo que abre a simbolo) valido = FALSE } } } if(!empty(s)) valido = FALSE if(valido) cout<<“Expresion correcta”<
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • NOTACION POLACA o REVERSE POLISH NORM (RPN)
  • El algoritmo para evaluar expresiones posfija, consiste en lo siguiente:
  • Cada operador en una cadena posfija hace referencia a los dos operandos anteriores de la cadena. Suponga que cada vez que se lee un operando lo agregamos a la pila, cuando se llega a un operador, los operandos serán los dos elementos superiores de la pila. Después se remueve estos dos elementos, se ejecuta la operación indicada sobre ellos y se agrega el resultado a la pila para que esté disponible como operando del operador siguiente.
  • La expresión en posfija se le conoce como Notación Polaca o Reverse Polish Norm (RPN).
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Pseudocódigo
  • Algoritmo RPN { Opndstk = la pila vacia // explora la cadena leyendo un elemento cada vez hacia simbolo while(no sea fin de la cadena) { simbolo = siguiente carácter en la entrada if(simbolo es un operando) push(opndstk,simbolo) else { //simbolo es un operador opnd2 = pop(opndstk) opnd1 = pop(opndstk) valor = resultado de aplicar a opnd1 y opnd2 push(opndstk,valor) } } return (pop(opndstk)); }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Ejemplo:
  • Evaluar la expresión posfija utilizando el algoritmo anterior. 6 2 3 + - 3 8 2 / + * 2 ^ 3 +
  • Solución
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Puede realizarse el cambio de notación en las expresiones. Por ejemplo, si se quiere cambiar A+B/C a su forma posfija, se debe tener en cuenta la precedencia de los operadores. En el cado de + y / se ejecuta primero / (en ausencia de paréntesis).
  • Si la expresión es (A+B)/C se tiene
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Cuando se examina operadores de la misma procedencia, se supone que el orden es de izquierda a derecha, excepto en el caso de la exponenciación en donde el orden se de derecha a izquierda. Por lo que A+B+C significa (A+B)+C, en tanto que A^B ^C significa A ^(B ^C). Observe que el uso de paréntesis ayuda a eliminar la precedencia predeterminada.
  • REGLA
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • C++
  • C++
  • COLAS

EL TAD COLA

  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • C++
  • Una cola es un caso especial de una lista, donde sólo se permite la inserción de elementos al final y la eliminación (sacar elementos de la cola) se realiza únicamente por el frente. A las colas también se les conoce como estructuras dinámicas de datos del tipo “primero en entrar, primero en salir” FIFO (First In First Out).
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Representación Gráfica del TAD COLA
  • Operaciones en una COLA
  • Las operaciones básicas definidas para la cola son:
  • 1) Frente o front.- Averiguar por el elemento que está al frente. 2.) Poner en cola o encolar (enqueue); es decir colocar elemento al final. 3) Sacar de cola o desencolar (dequeue); es decir sacar el elemento que está al frente. 4) Cola vacía o empty.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Aplicación práctica
  • Declaración de la cola
  • La declaración de la cola de caracteres es la siguiente:
  • struct colaNodo { /* es recursiva; se referencia asi misma */ char letra; struct colaNodo *nextPtr; }; typedef struct colaNodo COLANODO; typedef COLANODO *COLANODOPTR;
  • Preparar un programa que permita manipular una cola de caracteres alfabéticos y permita realizar las operaciones básicas de una cola: enqueue y dequeue; además, debe verificar si la cola está o no vacía e imprimir siempre la cola actual.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Operación poner en cola; enqueue o encolar
  • Supóngase que se tienen en cola los caracteres P, A, N y se quiere poner en la cola el carácter S. Esta situación se representa gráficamente como:
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • El código para la operación enqueue es:
  • /* Insertar un carácter en la cola */ void encolar(COLANODOPTR * cabezaPtr, COLANODOPTR *colaPtr, char carac) { COLANODOPTR newPtr; // newPtr = new COLANODO; if(newPtr != NULL) { /*hay espacio disponible */ newPtr -> letra = carac; newPtr -> nextPtr = NULL; if(esVacia(*cabezaPtr)) *cabezaPtr = newPtr; else *colaPtr -> nextPtr = newPtr; *colaPtr = newPtr; } else cout<
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Supóngase ahora que se quiere sacar un elemento de la cola actual P, A, N, S; el carácter que sale es P. Esta situación se representa en la figura siguiente:
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • El código para la operación dequeue es:
  • /* Borrar un elemento de la cola */ char desencolar(COLANODOPTR *cabezaPtr, COLANODOPTR *colaPtr) { char carac; COLANODOPTR tempPtr; carac = (*cabezaPtr) -> letra; tempPtr = *cabezaPtr; *cabezaPtr = (*cabezaPtr) -> nextPtr; if(*cabezaPtr == NULL) *colaPtr = NULL; delete tempPtr; return carac; }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • El TAD COLA puede implementarse como un arreglo donde la variable front contiene la posición dentro del arreglo para el elemento primero o inicial de la cola y la variable rear para el último elemento del arreglo.
  • Sea una cola q de enteros la cual se declara como:
  • Const int MAXCOLA = 100; struct queue { int items[MAXCOLA]; int front, rear; // indices }; struct queue q; // cola q q.front = q.rear = MAXCOLA-1;
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • Q.front = q.rear = 4
  • Debido a que q.front y q.rear “apunten” a MAXCOLA - 1 la cola esta vacía al comienzo.
  • int empty(struct queue *pq) { return((pq -> front == q -> rear)?true:false); }
  • La función empty se codifica como sigue:
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • if(empty(pq)) /* cola vacia */ else /* cola no vacia */
  • Una vez definida la función empty se puede probar con el siguiente bloque.
  • La operación remove (q) remueve el elemento al frente de la cola y se codifica como:
  • int remove(struct queue *pq) { if(empty(pq)) { cout<<“cola underflow!…”< front == MAXCOLA - 1) pq -> front = 0; else (pq -> front)++; return(pq -> items[pq -> front]); }
  • 23/09/17
  • Ing. Edgar Ruiz Lizama
  • La operación insert(q,x) o enqueue permite insertar un elemento al final de la cola. Se codifica como:
  • void insert(struct queue *pq, int x) { /* hacer espacio para un elemento nuevo */ if(pq -> rear ==MAXCOLA - 1) pq -> rear = 0; else (pq -> rear)++; // comprobar que no hay desbordamiento if(pq -> rear == pq -> front) { cout<<“cola en overflow!…”< items[pq -> rear] = x; }

REFERENCIAS

  • STAGUAARD, ANDREW “Técnicas Estructuradas y Orientadas a Objetos: Una Introducción utilizando C++". Editorial Prentice Hall Hispanoamericana. México, 1998.
  • LANGSAM, AUGENSTEIN, TENENBAUM “Estructuras de Datos con C/C++” Editorial Prentice-Hall Hispanoamericana. México 1996.
  • H.M. DEITEL y P.J. DEITEL “Como Programar en C++” 4ta Ed. Editorial Prentice-Hall Hispanoamericana, México 2003.
  • CAIRO OSVALDO y GUARDATI SILVIA “Estructura de Datos” 2da. Ed. Editorial McGraw Hill. México 2002.
  • JOYANES AGUILAR, LUIS "Programación en C++: Algoritmos y Estructura de Datos" 1ra. Ed. Editorial McGraw Hill. Madrid, 2002.
  • RUIZ LIZAMA EDGAR “Curso de Lenguaje C” Facultad de Ingeniería Industrial UNMSM. Lima 1999.
  • 23/09/17
  • Ing. Edgar Ruiz Lizama


La base de datos está protegida por derechos de autor ©absta.info 2016
enviar mensaje

    Página principal