Embedded Files
LISTAS ENLAZADAS
LISTAS ENLAZADAS
Una lista enlazada, también llamada lista encadenada, es una estructura de datos lineal que no presenta las limitaciones que presenta un array. Sin embargo, son menos eficientes en el uso de memoria que los arrays, y algunas operaciones que en un array requieren un tiempo constante (por ejemplo, el acceso a una posición cualquiera del array dado su ındice), en una lista enlazada tienen complejidad lineal. Por tanto, dependiendo del problema concreto, resultara más adecuado utilizar un array o una lista enlazada.
Una lista enlazada es una estructura de datos lineal compuesta por nodos, en la cual cada nodo almacena un dato y una referencia al nodo que le sigue en la estructura. En la siguiente figura se representa gráficamente un ejemplo de lista enlazada.
Figura. Ejemplo de lista enlazada. Los rectángulos representan nodos. Las flechas, referencias al siguiente nodo. Los rectángulos internos, los datos de cada nodo.
La lista contiene una referencia al primer nodo de la misma. A partir de este, cada nodo tiene una referencia al siguiente, hasta el último, cuya referencia al siguiente nodo tiene valor null. En problemas en los cuales el acceso al último nodo debe ser eficiente, no solo se almacena una referencia al primer nodo, sino también al último.
En una lista enlazada el acceso al primer y último nodo es muy eficiente. Sin embargo, el acceso a un nodo intermedio requiere recorrer la lista desde el principio hasta la posición de dicho nodo. En muchos problemas, sin embargo, solo es necesario acceder a las posiciones de los extremos, por lo que esto no supone una limitación.
Primeros pasos para conversión notación Infija a Postfija.
Primeros pasos para conversión notación Infija a Postfija.
EXPRESIONES InFija, PreFija Y PosFija
EXPRESIONES InFija, PreFija Y PosFija
PreFija:
La Expresión o Notación PreFija nos indica que el operador va antes de los operandos sus características principales son:
-Los operandos conservan el mismo orden que la notación infija equivalente.
-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.
Notación prefija: El orden es operador, primer operando, segundo operando
InFija:
La Expresión o Notación InFija es la forma mas común que utilizamos para escribir expresiones matemáticas, estas notaciones se refiere a que el operador esta entre los operandos. 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
Notación infija: La notación habitual. El orden es primer operando, operador, segundo operando.
PosFija:
Como su nombre lo indica se refiere a que 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*
Notación postfija: El orden es primer operando, segundo operando, operador.
EJEMPLO:
Si deseamos representar las expresiones (2+(3*4)) = x y ((2+3)*4)= x en las tres notaciones mencionadas, el resultado sería:
La notación Postfija es un método algebraico alternativo de introducción de datos que permite reducir el acceso a la memoria del ordenador, sobretodo en calculos masivos y complejos ya que los cálculos se realizan secuencialmente según se van introduciendo los operadores (en vez de tener que esperar a escribir la expresión al completo).
Basicamente consiste en que en una expresión de ese tipo primero están los operandos y después viene el operador.
Ej:
"3+5" pasado a notación Postfija seria: "3 5 +"
* Pasos para la conversión Infijo a Postfijo usando pilas.
EXPR = Expresión aritmética notación infija ( Ej: 2*(23+6)-1 )
E = pila de entrada
P = pila temporal para los operadores
S = pila de salida
1.- Añadir “(” al principio y “)” al final de EXPR. Seguidamente agregar uno a uno todos los parametros de EXPR a la Pila E.
(,2,*,(,23,+,6,),-,1,)
2.- Examinar E de izquierda a derecha y repetir los pasos 3 a 6 para cada elemento de E hasta que esta quede vacía.
3.- Si se encuentra “(”, meterlo en P.
4.- Si se encuentra un OPERADOR (+,-,*,/,^) entonces:
(a) Repetidamente sacar de P y añadir a S cada operador (de la cima de P) que tenga la misma precedencia o mayor que el operador de E.
(b) Añadir OPERADOR a P.
[Fin de condicional]
5.- Si se encuentra un “)”, entonces:
(a) Repetidamente sacar de P y añadir a S cada operador (de la cima de P), hasta que encuentre un “(”.
(b) Eliminar el “(” de P (no añadir a S).
[Fin de condicional]
6.- Si se encuentra un OPERANDO (2,23,6…), añadirlo a S.
[Fin del Bucle]
7.- Salir.
Nota: Los operadores siguen la siguiente jerarquía (El de arriba es el que tiene mayor jerarquía hasta abajo el que tiene la menor):
^
* /
+ -
)
(
EXPRESIONES InFija, PreFija Y PosFija
EXPRESIONES InFija, PreFija Y PosFija
PreFija:
La Expresión o Notación PreFija nos indica que el operador va antes de los operandos sus características principales son:
-Los operandos conservan el mismo orden que la notación infija equivalente.
-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.
Notación prefija: El orden es operador, primer operando, segundo operando
InFija:
La Expresión o Notación InFija es la forma mas común que utilizamos para escribir expresiones matemáticas, estas notaciones se refiere a que el operador esta entre los operandos. 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
Notación infija: La notación habitual. El orden es primer operando, operador, segundo operando.
PosFija:
Como su nombre lo indica se refiere a que 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*
Notación postfija: El orden es primer operando, segundo operando, operador.
EJEMPLO:
Si deseamos representar las expresiones (2+(3*4)) = x y ((2+3)*4)= x en las tres notaciones mencionadas, el resultado sería:
EJERCICIOS
EJERCICIOS
CONVERSIÓN EXPRESIÓN INFIJA A POSFIJA
El siguiente algoritmo traduce una expresión en notación infija a notación postfija:
Entrada: Una lista que contiene los términos de la ecuación en notación infija (la notación habitual).
Salida: Una lista que contiene los términos de la ecuación en notación postfija.
Datos locales: Una pila, que va a contener operadores y paréntesis izquierdos.
INICIO
Crear pila y la lista de salida, inicialmente vacias.
MIENTRAS lista de entrada no este vacia y
no se ha encontrado ningun error HACER
Extraer el primer termino de la lista (lo llamaremos E)
SEGUN-SEA E
CASO E es número :
Insertar E al final de la lista de salida
CASO E es la variable x :
Insertar E al final de la lista de salida
CASO E es un paréntesis izquierdo :
Insertar E en la pila
CASO E es un paréntesis derecho :
MIENTRAS La pila no este vacía y
su cima no sea un paréntesis izquierdo HACER
Extraer elemento de la pila
Insertarlo al final de la lista de salida
FIN-MIENTRAS
SI Encontramos el parentesis izquierdo ENTONCES
Extraerlo de la pila y destruirlo
SINO
Se ha detectado un ERROR 2
FIN-SI
Destruir E
CASO E es un operador :
MIENTRAS La pila no este vacía y
su cima sea un operador
de precedencia mayor o igual que la de E HACER
Extraer elemento de la pila
Insertarlo al final de la lista de salida
FIN-MIENTRAS
Insertar E en la pila
FIN-SEGUN-SEA
FIN-MIENTRAS
MIENTRAS Pila no esté vacía HACER
Extraer elemento de la pila
Insertarlo al final de la lista de salida
FIN-MIENTRAS
Destruir pila
FIN
CONCLUSIÓN
CONCLUSIÓN
Para concluir tenemos que las pilas las listas enlazadas, todos sus métodos y las diferentes expresiones son una de las herramientas utilizadas para programar y procesar de una manera automatizada todos los sistemas que usamos DIA tras DIA en relación a técnicas o métodos para agilizar operaciones se refiere, es su principio fundamental dar soluciones a procesos que ameritan de largos pasos que dan como resultado el control de un asusto. Estas herramientas son uno de los instrumentos más usados en la programación para estructurar y organizar información.
Page updated
Report abuse