Department of Computer and Information Science,
School of Science, IUPUI
Fraction Abstract Data Type
Dale Roberts, Lecturer
Computer Science, IUPUI
E-mail: [email protected]
Dale Roberts
Abstract Data Type Example
An Abstract Data Type is a data type that is
defined by the programmer, not the language.
Like any data type, it is a set of values with
operations that act on those values.
Working with ADTs involves three different
1. The public interface, or specification, defines
the ADT and how it is used.
2. The implementation, implements the ADT in
3. The client uses the ADT to perform a task.
Dale Roberts
Defining an ADT
Within C++, you define an ADTs public interface
with a header file.
#include “fraction.h”
Fraction x, y;
User-defined ADTs are typically
capitalized to distinguish them from
intrinsic data types.
Dale Roberts
ADT Operations
Several classes of operations are required in order to
effectively used ADT.
Constructors – used to create instances of the data
Destructors – used to destroy an instance of the data
Accessors – used to access attributes of the data type.
(Such as “get” functions)
Modifiers – used to modify attributes of the data type.
(Such as “set” functions)
Object-oriented languages provide some of this functionality within the
language. In C you must do it yourself.
Dale Roberts
Fraction ADT Specification
The specification for the Fraction ADT requires
a discussion of what operations are required.
Fraction() creates a new variable of type Fraction
with the default value of 0/1.
Fraction(int n, int d) creates a new variable of
type Fraction with the default value of n/d.
Note that you need to handle all combinations of
positive and negative for n and d in order to
determine the sign of the fraction.
Dale Roberts
Fraction ADT (Cont)
~Fraction() – frees Fraction variable.
Fraction g = f; – creates a new Fraction g, whose values
are copied from f. C++ provides a default copy
constructor, or you may write your own: Fraction(const
Fraction &)
You don’t need to provide you own
copy constructor if you don’t use
i = f.getNumerator();
i = f.getDenominator();
c = f.getSign();
Dale Roberts
Fraction ADT (cont)
f.reduceFract() – reduces a fraction to lowest
terms. Notice that this is a modifier, and cannot
be used in an expression.
Dale Roberts
Fraction ADT Operations
These Operations are designed to be used in an
expression. They never modify their arguments. They
always return type Fraction.
f = Fraction::negateFract(f) // returns -f
s = Fraction::addFract(f1,f2) // returns f1 + f2
d = Fraction::subFract(f1,f2) // returns f1 – f2
p = Fraction::mulFract(f1,f2) // returns f1 * f2
q = Fraction::divFract(f1,f2) // returns f1 / f2
i = Fraction::compareFract(f1,f2)
// f1 < f2 returns -1,
// f1 = f2 returns 0,
// f1 > f2 returns 1
Dale Roberts
Fraction ADT I/O
Fraction Fraction::getFract(istream, f) – return 1 if
OK, 0 if invalid, EOF if end of file.
int Fraction::putFract(ostream, f) – writes out
fractions with correct sign, does not print
denominator if 1
Dale Roberts
While we’ve defined an ADT interface, we can’t
just start coding quite yet. There are more
design decisions to be made before writing
code for the implementation.
A common error among programmers is to not
place enough emphasis on the design step.
This is the difference between a “programmer”
and an “analyst”.
Dale Roberts
Fraction ADT Design: Data
Data-centric analysis begins with the idea that all the operations will be acting
on Fractions that have some internal representation. The representation
shall be shared among all the operations.
Each operation is responsible for maintaining your design rules regarding the
representation of Fraction information.
typedef enum{ POS, NEG } SignType;
class Fraction {
// data members
int numerator;
/* numerator and denominator are declared as */
int denominator; /* int to simplify the algorithms, but they */
SignType sign;
/* will always be stored >= 0
// member functions would follow
// utility functions would follow
All operations must preserve these rules.
Dale Roberts
Fraction ADT Variables
Now that we’ve decided how to represent the
value of a fraction, how are we going to declare
variables whose values are fractions?
Fraction f1, f2;
Dale Roberts
Fraction ADT Algorithms
You are responsible for designing algorithms
that implement all the operations. What process
must you follow to implement the operations?
ad + bc
Sum:  +  =
 * = 
then, reduce
then, reduce
Subtraction involves adding the opposite, and
Division involves multiplying by the reciprocal.
Dale Roberts
Fraction ADT Algorithms
Reducing a fraction involves finding the Greatest
Common Divisor, and then dividing all the terms by that
Euclid’s Algorithm:
if x < y, then swap x and y
While y is not zero
remainder = x mod y
y = remainder
When you’re done, x is the GCD.
Dale Roberts
Fraction ADT Design Issues
There are three special situations that require special
Negative fraction have sign = NEG. However,
arithmetic expects the sign to be in the numerator.
We’ll need to move back and forth between
“arithmetic” representation of the sign and “standard”.
2. Fractions may not have zero in the denominator.
Dividing by zero is not allowed, even though 0/1 is
3. Different values of zero will not reduce using
reduceFract(). Special coding is required to reduce 0/5
to 0/1.
Dale Roberts
ADT Specification
In C++, the ADT Specification resides in a
header file, names like fraction.h.
/******** Constructors, Destructors, and Clone **********/
Fraction Fraction(); /* returns 0/1 */
Fraction Fraction( int n, int d ); /* returns n/d */
// void ~Fraction( Fraction f ); Implementation not needed
// Fraction(const Fraction &); Implementation not needed
Dale Roberts
/*********** Accessors **************/
int getNumerator();
int getDenominator();
char getSign();
Dale Roberts
/********** Modifiers ***********/
void setNumerator(int);
void setDenominator(int);
void setSign(char);
void reduceFract();
Dale Roberts
/******** Fraction Operations **********/
static Fraction negateFract( const Fraction &f1);
static Fraction addFract(
const Fraction &f1, const Fraction &f2 );
static Fraction subFract(
const Fraction &f1, const Fraction &f2 );
static Fraction mulFract(
const Fraction &f1, const Fraction &f2 );
static Fraction divFract(
const Fraction &f1, const Fraction &f2 );
static int compareFract(
const Fraction &f1, const Fraction &f2 );
/* returns -1 if f1 < f2
0 if f1 == f2
+1 if f1 > f2
Dale Roberts
/******************* I/O ********************/
static int getFract(
istream &infile, Fraction &f);
/* returns 1 if a valid fraction is read
0 if an invalid fraction is read
EOF if end of file is detected
static void putFract(
ostream &outfile, const Fraction &f );
Dale Roberts
Allowing for multiple #includes
#ifndef FRACTION_H
#define FRACTION_H
#include <iostream>
#include "boolean.h"
Dale Roberts
Sample Client - Declarations
#include <iostream>
#include "fraction.h"
#include "boolean.h"
using std::cout;
using std::endl;
int main()
Fraction f, g, half(1,2), sum, diff, prod,
quotient, neg, answer;
Boolean done = FALSE;
int readResult, cmpResult;
... code would follow
Dale Roberts
Sample Client – Creating Fractions
cout << "Enter your first fraction > ";
readResult = Fraction::getFract( cin, f );
if (readResult == 0 )
cout << "Error entering fraction" << endl;
else if ( f.getNumerator() == 9999 )
done = TRUE;
cout << "Enter another fraction > ";
readResult = Fraction::getFract(cin, g);
if ( readResult == 0 )
cout << "Error enterering fraction" << endl;
// Perform Calculations
Dale Roberts
Sample Client – Manipulating Fractions
// Perform Calculations
neg = Fraction::negateFract(f);
sum = Fraction::addFract(f,g);
diff = Fraction::subFract(f,g);
prod = Fraction::mulFract(f,g);
quotient = Fraction::divFract(f,g);
cmpResult = Fraction::compareFract( f, g );
/* (f + g) - ( f * -(1/2) ) */
answer = Fraction::subFract(
Fraction::addFract( f,g ),
Dale Roberts
Sample Client – Displaying Output
/* Display output */
cout << endl;
cout << "F1 = "; Fraction::putFract(cout, f); cout << endl;
cout << "F2 = "; Fraction::putFract(cout, g); cout << endl;
cout << "Neg = "; Fraction::putFract(cout,neg); cout << endl;
cout << "Sum = "; Fraction::putFract(cout,sum);
cout << " Diff = "; Fraction::putFract(cout,diff);
cout << " Prod = "; Fraction::putFract(cout,prod);
cout << " Quot = "; Fraction::putFract(cout,quotient); cout << endl;
if ( cmpResult == 0 )
cout << "equal" << endl;
else if (cmpResult < 0 )
cout << "less" << endl;
cout << "Greater" << endl;
cout << "Try one nested: " << endl;
out << "(f + g) - ( f * -(1/2) ) = ";
Fraction::putFract(cout,answer); cout << endl;
cout << "==========================================" << endl;
Dale Roberts
Sample Client – Clean Up
Unlike C, there is no requirement for cleanup
when dealing with the Fractions.
When Fractions go out of scope, they are
automatically destroyed. There is no need to
create and call a freeFract() function.
Creating a Fraction does not require explicit use
of a pointer or malloc(). You create a Fraction
on the stack simply by declaring a Fraction
variable. Using “new” to allocate a fraction on
the heap is not required.
int function(int x, y)
Fraction function(Fraction x, y)
int z;
Fraction z;
z = x+y;
z = fraction::addfract(x,y);
return z;
return z;
} // return is pass-by-value (copy)
} // return is pass-by-value (copy)
Dale Roberts
Sample Execution
To enter a fraction enter two integers separated by one space.
To indicate end of data enter 9999 for the numerator
of the first fraction. Use any denominator.
Enter your first fraction > 5 6
Enter another fraction > 3 4
F1 = 5/6
F2 = 3/4
Neg = -5/6
Sum = 19/12 Diff = 1/12 Prod = 5/8
Try one nested:
(f + g) - ( f * -(1/2) ) = 2
Quot = 10/9
Dale Roberts
The specification for this Fraction ADT comes
from Fecteau & Kirchherr.
The implementation is my own.
Dale Roberts

Fraction ADT in C++