16/04/2015Ing. Edgar Ruiz Lizama1. EL TAD LISTA 16/04/2015Ing. Edgar Ruiz Lizama2 El Tipo Abstracto de Datos LISTA es un estructura de datos básica que

21/04/23 Ing. Edgar Ruiz Lizama 1

EL TAD LISTA


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.

naaaa ,,,, 321 naaaa ,,,, 321

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.


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;


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;

}


Insertar NodoPara 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.


1) Crear nuevo nodo.

NULL

NuevoP//P es un apuntador temporal a la lista de Nodos.

2) Llenar el nodo.

10NULL

NuevoP

3)


4)

Los 4 pasos anteriores se resumen en el siguiente pseudocódigo

Algoritmo Insertar Nodo{

p = new Nodoinfo(p) = Elemento de datos a insertarsig(p) = inicioinicio = p

}


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();

}


// el constructor de la lista Lista :: Lista(){

inicio = NULL;}// destructor de la listaLista :: ~Lista(){ Nodo *p;

Nodo *temp;p = inicio;while(p != NULL) /*eliminar nodo a nodo */{

temp = p -> sig;delete p;p = temp;

}}


// operación insertar nodovoid Lista :: insertarNodo(int dato){

Nodo *p;p = new Nodo; // paso 1p -> info = dato; // paso 2p -> sig = inicio; // paso 3inicio = p; // paso 4

}


Operación eliminar NodoEl 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 quecontenga el elemento que se va a eliminar.

}

Como puede ver; antes de eliminar se debe de buscar.


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 = inicioantp = NULLencuentra = false //encuentra es una banderawhile(NOT encuentra AND p != NULL){ if info(p) == dato

encuentra = trueelse{ //continuar busqueda

antp = pp = sig(p)

}}

}


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.


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 quecontenga el elemento que se va a eliminar.

}

Como puede verse, antes de eliminar se debe de buscar.


El algoritmo básico es el siguiente:

Algoritmo EliminarNodo{

Algoritmo BuscarAlgoritmo Eliminar

}

// Operación EliminarNodo()void Lista :: eliminarNodo(int dato){

int encuentra = false;Nodo *p, *antP;p = inicio;antP = NULL;

El código:


// buscar elemento a eliminarif( listaVacia() )

cout<<“Lista vacia!…”<<endl;else { while(!encuentra && p!=NULL)

{ if (p -> info == dato) encuentra = true;

else{ antP = p;

p = p-> sig;}

}//eliminar nodo si se encuentraif(encuentra){ if(antP == NULL)

{ inicio = p-> sig;delete p;

}else{ antP -> sig = p -> sig;

delete p;}

}else

cout<<“El dato”<<dato<<“no se encuentra”<<endl;} // fin de 1er if

}


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 = iniciowhile( p !== NULL){ mostrar info(p)

p= sig(p) //ir al siguiente nodo}

}else

escribir (“Lista vacia”)}


El código

// Operación recorrer lista()void Lista :: recorrerLista(){ Nodo *p;

p = inicio;if(!listaVacia()){ while(p!=NULL)

{ cout<<p -> info<<“-> “;p = p -> sig;

}cout<<“NULO”<<endl;

}else

cout<<“lista Vacia…!”<<endl;}


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


EL TAD PILA( STACK)


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


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

1. Operación Push o Apilar

2. Operación Pop o Desapilar

3. Operación Pila Vacía o Empty

4. Operación Stacktop


Al puntero al extremo superior de la pila se le denomina también cima o tope

Operaciones Básicas


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)


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


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) y2. Push(p,i).


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) Arreglos2) Listas enlazadas


Programa que utiliza una clase llamada stack para almacenar caracteres en un arreglo.

#include<iostream.h>#include<stdlib.h>const int TAM = 10;


// declaración de la clase stackclass stack {

char stck[TAM]; //array para guardar caracteresint icp; //indice a la cabeza o tope de la pila

public:void inicio(); // inicializa o crea la pilavoid push(char ch); // meter o insertar carácterchar pop(); // retirar carácter

}; // inicializar la pilavoid stack :: inicio(){ icp = 0;}// Operación pushvoid stack :: push(char ch){ if (icp == TAM)

{ cout<<“Pila llena… overflow”<<endl;return; //también puede usar exit(1)

}stck[icp] = ch;icp++;

}


// operación popchar stack::pop() { if(icp == 0)

{ cout<<“Pila vacía… Underflow”<<endl;return 0; //devulve nulo

}icp--;return stck[icp];

}// funcion principalint main() //pila1.cpp{ stack p1,p2; //llenar dos pilas

int i;// inicializar p1 y p2p1.inicio(); p1.inicio();// insertando caracteresp1.push(‘p’); p2.push(‘a’);p1.push(‘p’); p2.push(‘a’);p1.push(‘m’); p2.push(‘a’);p1.push(‘m’); p2.push(‘a’);


