Resumen
La realización de un applet sobre polinomios que
obtenga las 4 operaciones fundamentales: suma, resta,
multiplicación y división, además de la
simplificación, la derivada y la integral. Todo con el
empleo de listas enlazadas.
Introducción
Las listas enlazadas son estructuras de datos semejantes
a los array salvo que el acceso a un elemento no se hace mediante
un índice sino mediante un puntero.
La asignación de memoria es hecha durante la
ejecución.
En una lista los elementos son contiguos en lo que
concierne al enlazado.
Las listas enlazadas pueden ser utilizadas cuando se
necesitan hacer varias operaciones de inserción y
eliminación de elementos
Listas
enlazadas
Una lista enlazada es un conjunto de elementos llamados
nodos en los que cada uno de ellos contiene un dato y
también la dirección del siguiente nodo, donde el
orden de los mismos se establece mediante punteros.
La idea básica es que cada componente de la lista
incluya un puntero que indique donde puede encontrarse el
siguiente componente por lo que el orden relativo de estos puede
ser fácilmente alterado modificando los punteros lo que
permite, a su vez, añadir o suprimir elementos de la
lista. El primer elemento de la lista es la cabecera, que
sólo contiene un puntero que señala el primer
elemento de la lista.
El último nodo de la lista apunta a NULL (nulo)
porque no hay más nodos en la lista. Se usará el
término NULL para designar el final de la
lista.
2.1 Clasificación.
Las listas enlazadas se clasifican en:
Listas enlazadas simples, doblemente enlazadas,
circulares simplemente enlazadas y circulares doblemente
enlazadas.
2.2 Listas Enlazadas frente a Arrays
Las listas enlazadas tienen las siguientes ventajas
sobre los arrays:
– No requieren memoria extra para soportar la
expansión. Por el contrario, los arrays requieren memoria
extra si se necesita expandirlo (una vez que todos los elementos
tienen datos no se pueden añadir datos nuevos a un
array).
– Ofrecen una inserción/borrado de elementos
más rápida que sus operaciones equivalentes en los
arrays. Sólo se tienen que actualizar los enlaces
después de identificar la posición de
inserción/borrado.
– Desde la perspectiva de los arrays, la
inserción de datos requiere el movimiento de todos los
otros datos del array para crear un elemento vacío. De
forma similar, el borrado de un dato existente requiere el
movimiento de todos los otros datos para eliminar el
elementovacío.
En contraste, los arrays ofrecen las siguientes ventajas
sobre las listas enlazadas:
– Los elementos de los arrays ocupan menos memoria que
los nodos por que no requieren campos de enlace.
– Los arrays ofrecen un aceso más rápido a
los datos, medante índices basados en enteros.
Las listas enlazadas son más apropiadas cuando se
trabaja con datos dinámicos. En otras palabras,
inserciones y borrados con frecuencia. Por el contrario, los
arrays son más apropiados cuando los datos son
estáticos (las inserciones y borrados son raras). De todas
formas, no olvide que si se queda sin espacio cuando añade
ítems a un array, debe crear un array más grande,
copiar los datos del array original el nuevo array mayor y
elimiar el original. Esto cuesta tiempo, lo que afecta
especialmente al rendimiento si se hace repetidamente.
Mezclando una lista de enlace simple con un array
uni-dimensional para acceder a los nodos mediante los
índices del array no se consigue nada. Gastará
más memoria, porque necesitará los elementos del
array más los nodos, y tiempo, porque necesitará
mover los ítems del array siempre que inserte o borre un
nodo. Sin embargo, si es posible integrar el array con una lista
enlazada para crear una estructura de datos
úti.
Existen diferentes tipos de listas enlazadas: Lista
Enlazadas Simples, Listas Doblemente Enlazadas y Listas Enlazadas
Circulares.
Las listas enlazadas pueden ser implementadas en muchos
lenguajes. Lenguajes tales como Lisp y Scheme tiene estructuras
de datos ya construidas, junto con operaciones para acceder a las
listas enlazadas. Lenguajes imperativos u orientados a objetos
tales como C, C++ o Java disponen de referencias para crear
listas enlazadas.
Las operaciones que podemos realizar sobre una lista
enlazada son las siguientes:
Recorrido. Esta operación consiste en visitar
cada uno de los nodos que forman la lista.
Para recorrer todos los nodos de la lista, se comienza
con el primero, se toma el valor del campo liga para avanzar al
segundo nodo, el campo liga de este nodo nos dará la
dirección del tercer nodo, y así
sucesivamente.
Inserción
Esta operación consiste en agregar un nuevo nodo
a la lista. Para esta operación se pueden considerar tres
casos:
Insertar un nodo al inicio.
Insertar un nodo antes o después de cierto
nodo.Insertar un nodo al final.
Borrado
La operación de borrado consiste en quitar un
nodo de la lista, redefiniendo las ligas que correspondan. Se
pueden presentar cuatro casos:
Eliminar el primer nodo.
Eliminar el último nodo.
Eliminar un nodo con cierta
información.Eliminar el nodo anterior o posterior al nodo cierta
con información.
Búsqueda
Esta operación consiste en visitar cada uno de
los nodos, tomando al campo liga como puntero al siguiente nodo a
visitar.
Polinomios
Los polinomios son expresiones algebraicas de la
forma:
Los coeficientes del polinomio son los números
que aparecen multiplicando a la variable.
Al término sin x se le llama término
independiente.
Grado de un Polinomio
El grado de un polinomio es el mayor
exponente al que se encuentra elevada
la variable x.
Tipos de Polinomios
Monomio
Es un polinomio que consta de un sólo
monomio.
P(x) = 2×2
Binomio
Es un polinomio que consta de dos monomios.
P(x) = 2×2 + 3x
Trinomio
Es un polinomio que consta de tres monomios.
P(x) = 2×2 + 3x + 5
Polinomio de grado cero
P(x) = 2
Polinomio de primer grado
P(x) = 3x + 2
Polinomio de segundo grado
P(x) = 2×2 + 3x + 2
Polinomio de tercer grado
P(x) = x3 – 2×2+ 3x + 2
Polinomio de cuarto grado
P(x) = x4 + x3 – 2×2+ 3x + 2
Polinomio nulo
El polinomio nulo tiene todos sus coeficientes
nulos.
Polinomio homogéneo
El polinomio homogéneo tiene todos sus
términos o monomios con el mismo grado.
P(x) = 2×2 + 3xy
Polinomio heterogéneo
Los términos de un polinomio heterogéneo
son de distinto grado.
P(x) = 2×3 + 3×2 – 3
Polinomio completo
Un polinomio completo tiene todos los términos
desde el término independiente hasta el término de
mayor grado.
P(x) = 2×3 + 3×2 + 5x – 3
Polinomio ordenado
Un polinomio está ordenado si los monomios que lo
forman están escritos de mayor a menor grado.
P(x) = 2×3 + 5x – 3
Suma de Polinomios
Para sumar dos polinomios se suman los coeficientes de
los términos del mismo grado.
P(x) = 2×3 + 5x – 3 Q(x) = 4x – 3×2 +
2×3
a. Ordenamos los polinomios, si no lo
están.
Q(x) = 2×3 – 3×2 + 4x
P(x) + Q(x) = (2×3 + 5x – 3) + (2×3 – 3×2
+ 4x)
b. Agrupamos los monomios del mismo
grado.
P(x) + Q(x) = 2×3 + 2×3 – 3 x2 + 5x + 4x
– 3
c. Sumamos los monomios semejantes.
P(x) + Q(x) = 4×3- 3×2 + 9x –
3
Resta de Polinomios
La resta de polinomios consiste en sumar el opuesto del
sustraendo.
P(x) – Q(x) = (2×3 + 5x – 3) – (2×3 – 3×2 +
4x)
P(x) – Q(x) = 2×3 + 5x – 3 – 2×3 + 3×2 – 4x
P(x) – Q(x) = 2×3 – 2×3 + 3×2 + 5x- 4x – 3
P(x) – Q(x) = 3×2 + x – 3
Multiplicación de
Polinomios
P(x) = 2×2 – 3 Q(x) = 2×3 – 3×2 + 4x
Se multiplica cada monomio del primer polinomio por
todos los elementos segundo polinomio.
P(x) · Q(x) = (2×2 – 3) · (2×3 – 3×2 + 4x)
=
= 4×5 – 6×4 + 8×3 – 6×3 + 9×2 – 12x =
Se suman los monomios del mismo grado.
= 4×5 – 6×4 + 2×3 + 9×2 – 12x
Se obtiene otro polinomio cuyo grado es la suma de los
grados de los polinomios que se multiplican.
División de Polinomios
La división algebraica es la operación que
consiste en hallar uno de los factores de un producto, que recibe
el nombre de cociente dado el otro factor, llamado divisor, y el
producto de ambos factores llamado dividendo.
De la definición anterior se deduce que el
dividendo coincide con el producto del divisor por el cociente.
Así por ejemplo, si dividimos, se cumplirá
que
Si el residuo no fuera igual a cero,
entonces:
Para efectuar una división algebraica hay que
tener en cuenta los signos, los exponentes y los coeficientes de
las cantidades que se dividen.
(+)÷(+)=+
(-)÷(-)=+
(+)÷(-)=-
(-)÷(+)=-
DIVISIÓN DE UN MONOMIO POR OTRO
Para dividir dos monomios se divide el coeficiente del
dividiendo entre el coeficiente del divisor y a
continuación se escriben las letras ordenadas
alfabéticamente, elevando cada letra a un exponente igual
a la diferencia entre el exponente que tiene en el dividendo y el
exponente que tiene en el divisor. El signo del cociente
será el que corresponda al aplicar la regla de los
signos.
Referencias
es.kioskea.net/faq/2842-la-lista-enlazada-simple
dmmolina.wordpress.com/2008/07/13/listas-enlazadas-defenicion-y-ejemplos/
www.ditutor.com/polinomios/polinomios.html
Autor:
Oscar Luis Rojas Murillo