Microsoft PowerPoint – ECE209_ADT.pptx
7/24/2018
1
ECE 209 Abstract Data Types
1
Abstract Data Types
• Review: data type = values + operations
• User-defined data types
• typedef + functions and/or operators
• struct + functions
• Abstract data type
• Hide implementation details
• Don’t expose struct to “client” code
• Use struct pointer as “handle”
ECE 209 Abstract Data Types
2
Data Type = values + operations
Example: int
Values: integers from INT_MIN to INT_MAX
Operations: + – * / % & | ^ ~ && || ! == <= …
Example: float
Values: real values from DBL_MIN to DBL_MAX
(limited by precision)
Operations: + - * / == <= …
These are “built-in” or “native” types defined by
the C language. Operations are expressed using
operators (and with user-defined functions).
7/24/2018
2
ECE 209 Abstract Data Types
3
User-Defined Data Type
Option 1: rename an existing type
typedef int Item;
Values and operations same as original type.
Doesn’t add any capabilities, but can be easy to
change implementation later – more generic code.
Can be used as shorthand for more complicated
type specification:
typedef struct card * [52] Deck;
ECE 209 Abstract Data Types
4
User-Defined Data Type
Option 2: create new type (struct) with user-
defined attributes (fields)
struct card {
int rank; /* 1 (Ace) to 13 (King) */
char suit; /* C, D, H, S */
};
typedef struct card Card;
Define functions that operate on cards, or access
fields directly:
hand[0].rank = 6;
7/24/2018
3
ECE 209 Abstract Data Types
5
Implementation Details are Exposed
Code that prints a card:
printf("%d%c", myCard.rank, myCard.suit);
What if I change my mind, and want to use
integers (0, 1, 2, 3) to represent suit?
Must find everywhere I used expr.suit and see if
it needs to be changed.
What if I decide to use rank values from 2 to 14
(Ace high)?
Must find everywhere I used expr.rank and see if
it needs to be changed.
ECE 209 Abstract Data Types
6
Abstract Data Type
Create a data type that uses abstraction to hide
the implementation details from the rest of the
code.
We don’t want user of data structure to see the
details. We want to create an “object” that we can
manipulate through a well-defined interface.
The interface should be independent from the
implementation – the details of the data structure.
If the implementation changes, the interface does
not. (So other code that uses the interface does
not need to change.)
7/24/2018
4
ECE 209 Abstract Data Types
7
Abstract Data Type
How do we describe the interface to the rest of the
program?
(1) Use pointer to undefined struct for the type.
(Compiler just knows it’s a pointer – doesn’t know
the size, field names, or field types.)
typedef struct card * Card;
Pointer is a “handle” to the data structure. Can only be used to
refer to the object; can’t directly manipulate the data.
(2) Declare a function for each operation.
int cardRank(Card);
char cardSuit(Card);
ECE 209 Abstract Data Types
8
Interface, Provider, Clients
Interface
typedef struct card * Card;
int cardRank(Card);
char cardSuit(Card);
#include "Card.h"
struct card {
int rank;
int suit;
};
int cardRank(Card c) {
return c->rank;
};
char cardSuit(Card c) {
char s;
int sval = c->suit;
if (sval == 0)
s = ‘C’;
else if (sval == 1)
s = ‘D’;
else if (sval == 2)
s = ‘H’;
else if (sval == 3)
s = ‘S’;
return s;
}
Provider
Included by clients
(other parts of code
that want to use type)
Clients
#include “Card.h”
int main() {
Card deck[52];
…
}
Implementation
(linked with clients)
7/24/2018
5
ECE 209 Abstract Data Types
9
Changing the Implementation
Suppose I decide that using two integers to
represent a card requires too much space. Each
value (rank, suit) is small, so I can squeeze them
into one integer value:
Implementation changes, but client does not.
Rank
(4 bits)
Rank
(4 bits)
Suit
(2 bits)
Suit
(2 bits)
ECE 209 Abstract Data Types
10
Interface, Provider, Clients
Interface
typedef struct card * Card;
int cardRank(Card);
char cardSuit(Card);
#include “Card.h”
struct card {
int sr;
};
int cardRank(Card c) {
return c->sr & 0xF;
};
char cardSuit(Card c) {
char s;
int sval = c->sr >> 4;
if (sval == 0)
s = ‘C’;
else if (sval == 1)
s = ‘D’;
else if (sval == 2)
s = ‘H’;
else if (sval == 3)
s = ‘S’;
return s;
}
Provider
Included by clients
(other parts of code
that want to use type)
Clients
#include “Card.h”
int main() {
Card deck[52];
…
}
Implementation
(linked with clients)
7/24/2018
6
ECE 209 Abstract Data Types
11
Interface, Provider, Clients
Interface
Provider
Client
Client
Client
Client
Clients cannot see details
of implementation.
Can only access data
via interface.
ECE 209 Abstract Data Types
12
FILE * is (almost) an ADT
typdef struct … {
…
} FILE;
int fscanf(FILE*,…);
int fprintf(FILE*,…);
Interface
stdio.h
Standard
C Library
Client
Client
Provider
Clients use FILE*
as a “handle,” not
as a pointer to
a struct.
Never dereferenced.
Clients can see
fields of FILE struct,
but shouldn’t
use them.
7/24/2018
7
ECE 209 Abstract Data Types
13
Example ADT: Complex
/* representation of a complex number */
typedef struct complex * Complex;
/* create/destroy a Complex number */
Complex newComplex(double real,
double imag);
void complexDestroy(Complex);
/* get parts of Complex number */
double complexReal(Complex);
double complexImag(Complex);
/* operations: 3rd argument gets result */
void complexAdd(Complex, Complex, Complex);
void complexMult(Complex, Complex, Complex);
ECE 209 Abstract Data Types
14
Example Client Code:
Complex Vector-Scalar Product
#include “complex.h”
/* v is an array (vector) of complex numbers */
/* result is a new array of complex numbers */
Complex * vsprod(Complex *v, Complex s, int size)
{
int i;
Complex *prod = (Complex *)malloc(size * sizeof(Complex);
for (i=0; i
new->imag = imag;
return new;
}
void complexMult(Complex a, Complex b, Complex c) {
c->real = a->real * b->real – a->imag * b->imag;
c->imag = a->real * b->imag + a->imag * b->real;
}
ECE 209 Abstract Data Types
16
Alternative Provider Code
#include “complex.h”
#include
struct complex { /* use polar coordinates */
double r; /* radius */
double theta; /* angle (radians) */
};
Complex newComplex(double real, double imag) {
Complex new = (Complex)malloc(sizeof (struct complex);
new->r = sqrt(real*real + imag*imag);
new->theta = atan(imag/real);
if (real < 0) new->theta += M_PI;
return new;
}
void complexMult(Complex a, Complex b, Complex c) {
c->r = a->r * b->r;
c->theta = a->theta + b->theta; /* normalize? */
}
7/24/2018
9
ECE 209 Abstract Data Types
17
Alternative #2
#include “complex.h”
#include
struct complex { /* save both representations */
int is_polar; /* keep track of which is valid */
double real; /* Cartesian (rectangular) representation */
double imag;
double r; /* Polar representation */
double theta;
};
Complex newComplex(double real, double imag) {
Complex new = (Complex)malloc(sizeof (struct complex);
new->real = real; new->imag = imag;
new->is_polar = 0;
new->r = 0.0; new->theta = 0.0;
return new;
}
Convert to polar to multiply, convert to rectangular to add…
If application performs mostly one or the other, will get the best performance.
ECE 209 Abstract Data Types
18
Alternative Interface
/* representation of a complex number */
typedef struct complex * Complex;
/* create/destroy a Complex number */
Complex newComplex(double real, double imag);
Complex newComplexPolar(double r, double theta);
void complexDestroy(Complex);
/* get parts of Complex number */
double complexReal(Complex);
double complexImag(Complex);
double complexRadius(Complex);
double complexAngle(Complex);
/* operations: 3rd argument gets result */
void complexAdd(Complex, Complex, Complex);
void complexMult(Complex, Complex, Complex);
NOTE: All three
implementations
can still be used
7/24/2018
10
ECE 209 Abstract Data Types
19
Other Examples
Other common implementation details
that can be hidden using an ADT:
• Collections
• Sorted vs. unsorted
• Dynamic vs. static sizes
• Which operations need to be fast: insert, search, …
• Which of these properties favor an array
implementation? A linked list implementation?
C Primer Plus, Chapter 17, shows several examples of linked list and array
implementations of the same ADT.
ECE 209 Abstract Data Types
20
ADT in C: Summary
Interface
typedef struct card * Card;
int cardRank(Card);
char cardSuit(Card);
#include “Card.h”
struct card {
int rank;
int suit;
};
int cardRank(Card c) {
return c->rank;
};
char cardSuit(Card c) {
char s;
int sval = c->suit;
if (sval == 0)
s = ‘C’;
else if (sval == 1)
s = ‘D’;
else if (sval == 2)
s = ‘H’;
else if (sval == 3)
s = ‘S’;
return s;
}
Provider
Included by clients
(other parts of code
that want to use type)
Clients
#include “Card.h”
int main() {
Card deck[52];
…
}
Implementation
(linked with clients)
Interface header file (.h) declares the
type name declares operations (functions).
Struct pointer is used to hide details.
Struct definition is not exposed to clients.
7/24/2018
11
ECE 209 Abstract Data Types
21
ADT in C: Summary
Interface
typedef struct card * Card;
int cardRank(Card);
char cardSuit(Card);
#include “Card.h”
struct card {
int rank;
int suit;
};
int cardRank(Card c) {
return c->rank;
};
char cardSuit(Card c) {
char s;
int sval = c->suit;
if (sval == 0)
s = ‘C’;
else if (sval == 1)
s = ‘D’;
else if (sval == 2)
s = ‘H’;
else if (sval == 3)
s = ‘S’;
return s;
}
Provider
Included by clients
(other parts of code
that want to use type)
Clients
#include “Card.h”
int main() {
Card deck[52];
…
}
Implementation
(linked with clients)
Client uses type name as “handle.”
Calls interface functions to create
objects, pass them to other functions.
Compiler will prevent any attempt to
dereference the pointer (to access
specific components of struct).
ECE 209 Abstract Data Types
22
ADT in C: Summary
Interface
typedef struct card * Card;
int cardRank(Card);
char cardSuit(Card);
#include “Card.h”
struct card {
int rank;
int suit;
};
int cardRank(Card c) {
return c->rank;
};
char cardSuit(Card c) {
char s;
int sval = c->suit;
if (sval == 0)
s = ‘C’;
else if (sval == 1)
s = ‘D’;
else if (sval == 2)
s = ‘H’;
else if (sval == 3)
s = ‘S’;
return s;
}
Provider
Included by clients
(other parts of code
that want to use type)
Clients
#include “Card.h”
int main() {
Card deck[52];
…
}
Implementation
(linked with clients)
Provider is implementation
source code, which includes
the struct definition and the
implementation for all
functions. Linked at compile
time with client code to create
the program.
7/24/2018
12
ECE 209 Abstract Data Types
23
Class Exercise
Design a Gradebook ADT, to represent the grades
for a single class. Simplify: For this exercise, assume only the final grade.
1. Design the interface.
• What information does the gradebook contain?
• What functions are needed to get data
into and out of the gradebook?
2. Think about the implementation options.
• Linked list? Array?
• What are pros and cons?
• What if you don’t know the class size when the
gradebook is created?