Transcript Chapter08

Chapter 8
Abstract Data Types
and Subprograms
What is Computer Science?
• One More Definition of Computer Science:
“Computer Science is the Automation
of Abstractions” – anonymous
9-2
More Simply Stated…
• Data
• Instructions
• Data organization and Algorithm affect each
other
9-3
Chapter Goals
• What is an Abstract Data Type?
• Concept of
“The Separation of Interface from Implementation”
• array-based implementation
• linked implementation
4
More Chapter Goals
Some Specific Common Abstract Data Types
• arrays and lists
• stacks and queues
• binary trees and binary search trees
• Graphs
Common Algorithms that Operate on these ADT’s
• Tree Searches
• Traveling Salesman Problem, etc
5
Abstract Data Types
Abstract data type
A composite data type containing:
•Data in a particular organization
•Operations (algorithms) to operate on that data
Remember the most powerful tool for managing
complexity?
6
Abstract Data Types
Abstract data type
The goals are to:
1) Reduce complexity thru abstraction
2) Organize our data into various kinds of
containers
3) Think about our problem in terms of data
and the operations (algorithms) that are
done to them
7
Why do We Need ADT’s?
Very DIFFICULT to write this without ADT’s
8
Why do We Need ADT’s?
Almost IMPOSSIBLE to write this without ADT’s
9
Stacks
All operations
occur at the
top
Stacks
Stack
An abstract data type in which accesses are
made at only one end
– LIFO, which stands for Last In First Out
– The insert is called Push and the delete is called
Pop
Name some everyday
structures that are stacks
11
Stacks
WHILE (more data)
Read value
Push(myStack, value)
WHILE (NOT IsEmpty(myStack))
Pop(myStack, value)
Write value
Hand simulate this algorithm
12
Queues
All operations
occur at the
front and back
Queues
Queue
An abstract data type in which items are entered
at one end and removed from the other end
– FIFO, for “First In First Out”
• EnQue: Get in line at rear
• Deque: Get served at front
14
Queues
WHILE (more data)
Read value
Enque(myQueue, value)
WHILE (NOT IsEmpty(myQueue))
Deque(myQueue, value)
Write value
Hand simulate this algorithm
Stacks and Queues
(using a Linked Implementation)
Stack and queue
visualized as
linked structures
16
Implementation: What’s Inside?
There are several ways to implement any ADT
2 Common implementations use:
1) An Array
2) Linked Nodes
Here, we are concerned with the details inside the ADT
(Building the car instead of Driving the car)
17
ADT Implementations
Array-based implementation
Items are in an array, physically next to each other in
memory
Linked-based implementation
Items are not next to each other in memory, instead
each item points to the next item
Did you ever play treasure hunt, a game in which each clue
told you where to go to get the next clue?
18
Array-Based Implementations
19
Linked Implementations
20
Algorithm for Playing Solitaire
WHILE (deck not empty)
Pop the deckStack
Check for Aces
While (There are playStacks to check)
If(can place card)
Push card onto playStack
Else
push card onto usedStack
Does implementation matter at this point?
21
“Logical Level”
The algorithm that uses the list does not need to
know how it is implemented
We have written algorithms using a stack, a
queue, and a list without ever knowing the
internal workings of the operations on these
containers
22
Trees
Can represent
more complex
relationships
between data
Trees
Root node
Node with two children
Node with right child
Leaf node
Node with left child
What is the unique path
to the node containing
5? 9? 7? …
24
Why Trees?
• Some real-world data is tree-like
– Geneology Family trees
– Management Hierarchies
– File Systems (Folders etc)
• Treeses are easy to search
25
Binary Search Trees
Binary search tree
Each “sub-tree” has the following property(s):
1. All sub-trees on one side are greater
2. All sub-tress on the other side are smaller
26
Binary Search Tree
Each node
is the root
of a subtree
made up of
its left and
right children
Prove that this
tree is a BST
Figure 8.7 A binary search tree
27
Binary Search Tree
(A Look at Implementation Details)
28
Trees and Recursion
Like Mona Lisa,
Trees have
repeating
patterns at
smaller levels
Recursive Binary Search Algorithm
Boolean BinSearch(node, item)
If (node is null)
item does not exist
Else
If (item < node)
BinSearch(node.leftchild, item)
Else
BinSearch(node.rightchild, item)
30
Binary Search Tree
31
Another Binary Search Tree
32
Building Binary Search Tree
Insert(tree, item)
IF (tree is null)
Put item in tree
ELSE
IF (item < info(tree))
Insert (left(tree), item)
ELSE
Insert (right(tree), item)
33
Graphs
Can represent
more complex
relationships
between data
Graphs
Graph
A set of nodes and a set of edges that relate the nodes
to each other
Undirected graph
Edges have no direction
Directed graph (Digraph)
Each edge has a direction (arrowhead)
Weighted Graph
Edges have values
35
Graphs
Figure 8.10
Examples of graphs
36
Graphs
Figure 8.10
Examples of graphs
37
Graphs
Figure 8.10
Examples of graphs
38
Common Graph Algorithms
•Traveling salesman problem
Finding the cheapest or shortest path
through several cities
•Internet data routing algorithms
•Family tree software
•Neural Nets (An Artificial Intelligence
technique)
39
Graph Algorithms
A Depth-First Searching Algorithm--Given a starting
vertex and an ending vertex, we can develop an
algorithm that finds a path from startVertex to
endVertex
This is called a depth-first search because we start at a
given vertex and go to the deepest branch and
exploring as far down one path before taking
alternative choices at earlier branches
40
Depth First Search(startVertex, endVertex)
Set found to FALSE
Push(myStack, startVertex)
WHILE (NOT IsEmpty(myStack) AND NOT found)
Pop(myStack, tempVertex)
IF (tempVertex equals endVertex)
Write endVertex
Set found to TRUE
ELSE IF (tempVertex not visited)
Write tempVertex
Push all unvisited vertexes adjacent with tempVertex
Mark tempVertex as visited
IF (found)
Write "Path has been printed"
ELSE
Write "Path does not exist")
41
Can we get from Austin to
Washington?
Figure 8.11 Using a stack to store the routes
42
Can we get from Austin to
Washington?
Figure 8.12, The depth-first search
43
Breadth-First Search
What if we want to answer the question of how to get
from City X to City Y with the fewest number of airline
stops?
A Breadth-First Search answers this question
A Breadth-First Search examines all of the vertices
adjacent with startVertex before looking at those
adjacent with those adjacent to these vertices
A Breadth-First Search uses a queue, not a stack, to
answer this above question Why??
44
Breadth First Search(startVertex, endVertex)
Set found to FALSE
Enque(myQueue, startVertex)
WHILE (NOT IsEmpty(myQueue) AND NOT found)
Deque(myQueue, tempVertex)
IF (tempVertex equals endVertex)
Write endVertex
Set found to TRUE
ELSE IF (tempVertex not visited)
Write tempVertex
Enque all unvisited vertexes adjacent with tempVertex
Mark tempVertex as visited
IF (found)
Write "Path has been printed"
ELSE
Write "Path does not exist"
How can I get from Austin to Washington in the fewest number of
stops?
Figure 8.13 Using a queue to store the routes
46
Breadth-First Search Traveling from Austin to
Washington, DC
Figure 8.14, The Breadth-First Search
47