• Abstract data types are representations of real world objects in your programs
• Let us say we have a real world object: Polynomial
• Physical characteristics of Real world objects are not as important as their actions.
• Let us look at another example. Stack: supports certain actions such as pop, push, peek_at_the_top, create and destroy
• Abstract data types is defined is only defined in terms of its member functions

class polynomial

{

public:

void read();

void write();

double evaluate();

};

• After ADT definition, the next step in creating a data structure is the design phase.
• We think about the data members
• Using our understanding of the programming language we describe the physical storage using pictures.
• In our case, we are going to use an array called a to store the coefficients of each term in the polynomial.
• The absent terms have a coeff. of zero.
• In addition, we will also use a variable called order to keep track of the maximum exponent in the poly.
• In the design phase, we also specify the algorithms for each of the operation and calculate their time requirements.

Read()

Get the order of the polynomial;

for(j = order; j >= 0; j--)

get the jth coeff.;

Write()

for(j = order; j >= 0; j--)

write the jth term;

evaluate(double x)

sum = 0; // Initialize sum to zero

for(j = order; j >= 0; j--)

sum += a[j]*power(x,j);

// add x to the power j multiplied by jth coeff to the sum

• Read requires O(n)
• Write requires O(n)
• Rule of thumb: one loop linear, two nested loops quadratic
• evaluate requires O(n^2). We really have two nested loops because of the power function
• It should be possible to do better for evaluate. Horner's rule.
• See the assignment and the example from the blackboard

sum = a[order]

for(j = order - 1; j >= 0; j --)

sum = sum*x + a[j];

return sum

• The freq. of multiplication will be O(n)
• The freq. of addition will be O(n)
• The next step in development of a data structure is the actual implementation. Generally, this is an easy step. All the work is already done.

const maxorder = 100;

class polynomial

{

int order;

double a[maxorder+1];

public:

void read();

void write();

double evaluate(double x);

};

void polynomial::read()

{ // make it more interactive

cin >> order;

for(int j = order; j >= 0; j--)

cin >> a[j];

}

double polynomial::evaluate(double x)

{

double sum = 0;

for(int j = order; j >= 0; j--)

sum += a[j]*power(x,j);

}

• This data structure works efficiently if there are not too many coefficients which are zero.
• p(x) = x^5000 + 19
• The above design will take 5001 elements, when only 2 are needed.