Examples of ADTs
Arrays
Linked Lists
Stacks
Queues
Graphs
Trees
Hash Tables
A Cell
A Single Unit of Data
One object of Abstract Data
Contains:
Actual Data
Extra Information for Manipulating the Structure
Also Called Overhead
Arrays
One-Dimensional Arrays
Strings
Class List
Two-Dimensional Arrays
Rainfall
Positions on a Grid
Arrays (cont.)
Three-Dimensional Arrays
Points in Space
N-Dimensional Arrays
Huh?
Age vs. Cancer Rate vs. Milk Intake vs. Place of Birth vs. Favorite Ice Cream
Linked-Lists
Think of a Train…
 
 

Can be Singly-Linked or Doubly-Linked
Linked-Lists (cont.)
Provide Dynamic Data Allocation
Easy to Insert or Remove one Cell
Stacks
Just What its Says!
Queues
Typical Type of Line, Like at McDonald’s or Burger King
Q: What’s the difference between lines at McD and B.K.?
FIFO: First-In, First-Out
LIFO: Last-In, First-Out
Graphs
A Group of V Vertices and E Edges
Can be:
Directed
Undirected
Acyclic
Trees
Binary
N-Ary
Walking a Tree (Tree Traversal)
Pre-Order
In-Order
Post-Order
Pre-Order Traversal
Pre-Order: A-B-D-E-C-F-G
In-Order: D-B-E-A-F-C-G
Post-Order: D-E-B-F-G-C-A

How to Develop a Program
Requirements Specification
Analysis
Design
Development of a Test Plan
Implementation
Testing
Production
Maintenance
Requirements, Analysis, Design
Don’t try to solve the whole problem all at once!
“Divide and Conquer”
Break down the problem into smaller pieces
Break down the pieces into smaller pieces
Implement the pieces
Requirements, Anaysis, Design (cont.)
Example: Calling your friend
What do you need in order to do the task?
What assumptions are you making?
What steps do you take?
What small steps do you take!
Once you break it down, the implementation part is simple!!
How This Translates into Programming
Think “High Level”
Sketch out the main procedure
Write the Package Specification first
Just put some stubs in the body
 Now fill in the body with the meat
Example: Restaurant Guide
People need to eat
There are many types of food
There are many locations
How can we help people to choose a restaurant?
Programming Tips
Use multiple windows
That’s what they are there for!!!!
Edit window(s)
Compile window
Execution window
Email window
Use a different directory for each project
Use makefiles   <== This is a big help!!
Debugging Tips
“My program died, and I don’t know where to start looking for the problem!”
Poor man’s Debugger
Insert print (put) statements into your code at strategic locations
Poorman’s Debugger
Use a variable to control debug statements

Debug : Boolean := True;
...
IF Debug THEN
  Ada.Text_IO.Put( “Rob, I’m at point 1” );
END IF;