Transcript Figure 12-10

Chapter 12
Abstract
Data Type
©Brooks/Cole, 2003
12.1
BACKGROUND
©Brooks/Cole, 2003
Abstract Data Type (ADT)
• In early days programming, to read a file, we
wrote a code to read the physical file. And we
had to do this over and over again.
• Using ADT, we write the code to read a file and
place it in the library for all programs to use.
• ATD consists of a set of definitions that allow
programmers to use the functions while hiding
the implementation.
©Brooks/Cole, 2003
The Concept of Abstraction
• The Generalization of operations with
unspecified implementations is known as
abstraction.
• Thus the concept of abstraction means:
– You know what data type can do
– How is done is hidden
©Brooks/Cole, 2003
Definition
• An Abstract data type is:
1. Declaration of data
2. Declaration of operations
3. Encapsulation of data and operations.
Note
• Application programs shouldn’t reference to
the data structure. Because if we did so, ADT
will not be fully portable to other applications.
©Brooks/Cole, 2003
Figure 12-1
Model for ADT
•
•
•
Data are entered, accessed … etc through operational interfaces
Only operation name is visible to the user
Additional operations may be created to satisfy specific requirements
©Brooks/Cole, 2003
12.2
LINEAR
LISTS
©Brooks/Cole, 2003
Figure 12-2
Linear list
• In linear list, each element has a unique successor
©Brooks/Cole, 2003
Figure 12-3
Categories of linear lists
• In general list, data can be inserted and deleted
anywhere and no restriction on operations.
• In restricted list, data can only be inserted or
deleted at the end of the structure.
©Brooks/Cole, 2003
Figure 12-4
(1) Insertion in a linear list
• Data are inserted in the middle of the list most of the time.
• To determine where data to be placed, search algorithm
(sequential search) is used.
• If there is no enough room for data, the list is in overflow
state and the item can not be added.
©Brooks/Cole, 2003
Figure 12-5
(2) Deletion from a linear list
• To delete data from the list, the data have to be located
using search algorithm (sequential search).
• Once located, the data are removed.
• If the list is empty, the list is underflow state and delete
operation fails.
©Brooks/Cole, 2003
Figure 12-6
(3)Retrieval from a linear list
• To retrieve data from the list, the data have to be located using
search algorithm.
• A copy of data should be retrieved without changing the content.
• You can not retrieve items form empty list.
©Brooks/Cole, 2003
Figure 12-7
(4)Traversal of a linear list
• List traversal is the operation where all elements in the list are
processed sequentially, one by one.
• Walker point to the element must be processed at a time.
• Processing could be retrieval, sorting … etc.
• List traversal requires looping algorithm rather than search,
loop terminate when all elements been processed.
©Brooks/Cole, 2003
Implementation of A General Liner
List
• The General list could be either an array or a
linked list
Liner List Applications
• Linear list can be used in situation where the
elements are accessed randomly. For example;
to store information about students in the college
Dr Barnawi
©Brooks/Cole, 2003
12.3
STACKS
©Brooks/Cole, 2003
Figure 12-8
Three representations of a stack
• Stack is a restricted linear list in which all additions and
deletions are made at the end, called the top.
• Stack is known as last in, first out (LIFO) data structure.
• Examples stack of coins, books….
©Brooks/Cole, 2003
Figure 12-9
(1) Push operation
• Push adds an item to the top of the stack.
• The new item becomes the top.
• If there is no enough room for new item, the stack is in an
overflow state and item can’t be added.
Dr Barnawi
©Brooks/Cole, 2003
Figure 12-10
(2) Pop operation in a stack
• Pop removes an item from the top of the stack and return it to
the user.
• If an empty stack has been popped, the stack is in an
underflow state.
©Brooks/Cole, 2003
(3) Empty operation
• This operation check to see if a stack is empty or not.
The response is either true or false
©Brooks/Cole, 2003
Example 1
Show the result of the following operations on a stack S.
push (S , 10)
push (S , 12)
push (S , 8)
if not empty (S), then pop (S)
push (S , 2)
©Brooks/Cole, 2003
Implementation of a stack
• Although Stack can be implemented either as
an array or a linked list, linked list is more
common because pop and push operations are
much easier on liked list.
©Brooks/Cole, 2003
Stack Applications
1. Reversing Data; data reordred so the first and
the last are exchanged.
2. Parsing; breaking data into independent order.
3. Postponement; first inputs are deferred for
later processing.
4. Backtracking; Going back to previous data is
used for computer gaming, decision analysis
and expert systems.
Dr Barnawi
©Brooks/Cole, 2003
12.4
QUEUES
©Brooks/Cole, 2003
Figure 12-12
Queue representation
• Queue is a linear list in which data are inserted at the rear
and deleted from the end.
• The Queue is FIFO; first data to be processed first
©Brooks/Cole, 2003
Figure 12-13
(1) Enqueue operation
• Enqueue insert data into the queue.
• The new item becomes the rear.
• If there is no enough room for new item, the queue is in an
overflow state and the item can’t be added.
Dr Barnawi
©Brooks/Cole, 2003
Figure 12-14
Dequeue operation
• Dequeue removes an item from the front of the queue and
return it to the user.
• If an empty queue has been dequeued, the queue is in an
underflow state.
©Brooks/Cole, 2003
Example 2
Show the result of the following operations on a queue Q.
enqueue (Q , 23)
if not empty (Q), dequeue (Q)
enqueue (Q , 20)
enqueue (Q , 19)
if not empty (Q), dequeue (Q)
©Brooks/Cole, 2003
Implementation of a queue
• A Queue can be implemented either as an
array or a linked list.
Queue Applications
• Queues are found in every operating systems
and network and countless other areas.
©Brooks/Cole, 2003
12.5
TREES
©Brooks/Cole, 2003
Figure 12-16
Representation of a tree
Indegree
branch
nodes
outdegree
branch
• The sum of the indegree and outdegree branches is the
degree of the node.
• The indegree of the root is zero by definition.
• All nodes in the tree must have indegree of one and
different number of outdegree .
©Brooks/Cole, 2003
Figure 12-17
Tree terminology
©Brooks/Cole, 2003
Figure 12-18
Subtrees
• Subtree is any connected structure below the root
Dr Barnawi
©Brooks/Cole, 2003
12.6
BINARY
TREES
©Brooks/Cole, 2003
Figure 12-19
Binary tree
• Binary Tree is a tree in which no node can have
more than two subtrees. In other word a node can
have 0,1 or 2 subtrees.
• These subtrees are designated as left and right
subtrees.
©Brooks/Cole, 2003
Figure 12-20
Examples of binary trees
©Brooks/Cole, 2003
Properties of Binary Trees
(1) Height of Binary Tree
Given the number of nodes, N;
• The maximum height; Hmax = N
• The minimum height; Hmin = [Log2 N ] + 1
Given the height of binary tree, H;
• The minimum number of nodes; Nmin= H
• The maximum number of nodes; Nmax= 2H - 1
©Brooks/Cole, 2003
Properties of Binary Trees
(2) Balance
• The balance factor of binary tree is the difference
in height between the left and right subtrees;
B = HL - H R
• A tree is balanced if B = 0 → Rare
• A tree is balanced if B = -1, 0, +1 → General
Dr Barnawi
©Brooks/Cole, 2003
Figure 12-21
Operations on Binary trees
Binary tree traversals
a. Depth-first traversal
Root node is
processed first
followed by the
lift subtree then
the right subtree
Left subtree is
processed first
followed by the
root node then
the right subtree
Left subtree is
processed first
followed by the
right subtree node
then the root node
©Brooks/Cole, 2003
Figure 12-22
Preorder traversal of a binary tree
Node is processed when you are on the left
©Brooks/Cole, 2003
Figure 12-23
Inorder traversal of a binary tree
Node is processed when you are under
©Brooks/Cole, 2003
Figure 12-24
Postorder traversal of a binary tree
Node is processed when you are on the right
©Brooks/Cole, 2003
Figure 12-25
b. Breadth-first traversal of a binary tree
Tree is processed in stair like fashion, starting
from root at level 0 then nodes in level 1 and so on
©Brooks/Cole, 2003
Implementation of a binary tree
• A binary tree is normaly implemented as a
linked list.
Dr Barnawi
©Brooks/Cole, 2003
Binary tree Applications
Expression tree
The expression tree is binary tree with
1. Each leaf is an oprand.
2. The root and internal nodes are operators.
3. Subtrees are subexpressions and the root is operator.
Standard traversals represent three expression formats:
1. Inorder traversal produces the infix expression.
2. Postorder traversal produces the postfix expression.
3. Preorder traversal produces the prefix expression.
©Brooks/Cole, 2003
Figure 12-26
Expression tree - infix
©Brooks/Cole, 2003
12.7
GRAPHS
©Brooks/Cole, 2003
Graphs-Terminology
• A Graph is collection of nodes called vertices (single is
vertex) and collection of line segments called lines
connecting pairs of vertices.
• Graph could be directed (diagraph) or undirected.
• Arcs, Edges
• Adjacent vertices (neighbor)
See
• Path, Cycle, Loop.
book
• Strongly, weakly connected and disjoint graphs
• Degree, outdegree, indegree
Dr Barnawi
©Brooks/Cole, 2003
Figure 12-27
Directed and undirected graphs
©Brooks/Cole, 2003
Figure 12-28
Operations On Graphs
(1) Add vertex
First vertex is added as a disjoint vertex
and then connected to a neighbor
©Brooks/Cole, 2003
Figure 12-29
(2) Delete vertex
When vertex is deleted all edges also are removed
©Brooks/Cole, 2003
Figure 12-30
(3) Add edge
To add an edge two vertex must be specified
Dr Barnawi
©Brooks/Cole, 2003
Figure 12-31
(4) Delete edge
When edge is deleted connection between two
neighbors are removed
©Brooks/Cole, 2003
Figure 12-32
(5) Find vertex
Find vertex search the graph and return data
for specific vertex
©Brooks/Cole, 2003
(6) Traverse Graph
• In graph traversal, you must ensure that you
process the data in each vertex only once.
• The problem is that there are more than one
path to a vertex in a graph.
• The solution is; before traversal, you set a
visited flag at each vertex “off”, as you
traverse the vertex you set the visited flag “on”
©Brooks/Cole, 2003
Figure 12-33
(a) Depth-first traversal of a graph
Select any vertex adjacent to processed vertex
Dr Barnawi
©Brooks/Cole, 2003
Figure 12-34
(b) Breadth-first traversal of a graph
Process all vertex adjacent to processed vertex
©Brooks/Cole, 2003
Figure 12-35: Part I
Graph implementations
To represent a graph two sets of data are needed; the first to
represent the vertices and the second to represent the arcs
©Brooks/Cole, 2003
Figure 12-35: Part 2
Graph implementations
Dr Barnawi
©Brooks/Cole, 2003