Unidad II.ESTRUCTURAS LINEALES

2.1 Listas

 Concepto de Lista:

Consiste en una secuencia de nodos, en los que se guardan campos de datos arbitrarios y una o dos referencias, enlaces o punteros al nodo anterior o posterior.

Ejemplo en Lenguaje de Programación:

 

2.2 Pilas Estáticas y Dinámicas

PILA: Es una lista ordenada  en la que el modo de acceso a sus elementos es de tipo   Last In First Out, último en entrar, primero en salir) que permite almacenar y recuperar datos.

Una pila cuenta con 2 operaciones imprescindibles: apilar y desapilar, a las que en las implementaciones modernas de las pilas se suelen añadir más de uso habitual.

• Crear: se crea la pila vacía. (constructor)

• Tamaño: regresa el número de elementos de la pila. (size)

• Apilar: se añade un elemento a la pila.(push)

• Desapilar: se elimina el elemento frontal de la pila.(pop)

• Cima: devuelve el elemento que esta en la cima de la pila. (top o peek)

• Vacía: devuelve cierto si la pila está vacía o falso en caso contrario (empty).

 

EXPRECIONES  ARITMETICAS EN PILA

 

JERARQUIA DE OPERADORES:

Forma especial en la que se pueden expresar una expresión matemática en tres formas: Infija, Prefija y Posfija.

 

 

 

 

Prefija:

 

Los operandos conservan el mismo orden que la notación infija

•  Nos indica que el operador va antes de los operandos.

• No requiere de paréntesis para indicar el orden de precedencia de operadores ya que el es una operación.

• Se evalúa de izquierda a derecha hasta que encontrémosle primer operador seguido inmediatamente de un par de operandos.
• Se evalúa la expresión binaria y el resultado se cambia como un nuevo operando.

Se repite este hasta que nos quede un solo resultado.

 

 

(2+(3*4)) = x

((2+3)*4) = x

= + 2 * 3 4 x

= * + 2 3 4 x

INFIJA

Estas notaciones se refiere a que el operador esta entre

los operandos.

•  El orden es primer operando,operador, segundo operando
•  La notación infija puede estar completamente parentizada o puede basarse en un esquema de precedencia de operadores así como el uso de paréntesis para invalidar los arreglos al expresar el orden de evaluación de una expresión:

3*4=12

3*4+2=14

3*(4+2)=18

 



(2+(3*4)) = x

((2+3)*4) = x

Notación infija

2+3*4 = x

(2+3)*4 = x

 

 

POSFIJA 

El operador ocupa la posición después de los operandos sus características principales son:

• El orden de los operandos se conserva igual que la expresión infija equivalente no utiliza paréntesis ya que no es una operación ambigua.

• La operación posfija no es exactamente lo inverso a la operación prefija equivalente:

(A+B)*C AB+C*

 

(2+(3*4)) = x

((2+3)*4) = x

Notación postfija

2 3 4 * + x =

2 3 + 4 * x =

 

 

EJEMPLO JAVA PILA ESTATICA :



 CLASE PILA

 

 

public class PILA {

     public int dato;

    public static int tope;

    public static int op;

   private int pila[]=new int[5];

   INSERTAR

   public void Insertar(){

       if(tope==5){

           System.err.println("Pila llena");

       }

       else{

           System.out.println("Proporciona el dato para la pila");

           System.out.println("Dato"+tope);

           Scanner cap=new Scanner(System.in);

           pila[tope]=cap.nextInt();

           tope++;

       }

   }

IMPRIMIR

    public void Imprimir(){

 

    if(tope>=10){

   for(int topem=tope-1;topem>=0;topem--){

    System.out.println("\n\n"+pila[topem]);

     }    

  } else

   System.err.println("Pila Vacia no hay nada que mostrar");

 

   }

                                  ELIMINAR

     public void elminar(){

 

       if(tope<0){

           System.err.println("pila vacia");

       }else if(tope==10)
          tope--;

           pila[tope]=0;

           tope--;

       }

       else{

           pila[tope]=0;

           tope--;

       }  

 

 



 Estructuras dinámicas

Las estructuras dinámicas de datos son estructuras que cuya dimensión puede crecer o disminuir durante la ejecución del programa. 

• Una estructura dinámica de datos es una colección de elementos llamados nodos. 
• Una estructura dinámica de datos se amplía y contrae durante la ejecución del programa.

Se pueden dividir en dos grandes grupos:

 

1. Lineales: listas enlazadas, pilas, colas
2. No lineales: árboles , grafos

Las estructuras dinámicas de datos son de gran utilidad para almacenar datos del mundo real, que están cambiando constantemente.

 

EJEMPLO REAL

Por ejemplo si tenemos almacenados en un array los datos de los alumnos de un curso, los cuales estan ordenados de acuerdo al promedio, para insertar un nuevo alumno seria necesario correr cada elemento un espacio: Si en su lugar se utilizara una estructura dinámica de datos, los nuevos datos del alumno se pueden insertar fácilmente.