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