CH2. ARRAYS.ppt

1、CH2. ARRAYS,10/10/2018,2,2.1 Abstract Data Types and the C+ Class,2.1.1 C+ Class : represents an ADT Consists of four components class name data members member functions levels of program access public : anywhere private : within its (friend) class a function protected : within its class friend,10/1

2、0/2018,3,2.1 Abstract Data Types and the C+ Class(Cont),#ifndef RECTANGLE_H #define RECTANGLE_H / In the header file Rectangle.h class Rectangle public: / the following members are public / The next four members are member functions Rectangle(); / constructor Rectangle(); / destructor int GetHeight(

3、); / returns the height of the rectangle int GetWidth(); / returns the width of the rectangle private: / the following members are private / the following members are data members int x1, y1, h, w; / (x1, y1) are the coordinates of the bottom left corner of the rectangle / w is the width of the rect

4、angle; h is the height of the rectangle ; #endif,Program 2.1 : Definition of the C+ class Rectangle,10/10/2018,4,2.1 Abstract Data Types and the C+ Class(Cont),2.1.2 Data Abstraction and Encapsulation in C+ Data encapsulation of C+ class all data members are private (or protected) external access to

5、 data members are by member functions Separation of specification and implementation of member functions specification (function prototype) name of functions type of function arguments type of function result Implementation placed in a source file of the same name can be included inside its class de

6、finition,10/10/2018,5,2.1 Abstract Data Types and the C+ Class(Cont),/ In the source file Rectangle.C #include “Rectangle.h“ / The prefix “Rectangle:“ identifies GetHeight() and / GetWidth() as member functions / belonging to class Rectangle. It is required because the member functions / are impleme

7、nted outside their class definition int Rectangle:GetHeight() return h; int Rectangle:GetWidth() return w;,Program 2.2 : Implementation of operations on Rectangle,10/10/2018,6,2.1 Abstract Data Types and the C+ Class(Cont),2.1.3 Declaring class objects in the same way as variables Invoking member fu

8、nctions using component selection operators dot(.) : direct selection arrow : indirect selection through a pointer,10/10/2018,7,2.1 Abstract Data Types and the C+ Class(Cont),/ In a source file main.C #include #include “Rectangle.h“ main() Rectangle r, s; / r and s are objects of class Rectangle Rec

9、tangle *t = ,Program 2.3 : A C+ code fragment demonstrating how Rectangle objects are declared and member functions invoked,10/10/2018,8,2.1 Abstract Data Types and the C+ Class(Cont),2.1.4 Special Class Operations Constructor a member function which initializes data members of an object If provided

10、 for a class, automatically executed when an object of that class is created must be public the name must be identical to the name of the class must not specify a return type or return a value,Rectangle:Rectangle(int x, int y, int height, int width) x1=x; y1=y; h=height; w=width; ,Program 2.4 : Defi

11、nition of a constructor for Rectangle,10/10/2018,9,2.1 Abstract Data Types and the C+ Class(Cont),initialize Rectangle object using constructor Rectangle r(1, 3, 6, 6); Rectangle *s = new Rectangle(0, 0, 3, 4); initialize using a default constructor Rectangle r;,Rectangle:Rectangle (int x=0, int y=0

12、, int height=0, int width=0) : x1 (x), y1(y), h(height), w(width) ,Program 2.5 : A default constructor,10/10/2018,10,2.1 Abstract Data Types and the C+ Class(Cont),Destructor a member function which deletes data members automatically invoked when a class object goes out of scope or is deleted must b

13、e public its class name prefixed with if a data member is a pointer, only the space of the pointer is returned Operator overloading polymorphism : same operator for different situations for example, algorithm comparing two floats is different from algorithm comparing two ints,10/10/2018,11,2.1 Abstr

