Transcript CS2006Ch03

COSC2006 - Data Structures I
Chapter 4
Data Abstraction
The Walls
Topics




2
Introduction
ADT Examples
Specify ADT
Implement ADT
Information Hiding: Why?

“You don’t want to know.”
… but also …

“If I told you, I’d have to kill you!”


3
… OK, not quite that extreme, but …
“A little knowledge is a dangerous thing.”
ADT

Abstract data type (ADT):

4
A collection of data together with a set of
operations on that data
ADT Why?

During a design of a solution, we need to
support operations on data (Specification)



After defining ADT operations (specification), we
consider their implementation (Implementation)


5
Design an ADT
Specify the operations (Interface) that enable communication
with the data
Specify the data structure
Specify the details of how operations work
ADT
Wall
Request to
perform
operation
Program
using
method
s
6
Slit in Wall
Result of
operation
Implementation
of
method
s
ADT Example: Ice Dispenser

Specification

Data



Input: water
Output: chilled water, crushed ice, ice cubes, or red
light
Operations:
Chill, Crush, Cube, IsEmpty
 Don’t care how operations are done inside

Chilled
water
7
Water
Crushed
ice
Ice
cubes
Out of ice
indicator
ADT Example: Ice Dispenser

Implementation:

Internal structure of the dispenser





8
Manual
Mechanical
Electronic
We can improve an operation by modifying its module
We can add another operation by adding another
module to the machine without affecting the other
modules
ADT List

Specification

Data characteristics
Items appear in sequence
 Has one first element
 One last element
 The first item is called the head (front)
 The last item is called the tail (rear/end)
 Items are of the same type

9
ADT List

Specification

Operations (Behavior):
Create an empty list
 Destroy a list
 Determine whether a list is empty
 Determine the number of items in the list
 Insert an item in a given position
 Delete an item at a given position
 Retrieve (look at) an item at a given position

10
ADT List Specification
CreateList
Retrieve
item at
index
Method
DisplayList
DataItem
DestroyList
ListInsert
ListDelete
ListRetrieve
Client
ADT Wall
Server
11
Implementation
of ADT-List
Using ADT List

Example: Display list data items
displayList(in aList: List)
// Displays the items on the list aLIst
for (Position = 1, through aList.getLength ( ) )
{ aList . retrieve (position, dataItem, success)
Display aataItem
} / / end for

Example: Replace an item with another
replace (in aList: List, in i: integer, in newItem: ListItemType,
out success: boolean)
// Replaces the ith item on the list aList with newItem.
// success flag indicates whether the replacement was successful
aList . remove (i, success)
if (success)
aList . insert (i, newItem, success)
12
Designing an ADT

Case Study: List Holidays

Problem:


Determine the dates of all holidays in a given year
Specification:

Data:




Operations:





Determine date of fist day of a given year firstDay( in year: integer)
Determine whether a date is before another date isBefore(in Date1: Date, in Date2:
Date)
Determine whether a date is a holiday isHoliday(in aDate: Date)
Determine the date following a given date nextDay(in aDate: Date)
Assumption:


13
Month
Day
Year
Days in a year form a sorted list
The list is accessed by giving the year number
Designing an ADT

Case Study: List Holidays

Using ADT List-Holidays Operations:

After specifying the operations, we can use them to solve
other problems independent of the implementation details of
the ADT.
listHolydays ( in year : integer )
// Displays the dates of 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 )
} // end while
} // end listHolidays
14
Implementing ADT
• Choose the data structure
• Implement operations:
Write the functions definition that access the data
according to the ADT operations
 Both the data structures & the functions should be
hidden from the client

15
ADT List Array-Based Implementation

Data Structure:
private final int MAX_LIST = 100; // max length of list
private listItemType items [MAX_LIST] ;
// array of list items
private int numItems;
// length of list
Each operation will need access to both array Items &
the list's length Size , They should be made as private
data members of the class
Implementation of Operations
 Extra function needed



Index (Position)

16
Defined to return the index value, since the client can't access
private data members
ADT List Array-Based Implementation

Insert Item

To insert an item at a given position

Shift items from the position on to the right, then insert the
new item
Array indexes
0
K
Size
1
2
3
19
10
2
3
4
12
1
3
k-1
...
5
10 18
Items
k
K+1
Size
17
12
1
1
2
3
3 44
19
2
4
3
...
?
?
...
?
MAX_LIST
ADT list positions
Array indexes
New item
0
MAX_LIST - 1
k
10
...
Items
5
10
18 . . .
k+1
ADT list positions
MAX_LIST - 1
?
...
?
MAX_LIST
ADT List Array-Based Implementation

Delete Item

To delete an item

