Applications: Linked Implementation of Sparse polynomials Consider a polynomial of degree n Can be represented by a list Degree 5 0123456789 my Coeffs 0-8040000 For a sparse polynomial this is not efficient my Degree 0123456789 9596979899 myCoeffs500000 oo1 COMP 152
16 Applications: Linked Implementation of Sparse Polynomials Consider a polynomial of degree n Can be represented by a list For a sparse polynomial this is not efficient COMP152 16 myDegree 5 0 1 2 3 4 5 6 7 8 9 myCoeffs 5 7 0 -8 0 4 0 0 0 0 myDegree 99 0 1 2 3 4 5 6 7 8 9 … 95 96 97 98 99 myCoeffs 5 0 0 0 0 0 0 0 0 0 … 0 0 0 0 1
We could represent a polynomial by a list of ordered pairs (coef; exponent)… my Degree my Degree 99 my Terms5|07|1-8|34|5 my Terms 50 199 Fixed capacity of array still problematic Wasted space for sparse polynomial COMP 152
17 We could represent a polynomial by a list of ordered pairs { (coef, exponent) … } Fixed capacity of array still problematic Wasted space for sparse polynomial COMP152 17 myDegree 5 0 1 2 3 myTerms 5 0 7 1 -8 3 4 5 myDegree 99 0 1 myTerms 5 0 1 99
18 Linked list of these ordered pairs provides an appropriate solution Now whether sparse or well populated, the polynomial is represented efficiently Polynomial class(Polynomial.h) Type parameter coefType Term and Node are inner private classes for internal use and access only Used to create internal data structure of a linked node(for internal access only) my Degree 00 07 83 my Terms xt dummy/header/ sentinel COMP 152
18 Linked list of these ordered pairs provides an appropriate solution Now whether sparse or well populated, the polynomial is represented efficiently Polynomial class (Polynomial.h) Type parameter CoefType Term and Node are inner private classes for internal use and access only Used to create internal data structure of a linked node (for internal access only) COMP152 18 0 0 myTerms 5 0 7 1 -8 3 4 5 / myDegree 5 data next dummy/header/ sentinel
Stacks
19 Stacks
20 Stack overview Stack ADT Basic operations of stack Pushing, popping etc Implementations of stacks using array linked list
20 Stack Overview Stack ADT Basic operations of stack Pushing, popping etc. Implementations of stacks using array linked list