Stack.
Representations
initEmpty
push O(1)
pop
isEmpty
- over array (/ vector)
- over linked-list
4/9/2014 1
Queue. Representations
initEmpty
enqueue O(1)
dequeue
isEmpty
- over array (/ vector)
- over linked-list
4/9/2014 2
Deque. Representations
initEmpty
push_back O(1)
push_front
pop_back
pop_front
isEmpty
- over array (/ vector)
- over linked-list
4/9/2014 3
STL: Stack, Queue. Issues
std::stack - container adaptor
template < class T, class Container = deque<T> > class queue;
• the underlying container •back()
•push_back()
•pop_back()
std::queue - container adaptor
template < class T, class Container = deque<T> > class queue;
• the underlying container •front()
•back()
•push_back()
•pop_front()
4/9/2014 4
STL: deque
Deque:
• Specific libraries may implement deque in different ways
generally as some form of dynamic array
• with efficient insertion and deletion of elements at the beginning and at its end.
Vector vs. deque
provide a very similar interface and can be used for similar purposes
internally can be quite different
Vector: use a single array
Deque: deques are not guaranteed to store all its elements in contiguous storage locations
can be scattered in different chunks of storage
ex.: implemented as a vector of vectors
4/9/2014 5
Java: Stack, Queue, Deque. Issues
Java™ Platform
Standard Ed. 7
Interface : Queue
Subinterface: Deque
Implementing Classes: ArrayDeque
LinkedList
4/9/2014 6
Java: Stack, Queue, Deque. Issues
Java™ Platform
Standard Ed. 7
public class Stack<E>
extends Vector<E>
• Use Deque instead of Stack
Deque<Integer> stack = new ArrayDeque<Integer>();
A more complete and consistent set of LIFO stack operations is provided by
the Deque interface and its implementations,
which should be used in preference to this class.
4/9/2014 7
Lists. Variations
• Multiple Values Per Node
ULNode = record
next: Position
elemCount: integer
elemData: array[0..MAX-1] of TElement
end
Position = ^ULNode
Terminology: unrolled linked list
4/9/2014 1
Lists. Variations
• with multiple links from nodes
Node = record:
info: TElement
links: List<Position> //array, record, linked
end
Terminology: General Linked Lists
Multiply Linked List
Multi-Linked Lists
4/9/2014 2
Multidimensional arrays
For example:
C++ : described as "arrays of arrays".
int matrix [3][5];
matrix[1][3]
the second element vertically and fourth horizontally
Using STL : Vector based multi-dim. array
vector<vector<double> > array2D
// Put some values in
array2D[1][2] = 6.0
4/9/2014 3
Jagged arrays
many rows of varying lengths
For example:
int jagged_row0[] = {0,1};
int jagged_row1[] = {1,2,3};
int *jagged[] = { jagged_row0,
jagged_row1 };
4/9/2014 4
Lists. Variations. Application
Sparse Matrices
4/9/2014 5
Sparse Matrix
• sparse … many elements are zero
• dense … few elements are zero
Structured sparse
• diagonal
• tridiagonal
• upper/lower triangular (?)
4/9/2014 6
Unstructured sparse matrix. Example
• Web page matrix.
– web pages are numbered 1 through n
– web(i,j) = number of links from page i to page j
• n ~ 109
• n x n array => 1018 consecutive position
(linear representation)
• each page links to 10 (say) other pages on average
on average there are 10 nonzero entries per row
• space needed for non-empty elements is approximately
1 billion x 10 = 1010 consecutive elements
4/9/2014 7
• sparse matrix is a matrix populated primarily with zeros
• How to store it will depend at least partly on exactly how
sparse it is, and what you want to do.
– For some applications, just treating it as a regular matrix is just
fine (especially if the dimensions aren't very big). A 15x15 sparse
matrix isn't a big memory hog.
– suppose the sparse matrix has 10240x10240 elements, and you're
using 8-byte floating point numbers: how much memory do you
need?
• Representation of sparse matrix (idea)
– list: keep information about non-zero cells
– links: for fast access from one non-zero cell to the next, on the
same raw/column general linked list
4/9/2014
sparse matrix 8
Unstructured Sparse Matrices. Representations
linear list in row-major order.
• nonzero elements of the sparse matrix
• each nonzero element is represented by a triple
(row, column, value)
the list of triples (linked , …)
List:
00304
row 1 1 2 2 4 4
00570
column 3 5 3 4 2 3
00000
value 3 4 5 7 2 6
02600
4/9/2014 9
One Linear List Per Row
00304 row1 = [(3, 3), (5,4)]
00570 row2 = [(3,5), (4,7)]
00000 row3 = []
02600 row4 = [(2,2), (3,6)]
4/9/2014 10
One Linear List Per Row (Linked)
null
3 3 5 4
00304 null
3 5 4 7
00570
00000 nul
02600 l
null
2 2 3 6
row[]
Similar:
4/9/2014
one list per column 11
Orthogonal Lists
1 3 3 1 5 4
n n
00304
00570 2 3 5 2 4 7
n
00000
02600 nul
l
4 2 2 4 3 6
n n n
Variation: row[]lists
use circular
4/9/2014 12
#include <iostream>
#include <string>
typedef char * CString;
typedef CString* TJaggedArray;
//typedef char** TJaggedArray;
void readStrings(TJaggedArray& strs)
{
int n;
char myStr[200];
std::cin >> n;
strs = new CString[n+1];
strs[n]=NULL;
for(int i=0; i<n;i++){
std::cin >> myStr;
strs[i]=new char[strlen(myStr)+1];
strcpy(strs[i],myStr);
}
}
void printStrings(const TJaggedArray& strs)
{
for(int i = 0; strs[i] != NULL ; i++) {
std::cout << strlen(strs[i]) <<" : " << strs[i] << std::endl;
}
}
Tree
1
Tree
Free tree (graph theory)
• any two vertices are connected
• no cycles
Rooted tree
• + root : one of the nodes is distinguished from the others
Ordered tree (most used in computer science)
• is a rooted tree in which the children of each node are ordered
if a node has k children, then there is a first child, a second
child, . . . , and a k-th child
Data Structure rooted, ordered tree
(for us, by default)
2
Tree
recursive definition
Tree:
is empty
or it has a root r and 0 or more sub-trees
Properties:
• Each node has exactly one “predecessor” – its parent
• has exactly zero, one or more “successors” – its children
3
Trees
• root
• parent , children, sibling
• ancestor , descendants
• leaves , internal
• depth (level) , height
• degree
4
Tree
Node degree – the number of descendants
Node depth (level)
• the length of the path to the root
• root – depth 0
Node height:
• the longest path from that node to a leaf (of the tree)
• (equivalent) the height of the subtree having that node as root
If the last edge on the path from the root r of a tree T to a node x is (y, x), then y
is the parent of x, and x is a child of y.
If two nodes have the same parent, they are siblings.
The root is the only node in T with no parent.
A node with no children is a leaf. A non-leaf node is an internal node.
5
k-ary tree
• A k-ary tree – each node have at most k descendants
6
Binary trees
Rooted trees
each node have at most two descendants.
– first descendant is the left descendant
– second descendant is the right descendant
A tree with N nodes has N-1 edges
8
Binary trees
degenerated
perfect
9
Binary trees
10
Binary trees
degenerated
(almost)
complete
11
Binary tree types
Perfect tree:
• all leaves have the same depth
• and all internal nodes have two children
(Almost) complete tree:
• for each level , except possibly the deepest, the nodes have 2
children
• in the deepest level, all nodes are as far left as possible
A degenerate tree
• each parent node has only one child
the tree will essentially behave like a linked list data structure
A balanced binary tree
• no leaf is much farther away from the root than any other leaf
– different balancing schemes allow different definitions of "much farther
12
Binary tree types
(true or false ?)
Perfect tree:
A binary tree with all leaf nodes at the same depth.
All internal nodes have degree 2.
(Almost) complete tree:
A binary tree in which every level, except possibly the deepest,
is completely filled.
At depth n, the height of the tree, all nodes must be as far left
as possible.
http://xlinux.nist.gov/dads
(equivalent definitions)
13
Binary tree properties
1. A tree with N nodes has N-1 edges
(true for any tree)
2. No of nodes in a perfect binary tree with height h is 2h+1-1
3. Maximum no of nodes in a binary tree with height h is 2h+1-1
4. A binary tree with n nodes has height at least [log2 n]
14
Tree representation
15
Tree representation
(A (B (E (K, L) , F) , C (G) , D (H, I, J) ) )
16
Tree representation (1)
Based on recursive definition
• Node root information collection?
list of subTrees
remark: a tree is known by knowing its root
(links to subtrees)
Linked representation (1)
17
Tree representation (1b)
• Sometimes, a link to the parent node is also kept
18
Tree Representation (2)
=> sibling list
Linked
representation (2) 19
Tree traversal
can be traversed in many ways
• depth-first traversal
• breadth-first traversal
on levels
20
Representation (1) & dynamic allocation
TreeNode: record
info: TElement
left: Position
right:Position
end
Position: ^TreeNode
Tree: record
root: Position
end
21
Representation (1) & dynamic allocation
TreeNode: record class TreeNode {
private:
info: TElement TElement info;
TreeNode* left;
left: ^TreeNode TreeNode* right;
right: ^TreeNode public:
end TreeNode(TElement value) {
this->info = value;
left = NULL;
Tree: record right = NULL;
}
root: ^TreeNode …
};
end class BinaryTree {
private:
TreeNode* root;
public:
…
22
Representation (1b) & dynamic allocation
TreeNode: record This representation fits the
recursive definition of binary tree.
info: TElement
For some recursive algorithms,
left: ^TreeNode we are going to use this
right:^TreeNode representation.
end
Tree: ^TreeNode
23
Representation (1) & over arrays
TreeNode: record
info: TElement
left: Integer
right: Integer
end
Tree: record
root: Integer
nodes: array [1..MAX] of TreeNode
// … information needed for freespace management
end
Variations:
• using 3 arrays: Infos, Lefts, Rights
• over a dynamic vector 24
