Transcript slides

Data Structures – A Computing
Abstraction
Abstraction Revisited
• Abstraction (key concept in computation) –
the difference between your mental picture of
a data structure and the actual way a
computer stores a data structure in memory
• Computer Memory - Every piece of data that
is stored in a computer is kept in a memory
cell with a specific address, organized
linearly, fixed. Lends itself to linear, static data
structures. Can all problem spaces be
represented this way? But what about
dynamic, non-linear data structures?
Data Relationships
list : 1-1 relationship between elements, each
element has one next element (or one prior
element).
tree : 1-n relationship between elements, each
element has possibly n children, every
element has only one parent.
graph : n-n relationship between elements,
each element can be related to possibly
every other element and vice-versa.
Linear Data Structures
• Unordered List: The Abstract View - List is
general case, array/string special cases; next
item, previous item, nth item, add to
beginning, add to end, insert here, find item
• Ordered List: The Abstract View - same
functions as unordered list except must
maintain (and take advantage of) order
• Stack: The Abstract View - restricted access
List via PUSH/POP; "last-in, first-out" or LIFO
• Queue: The Abstract View - restricted access
List via ENQUEU/DEQUEUE; "first-in, firstout" or FIFO structure
Linear Questions
Unordered List, Ordered List, Stack, Queue
• You wish to find the minimum value in a set of data
(without erasing the information or changing its
order). In which of the following data structures can
you do this, but you must you go through all the data
values?
• You wish to add a value to the end of a data
structure. In which of these data structures must you
go through all the values in order to accomplish your
goal?
• You are searching for a specific item known to be in
your data set. In which structure must you always go
through all data values in order to locate it (and not
lose or reorder the rest of your data)?
Tree Data Structures
• A collection of vertices and edges
representing some sort of relationship
between vertices.
• Any vertex can have multiple children,
but each vertex can have only one
parent.
• Representing hierarchical data
• Trees can be rooted or not rooted,
ordered or unordered, binary, ternary,
. . n-ary
Tree Applications
•
•
•
•
Directory structure on computers
Decision Trees
Game Theory
Binary Search Tree - Efficient data structure for
dictionary operations (insert, update, search,
delete)
Tree Traversals
• Depth first
• Breadth first
• BST – pre-order, in-order, post-order
Expression Tree
+
/
^
/
+
/
x
\
/
\
/
2
\
y
\
3
/
\
x
4
Graph Data Structures
• A collection of vertices and edges representing
some sort of relationship between vertices.
• Any vertex can be connected to any other vertex,
even itself.
• Graphs can be directed or undirected, connected
or unconnected, weighted or un-weighted
TN
MS
AL
NC
SC
GA
LA
FL
Graph Applications
•
•
•
•
•
Networking, scheduling, path planning
Airline Routes
Six Degrees of Kevin Bacon
Call Graph
Google maps
Graph Algorithms
• Traversals
• Finding Connected components
• Spanning Tree
• Shortest Path