Introduction to ADTs
Tom Kelliher, CS23
Feb. 21, 1996
- Large team project to create, prove, develop product
- Proof of concept prototype
- Re-write for time/space efficiency before shipping
What can go wrong?
How can these problems be addressed?
- Procedural abstraction --- what, not how
- Information hiding
- Data abstraction
A collection of data together with a set of operations on that data.
- Object oriented programming
Interface/Implementation (data structure)
- Complex numbers
- The factorial of a number
- A chair
- An automobile
- A CD collection (classical vs. rock)
A list is a collection of ordered items
- Successor, predecessor
- Insertion/deletion semantics --- yield different ``lists:''
- Anywhere --- list
- Insert at tail, delete at head --- queue
- Insert, delete at head --- stack
- ListInsert(newPosition, newItem, success)
- ListDelete(position, success)
- ListRetrieve(position, dataItem, success)
Have we specified a data structure (implementation)?
l.ListInsert(1, bread, success);
l.ListInsert(2, butter, success);
l.ListInsert(3, jam, success);
l.ListInsert(4, toaster, success);
l.ListRetrieve(2, d, success);
Without knowledge of the implementation:
- Write a display function
- Write a multiple insert function
- Delete all items and destroy entire list
- Build other ADTs from ADT List:
- Sorted list
Example: ADT Sorted List Operations:
- SortedListInsert(newItem, success)
- SortedListDelete(item, success)
- SortedListRetrieve(position, dataItem, success)
- LocatePosition(anItem, position, success)
- Terry Winograd developed a program called SHRDLU that was intended to
model a simple ``world'' consisting of children's blocks of various shapes
and colors. Among other things, SHRDLU was designed to simulate
manipulation of the blocks by picking them up and placing them elsewhere.
Design ADT block operations.
Thomas P. Kelliher
Tue Feb 20 13:20:01 EST 1996