Transcript data member

Data Abstraction: The Walls
• Abstract Data Types (ADT)
• Specifying ADTs
– The ADT List
– The ADT Sorted List
– Designing an ADT
• Implementation of ADTs
– C++ classes
– Array based implementation of ADT List.
COP3530 Data Structures
300
Abstract Data Type
• A moduler program is easier to read, write,
and modify.
• Focus on “what” a module does. Not “how”
• Build loosely coupled functions.
• Functional Abstraction.
• Information Hiding. What to hide?
• Not only hide, but make it inaccessible.
• Hide implementation details from others.
COP3530 Data Structures
301
Walls
•
•
•
•
Imagine a wall separating task Q and T.
The user task Q needs to know what T does.
Q need not know how T does it.
Wall prevents Q’s method of solution to
depend on the task T’s method of solution.
• If T changes the implementation, Q does not
have to be changed.
• If T’s specification changes, Q needs to
change.
COP3530 Data Structures
302
Walls (contd)
Task T
Task Q
First
Implementation
Client of T
Task T
Second
Implementation
COP3530 Data Structures
303
ADT Operations
Program
Request op
that uses
function S
Implementation
of
Result of Op
COP3530 Data Structures
function S
304
What is ADT?
• Solution to problems often require
operations on data.
• Broad categories of operations:
– Add data to a data collection
– Remove data from a data collection
– Make a query about the data collection
• Details vary from application to application.
• Not all problems require all types of
operations.
COP3530 Data Structures
305
What is ADT? (contd)
• Data Abstraction
– “What” opeations you can do with data.
– Not “how” to do them.
• ADT = Collection of Data + Operations
• Often, the data collection needs to maintain
certain integrity constraints.
• Data Structures are useful to implement
ADTs.
COP3530 Data Structures
306
Data Structures
• Data structures are constructs that you can
define in a programming language.
• Arrays, Structures are data structures.
• You can combine basic data structures to
make more complex data structures.
• Data Structures are part of ADT
implementation.
• You should also focus on efficiency of
operations when choosing data structures.
COP3530 Data Structures
307
Data Structure: An example.
• Suppose you want to store both names and
salaries of a group of employees.
const MAX_EMPLOYEES
= 500;
string empNames[MAX_EMPLOYEES];
double empSalary[MAX_EMPLOYEES];
string class takes care of memory
to accommodate any size string.
COP3530 Data Structures
308
Data Structure: An example
Alternative way for the previous example:
const MAX_EMPLOYEES = 500;
typedef struct
{
string name;
double salary;
} Employee;
Employee employees[MAX_EMPLOYEE];
• If language doesn’t support, we build new ADTs.
COP3530 Data Structures
309
ADT vs Data Structure
• ADT is like a ice dispenser machine.
• The dispenser supports operations like ADT
– Chilled water
– Crushed ice
– ice cubes
• Water and ice are like data.
• The internal design of the dispenser is like
the internal design of the ADT. We need
data structures to build ADT.
COP3530 Data Structures
310
Building ADT
• User of ADT wants operations to be fast.
• Builder of ADT wants implementation to be
simple.
• User will look for an ADT that meets their
requirement just like a customer will shop
for a refrigerator that is convenient.
• User will look at the ADT interface for
suitability not its implementation details.
COP3530 Data Structures
311
Wall for the ADT
Add
Request
Remove
Program
Response
Find
Data
Structure
Display
Interface
Wall of ADT operations
COP3530 Data Structures
312
Specifying an ADT
• Consider a list of grocery items in 1 column
• Where do you add a new item?
– At the beginning
– At the end
– Anywhere in the middle.
• There is a sequence for the items.
• Each item has a predecessor except first.
• Each item has a successor except the last.
COP3530 Data Structures
313
Specifying an ADT (contd)
• How do you specify the Add operation?
– Add newitem at position pos.
– pos = 1  new item is first item
– pos can be between 1 and (# of items in list + 1)
• How do you specify remove?
– Remove item at position pos.
• How do you retrieve an item?
– Retrieve item at position pos.
• Find the length of the list.
COP3530 Data Structures
314
List ADT
•
•
•
•
•
•
•
Create an empty list.
Destroy a list.
Check if the list is empty.
Find the number of items in the list.
Insert an item at a given position.
Delete an item at a given position.
Retrieve (look) an item at a given position.
COP3530 Data Structures
315
List ADT Operations
// Create an empty list.
CreateList()
// Destroy a list.
DestroyList()
// Return the # of items in list.
ListLength()
COP3530 Data Structures
316
List ADT Operations(contd)
//
//
//
//
//
//
//
Insert a new item at position
newPos of a list, if
1 <= newPos <= ListLength()+1
The new item becomes the item
at position newPos. Success
indicates whether the operation
was successful or not.
ListInsert(newPos, newItem, success)
COP3530 Data Structures
317
List ADT Operations(contd)
// Delete the item at position pos
// if 1 <= pos <= ListLength().
// The existining items are
// renumbered accordingly.
// success indicates whether the
// operation was successful or not.
ListDelete(pos, success)
COP3530 Data Structures
318
List ADT Operations(contd)
//
//
//
//
//
//
Retrieve the item at position
pos of a list into dataItem, if
1 <= pos <= ListLength(). The
list is left unchanged. success
indicates whether the operation
was successful or not.
ListRetrieve(pos, dataItem, success)
COP3530 Data Structures
319
Using List ADT
myList.CreateList()
myList.ListInsert(1,
success)
myList.ListInsert(2,
success)
myList.ListInsert(3,
success)
myList.ListDelete(2,
myList.ListLength()
milk,
eggs,
butter,
success)
COP3530 Data Structures
320
ADT Contract
• Client programs should only rely on ADT
specification, not on its implementation.
• As long as client follows the rules, any
change in the implementation of the ADT
will not affect the client program.
• The specification of ADT is the contract
between the ADT and its client.
• Client can use the ADT based only on the
contract.
COP3530 Data Structures
321
List ADT Usage
• Client wants to display all items in a list.
DisplayList(list)
// Display the items in list.
for (pos = 1..list.ListLength())
{
list.ListRetrive(pos, dataItem, success)
Display dataItem
}
COP3530 Data Structures
322
List ADT Usage
Replace(list, pos, newItem, success)
// Replaces item at pos in list by
// newItem. success indicates whether
// the operation was successful or not
list.ListDelete(pos, success)
if (success)
{
list.ListInsert(pos, newItem, success)
}
COP3530 Data Structures
323
Contract Advantages
• Client does not need to get distracted about
the ADT implementation details.
• Client can concentrate on ADT usage.
• Improvements in implementation of ADT
affects only the ADT code, not client code.
• ADT implementation is isolated from client.
• contract binds the ADT implementers.
COP3530 Data Structures
324
Sorted List ADT
• Consider a list of items sorted by name.
• How are the list operations affected now?
– We no longer need the position for insert.
– position is implicit except for retrieve.
• The ADT operations must make sure that
the list always remains sorted.
• For example, insert need to add the new
item at the appropriate place.
COP3530 Data Structures
325
Sorted List ADT Specification
//
//
//
//
//
Insert newItem into its proper
sorted position in a sorted
list. success indicates whether
the operation was successful
or not.
SortedListInsert(newItem, success)
COP3530 Data Structures
326
Designing an ADT
• Consider an application where you want to
print all holidays in a year.
• We may need an ADT that deals with dates.
• Clearly, we need an operation to get the first
date of a year.
• We need to know if a date is holiday.
• Given a date, we need to find the next date.
• Compare two dates.
COP3530 Data Structures
327
ListHolidays
ListHolidays(year)
// Displays the dates of all
// holidays in a given year.
date = FirstDay(year);
while (IsBefore(date, FirstDay(year+1)))
{
if (IsHoliday(date))
{
write date + “is a holiday”
}
date = NextDay(date);
}
COP3530 Data Structures
328
Implementing ADTs
• Given the ADT specification, how do we
implement the ADT?
• We choose an appropriate data structure.
• Verify if all the operations can be
implemented with this data structure.
• If efficiency is part of the specification, then
we need to verify that too.
• Look at alternative data structures and
choose the best.
COP3530 Data Structures
329
Implementing ADTs
• Once you choose the data structure, you
should use top-down approach to implement
each of the ADT operations.
• As you work through successive level of
abstraction, you will break the data structure
into smaller pieces.
• Refine until the data structure can be easily
implemented in the target language.
COP3530 Data Structures
330
Implementing ADTs
• Data structure and the implementation of
the operations should be hidden from the
client programs.
• In non-object oriented languages, both data
structure and the ADT operations are
distinct pieces.
• The data structure may not be hidden from
the client.
• Clients might violate the wall and access the
data structures directly. This may be
intentionally or accidentally.
COP3530 Data Structures
331
Implementing ADTs
• Object-oriented languages have better
support for enforcing the wall of the ADT.
• C++ provides a way to prevent the clients
from accessing the ADT data.
• Hiding the data and implementation details
is not straight forward but can be done with
careful planning.
• The algorithm can be easily hidden by
placing all the code in .cc files and giving
clients only object or library files.
COP3530 Data Structures
332
C++ Classes
• OOD deals with a collection of objects and
their relationship.
• C++ classes are used to represent these
objects.
• Objects provide encapsulation. (Walls)
• Object = Data + Operations (or methods).
• Object hides its inner details from the
programmers who uses it.
• ADT operations are object’s behaviors.
• Encapsulation hides implementation details.
COP3530 Data Structures
333
Object
Object’s data
Request
Methods
and methods
are
encapsulated
Results
Data
COP3530 Data Structures
334
Classes and Instances
• Class is a new data type in C++.
• variables of this type are called instances.
• class has data member as well as function
members.
• Every member function has access to all the
data members. Thus, they need not be
passed as parameters.
• To access the data or function member of a
class instance, you qualify the member with
the instance using the . notation.
COP3530 Data Structures
335
Classes and Instances (contd)
• An object is an instance of a class.
• By default, all members of a class are
private.
• The class designer can designate members
as belonging to public category.
• Only public member are accessible to
clients.
• Clients are functions or program that
created the object.
• All members of a structure are public by
default.
COP3530 Data Structures
336
Constructor and Destructor
• Every ADT has support for Create and
Destroy.
• All classes in C++ have 1 or more
constructor functions and 0 or 1 destructor
function.
• Constructors are used to initialize the
object.
• Constructors are called automatically when
an object is created.
• Destructor is called automatically when the
object is destroyed. Only one.
COP3530 Data Structures
337
Constructors
• Name of constructors is same as class name.
• Constructors should not have return type.
Not even void.
• Constructors can be overloaded.
• Default constructor is one with no
parameters.
• If a class has no constructors, then the
compiler will supply a default constructor
which basically does nothing.
• Copy constructor has one parameter whose
type is same as the class. const reference.
COP3530 Data Structures
338
Constructors (Example)
class Sphere
{
public:
// Default Constructor
Sphere();
// Copy Constructor
Sphere(const Sphere &rhs);
// Another constructor
Sphere(double initialRadius);
:
}
COP3530 Data Structures
339
Constructors (contd)
// Default Constructor called.
Sphere sphere1;
// Copy Constructor called.
Sphere sphere2(sphere1);
• If a class is missing default constructor but
has others, you must initialize an object
with something when you declare.
Sphere sphere1; // invalid.
COP3530 Data Structures
340
Constructor Coding
• Assume that Sphere class has variable
radius of type double in private section.
Sphere::Sphere()
{
radius = 1.0;
}
Sphere::Sphere(const Sphere &rhs)
{
radius = rhs.radius;
}
:: is scope resolution operator.
COP3530 Data Structures
341
Constructor Coding (contd)
• An alternative better way to initialize data
members of a class is to use the intializer
list. The body of the function can be used
other computational work, if any. The
Initializers are allowed only for constructor
functions. Use , for additional variables.
Sphere::Sphere():radius(1.0)
{
}
Sphere::Sphere(const Sphere &rhs):
radius(rhs.radius)
{
}
COP3530 Data Structures
342
Destructor
• Destructors are useful to perform cleanup
work when an object is destroyed.
• In particular, they are useful to free any
dynamic memory allocated by constructors.
• If there is no work to be done when an
object is destroyed, there is no need for the
destructor function.
Sphere::~Sphere() // No parameters
{
}
COP3530 Data Structures
343
Compiler Generated Constructors
• If a class has NO constructors, compiler
supplies a default constructor that does
nothing.
• If a class is missing a copy constructor, the
compiler will generate one that simply
assigns the data members of one instance to
those of the others.
• If a class is missing destructor function, the
compiler will supply one. Does nothing.
COP3530 Data Structures
344
Implementation
• Typically, we place the code for all member
functions of a class and non-member
functions related to the class in the source
file (.cpp or .cc).
• We can compile this independly of the
application program and create the object
file.
• The object file can also be placed in a
library file.
COP3530 Data Structures
345
Sphere Member Function (example)
Assume PI is defined in sphere.h
double Sphere::Area() const
{
return 4.0 * PI * radius * radius;
}
double Sphere::SetRadius(double newRadius)
{
if (newRadius >= 0)
{
radius = newRadius;
}
}
Exercise: Read the rest on page 132.
COP3530 Data Structures
346
Using Sphere Class (p 133)
#include <iostream.h>
#include <sphere.h>
int main()
{
Sphere unitSphere; // default is 1.0
Sphere mySphere(5.1);
unitSphere.DisplayStatistics();
mySphere.SetRadius(4.2);
return 0;
}
COP3530 Data Structures
347
Array-Based ADT List
• One way to implement a list is using an
array and an integer to store the length.
• Item at Position 1 is stored at index 0.
• Item at Position 2 is stored at index 1 etc.
• We need to decide on capacity of array.
• If array is full, Insert will be unsuccessful.
• Item type depends on the application.
• Insert and Delete involve shifting of items.
COP3530 Data Structures
348
Array-Based ADT List (contd)
Array Index
0
1
2
3
4
5
12
3
19
10
7
?
1
2
3
4
5
6
?
…
?
Unused entries
ADT Position
size
C-1
5
COP3530 Data Structures
349
Array-Based ADT (contd)
Array Index
New Item
0
1
2
3
4
5
12
3
34
19
10
7
1
2
3
4
5
6
6
?
…
?
Unused entries
ADT Position
size
C-1
After Insert 34 at Pos 3.
COP3530 Data Structures
350
Some ADT Guideline
• Declare member functions that do not
change the data values as const.
– Safeguards against accidental mistakes
– Needed to call these functions on const objects.
• Keep variables that are to be hidden from
clients in the private section of the class.
• Do not depend on compiler generated
constructors or destructor.
• Always define default & Copy constructors.
COP3530 Data Structures
351
Exercise 3.1 p142
int ListSum(const List &list)
{
int sum = 0;
int length = list.ListLength();
int pos, item;
bool success;
for (pos = 1; pos <= length; pos++)
{
list.ListRetrieve(pos, item, success);
sum = sum + item;
}
return sum;
}
COP3530 Data Structures
352