ADT Example
Example: Fractions
A fraction consists of a numerator and denominator and is
used when discussing parts of a whole.
Example: The fraction 1/2 means that
if an object is divided into two equal parts, then we are working with one
of those parts.
The 1 is known as the numerator and the 2 is known as the
denominator. Both the numerator and denominator of a fraction are integers.
The denominator cannot be 0.
When working with fractions, we are sometimes interested in a whole number
as well, as in 5/4 = 1 1/4. Numbers expressed as fractions can have a whole
number part as well as a fractional part.
The operations on fractions include :
- addition
- subtraction
- multiplication
- division
- reduce to lowest terms
- find least common denominator
- etc.
Since we have just defined a mathematical object (the fraction) and the
operations on that object, we can say that a fraction
is an abstract data type.
Example implementation of a fraction:
A fraction could be a structure that has three members, all of type int.
One member would be the whole number part and the other members would be
the numerator and the denominator.
Fractions have many operations on them, which could all be written as
functions. Standard practice is to write an interface (the .h file)
called fraction.h that contains both the definition of the fraction
structure and prototypes for all of the functions (the operations
on fractions) with detailed explanations of the functions.
<![CDATA[
/************************************************\
* Filename: frac1.h *
* Author: Sue Bogar *
* Date Written: 4/14/98 *
* Modified: 11/20/05 *
* Section: 101 *
* EMail: bogar@cs.umbc.edu *
* *
* Description: *
* This header file contains the structure *
* definition for a fraction type called FRACTION *
* and the function prototypes for the functions *
* defined in frac1.c, the implementation of the *
* ADT fraction. This example is NOT meant to be *
* a good example of an interface since it *
* doesn't have any of the descriptions of the *
* type FRACTION or of the functions. *
\************************************************/
typedef struct fraction
{
int whole;
int numerator;
int denominator;
} FRACTION;
typedef FRACTION* FRACTPTR;
void AddFractions (FRACTPTR fPtr1, FRACTPTR fPtr2, FRACTPTR sumPtr);
void SubFractions (FRACTPTR fPtr1, FRACTPTR fPtr2, FRACTPTR differencePtr);
void MultFractions (FRACTPTR fPtr1, FRACTPTR fPtr2, FRACTPTR productPtr);
void DivFractions (FRACTPTR fPtr1, FRACTPTR fPtr2, FRACTPTR quotientPtr);
void RedToLowTerms (FRACTPTR fPtr);
.
.
.
]]>
Alternative implementation of a fraction:
A fraction could be an array of ints that always had three elements,
where the whole number part would always be stored at FRACTION[0],
the numerator would be held in FRACTION[1], and the denominator in
FRACTION[2].
Fractions have many operations on them, which could all be written as
functions. Standard practice is to write an interface (the .h file)
called fraction.h that contains both the definition of the fraction
and prototypes for all of the functions (the operations on fractions) with
detailed explanations of the functions.
<![CDATA[
/**************************************************\
* Filename: frac2.h *
* Author: Sue Bogar *
* Date Written: 4/14/98 *
* Modified: 11/20/05 *
* Section: 101 *
* EMail: bogar@cs.umbc.edu *
* *
* Description: This header file contains the *
* typedef of a FRACTION type, using an array of *
* ints and the function prototypes for the *
* functions defined in frac2.c, the implementation *
* of the ADT fraction. This example is NOT meant *
* to be a good example of an interface since it *
* doesn't have any descriptions of the type *
* FRACTION or of the functions. *
\**************************************************/
#define SIZE 3
typedef int FRACTION [SIZE];
void AddFractions (FRACTION f1, FRACTION f2, FRACTION sum);
void SubFractions (FRACTION f1, FRACTION f2, FRACTION difference);
void MultFractions (FRACTION f1, FRACTION f2, FRACTION product);
void DivFractions (FRACTION f1, FRACTION f2, FRACTION quotient);
void RedToLowTerms (FRACTION f1);
.
.
.
]]>
Differences in Implemetation
The functions that are operations on fractions should have the same names
in either implementation. The functions may (or may not) take different
types of arguments, but they will do the same things even though the code in
each function will be significantly different from its counterpart using the
other implementation.
Typically, abstract data types are somewhat complicated as are most things
in life. Until we covered structures, we were unable to envision ways of
handling most abstract data types. Although some abstract data types can be
implemented with arrays, most are implemented with structures. Obviously,
the more complex the ADT, the more complex the structure becomes.
<![CDATA[
]]>