CMP 507 Homework #6
1. Give a C++ example to show how to use class derivation, inheritance and customization.
class TShape{
public:
void SetEnclosingRect (int x1, int y1,int x2, int y2);
virtual void Draw( );
void Move(int deltaX, int deltaY);
protected:
Rect EnclosingRectangle;
};
class TRectangle: public TShape{
public: void Draw( );
};
class TOval: public TShape{
public: void Draw( );
};
class TRoudedRectangle: public TShape{
public: void Draw( );
};.
//…………………………//
As above, TShape, base class (abstract case), defines a class of objects, having three derived subclasses: class
TrRectangle, class TOval, class TRoudedRectangle. Three derived subclasses are said to inherit the data and
functions of the base class TShape; Each of the three is defined to have its own local Draw method (void Draw(
)), which supplies a local customized meaning for the virtual Draw method declared in the base class TShape.
2. Give a C++ example to show how to use object pointers and how to send a message to each of a collection of
objects dynamically.
#include
#include
#include “Shapes.h”
Boolean UserDesignatesShape(TShape **theShape)
{
char *reply=” “;
int ReplyLength;
while (1){
printf(“Designate one of: Q=Quit, O=Oval, R=Rectangle,\n);
gets (reply);
if ((reply[0]==’Q’)||(reply[0]==’q’)
return false;
else
switch (reply[0]){
case ‘O’:case ‘o’:*theShape=new TOval;
return true;
case ‘R’: case ‘r’: if (strlen(reply)==1){
*theShape=new Trectangle;
}else
*theShape=new TRoundedRectangle;
return true;
default: *theShape=NULL;
return true;
}
}
void main()
{
TShape *theShape;
short x1, y1, x2, y2;
SetUpWindows( );
DrawCoordinateSystem( );
while (UserDesignatesShape(&theShape)) {
if (theShape==NULL)
prints(“unknown shape\n”);
else {
printf(“Give Coordinates of Enclosing Rectangle; \n);
printf(“left top right bottom:”);
scanf(“%hd%hd%hd%hd”,&x1,&y1,&x2,&y2);
theShape->SetEnclosingRect(x1,y1,x2,y2);
theShape->Draw();
}
}
} // end of main
In the function, UserDesignatesShape, the Shape is a variable of type Tshape (pointer). Line 13 allocates new
object in the heap and returns a pointer to the object; in main program, this pointer is also used in line 21 line 25:
and 35 in the while-loop. That means, this pointer belongs to not only Tshape, but also its derived subclasses. In
line 32, the shape-> SetEnclosingRect (x1,y1,x2,y2); sends the message SetEnclosingRect (x1,y1,x2,y2); sends
the message SetEnclosingRect (x1,y1,x2,y2) to the object TOval, since TOval is the subclass of Tshape and is
inherited from the base class Tshape, and the SetEnclosingRect method of Tshape is excuted, this causes the
instance variable EnclosingRectangle of the Toval to be set to the coordinates (x1,y1,x2,y2) passed in the
message SetEnclosingRect (x1,y1,x2,y2). Then, the specific action of the Draw method (in line 33) is determined
dynamically at running-time, depending on the subtype of the object receiving the Draw message.
3. Describe how the OOP can help make the reusable software components easier to use.
Object Oriented Programming provides another set of concepts for modular programming that differs slightly
from the modular programming concepts used before. A module is that of a section of text inside a bigger
program which has its own internal data structure and functions and exports a carefully defined set of function
and data through is interface, while keeping its other internal mechanics hidden.
Class libraries can furnish useful reusable software components, such as objects that allow you to generate
complete file and printing systems. To use these library objects, you define individual methods that customize
the virtual (or blank fill-in) methods in the library objects in order to establish the necessary connections with the
rest of your system.
4. Distinguish among the public, private and friend data members of class and give an example.
Public data members are visible to (and can be used by) users external to the class; private members are visible
only within the class or their friends, but cannot be used externally; Friend data members are visible to (and can
be used by ) the users in subclasses derived from the base class. For instance:
Class TShape{
public:
void SetEnclosingRect (int x1, inty1, int x2, int y2);
virtual void Draw();
protected: //friend data members of class
Rect EnclosingRectangle;
private: //private data members of class
TShape *shape;
Tlist *link;
}
5. Describe the advantages and disadvantages of OOP techniques.
Advantages:
Providing a clear modular software structure at a level of organization finer than that of C module;
Providing a framework in which reusable software components can be expressed and can be conveniently
used;
Providing for ease of maintenance and modification of a program by permitting a style of programming in
which new objects and new behaviors can be introduced merely by expressing the differences they exhibit
when compare to existing objects;
Providing convenient avenues for natural growth of a system via the introduction of new derived classes of
customized objects that nonetheless share inherited common behaviors which other similar classes of
objects;
Providing for fast, easy definition of graphical user interfaces to a system.
Disadvantages:
There is some memory storage or time penalties in running time that influences the efficiency by using OOP
techniques.
6. Why JAVA is considered to be better than C++?
JAVA uses interpreter to execute program, so it is easier to use and flexible. Almost all programs can be called
by JAVA without compiled beforehand. It is object-oriented programming and has universal code, intermediate
level code and has the world wide web.
7. What is a design walkthrough and what role does it play in the software life cycle?
A design walk through is to go over the design with a fine-toothed comb to attempt to catch errors and problems
early in the life cycle before investing in costly implementations that will be thrown away. A design walk
through is a very useful practice after finishing a design It acts just like the pre-testing and pre-checking before a
implementation is actual performed after the design.
8. Describe the Boehm's COCOMO model software productivity ranges.
The software productivity ranges for the various attributes are ratios between the highest and lowest measures on
the COCOMO rating scales for each of the attributes.
9. Explain the characteristics of the Code-and-Fix model, the Waterfall Model, the Evolutionary Development
Model, and the Spiral Model.
The Code-and-Fix model is a code-driven process in which you repeatedly write some code and fix it, until a
satisfactory system is produced.
The Waterfall Model tends to be a document-driver process in which, often under contract, a software
development organization must produce a requirements document, a specification document, a design document,
a system code document, and various users manuals and system maintenance manuals. It incorporates validation
activities such as design walk through, unit testing, integration testing and acceptance testing.
The Evolutionary Development Model whose each of prototypes is modified by assessing its defects using a risk-
identification strategy and which is improved using a suitable risk-resolution strategy. The last completely
evolved prototype in the sequence of prototypes becomes the final system that is released to use.
The Spiral Model uses a risk-management-driven process, built upon the notation of using multiple passes (or
cycles of a spiral), each of which incorporates risk analysis, risk-item prioritization and risk-item resolution. The
Spiral Model can specialize any given cycle of the spiral to be have like one of the other software process
models.
10. In what sense can prototyping activities or simulation activities used in the Evolutionary Development Model
considered as risk-resolution strategies?
Prototyping activities used in the Evolutionary Development Model can be considered as risk-resolution strategy
by trial use that reveals aspects of the user interface problem and by end users who suggest how to change and
install the program.
11. Why are stacks useful for processing nested structures?
Stacks are sequences of items that are allowed to grow and shrink only at top, and stacks have the property of
LIFO (last in first out); a nested structure is one that can contain instances of itself embedded within itself. For
example, algebraic expressions can be nested because a sub-expression of an algebraic expression can be another
algebraic expression. Other examples of nested structures are levels of outlines for term paper, function calls
containing other function call as arguments and nested sets, which containing other set as elements. Stacks are
useful for processing nested structures. When processes encounter (call) sub-processes, stacks are natural to
perform first sub-process, then continue to finish main process.
12. What can push-down automata accomplish according to the theory of formal languages?
Because push-down automata serve as the recognizers for context-free languages, as a consequence, syntax
analyzers for programming languages often employ push-down stacks to accomplish recognition of the structure
of computer programs during compilation.
13. How can you be sure that you have used proper modular programming practices when defining and using an
ADT?
When defining and using an ADT, we need write two parts of a c module: interface file c prototype of function
etc. and implementation file. These two parts declare clearly the whole entities of an ADT.
14. What property of program 7.5 guarantees that separately defined linked and sequential representations of the
stack ADT can be used interchangeably, and thus the property of "substitutability of representations" will be
achievable?
The “last-in, first-out” property of stacks can satisfy the requirements above. That is, pushing and popping keep
track of matching pairs.
15. Why is a stack useful for evaluating postfix expression? Would a queue work just as well?
Because a stack has a property of “ LIFO”, it is convenient to use stacks to evaluate postfix expressions. Since
evaluating a postfix expression, you scan from left-to-right, encounter first two operands and push them
respectively onto a stack; when encounter an operator ?, pop the topmost operand (the second) on the stack to a
variable R, then pop another one (the first) to a variable L, perform (L ? R). We do not change at all the order of
the expression by using stacks. Under this meaning, we do understand that a queue does not work just as well as
stacks for evaluating postfix expression.
15. When would it be advantageous to use a sequential array list representation instead of a linked list
representation?
When space efficiency is the principal design constraint that needs to be met, it would be advantageous to use a sequential
array list representation instead of a linked list representation.
17. What flexibility and generality do typeless list processing languages provide that is difficult to achieve in hard-
typed languages such as C?
The typeless list processing language such as lisp language compared to C language has more flexibility and
generality which can perform all kinds of ADT no matter what kind of types they have. In short, lisp does not
need define ADT.
18. Write a C function to implement the string operation strstr(S,T) described in figure 8.15
char *Concat(char *S, char *T);
{
if (S[0]+T[0]<=strlen) {
p[1..S[0]]= S[1..S[0]];
p[S[0]+1..S[0]+T[0]]=T[1..T[0]];
p[0]=S[0]+T[0];strpbrk=0;
}
else if (S[0]S[0] || len<0 || len>S[0]-pos+1)
return error;
T[1..len]=S[pos..pos+len-1];
T[0]=len;
return ok;
}
19. What is a heap ? How is it used to support dynamic memory allocation?
A heap is a zone of memory organized to support dynamic memory allocation of blocks of storage of deferring
sizes. When we execute a statement L=(GenListNode *) malloc (sizeof(GenListNode)); we can use a separate
region of memory to guarantee the persistence of the storage for made L, dynamic memory allocation can then
take place using blocks allocated from this region any time during the running of a program.
20. Write a C++ program to: (a) create a binary tree with 10 integers. (b) delete an integer Ron the binary tree. (c)
to display the binary tree.
/*…….…….*/
#define MAXCOUNT 10
typedef int PQitem;
typedef PQitem PQArray [MAXCOUNY+1];
typedef struct{
int COUNT;
PQArray ItemArray;
} PriorityQueue;
/*--------------------*/
#include “PQTypes.h”
extern void Initialize(PriorityQueue *PQ);
extern int Creat(PriorityQueue *PQ);
extern int Empty(PriorityQueue *PQ);
extern int Full(PriorityQueue *PQ);
extern PQitem Delete(PriorityQueue *PQ);
extern PQitem Display(PriorityQueue *PQ);
/* ---------------------*/
//-----------------------
#include “PQInterface.h”
//---------------- initialize PQ----------------------
void initialize (PriorityQueue *PQ)
{
PQ->count=0;
}
//----------------Empty-----------------------------
int Empty (PriorityQueue *PQ)
{
return (PQ->count==0);
}
//--------------- Create-------------------
void Create (PriorityQueue *PQ)
{
int childloc;
int parentloc;
while (PQitem !=NULL)
{
printf (“ten integers: %d%d\n”,count, ItemArray);
scanf (“ten integers: %d%d\n”,count, ItemArray);
childloc=PQ->count;
parentloc=childloc/2;
}
PQ->count +;
}
//------------------- Delete---------------------
{
int current loc;
int childloc;
PQitemToPplace;
PQitem to return;
while (childloc<=PQ->count)
if ((childloccount)&&(PQ->ItemArray[childloc+1]>PQ->ItemArray[childloc]))
childloc ++;
if (PQ->ItemArray[currentloc]<=ItemToPlace){
PQ->ItemArray[currentloc]=ItemToPlace;
return;
}
else{
(PQ->ItemArray[currentloc]= PQ->ItemArray[childloc]);
currentloc=childloc;
childloc=2*currentloc;
}
}
//-------------------- Display-----------------------
PQitem Display(PriorityQueue *PQ)
{
int i;
printf (“ten integers \n”);
for (I=0;ICount == MAXCOUNT);
}
2
1