Pointers and Dynamic Arrays

Classes, Pointers, and Dynamic Arrays

Download 225.1 Kb.

Page	4/4
Date	05.08.2017
Size	225.1 Kb.
	#26675

1 2 3 4

3. Solutions to, and remarks on, selected Programming Projects

10.3 Classes, Pointers, and Dynamic Arrays

The -> Operator

If pointer p points to a structure or class object, access to a member of the structure or class object member through the pointer is (*p).member. The expression (*p).member and p->member have the same meaning.

The parentheses in the expression (*p).member are necessary because the structure member access operator . binds more closely than the dereferencing operator *. The general rule is that postfix operators bind more closely than prefix operators. The structure access operator . is a postfix operator, and the dereference operator, *, is a prefix operator.
The this pointer

In a member function definition the predefined this pointer variable is provided (implicitly) to every non-static member function. This pointer points to the calling object. Any member function or variable that may be used in the implementation of a member function has this-> implicitly prefixed. If the function is declared to be static, then this is not supplied, and direct access to non-static members is unavailable.

Overloading the Assignment Operator

The assignment operator must be implemented as a member function. There are several operators whose overloaded operator functions must be implemented as non-static member functions. These are [], (), ->, and =.

The assignment operator should return *this so that the overloaded operator provides the expected behavior of assignment

a = b = c;

If these continued assignments aren’t required, a void return type suffices.
Destructors

A destructor is a member function that is called implicitly when a class object passes out of scope. If a class is properly designed, the class can allocate memory on the free store and its destructor will automatically deallocate the memory when the automatic variable goes out of scope.

Copy Constructors

Copying is not quite intuitive in C++. C++ considers these three situations to be copying:

when a class object is declared and initialized by another class object of the same type.
when a function return value has class type.
when class is the type for a call-by-value parameter.

The Big Three

If you need any one of the copy constructor, operator assignment, or destructor, you probably need all three. For this reason, these three members are called the big three. When either the copy constructor or operator assignment is needed, then deep copy is needed. (See the Shallow Copy and Deep Copy on page 445 in the text.)

3. Solutions to, and remarks on, selected Programming Projects

1. class TwoD: A two dimensional dynamic array of double

Based on code from Display 10.9, write a class TwoD that implements a two-dimensional dynamic array of double.

Student should supply:

Default constructor for which you choose a default maximum rows and maximum columns
Parameterized constructor, which sets maximum rows and maximum columns
A void member function that allows setting a particular row-column entry
A double member function that allows retrieving a particular row-column entry
Remark: Suggest accessor and mutator member functions for these accesses.
Overload + as friend to add to matrices of the same size
Overload =
Copy constructor
Destructor
Use const for members that do not change

Notes: I overloaded the function call operator to serve as index. That way, matrix(i, j) returns the (i, j) element, while matrix(i) returns the i^th row. (I did not implement this last overloading. I only supplied the declaration.)

#include

using std::exit;

using std::cin;

using std::cout;

using std::endl;

typedef double* DoubleArrayPtr;
class TwoD

{

public:

TwoD(); // sets maxRows and maxCols each to 10
TwoD(int maxR, int maxC);
~TwoD();

TwoD(const TwoD&);

const TwoD& operator=(const TwoD& rhs);

double& operator()(int r, int c); // returns row r, col c element

double* operator()(int r); //returns pointer to row r. Ordinary index

//extracts elements from this operator.

friend TwoD operator+(const TwoD& lhs, const TwoD& rhs);

friend int myRows(const TwoD&);

friend int myCols(const TwoD&);

private:

DoubleArrayPtr * matrix;

int maxRows;

int maxCols;

};
int main( )

{

int d1, d2, i, j;

cout << "Enter the row and column dimensions of the array\n";

cin >> d1 >> d2;

TwoD matrix1(d1, d2);
cout << "Enter " << d1 << " rows of "

<< d2 << " doubles each\n";

for (i = 0; i < d1; i++)

for (j = 0; j < d2; j++)

cin >> matrix1(i,j);

cout << "Echoing the 2 dim. array, matix1\n";

for (i = 0; i < d1; i++)

{

for (j = 0; j < d2; j++)

cout << matrix1(i,j) << " ";

cout << endl;

}
cout << "Enter the row and column dimensions of the array\n";

cin >> d1 >> d2;

TwoD matrix2(d1, d2), matrix3;
cout << "Enter " << d1 << " rows of "

<< d2 << " doubles each\n";

for (i = 0; i < d1; i++)

for (j = 0; j < d2; j++)

cin >> matrix2(i,j);

cout << "Echoing the 2 dim. array, matrix2\n";

for (i = 0; i < myRows(matrix2); i++)

{

for (j = 0; j < myCols(matrix2); j++)

cout << matrix2(i,j) << " ";

cout << endl;

}
cout << "assigning matrix 2 to matrix 3 " << endl;

matrix3 = matrix2;

cout << "Displaying the 2 dim array, matrix3 "

<< "resulting from assignmnet.\n";

cout << "rows " << myRows(matrix3) << " "

<< "cols " << myCols(matrix3) << endl;

for (i = 0; i < myRows(matrix3); i++)

{

for (j = 0; j < myCols(matrix3); j++)

cout << matrix3(i,j) << " ";

cout << endl;

}
matrix3 = matrix2 + matrix1;
cout << "Echoing the 2 dim array, sum of matrix 1 and 2\n";

cout << "rows " << myRows(matrix3) << " "

<< "cols " << myCols(matrix3) << endl;

for (i = 0; i < myRows(matrix3); i++)

{

for (j = 0; j < myCols(matrix3); j++)

{

// cout << "i,j " << i << " " << j << " ";

cout << matrix3(i,j) << " ";

}

cout << endl;

}
return 0;

}
int myRows(const TwoD& arg){ return arg.maxRows;}

int myCols(const TwoD& arg){ return arg.maxCols;}
TwoD operator+(const TwoD& lhs, const TwoD& rhs)

{

if(lhs.maxRows != rhs.maxRows || lhs.maxCols != rhs.maxCols)

{

cout << "Matrices not same size "

<< " lhs matrix row, col sizes "

<< lhs.maxRows << " " << lhs.maxCols << endl

<< "rhs matrix row, col sizes "

<< rhs.maxRows << " " << rhs.maxCols << endl;

exit(1); // Die if matrices not same.

}
//sizes are same

TwoD sum(lhs.maxRows, lhs.maxCols);

for(int i = 0; i < lhs.maxRows; i++)

for(int j = 0; j < lhs.maxCols; j++)

sum.matrix[i][j] = rhs.matrix[i][j] + lhs.matrix[i][j];
return sum;

}

double& TwoD::operator()(int r, int c) // returns row r, col c element

{

return matrix[r][c];

}

const TwoD& TwoD::operator=(const TwoD& rhs)

{

if(matrix == rhs.matrix)

return rhs; // lhs == rhs, do nothing
//lhs != rhs, blow away lhs

for(int i = 0; i < maxRows; i++)

delete[] matrix[i];

delete[] matrix;

maxRows = rhs.maxRows;

maxCols = rhs.maxCols;

//reallocate

matrix = new DoubleArrayPtr[maxRows];

for(int i = 0; i < maxRows; i++)

matrix[i] = new double[maxCols];

//deep copy

for(int i = 0; i < maxRows; i++)

for(int j = 0; j < maxCols; j++)

matrix[i][j] = rhs.matrix[i][j];

return rhs;

}
TwoD::TwoD(const TwoD& rhs)

: maxRows(rhs.maxRows), maxCols(rhs.maxCols)

{

matrix = new DoubleArrayPtr[maxRows];

for(int i = 0; i < maxRows; i++)

matrix[i] = new double[maxCols];

for(int i = 0; i < maxRows; i++)

for(int j = 0; j < maxCols; j++)

matrix[i][j] = rhs.matrix[i][j];

}

TwoD::~TwoD()

{

for(int i = 0; i < maxRows; i++)

delete[] matrix[i];

delete[] matrix;

}
TwoD::TwoD() : maxRows(10), maxCols(10)

{

matrix = new DoubleArrayPtr[maxRows];

for(int i = 0; i < maxRows; i++)

matrix[i] = new double[maxCols];

for(int i = 0; i < maxRows; i++)

for(int j = 0; j < maxCols; j++)

matrix[i][j] = 0;

}
TwoD::TwoD(int maxR, int maxC ) : maxRows(maxR), maxCols(maxC)

{

matrix = new DoubleArrayPtr[maxRows];

for(int i = 0; i < maxR; i++)

matrix[i] = new double[maxCols];

for(int i = 0; i < maxRows; i++)

for(int j = 0; j < maxCols; j++)

matrix[i][j] = 0;

}

I usually use the command line to execute with input redirected

from a file. It is easier than typing in the data every time:

ch10prog1 < ch10prog1Data.txt > ch10prog1out.txt
With this data:
3 4

1.0 2.0 3.0 4.0

5.0 6.0 7.0 8.0

9.0 8.0 1.0 2.0

3 4

1.0 1.0 1.0 1.0

-1.0 -1.0 -1.0 -1.0

2.0 2.0 2.0 2.0

A run of this produces this output:
Enter the row and column dimensions of the array

Enter 3 rows of 4 doubles each

Echoing the 2 dim. array, matix1

1 2 3 4

5 6 7 8

9 8 1 2

Enter the row and column dimensions of the array

Enter 3 rows of 4 doubles each

Echoing the 2 dim. array, matrix2

1 1 1 1

-1 -1 -1 -1

2 2 2 2

assigning matrix 2 to matrix 3

Displaying the 2 dim array, matrix3 resulting from assignmnet.

rows 3 cols 4

1 1 1 1

-1 -1 -1 -1

2 2 2 2

Echoing the 2 dim array, sum of matrix 1 and 2

rows 3 cols 4

2 3 4 5

4 5 6 7

11 10 3 4

*/
2. Polynomial class.

Using dynamic arrays, implement a polynomial class with infix operators +, -, *.
Discussion:

In a polynomial, a variable is placeholder for coefficient. If term is missing, the coefficient is 0. For example, the cubic polynomial

2x³ -3x + 4

or, written out as C++ code,

2*x*x*x –3*x + 4

has the coefficients for terms as listed:

degree 3 term has coefficient 2,

degree 2 term has coefficient 0,

degree 1 term has coefficient -3, and

degree 0 term has coefficient 4.

Note that the term with degree 2 is missing, but we will use a coefficient of 0 to indicate that. Observe that the size of the coefficient array is 4, one more than the degree.
Use of sparse matrix techniques not recommended. We will assume that there are few missing terms.
The student is to provide these member functions:

default constructor,
copy constructor,
operator=
destructor
parameterized constructor to create an arbitrary polynomial

operator+
operator-
operator*
assign and inspect function (or functions) for
coefficients, indexed by exponent

function to evaluate polynomial as a value of type double

The student is to decide on whether these are to be member, friend, or neither

(standalone).
NOTES:

The default constructor creates an empty polynomial. A zero polynomial has degree 0, since it has only the zero degree coefficient.

In the coefficient array, the index is the value of the exponent of term having this coefficient. For example, the index 0 entry is the constant coefficient, the index 1 entry is coefficient of the linear term, the index 2 entry is the coefficient of the quadratic term (term in x²), etc.
The size of the coefficient array include a degree 0 entry, so the size is the degree of the polynomial + 1.
Odd error messages associated with overloading some of the operators occur if you try to pass a Polynomial object to one of the functions by const reference and do not implement both these operator[] implementations,
//This version of operator[] is used when an indexed

//expression is used as an l-value.

double& operator[](int degree);

//This version of operator[] is used when an indexed

//expression is used as an r-value.

const double& operator[](int degree)const;

Instead of difficult-to-understand compiler error messages, you may get linker errors, which is an even harder situation, since linker errors are not associated with any particular line in your source.
The alternative is to pass by value. In this example, that is not a problem but in general, passing a class object has the potential for a large amount of copying of data, so const reference is the desirable way to do it.
Neither of the operator functions for multiply, add or subtract check for zero lead coefficients. For polynomials that have many zero terms, these functions should account for the zero entries. Two polynomials of high degree with few nonzero terms will waste considerable time multiplying zero entries using this technique. The fix is the use of a linked list (Chapter 17), or the STL list (Chapter 19.)
My solution follows:
//file: ch10Prog2.cpp
//Polynomial class -- Chapter 10 Programming Problem #2
#include

using namespace std;

class Polynomial

