Data Structures and Algorithms in C++, Drozdek - Downloadable Solutions Manual (Revised)

Chapter 1

OBJECT-ORIENTED
PROGRAMMING USING C++

1. The following assignments are illegal:
(b) p = *&i; // cannot convert int to int*
(c) p = &*i; // invalid indirection (i is not a pointer)
(e) i = *&p; // cannot convert int* to int
(f) i = &*p; // cannot convert int* to int
(h) q = *&*p; // cannot convert int to int*
(i) q = **&p; // cannot convert int to int*

2. (a) Function f() returns the reference to a local variable; upon exit, the variable is destroyed, so that
the returned reference refers to a non-existing variable.
(b) Before copying s2 to s1, enough room has to be allocated to accommodate the contents of s1, as
in
char *s1 = new char[strlen(s2)+1];
strcpy(s1,s2);
(c) When allocating room for the contents of s2, one more character has to be allocated for the
end-of-string character.

3. Assuming that these declarations have been made:

int intArray[] = {1, 2, 3}, *p = intArray;

then
(a) *p++; returns 1 and then increments pointer p; intArray remains unchanged.
(b) (*p)++; returns 1 and then increments 1 in the first cell to 2, so that intArray becomes [2 2 3].
(c) Statements *p++; (*p)++; cause 1 to be returned, pointer p to be incremented so that the second
statement returns 2 and then increments it to 3; intArray becomes [1 3 3].

4. (a) // A function to add all numbers in an integer array;
int sumIntegerArray(int *intArray, int size) {
int *last = intArray + size, sum;
for (sum = 0; intArray < last; intArray++)
sum += *intArray;
return sum;
}



1

, (b) // [2 4 5 7 8 9 10] ==> [2 4 8 10 10 10 10]
int removeOddNumbers1(int *intArray, int size) {
int *localArray = new int[sizeof(int) * size], i, j, last;
for (i = j = 0; i < size; i++)
if (*(intArray + i) % 2 == 0) // copy even numbers to localArray;
*(localArray + j++) = *(intArray + i);
for (i = 0; i < j; i++) // copy even numbers from localArray
*(intArray + i) = *(localArray + i); // back to intArray and
for (last = *(intArray+i-1); i < size; i++) // pad the ending places
*(intArray + i) = last; // with the largest even number of intArray;
return j; // return number of even numbers without the trailing ones;
}
In the case of an unordered array, in one pass through the array, cluster all even numbers at the
beginning of the array by using two pointers, to scan the array forward and backward. After the
forward pointer finds an odd number and the backward pointer locates an even number a swap
occurs. The process stop after forward pointer crosses the backward pointer. Then, return an
integer indicating how many even numbers there are in the array.
5. (a) int Strlen(char *s) {
char *tmp = s;
while (*s++ != ’\0’);
return s - tmp - 1;
}
(b) int Strcmp(char *s1, char *s2) {
for ( ; *s1 != ’\0’ && *s1 == *s2; s1++, s2++);
return *s1 - *s2;
}
(c) char* Strcat(char *s1, char *s2) {
char *s = s1 + strlen(s1);
while (*s++ = *s2++);
return s1;
}
(d) char* Strchr(char *s, char ch) {
for ( ; *s != ch && *s != ’\0’; s++);
return *s == ch ? s : 0;
}
6. In the condition (p == q), values of pointers are compared to check whether they point to the same
location, in the condition (*p == *q), contents of locations pointed to by the two pointers are com-
pared.

7. All macros are handled by a preprocessor and inserted in programs with no consideration of types and
context, unlike templates which are compiled. Also, templates are a natural generalization of classes,
which is lost when macros are used.
8. Function and data members declared private in a class C are accessible only to other members of
C and to functions declared by C as friends. Function and data members declared protected are
accessible to any class derived from C and to friend functions. Function and data members declared
public can be accessed by any function.

9. It is illegal to specify a return type for constructors and destructors, even if it is to be void.
10. Providing that the following declaration has been made:

template<class T>


2

, class genClass {
...
char aFunction(...);
... };

the definition

char genClass::aFunction(...) { ... }

is improper, since the class is not genClass but genClass<T>. Also, since aFunction by being a part
of a generic class becomes itself generic, it requires a template as well, hence its declaration should be

template<class T>
char genClass<T>::aFunction(...) { ... }

11. The following operators cannot be overloaded: 1. class member, ., 2. class member dereference, .*,
conditional, ?:, scope resolution, ::, and sizeof.
12. For any of the three derivation modes, a private variable remains private to the base class and as
such invisible in derived classes, hence n cannot be used in classB. In public derivation, each public
and protected variable retains its status, e.g., public variable in classA remains public in classB.
In protected derivation, both public and protected variables of base class are protected in derived
class. In private derivation, both public and protected variables of base class are private in derived
class. However, the status of some variables can be adjusted to the status this variable has in the base
class. For example, in private derivation, the protected variable m can remain such if listed in the
protected section as classA::m, and the public variable k can be redeclared as public (but not as
protected).
13. A new declaration of genClass is:

template<class T>
class genClass2 {
T *storage;
..................
int size;
void memberFun() {
............
if (someVar < size) { ...... }
............
}
public:
genClass2(int n = 50) { storage = new T[size = n]; ... }
};

and then declarations of objects is:

genClass2<int> intObject1(); // use the default size;
genClass2<int> intObject2(25);

If size is a parameter to template, storage allocation is static, if it is a parameter of a stack
constructor, the allocation is dynamic. Therefore, for someFun() declared as

int someFun(int size, ... ) {
genClass<int,size> ob1;
genClass2<int> ob2(size);
......................
}


3

, the first declaration is impossible, since genClass<int,size> requires size to be a constant, not a
variable, which is permissible in the case of genClass<int>.
14. For virtual functions, the system decides at run-time which function should be invoked, whereas
in the case of nonvirtual function members this decision is made at compile time. The difference
between virtual and nonvirtual means the difference between run time binding and compile time
binding.

15. If declarations:

class genClass {
..................
virtual void process1(char);
virtual void process2(char);
};
...............
class derivedClass : public genClass {
..................
void process1(int);
int process2(char);
};
...............
genClass *objectPtr1 = &derivedClass, *objectPtr2 = &derivedClass;

are followed by these statements:

objectPtr1->process1(1000);
objectPtr2->process2(’A’);

then since process1() is declared in derivedClass as a function with an integer parameter, it hides the
declaration of process1() in genClass, hence, genClass::process1() and derivedClass::process1()
are two different member functions. In this situation, the function genClass::process1() is invoked
by the statement objectPtr1->process1(1000);, since objectPtr1 is of type genClass*, number
1000 is converted into a character type, which means that it is truncated. On the other hand, the dec-
laration of process2() in derivedClass changes return type of virtual function process2() defined
in genClass, which causes a compile time error.




4