En primer lugar, es importante que cualquier lector común tenga una idea general de qué es un tipo de datos abstractos (ADT) . Citando de CS13002 Programación y estructuras de datos
Un tipo de datos abstractos ( ADT ) es un objeto con una descripción genérica independiente de los detalles de implementación. Esta descripción incluye una especificación de los componentes a partir de los cuales está hecho el objeto y también los detalles de comportamiento del objeto.
Ahora, volvamos al problema. Deje que [matemática] P [/ matemática] [matemática] = [/ matemática] [matemática] a_ {0} [/ matemática] [matemática] + [/ matemática] [matemática] a_ {1} x ^ {1} [/ matemáticas] [matemáticas] + [/ matemáticas]…. [matemática] + [/ matemática] [matemática] a_ {n} x ^ {n} [/ matemática] puede ser un polinomio de grado [matemático] n [/ matemático] (el polinomio en múltiples variables se puede manejar de manera similar). Si tuviéramos que representar P usando el lenguaje C, entonces se podría usar el siguiente ADT:
- ¿Hay ejemplos fractales que usen entradas aleatorias externas de alguna manera en las iteraciones?
- En algoritmos, proporcione una matriz incremental del entero (-200, ... 0, ... 500) y quite un número. ¿Cuál es el algoritmo eficiente para encontrar el número que falta?
- Si soy bueno en matemáticas, ¿seré bueno en programación?
- Cómo desplazar cíclicamente a la derecha un número entero en C ++
- ¿Cuáles son los impactos de resolver el problema P = NP en la criptología?
1. Matriz simple: Sea A una matriz de tamaño n + 1 . Establezca [matemáticas] A [0] = a_ {0}, A [1] = a_ {1}, …, A [n] = a_ {n} [/ matemáticas].
Entonces, la matriz A es un ADT para el polinomio P.
Por ejemplo, si [matemáticas] P = 2 + 1x + 4x ^ {2} [/ matemáticas], entonces
Ahora, si hay múltiples polinomios con diversos grados, entonces se pueden hacer dos cosas:
(a) Encuentre el grado máximo de todos los polinomios y use una matriz de ese tamaño. No es muy difícil ver que es altamente ineficiente ya que cualquier polinomio con un grado inferior al grado máximo desperdiciará memoria.
Por ejemplo, deje que el grado máximo = 5 y P = x, entonces 
(b) Obtenga el grado de polinomio en tiempo de ejecución y asigne dinámicamente la cantidad de memoria requerida a la matriz.
A continuación, echemos un vistazo a la compensación involucrada con el uso de una sola matriz como ADT polinomial.
Pros: (i) Muy fácil de construir.
(ii) La suma y multiplicación polinómica es fácil.
Contras: (i) Ineficiente para polinomios dispersos como se ve en el ejemplo anterior.
(ii) No es posible modificar el ADT para representar un polinomio de mayor grado.
2. Doble matriz: deje que haya k coeficientes distintos de cero en el polinomio P.
Que haya dos matrices unidimensionales A1 y A2 , ambas de tamaño k.
Establezca [math] A1 [i] = e_ {i}, i = 0,1,2… k-1 [/ math], donde [math] e_ {i} [/ math] son exponentes en orden creciente con coeficientes cero
Establezca [matemática] A2 [i] = a_ {i}, i = 0,1,2… k-1 [/ matemática], donde [matemática] a_ {i} [/ matemática] es el coeficiente correspondiente al exponente [matemática ] e_ {i} [/ matemáticas].
Por ejemplo, deje que [math] P = 5 + 3x + 9x ^ {10} [/ math], luego [math] k = 3 [/ math] y [math] e_ {0} = 0, e_ {1} = 1, e_ {2} = 10, a_ {0} = 5, a_ {1} = 3, a_ {2} = 9 [/ matemáticas]. Luego
Aquí, A1 y A2 juntos actúan como un ADT para el polinomio P. Ahora, echemos un vistazo a la compensación:
Pros: (i) Fácil de construir.
(ii) Espacio eficiente incluso para polinomios dispersos.
Contras: (i) La adición y multiplicación de polinomios se vuelven difíciles.
(ii) No es posible modificar el ADT para representar un polinomio con más coeficientes distintos de cero.
3. Lista enlazada: como en el caso anterior, deje que haya k coeficientes distintos de cero en el polinomio P. Deje que haya una lista enlazada (individual o doblemente) L con k nodos. Cada nodo almacenará el valor del exponente y el correspondiente coeficiente distinto de cero. Es aconsejable organizar los nodos en orden creciente / decreciente de exponentes que almacenan.
por ejemplo, [matemáticas] P = 5 + 3x + 9x ^ {10} [/ matemáticas], luego [matemáticas] k = 3 [/ matemáticas]. L se verá así:
De acuerdo con la tradición, aquí está la compensación:
Pros: (i) Mantiene una estructura de datos única para almacenar exponentes y coeficientes (a diferencia de la doble matriz torpe).
(ii) Fácil de modificar, ya que la inserción y eliminación de nodos en una lista vinculada es muy conveniente.
Contras: (i) No es tan fácil de construir como las matrices.
(ii) La adición y multiplicación de polinomios se vuelve difícil.
Ahora que tiene tres ADT, esta pregunta surge naturalmente: ¿Cuál de ellos usar? Bueno, me gustaría actuar de manera perezosa y omitir esta parte diciendo: “Este es un ejercicio para el programador” .
ps: por supuesto, la elección de ADT depende de si estás limitado por la memoria o no 🙂 .