Shift the elements to the left to fill the gap left by the deleted
item
Array indexes
0
K+1
Size
1
12
1
2
3
3 44
19
2
4
3
k
10
...
5
10
MAX_LIST - 1
18 . . .
Items
?
k+1
...
?
MAX_LIST
ADT list positions
Array indexes
0
K
18
Size
12
1
1
2
3
44
2
3
3
k-1
10
4
...
Items
5
10
MAX_LIST - 1
18
k
ADT list positions
... ?
...
?
MAX_LIST
Array Implementation of List: Issues




19
Array has fixed physical size; List ADT has
variable logical size
ADT-specific exceptions are informative
The array and its logical size are private
data fields
Gaps are bad: must shift elements when
adding or deleting
Array Implementation (page 1)
/ ********************************************************
// Array-based implementation of the ADT list.
// *********************************************************
public class ListArrayBased implements ListInterface {
private static final int MAX_LIST = 50;
private Object items[]; // an array of list items
private int numItems; // number of items in list
public ListArrayBased() {
items = new Object[MAX_LIST];
numItems = 0;
} // end default constructor
private int translate(int position) {
return position - 1;
} // end translate
20
Array Implementation (page 1)
/ ********************************************************
// Array-based implementation of the ADT list.
// *********************************************************
public class ListArrayBased implements ListInterface {
private static final int MAX_LIST = 50;
private Object items[]; // an array of list items
private int numItems; // number of items in list
public ListArrayBased() {
items = new Object[MAX_LIST];
numItems = 0;
} // end default constructor
private int translate(int position) {
return position - 1;
} // end translate
21
Array Implementation (page 2)
public boolean isEmpty() {
return (numItems == 0);
} // end isEmpty
public int size() {
return numItems;
} // end size
public void removeAll() {
// Creates a new array; marks old array for
// garbage collection.
items = new Object[MAX_LIST];
numItems = 0;
} // end removeAll
22
Array Implementation (page 2)
public boolean isEmpty() {
return (numItems == 0);
} // end isEmpty
public int size() {
return numItems;
} // end size
public void removeAll() {
// Creates a new array; marks old array for
// garbage collection.
items = new Object[MAX_LIST];
numItems = 0;
} // end removeAll
23
Array Implementation (page 3)
public void add(int index, Object item)
throws ListIndexOutOfBoundsException {
if (numItems >= MAX_LIST) {
throw new ListException("ListException on add");
}
if (index >= 1 && index <= numItems+1) {
// make room for new element by shifting all items at
// positions >= index toward the end of the
// list (no shift if index == numItems+1)
for (int pos = numItems; pos >= index; pos--) {
items[translate(pos+1)] = items[translate(pos)];
}
// insert new item
items[translate(index)] = item;
numItems++;
}
24
else { // index out of range
throw new ListIndexOutOfBoundsException(
"ListIndexOutOfBoundsException on add");
}
} //end add
Array Implementation (page 4)
public void remove(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems) {
// delete item by shifting all items at
// positions > index toward the beginning of the list
// (no shift if index == size)
for (int pos = index+1; pos <= size(); pos++) {
items[translate(pos-1)] = items[translate(pos)];
}
numItems--;
Trace this … notice something funny at the end?
}
else { // index out of range
throw new ListIndexOutOfBoundsException(
"ListIndexOutOfBoundsException on remove");
}
} //end remove
25
Array Implementation (page 5)
public Object get(int index)
throws ListIndexOutOfBoundsException {
if (index >= 1 && index <= numItems) {
return items[translate(index)];
}
else { // index out of range
throw new ListIndexOutOfBoundsException(
"ListIndexOutOfBoundsException on get");
}
} // end get
}
26
// end ListArrayBased
Review

The specifications of an ADT’s operations
indicate ______.




27
what the operations do
how to implement the operations
how to store the data in the ADT
how to carry out the operations
Review

A(n) ______ allows two modules to
communicate with each other.




28
data structure
axiom
Interface
client
Review



In the following list:
John, Kate, Fred, Mark, Jon, Adam, Drew
which element is the tail of the list?




29
John
Mark
Drew
Adam
Review

The items in the ADT list are referenced
by ______.




30
name
value
position number
position name
Review

The insertion operation of the ADT list can
insert new items ______.




31
only at the front of the list
only at the end of the list
only in the middle of the list
into any position of the list
Review

In the ADT list, when an item is deleted
from position i of the list, ______.




32
the position of all items is decreased by 1
the position of each item that was at a position
smaller than i is decreased by 1
the position of each item that was at a position
greater than i is decreased by 1
the position of each item that was at a position
smaller than i is increased by 1 while the position of
each item that was at a position greater than i is
decreased by 1
Review

Which of the following operations of the
ADT list changes the list?




33
remove
isEmpty
Size
get