MODELLING | Programming World |
Real World | Collection |
ADT | DT |
real world object |
abstract model entities & attributes |
set sequence tree graph |
arrays structures & pointers objects |
ADS | Properties | Operations |
Set |
Unique values Unordered |
is_empty() cardinality() display()
-----------------------------------------------------------
add(value) remove(value) find(value) |
Sequence |
Ordered Possibly Sorted |
is_empty(), cardinality(), display()
-----------------------------------------------------------
add(value), remove(value), find(value)
-----------------------------------------------------------
add_pos(value, position), rem_pos(position), find_pos(position)
-----------------------------------------------------------
get_first(), get_next()
|
Stack |
LIFO |
add_pos(value, 1) (push) rem_pos(value, 1) (pop) find_pos(1) (TOS) |
Queue |
FIFO |
add_pos(value, n+1) (enqueue) rem_pos(value, 1) (dequeue) |
ADS | Properties |
Operations | Algorithms |
Tree: General (GT) Binary (BT) Binary Search (BST) AVL B-Tree |
BT is ordered BST is sorted AVL is sorted & balanced B-Tree is ordered, sorted & balanced |
is_empty() cardinality() display()
-----------------------------
add(value) remove(value) find(value)
-----------------------------
pre-, in-, post-order
|
AVL add Heap Topological Sort |
ADS | Properties | Operations | Algorithms |
Graph: Directed Undirected |
G = (V, E) Unordered Nodes (Vertices) Edges |
is_empty() cardinality_nodes() cardinality_edges() display()
-----------------------------
add_node(id) remove_node(id) find_node(id)
-----------------------------
add_edge(id1, id2, cost) remove_edge(id1, id2) find_edge(id1, id2)
-----------------------------
is_path(id1, id2) in_degree(id) out_degree(id)
|
Dijkstra Floyd Warshall Prim Kruskal
Strong Components
Articulation Point |