{

public:

Polynomial(); // creates an empty polynomial

Polynomial(const Polynomial&);

// The size of the coefficient array is degree of the polynomial + 1.

Polynomial(double coefficient[], int size);

~Polynomial();
//Use indexed polynomial as r-value to inspect coefficient

//and as l-value to assign coefficient

double& operator[](int degree);

//This is required if we are to have const correctness

const double& operator[](int degree)const;
const Polynomial& operator=(const Polynomial & rhs);

int misuse();

//friend functions:

friend double evaluate(const Polynomial& ploy, double arg);

friend Polynomial operator+(const Polynomial& lsh,

const Polynomial& rhs);

friend Polynomial operator-(const Polynomial& lsh,

const Polynomial& rhs);

friend Polynomial operator*(const Polynomial& lsh,

const Polynomial& rhs);

private:

double * coef;

int size;

};
int main()

{

Polynomial empty;

double one[] = {1};

Polynomial One(one, 1);

double quad[] = {3, 2, 1};

double cubic[] = {1, 2, 0, 3};

Polynomial q(quad, 3); // q is 3 + 2*x + x*x

Polynomial c(cubic, 4);// c is 1 + 2*x + 0*x*x + 3*x*x*x

Polynomial p = q; // test copy constructor

Polynomial r;

r = q; //test operator=

r = c;
cout << "Polynomial q " << endl;

{for(int i = 0; i < 3; i++)

cout << "term with degree " << i

<< " has coefficient " << q[i] << endl;

}

cout << "Polynomial c " << endl;

{for(int i = 0; i < 4; i++)

cout << "term with degree " << i

<< " has coefficient " << c[i] << endl;

}

cout << "value of q(2) is " << evaluate(q, 2) << endl;

cout << "value of p(2) is " << evaluate(p, 2) << endl;

cout << "value of r(2) is " << evaluate(r, 2) << endl;

cout << "value of c(2) is " << evaluate(c, 2) << endl;
r = q + c;

cout << "value of (q + c)(2) is " << evaluate(r, 2) << endl;

r = q - c;

cout << "value of (q - c)(2) is " << evaluate(r, 2) << endl;

r = q * c;

cout << "size of q*c is " << r.mySize() << endl;

cout << "Polynomial r (= q*c) " << endl;
for(int i = 0; i < r.mySize(); i++)

cout << "term with degree " << i

<< " has coefficient " << r[i] << endl;
cout << "value of (q * c)(2) is " << evaluate(r, 2) << endl;

return 0;

}
int Polynomial::mySize()

{

return size;

}
// creates an empty polynomial

Polynomial::Polynomial():coef(0), size(0)

{// deliberately empty

}
const Polynomial& Polynomial::operator=(const Polynomial & rhs)

{

if(rhs.coef == coef) //if both coefficient arrays start at the same

return rhs; //place our two Polynomials are the same.

else

{

delete [] coef;

coef = new double[rhs.size];

for(int i = 0; i < rhs.size; i++)

coef[i] = rhs.coef[i];

size = rhs.size;

}

return rhs;

}
Polynomial::Polynomial(const Polynomial& rhs) : size(rhs.size)

{

coef = new double[rhs.size];

for(int i = 0; i < rhs.size; i++)

coef[i] = rhs.coef[i];

}
Polynomial::Polynomial(double coefficient[],

int newSize) : size(newSize)

{

coef = new double[size];

for(int i = 0; i < size; i++)

coef[i] = coefficient[i];

}
Polynomial::~Polynomial()

{

delete [] coef;

}
//return the coefficient of term in variable to exponent 'degree'

const double& Polynomial::operator[](int degree) const

{

return coef[degree];

}
double& Polynomial::operator[](int degree)

{

return coef[degree];

}
double max(double lhs, double rhs)

{

return (lhs > rhs) ? lhs : rhs;

}
// friend function and operator function implementations

Polynomial operator+(const Polynomial& lhs, const Polynomial& rhs)

{

const int sumSize = max(lhs.size, rhs.size);

double* sumCoefs = new double[sumSize];
for(int i = 0; i < sumSize; i++)

sumCoefs[i] = lhs.coef[i] + rhs.coef[i];

return Polynomial(sumCoefs, sumSize);

}
Polynomial operator-(const Polynomial& lhs, const Polynomial& rhs)

{

int sumSize = max(lhs.size, rhs.size);

double* sumCoefs = new double[sumSize];
for(int i = 0; i < sumSize; i++)

sumCoefs[i] = lhs.coef[i] - rhs.coef[i];

return Polynomial(sumCoefs, sumSize);

}

// Notes:

// The multiplication routine does not check for zero lead

// coefficients. It also assumes few zero terms.

Polynomial operator*(const Polynomial& lhs, const Polynomial& rhs)

{

int i; int j;

int prodSize = lhs.size + rhs.size;

double* prodCoefs = new double[prodSize];

for(i = 0; i < prodSize; i++)

prodCoefs[i] = 0;

for(i = 0; i < lhs.size; i++)

for(j = 0; j < rhs.size; j++)

prodCoefs[i + j] += lhs[i] * rhs[j];
return Polynomial(prodCoefs, prodSize);

}
double evaluate(const Polynomial& poly, double arg)

{

double value = 0;

int i;
for(i = poly.size - 1; i >= 0; i--)

value = poly[i] + arg * value;

return value;

}

This is the output from this program follows.

Polynomial q

term with degree 0 has coefficient 3

term with degree 1 has coefficient 2

term with degree 2 has coefficient 1

Polynomial c

term with degree 0 has coefficient 1

term with degree 1 has coefficient 2

term with degree 2 has coefficient 0

term with degree 3 has coefficient 3

value of q(2) is 11

value of p(2) is 11

value of r(2) is 29

value of c(2) is 29

value of (q + c)(2) is 40

value of (q - c)(2) is -18

size of q*c is 7

Polynomial r (= q*c)

term with degree 0 has coefficient 3

term with degree 1 has coefficient 8

term with degree 2 has coefficient 5

term with degree 3 has coefficient 11

term with degree 4 has coefficient 6

term with degree 5 has coefficient 3

term with degree 6 has coefficient 0

value of (q * c)(2) is 319

1 For a discussion of programming language paradigms, see Ravi Sethi, Programming Languages, Concepts and Constructs, ISBN 0-201-59065-4 , or Robert W. Sebesta, Concepts of Programming Languages, third edition, ISBN 0-8053-7133-8, both available from Addison Wesley Longman. See George Orwell, 1984, appendices, for a serious discussion of social issues regarding language.

2 To find the Microsoft download page for this patch, I use the Google search engine with search string Microsoft Visual Studio Service Patch. This usually finds a page at Microsoft from which you can navigate to the site that has the required patch.

3 Ellis and Stroustrup, in The Annotated C++ Reference Manual, say that declarations are statements.

4 An l-value is capable of being assigned, and an r-value has a value that can be fetched.

5 Bitwise AND is not discussed in the text. It does an AND between bits of each operand, bit by bit. The operands must be integers.

6 Most compilers track this ANSI C++ Standard required behavior. Read your compiler documentation and run test programs to determine your compilers behaviioujor.

7 As expected, different compilers produce different changes.

8 The common usage is “deleted pointer” but it should be “deleted memory”, for it is the memory that is “deleted,” not the pointer.

9 This has a cognate in Java with the declaration of Java references. In Java, you don’t get an object by declaring a variable of class type. You only get a reference that can refer to a class object. Until the programmer writes code to do the allocation, there is no object.

10 The word “thrashing” is used to describe this situation. When disk drives were really noisy, the disk drive sounded like a thrashing machine when this situation was encountered.

11 The sizeof operator applied to an expression returns the number of bytes of memory that the expression requires. If applied to a type, sizeof requires that the type name be placed in parentheses.

Directory: wps -> media -> objects
objects -> Engine Manufacturers Association v. South Coast Air Quality Management District, 124 S. C
wps -> Anarchist Women Printers: Old and New Materialisms
objects -> Basic telephone etiquette
objects -> Review of Probability (a) Probability distribution function for
objects -> Internet Mini Case 1 Palm, Inc
objects -> Apple Computer Inc v. Franklin Computer Corp
objects -> Chapter 16: Population Growth and the Atlantic Migration Summary
objects -> Environmental protection
objects -> Toyota and the Changing Car Market a case of non-price competition

Download 225.1 Kb.

Share with your friends:

1 2 3 4