14、act Data Types and the C+ Class(Cont),int Rectangle:operator=(const Rectangle ,Program 2.6 : Overloading operator = for class Rectangle,10/10/2018,12,2.1 Abstract Data Types and the C+ Class(Cont),this represents a pointer to the object that invoked a member function *this represents the object,10/1

15、0/2018,13,2.1 Abstract Data Types and the C+ Class(Cont),Ostream ,Program 2.7 : Overloading operator for class Rectangle,10/10/2018,14,2.1 Abstract Data Types and the C+ Class(Cont),2.1.5 Miscellaneous Topics static class data member a global variable for its class there is only one copy of a static

16、 data member and all class objects share it declaration does not constitute a definition,10/10/2018,15,2.1 Abstract Data Types and the C+ Class(Cont),2.1.6 ADTs and C+ classes They are similar Some operators in C+, when overloaded for user defined ADTs, are declared outside the C+ class definition o

17、f the ADT,10/10/2018,16,2.1 Abstract Data Types and the C+ Class(Cont),class NaturalNumber / An ordered subrange of the integers starting at zero and ending at / the maximum integer (MAXINT) on the computer public: NaturalNumber Zero(); / returns 0 Boolean IsZero(); / if *this is 0, return TRUE; oth

18、erwise, return FALSE NaturalNumber Add(NaturalNumber y); / return the smaller of *this+y and MAXINT; Boolean Equal(NaturalNumber y); / return TRUE if *this=y; otherwise return FALSE NaturalNumber Successor(); / if *this is MAXINT return MAXINT; otherwise return *this+1 NaturalNumber Substract(Natura

19、lNumber y); / if *thisy, return 0; otherwise return *this-y ;,ADT 1.2 : Abstract data type NaturalNumber,10/10/2018,17,2.2 Array As Abstract Data Type,Array a set of pairs ADT for array provides operations retrieves a value stores a value C+ Array index starts at 0 C+ does not check bounds for an ar

20、ray index example float examplen; ith element: examplei and *(example+i),10/10/2018,18,2.2 Array As Abstract Data Type(Cont),Class GeneralArray / objects: A set of pairs where for each value of index / in IndexSet there is a value of type float. / IndexSet is a finite ordered set of one or more dime

21、nsions, / for example, 0, ., n-1 for one dimension, / (0,0), (0,1), (0,2), (1,0), (1,1), (1,2), (2,0), (2,1), (2,2) for two / dimensions, etc. public: GeneralArray(int j, RangeList list, float initValue = defaultValue); / The constructor GeneralArray creates a j dimensional array / of floats; the ra

22、nge of the kth dimension is given by the / kth element of list. For each index i in the index set, insert / into the array.,10/10/2018,19,2.2 Array As Abstract Data Type(Cont),float Retrieve(index i); / if (i is in the index set of the array) return the float / associated with i in the array; else s

23、ignal an error. void Store(index i, float x); / if (i is in the index set of the array) delete any pair of the / form present in the array and insert the new pair / ; else signal an error. ; / end of GeneralArray,ADT 2.1 : Abstract data type GeneralArray,10/10/2018,20,2.3 Polynomial Abstract Data Ty

24、pe,Ordered (or linear) list days of the week : (Sunday, Monday, Tuesday, Wednesday, Thursday, Friday, Saturday) years Switzerland fought in WWII : () Operations on lists (a0, a1, ., an-1) : find the length, n, of the list read the list from left to right (or reverse) retrieve the ith element, 0in st

25、ore a new value into the ith position, 0in insert a new element at the position i, 0in delete the element at position i, 0in,10/10/2018,21,2.3 Polynomial Abstract Data Type(Cont),Polynomial requires ordered lists the largest exponent is called degree sum and product of polynomials A(x) = aixi and B(

26、x) = bixi A(x) + B(x) = (ai + bi)xi A(x) B(x) = (aixi (bjxj),10/10/2018,22,2.3 Polynomial Abstract Data Type(Cont),Class Polynomial / objects : p(x) = a0xe0 + + anxe0 ; a set of ordered pairs of , / where ai Coefficient and ei Exponent/ We assume that Exponent consists of integers 0public: Polynomia

27、l(); / return the polynomial p(x)=0 int operator!(); / If *this is the zero polynomial, return 1; else return 0; Coefficient Coef(Exponent e); / return the coefficient of e in *this Exponent LeadExp(); / return the largest exponent in *this,10/10/2018,23,2.3 Polynomial Abstract Data Type(Cont),Polyn

28、omial Add(Polynomial poly); / return the sum of the polynomials *this and poly Polynomial Mult(Polynomial poly); / return the product of the polynomials *this and polyfloat Eval(float f); / Evaluate the polynomial *this at f and return the result. ; / end of polynomial,ADT 2.2 : Abstract data type P

29、olynomial,10/10/2018,24,2.3 Polynomial Abstract Data Type(Cont),2.3.1 Polynomial Representation Principle unique exponents are arranged in decreasing order,10/10/2018,25,2.3 Polynomial Abstract Data Type(Cont),Representation 1 (Array: static memory allocation) define the private data members of Poly

30、nomialprivate :int degree ; / degreeMaxDegreefloat coefMaxDegree+1 ; for Polynomial object a, nMaxDegreea.degree=na.coefi=an-i, 0in a.coefi is the coefficient of xn-IA(x)=anxn+an-1xn-i+.+a1x+a0leads to a very simple algorithms for many of the operations on polynomials wastes computer memory for exam

31、ple, if a.degree MaxDegree,10/10/2018,26,2.3 Polynomial Abstract Data Type(Cont),Representation 2 (Array: dynamic memory allocation) define coef with size a.degree+1 declare private data membersprivate :int degree ;float *coef ; add a constructor to PolynomialPolynomial:Polynomial(int d) degree=d ;c

32、oef=new floatdegree+1 ; wastes space for sparse polynomials for example, x1000+1,10/10/2018,27,2.3 Polynomial Abstract Data Type(Cont),Representation 3 previously, exponents are represented by array indices now, (non-zero) exponents are stored all Polynomials will be represented in a single array ca

33、lled termArray termArray is shared by all Polynomial objects it is declared as static each element in termArray is of type termclass term friend Polynomial ;private :float coef ; / coefficientint exp ; / exponent ;,10/10/2018,28,2.3 Polynomial Abstract Data Type(Cont),declare private data members of

34、 Polynomial class Polynomial private :static term termArrayMaxTerms;static int free;int Start, Finish;public:Polynomial ADD(Polynomial poly);. required definitions of the static class members outside the class definition term Polynomial:termArrayMaxTerms; int Polynomial:free=0; / next free location

35、in termArray A(x)=2x1000+1, B(x)=x4+10x3+3x2+1,10/10/2018,29,2.3 Polynomial Abstract Data Type(Cont),2,1,1,10,3,1,1000,0,4,3,2,0,0,1,2,3,4,5,6,coef,exp,A.Start,A.Finish,B.Start,B.Finish,Free,Figure 2.1 : Array representation of two polynomials,10/10/2018,30,2.3 Polynomial Abstract Data Type(Cont),A(

36、x) has n nonzero terms A.Finish=A.Start+n-1 if n=0, A.Finish=A.Start-1 comparison with Representation 2 Representation 3 is superior when many zero terms are present as in A(x) when all terms are nonzero, as in B(x), Representation 3 uses about twice as much space as Representation 2,10/10/2018,31,2

37、.3 Polynomial Abstract Data Type(Cont),2.3.2 Polynomial Addition Representation 3 is used C(x)=A(x)+B(x),10/10/2018,32,2.3 Polynomial Abstract Data Type(Cont),Polynomial Polynomial:Add(Polynomial B) / return the sum of A(x) (in *this) and B(x) Polynomial C; int a = Start; int b = B.Start;C.Start = f

38、ree; float c;while (a=Finish) ,10/10/2018,33,2.3 Polynomial Abstract Data Type(Cont),case :NewTerm(termArraya.coef, termArraya.exp);a+; / end of switch and while / add in remaining terms of A(x)for (; a=Finish; a+)NewTerm(termArraya.coef, termArraya.exp);/ add in remaining terms of B(x)for (; b=B.Fi

39、nish; b+)Newterm(termArrayb.coef, termArrayb.exp);C.Finish = free - 1;return C; / end of Add,Program 2.8 : Adding two polynomials,10/10/2018,34,2.3 Polynomial Abstract Data Type(Cont),void Polynomial:NewTerm(float c, int e) / Add a new term to C(x). if (free=MaxTerms) cerr “Too many terms in polynom

40、ials“ endl;exit(1);termArrayfree.coef = c;termArrayfree.exp = e;free+; / end of NewTerm,Program 2.9 : Adding a new term,10/10/2018,35,2.3 Polynomial Abstract Data Type(Cont),Analysis of Add m and n are number of nonzero-terms in A and B, respectively the while loop of line 5 is bounded by m+n-1 the

41、for loops of lines 21 and 24 are bounded by O(n+m) summing up, the asymptotic computing time is O(n+m) Disadvantages of representing polynomials by arrays space must be reused for unused polynomials linked lists in chapter 4 provide a solution,10/10/2018,36,2.4 Sparse Matrices,2.4.1 Introduction Mat

42、rix with m rows and n columns mn (m by n) mn elements when m=n, the matrix is square Storing a matrix two dimensional array Amn an element is Aij sparse matrix store only the nonzero elements,10/10/2018,37,2.4 Sparse Matrices(Cont),Matrix operations Creation Transposition Addition multiplication,(a)

43、 (b),Figure 2.2 : Two matrices,10/10/2018,38,2.4 Sparse Matrices(Cont),Class SparseMatrix / objects : A set of triples, , where row / and column are integers and form a unique combination; value / is also an integer.public:SparseMatrix(int MaxRow, int MaxCol);/ the constructor function creates a Spa

44、rseMatrix/ that can hold up to MaxItems=MaxRow x MaxCol and whose/ maximum row size is MaxRow and whose maximum/ column size is MaxColSparseMatrix Transpose();/ returns the SparseMatrix obtained by interchanging the / row and column value of every triple in *this,10/10/2018,39,2.4 Sparse Matrices(Co

45、nt),SparseMatrix Add(SparseMatrix b); / if the dimensions of a(*this) and b are the same, then / the matrix produced by adding corresponding items, / namely those with identical row and column values is / returned else error.SparseMatrix Multiply(SparseMatrix b);/ if number of columns in a (*this) e

46、quals number of / rows in b then the matrix d produced by multiplying a / by b according to the formula/ dij= (aikbkj),/ where dij is the (i, j)th element, is returned./ k ranges from 0 to the number of columns in a-1/ else error. ;,ADT 2.3 : Abstract data type SparseMatrix,10/10/2018,40,2.4 Sparse

47、Matrices(Cont),2.4.2 Sparse Matrix Representation Representation use the triple to represent an element store the triples by rows for each row, the column indices are in ascending order store the number of rows, columns, and nonzero elements,10/10/2018,41,2.4 Sparse Matrices(Cont),C+ code class Spar

48、seMatrix; / forward declaration class MatrixTerm friend class SparseMatrix private:int row, col, value; ;class SparseMatrix private:int Rows, Cols, Terms;MatrixTerm smArrayMaxTerms;public:SparseMatrix Transpose();.,10/10/2018,42,2.4 Sparse Matrices(Cont),Representation of the matrix of Figure 2.2(b) using smArray,smArray0,0,1,0,2,0,3,1,4,1,5,2,6,4,7,5,row,0,3,5,1,2,3,0,2,col,15,22,-15,11,3,-6,91,28,value,smArray0,0,1,0,2,1,3,2,4,2,5,3,6,3,7,5,row,0,4,1,1,5,0,2,0,col,15,91,11,3,