Transcript An Array-Based ADT List

Chapter 3
Data Abstraction:
The Walls
Abstract Data Types
• Modularity
– Keeps the complexity of a large program
manageable by systematically controlling
the interaction of its components
– Isolates errors
– Eliminates redundancies
– A modular program is
• Easier to write, read and modify
© 2005 Pearson Addison-Wesley. All rights reserved
3-2
Abstract Data Types
• Procedural abstraction
– Separates the purpose and use of a module from
its implementation
– A module’s specifications should
• Detail how the module behaves
• Identify details that can be hidden within the module
© 2005 Pearson Addison-Wesley. All rights reserved
3-3
Abstract Data Types
• Information hiding
– Hides certain
implementation details
within a module
– Makes these details
inaccessible from
outside the module
Isolated tasks: the implementation of task T does not
affect task Q
© 2005 Pearson Addison-Wesley. All rights reserved
3-4
Abstract Data Types
• Typical operations on data
– Add data to a data collection
– Remove data from a data collection
– Ask questions about the data in a data
collection
© 2005 Pearson Addison-Wesley. All rights reserved
3-5
Abstract Data Types
• Data abstraction
– Asks you to think what you can do to a
collection of data independently of how you do
it
– Allows you to develop each data structure in
relative isolation from the rest of the solution
– A natural extension of procedural abstraction
© 2005 Pearson Addison-Wesley. All rights reserved
3-6
Abstract Data Types
• Abstract data type (ADT)
– An ADT is composed of
• A collection of data
• A set of operations on that data
– Specifications of an ADT indicate
• What the ADT operations do, not how to implement
them
– Implementation of an ADT
• Includes choosing a particular data structure
© 2005 Pearson Addison-Wesley. All rights reserved
3-7
Abstract Data Types
Figure 3.4
A wall of ADT operations isolates a data structure from the program that uses it
© 2005 Pearson Addison-Wesley. All rights reserved
3-8
Implementing ADTs
Figure 3.9 Violating the wall of ADT operations
© 2005 Pearson Addison-Wesley. All rights reserved
3-9
The ADT List
• Except for the first and last items, each item
has a unique predecessor and a unique
successor
• Head or front do not have a predecessor
• Tail or end do not have a successor
© 2005 Pearson Addison-Wesley. All rights reserved
3-10
The ADT List
• Items are referenced by their position within
the list
• Specifications of the ADT operations
– Define the contract for the ADT list
– Do not specify how to store the list or how to
perform the operations
• ADT operations can be used in an
application without the knowledge of how
the operations will be implemented
© 2005 Pearson Addison-Wesley. All rights reserved
3-11
The ADT List
• ADT List operations
–
–
–
–
–
–
–
Create an empty list
Determine whether a list is empty
Determine the number of items in a list
Add an item at a given position in the list
Remove the item at a given position in the list
Remove all the items from the list
Retrieve (get) item at a given position in the list
© 2005 Pearson Addison-Wesley. All rights reserved
3-12
The ADT List
• The ADT sorted list
– Maintains items in sorted order
– Inserts and deletes items by their values, not
their positions
© 2005 Pearson Addison-Wesley. All rights reserved
3-13
The ADT List
Figure 3.7
The wall between displayList and the implementation of the ADT list
© 2005 Pearson Addison-Wesley. All rights reserved
3-14
Designing an ADT
• The design of an ADT should evolve
naturally during the problem-solving
process
• Questions to ask when designing an ADT
– What data does a problem require?
– What operations does a problem require?
© 2005 Pearson Addison-Wesley. All rights reserved
3-15
Designing an ADT
• For complex abstract data types, the
behavior of the operations must be specified
using axioms
– Axiom: A mathematical rule
– Ex. : (aList.createList()).size() = 0
© 2005 Pearson Addison-Wesley. All rights reserved
3-16
Implementing ADTs
• Choosing the data structure to represent the
ADT’s data is a part of implementation
– Choice of a data structure depends on
• Details of the ADT’s operations
• Context in which the operations will be used
© 2005 Pearson Addison-Wesley. All rights reserved
3-17
Implementing ADTs
• Implementation details should be hidden
behind a wall of ADT operations
– A program would only be able to access the
data structure using the ADT operations
© 2005 Pearson Addison-Wesley. All rights reserved
3-18
An Array-Based ADT List
• A list’s items are stored in an array items
• Both an array and a list identify their items
by number
© 2005 Pearson Addison-Wesley. All rights reserved
3-19
An Array-Based ADT List
• A list’s kth item will be stored in
items[k-1]
Figure 3.11 An array-based implementation of the ADT list
© 2005 Pearson Addison-Wesley. All rights reserved
3-20
Array-Based ADT List Implementation
//
//
//
//
*************************************
Header file ListA.h for the ADT list
Array-based implementation
*************************************
const int MAX_LIST = maximum-size-of-list;
typedef desired-type-of-list-item ListItemType;
class List{
public:
List();
// default constructor
// destructor is supplied by
// compiler
© 2005 Pearson Addison-Wesley. All rights reserved
3-21
Array-Based ADT List Implementation
// list operations:
bool isEmpty() const;
// Determines whether a list is empty.
// Precondition: None.
// Postcondition: Returns true if the
// list is empty; otherwise returns
// false.
© 2005 Pearson Addison-Wesley. All rights reserved
3-22
Array-Based ADT List Implementation
int getLength() const;
// Determines the length of a list.
// Precondition: None.
// Postcondition: Returns the number of
// items that are currently in the list.
© 2005 Pearson Addison-Wesley. All rights reserved
3-23
Array-Based ADT List Implementation
void insert(int index,
ListItemType newItem,
bool& success);
// Inserts an item into the list at
// position index.
// Precondition: index indicates the
// position at which the item should be
// inserted in the list.
// Postcondition: If insertion is
// successful, newItem is at position
// index in the list, and other items are
// renumbered accordingly, and success is
// true; otherwise success is false.
// Note: Insertion will not be successful
// if index < 1 or index > getLength()+1.
© 2005 Pearson Addison-Wesley. All rights reserved
3-24
Array-Based ADT List Implementation
void remove(int index, bool& success);
// Deletes an item from the list at a
// given position.
// Precondition: index indicates where
// the deletion should occur.
// Postcondition: If 1 <= index <=
// getLength(), the item at position
// index in the list is deleted, other
// items are renumbered accordingly,
// and success is true; otherwise success
// is false.
© 2005 Pearson Addison-Wesley. All rights reserved
3-25
Array-Based ADT List Implementation
void retrieve(int index,
ListItemType& dataItem,
bool& success) const;
// Retrieves a list item by position.
// Precondition: index is the number of
// the item to be retrieved.
// Postcondition: If 1 <= index <=
// getLength(), dataItem is the value of
// the desired item and success is true;
// otherwise success is false.
© 2005 Pearson Addison-Wesley. All rights reserved
3-26
Array-Based ADT List Implementation
private:
ListItemType items[MAX_LIST];
// array of list items
int size;
// number of items in list
int translate(int index) const;
// Converts the position of an item in a
// list to the correct index within its
// array representation.
};
// end List class
© 2005 Pearson Addison-Wesley. All rights reserved
3-27
Array-Based ADT List Implementation
//
//
//
//
//
**************************************
Implementation file ListA.cpp for the ADT
list
Array-based implementation
*****************************************
#include "ListA.h"
//header file
List::List() : size(0){
}
// end default constructor
© 2005 Pearson Addison-Wesley. All rights reserved
3-28
Array-Based ADT List Implementation
bool List::isEmpty() const{
return size == 0;
}
// end isEmpty
© 2005 Pearson Addison-Wesley. All rights reserved
3-29
Array-Based ADT List Implementation
int List::getLength() const{
return size;
} // end getLength
© 2005 Pearson Addison-Wesley. All rights reserved
3-30
Array-Based ADT List Implementation
int List::translate(int index) const{
return index - 1;
} // end translate
© 2005 Pearson Addison-Wesley. All rights reserved
3-31
Array-Based ADT List Implementation
void List::insert(int index, ListItemType newItem,
bool& success){
success = (index >= 1) &&
(index <= size + 1) &&
(size < MAX_LIST);
if (success){
// make room for new item by shifting all
// items at positions >= index toward the end
// of the list (no shift if index == size+1)
for (int pos = size; pos >= index; --pos)
items[translate(pos+1)] = items[translate(pos)];
// insert new item
items[translate(index)] = newItem;
++size; // increase the size of the list by one
}
} // end insert
© 2005 Pearson Addison-Wesley. All rights reserved
3-32
Array-Based ADT List Implementation
void List::remove(int index, bool& success){
success = (index >= 1) && (index <= size) ;
if (success){
// delete item by shifting all items at
// positions > index toward the beginning
// of the list (no shift if index == size)
for (int fromPosition = index+1;
fromPosition <= size;
++fromPosition)
items[translate(fromPosition-1)] =
items[translate(fromPosition)];
}
}
--size;
// decrease the size of the list by one
// end remove
© 2005 Pearson Addison-Wesley. All rights reserved
3-33
Array-Based ADT List Implementation
void List::retrieve(int index, ListItemType& dataItem,
bool& success) const{
success = (index >= 1) && (index <= size);
if (success)
dataItem = items[translate(index)];
} // end retrieve
© 2005 Pearson Addison-Wesley. All rights reserved
3-34
Array-Based ADT List Implementation
with Exceptions
#include <stdexcept>
#include <string>
using namespace std;
class ListIndexOutOfRangeException: public out_of_range{
public:
ListIndexOutOfRangeException(const string& message="")
: out_of_range(message.c_str())
{ }
};
// end ListIndexOutOfRangeException
© 2005 Pearson Addison-Wesley. All rights reserved
3-35
Array-Based ADT List Implementation
with Exceptions
#include <stdexcept>
#include <string>
using namespace std;
class ListException: public logic_error{
public:
ListException(const string & message = "")
: logic_error(message.c_str())
{ }
};
// end ListException
© 2005 Pearson Addison-Wesley. All rights reserved
3-36
Array-Based ADT List Implementation
with Exceptions
//
//
//
//
******************************************
Header file ListAexcept.h for the ADT list
Array-based implementation with exceptions
******************************************
#include "ListException.h"
#include "ListIndexOutOfRangeException.h"
const int MAX_LIST = maximum-size-of-list;
typedef desired-type-of-list-item ListItemType;
class List{
public:
List();
// default constructor
// destructor is supplied by
// compiler
© 2005 Pearson Addison-Wesley. All rights reserved
3-37
Array-Based ADT List Implementation
with Exceptions
// list operations:
bool isEmpty() const;
// Exception: None.
© 2005 Pearson Addison-Wesley. All rights reserved
3-38
Array-Based ADT List Implementation
with Exceptions
int getLength() const;
// Exception: None.
© 2005 Pearson Addison-Wesley. All rights reserved
3-39
Array-Based ADT List Implementation
with Exceptions
void insert(int index,
ListItemType newItem)
throw(ListIndexOutOfRangeException,
ListException);
//
//
//
//
//
//
Exception: Throws
ListIndexOutOfRangeException if
index < 1 or index > getLength()+1.
Exception: Throws ListException if
newItem cannot be placed in the list
because the array is full.
© 2005 Pearson Addison-Wesley. All rights reserved
3-40
Array-Based ADT List Implementation
with Exceptions
void remove(int index)
throw(ListIndexOutOfRangeException);
// Exception: Throws
// ListIndexOutOfRangeException if
// index < 1 or index > getLength().
© 2005 Pearson Addison-Wesley. All rights reserved
3-41
Array-Based ADT List Implementation
with Exceptions
void retrieve(int index,
ListItemType& dataItem) const
throw(ListIndexOutOfRangeException);
// Exception: ListIndexOutOfRangeException
// if index < 1 or index > getLength().
© 2005 Pearson Addison-Wesley. All rights reserved
3-42
Array-Based ADT List Implementation
with Exceptions
private:
ListItemType items[MAX_LIST];
// array of list items
int size;
// number of items in list
int translate(int index) const;
};
// end List class
© 2005 Pearson Addison-Wesley. All rights reserved
3-43
Array-Based ADT List Implementation
with Exceptions
void List::insert(int index, ListItemType newItem)
throw(ListIndexOutOfRangeException,
ListException){
if (size >= MAX_LIST)
throw ListException("ListException: List full on insert");
if (index >= 1 && index <= size+1){
for (int pos = size; pos >= index; --pos)
items[translate(pos+1)] = items[translate(pos)];
// insert new item
items[translate(index)] = newItem;
++size; // increase the size of the list by one
}
else // index out of range
throw ListIndexOutOfRangeException(
"ListIndexOutOfRangeException: Bad index on insert");
} // end insert
© 2005 Pearson Addison-Wesley. All rights reserved
3-44
Summary
• Data abstraction controls the interaction between a
program and its data structures
• Abstract data type (ADT): a set of datamanagement operations together with the data
values upon which they operate
• Mathematical study of ADTs uses axioms to
specify the behavior of ADT operations
• An ADT should be fully defined before any
implementation decisions
• Hide an ADT’s implementation by defining the
ADT as a C++ class
© 2005 Pearson Addison-Wesley. All rights reserved
3-45