Which of the following are part of an abstract data type specification? (Circle the letter of all that apply.) The specification is the part that is exported, or, equivalently, is the description of what the abstract data type provides.
The following function is supposed to test whether two strings are the same, provided upper and lower case letters are treated as equal. That is, 'a' and 'A' should be considered the same letter. It is supposed to return 1 if the two strings are the same (when case is ignored) and 0 when they are not the same. For example, sameUpper("abc", "ABC") = 1, but sameUpper("abc", "AbD") = 0. This function works by copying each string, replacing lower case letters by upper case letters, and then using library function strcmp to tell whether the resulting strings are the same. (strcmp(s,t) returns 0 if strings s and t are equal, a negative number if s comes before t in alphabetical order, and a positive number if s comes after t in alphabetical order.) The function also uses function toupper, which converts a lower case letter to upper case, and returns all other characters unchanged. So toupper('a') = 'A', toupper('A') = 'A' and toupper(':') = ':'. There is a serious mistake in this function. Explain what the mistake is, and rewrite the function to avoid the mistake. You might need to make more than one change, but try to keep the spirit of the method instead of choosing a completely different method. Make sure the external behavior of the function is correct.
The problem is that no memory is allocated for the copies. The changes are shown in red.
bool sameUpper(char* x, char* y)
{
char *cpyx, *cpyy;
int xlen = strlen(x);
int ylen = strlen(y);
int i;
bool result;
if(xlen != ylen) return 0;
cpyx = new char[xlen];
cpyy = new char[ylen];
for(i = 0; i <= xlen; i++) {
cpyx[i] = toupper(x[i]);
cpyy[i] = toupper(y[i]);
}
if(strcmp(cpyx, cpyy) == 0) result = 1;
else result = 0;
delete[] cpyx;
delete[] cpyy;
return result;
}
Note. A different approach would be to avoid copying the strings, and to write your own loop instead of using strcmp. When comparing single characters, convert characters to upper case.
A rational number can be represented by a pair of integers, the numerator and the denominator. For example, the rational number with numerator 1 and denominator 3 stands for 1/3. The advantage is that some numbers that can only be represented approximately using type double can be represented exactly as ratios of integers.
An abstract data type Rational is intended to represent rational numbers. So a member of type Rational is thought of as having a numerator and a denominator. Among the operations are a constructor that takes two integers (a numerator and a denominator) and initializes a rational number; a function invert where invert(x) changes x into its reciprocal (so it changes a/b into b/a); a function multiplyBy so that multiplyBy(x,y) makes x into the product of x's current value and y, where y is a rational number; a function getNumerator(x) that returns the numerator of x, and a function getDenominator(x) that returns the denominator of x.
Rational numbers are always stored in a form where the numerator and denominator have no common factors. Instead of 3/6, you store 1/2. You cannot assume that somebody who uses this data type knows this convention. There is nothing wrong with creating a rational number with numerator 3 and denominator 6. But if you then ask for the numerator, it will be 1, not 3. This can be achieved by dividing the numerator and denominator by their greatest common divisor. Assume that function gcd(m,n), computing the greatest common denominator of m and n, is available to you. You do not need to write it.
What follows is one solution. There are other correct solutions.
Write the Rational data type in C++, including the constructor and functions invert, multiplyBy, getNumerator and getDenominator. Also write a function called reduce that reduces a rational number by dividing the numerator and denominator by their greatest common divisor. It is a helper for the other functions.
struct Rational
{
int numerator, denominator;
Rational(int n, int d)
{
int g = gcd(n,d);
numerator = n/g;
denominator = d/g;
}
};
void reduce(Rational& x)
{
int g = gcd(x.numerator, x.denominator);
x.numerator = x.numerator / g;
x.denominator = x.denominator / g;
}
void invert(Rational& x)
{
int temp = x.numerator;
x.numerator = x.denominator;
x.denominator = temp;
}
void multiplyBy(Rational& x, const Rational& y)
{
x.numerator = x.numerator * y.numerator;
x.denominator = x.denominator * y.denominator;
reduce(x);
}
int getNumerator(const Rational& x)
{
return x.numerator;
}
int getDenominator(const Rational& x)
{
return x.denominator;
}
Write a main program that creates rational numbers 1/3 and 3/7, calculates the product of those two numbers, and prints the product in the form numerator/denominator. (So it will print "1/7".)
int main()
{
Rational a(1,3);
Rational b(3,7);
multiplyBy(a,b);
printf("%i/%i\n", getNumerator(a), getDenominator(a));
}
Note: Instead of getNumerator(a), you could write a.numerator, and instead of getDenominator(a), you could write a.denominator.