// sacar de pila// para p1for (i = 0; i < 4; i++)

cout<<“pila1: ”<<p1.pop()<<endl;cout<<endl;//para p2for (i = 0; i < 4; i++)

cout<<“pila2: ”<<p2.pop()<<endl;cout<<endl;system(“PAUSE”);

}

IMPLEMENTACIÓN DEL TAD PILAMEDIANTE 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



Operación Push.

Representación gráfica.- Sea la pila con datos: 11, 7. Se desea insertar el 5.


7 11NULL

5

FASE 2

*cimaPtr

*newPtr

7 11NULL

5

FASE 2

*cimaPtr

*newPtr


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<<info<<“no insertado, no hay memoria disponible” <<endl;}


Operación Pop.

Representación gráfica.- Hacer pop a la pila anterior.


El código de Pop

int pop(PILANODOPTR *cimaPtr) { PILANODOPTR tempPtr; // crear puntero temporal

int popValor; // variable que almacena el entero a retirartempPtr = *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;}


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 PILAPARA 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.


Sea la expresión:

7-((x*((x+y)/(5-3))+y)/(4-2.5))


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!.


Pseudocódigo para el algoritmoExaminar 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 = FALSEelse{ 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”<<endl; else

cout<<“Expresion incorrecta”<<endl;}

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 = FALSEelse{ 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”<<endl; else

cout<<“Expresion incorrecta”<<endl;}


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).


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 opnd2push(opndstk,valor)

} } return (pop(opndstk));}


Ejemplo: Evaluar la expresión posfija utilizando el algoritmo anterior.

6 2 3 + - 3 8 2 / + * 2 ^ 3 +

simbolo oprid1 oprid2 valorpila

opridstk6 62 6,23 6,2,3+ 2 3 5 6,5- 6 5 1 13 6 5 1 1,38 6 5 1 1,3,82 6 5 1 1,3,8,2 / 8 2 4 1,3,4+ 3 4 7 1,7* 1 7 7 72 1 7 7 7,2^ 7 2 49 493 7 2 49 49,3+ 49 3 52 52

simbolo oprid1 oprid2 valorpila

opridstk6 62 6,23 6,2,3+ 2 3 5 6,5- 6 5 1 13 6 5 1 1,38 6 5 1 1,3,82 6 5 1 1,3,8,2 / 8 2 4 1,3,4+ 3 4 7 1,7* 1 7 7 72 1 7 7 7,2^ 7 2 49 493 7 2 49 49,3+ 49 3 52 52

Solución


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).

Infija Posfija ComentarioA+B/C A+(B/C) Se añaden paréntesis.

A+(BC/) Se pasa a posfija dentro del paréntesis.A(BC/)+ El paréntesis y su contenido se tratan como un operando.ABC/+ Se eliminan los paréntesis.

Infija Posfija ComentarioA+B/C A+(B/C) Se añaden paréntesis.

A+(BC/) Se pasa a posfija dentro del paréntesis.A(BC/)+ El paréntesis y su contenido se tratan como un operando.ABC/+ Se eliminan los paréntesis.

Si la expresión es (A+B)/C se tiene

Infija Posfija Comentario(A+B)/C (A+B)/C

(AB+)/C Pasando a posfija dentro del paréntesis.(AB+)C/ tomando el paréntesis como un operando y pasando a posfija.AB+C/ Quitando paréntesis.

Infija Posfija Comentario(A+B)/C (A+B)/C

(AB+)/C Pasando a posfija dentro del paréntesis.(AB+)C/ tomando el paréntesis como un operando y pasando a posfija.AB+C/ Quitando paréntesis.


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


EL TAD COLA


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).


Representación Gráfica del TAD COLA

Operaciones en una COLALas 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.


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.


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:


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<<carac<<“no insertado,no hay memoria disponible”<<endl;}


Operación sacar de cola; dequeue o desencolar

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:


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;

}


EL TAD COLA COMO UN ARREGLO

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 qq.front = q.rear = MAXCOLA-1;


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:


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!…”<<endl;

exit(1);}if(pq -> front == MAXCOLA - 1)

pq -> front = 0;else

(pq -> front)++;return(pq -> items[pq -> front]);

}


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 desbordamientoif(pq -> rear == pq -> front){ cout<<“cola en overflow!…”<<endl;

exit(1);}pq -> items[pq -> rear] = x;

}

REFERENCIASSTAGUAARD, 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.


Documents

16/04/2015Ing. Edgar Ruiz Lizama1. EL TAD LISTA 16/04/2015Ing. Edgar Ruiz Lizama2 El Tipo Abstracto de Datos LISTA es un estructura de datos básica que