Skip to the content of the web site.

Project A.2: Polynomials as linked lists

Up to this point, we have defined a polynomial-as-array class calculate them. This is, however, inefficient if we are storing sparse polynomials, that is, polynomials where the coefficients of most terms are zero. Recall that an expanded polynomial is one that is the sum of a finite number of terms, were each term is a coefficient multiplied by a variable raised to a non-negative integer power.

We will only store those terms in the polynomial that have non-zero coefficients, and thus each node in the linked list must not only contain the coefficient, but also the power of the variable. We don't really care what the variable is, and thus we will not store this information. To make our lives easier, we will keep the polynomial in order with the leading term first. If the linked list is empty, this is of course the representation of the zero polynomial:

class Polynomial_as_linked_list;
class Term;

class Term {
	private:
		double coefficient;
		unsigned int degree;

	friend class Polynomial_as_linked_list;
};

class Polynomial_as_linked_list {
	public:
		Polynomial_as_linked_list();
		~Polynomial_as_linked_list();

	private:
		Term *p_terms;
};

We will now proceed to accessing or setting the coefficients in both of these examples.

ECE 150 Fundamentals of programming

Project A.2: Polynomials as linked lists

Questions and practice: