C++ Consider a sparse implementation of the ADT polynomial that stores only the
ID: 3888190 • Letter: C
Question
C++
Consider a sparse implementation of the ADT polynomial that stores only the terms with nonzero coefficients. For example, you can represent the revised polynomial p in Exercise 9 of Chapter 1with the linked chain shown in Figure 4-10. a. Complete the sparse implementation. b. Define a traverse operation for the ADT polynomial that will allow you to add two sparse polynomials without having to consider terms with zero coefficients explicitly. Consider the ADT polynomial-in a single variable x-whose operations include the following: degree() // Returns the degree of a polynomial coefficient(power) // Returns the coefficient of the x^term. changeCoefficient (newCoefficient, power) // Replaces the coefficient of // the x^power with newCoefficient. For this problem, consider only polynomials whose exponents are nonnegative integers. For example, p = 4x^5 + 7x^3 - x^2 + 9 The following examples demonstrate the ADT operations on this polynomial P .degree() is 5 (the highest power of a term with a nonzero coeffi cient) p.coefficient (3) is 7 (the coeffi cient of the x^3 term) p.coefficient(4) is 0 (the coeffi cient of a missing term is implicitly 0) p. change Coefficient(-3, 7) changes the polynomial p to -3x^7 + 4x^7 + x^3 - x^2 + 9Explanation / Answer
class polynomial {
struct Term {
int coef;
int power;
Term *next;
};
private:
int maxDeg;
Term *headPtr = NULL;
public:
int degree() {
return maxDeg;
}
int coefficient(int power) {
Term *tmp = headPtr;
while (tmp != NULL) {
if (tmp -> power == power)
return tmp->coef;
else if (tmp -> power < power)
break;
}
return 0;
}
void changeCoefficient(int newCoefficient, int power) {
if (headPtr == NULL) {
headPtr = new Term;
headPtr->coef = newCoefficient;
headPtr->power = power;
headPtr->next = NULL;
return;
}
Term *tmp = headPtr;
if (headPtr -> power < power) {
headPtr = new Term;
headPtr->coef = newCoefficient;
headPtr->power = power;
headPtr->next = tmp;
return;
}
while (tmp->next != NULL) {
if (tmp-> next-> power == power) {
tmp-> next-> coef = newCoefficient;
return;
}
else if (tmp-> next-> power < power)
break;
}
Term *newTerm = newTerm;
newTerm->coef = newCoefficient;
newTerm->power = power;
newTerm->next = tmp->next;
tmp->next = newTerm;
}
}
Let me know if this works for you
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.