Transcript Introduction To Programming Course

Basic Data
Structures
Lists, Stacks, Queues, Trees, Hash Tables
Contents
• Abstract Data Types (ADT)
• Lists – ArrayList Class
• Stacks – Stack Class
• Queues – Queue Class
• Trees – Terminology and Types
• Dictionaries – HashMap Class
Abstract Data Types
• An Abstract Data Type (ADT) is a data type
together with the operations, whose
properties are specified independently of any
particular implementation
• ADT are set of definitions of operations (like
the interfaces in Java)
• Can have several different implementations
• Different implementations can have different
efficiency
Basic Data Structures
• Linear structures
• Lists: Variable-size
• Stacks: LIFO (last in first out) structure
• Queues: FIFO (first in first out) structure
• Trees
• Dictionaries (maps)
• Contain pairs (key, value)
• Hash tables: Unordered lists which use a
‘hash function’ to insert and search
What Is a List?
The List ADT
• List is linear data structure (container) that
contains a sequence of elements (objects)
• Has variable size
• Objects are arranged linearly
• Can be implemented in several ways
• Statically (using array)
• Dynamically (linked implementation)
• Using the ArrayList class
Static and Linked Lists
Static List
• Implemented by an array
• Provide direct access by index
• Usually has limited capacity
• Resizing is slow operation
• Slow insert and deletion
L
0
1
11
7
2
3
18 14
4
5
5
2
6
7
8
33 47 3
Linked List
• Dynamic (pointer-based) implementation
• Different forms
• Singly-linked and doubly-linked
• Sorted and Unsorted
• Singly-linked List - each “Object” has
“value” and “next” fields
head
11
7
18
14
next
next
next
next
null
Linked List (2)
• Doubly-linked List - each “Object” has
“value”, “next” and “prev” fields
tail
head
null
11
7
18
next
next
next
14
next
prev
prev
prev
prev
null
Using the
ArrayList class
The java.util.ArrayList
Class
• Implements the list data structure using an
array whose size is dynamically increased
as needed
• Allocates in advance buffer space for new
elements (for better performance)
• Insertion methods:
• add(Object) – adds an object at the end
• add(index, Object) – inserts an object to
the list at a specified position
• size() – returns the number of elements
The ArrayList Class
• Deletion methods:
• remove(Object) – removes the first
occurrence of a specific object
• remove(index) – removes the element at the
specified position
• clear() – removes all elements
• Other supported methods:
• contains(), toArray()
The ArrayList Class(2)
• ArrayList can contain any data type
• Elements are added directly
List list = new ArrayList();
list.add(5); // Add integer value
list.add("some string"); // Add string value
• Typecasting is required when extracting
elements unless we use Generics
int firstElement =
((Integer)(list.get(0))).intValue();
String secondElement = (String)list.get(1);
• Converting to array
Integer[] arr = list.toArray(new
Integer[list.size()]);
What are Generics
• Generics are classes or interfaces that can
be instantiated with a variety of types
• They have 1 or more formal type parameters
• When using a generic you specify an actual
type
Specifies that String is actual
type of this List
List<String> list = new ArrayList<String>();
String s = new String("li1");
5 is not a
list.add(s);
String
list.add(5); // This will cause compile time error
Primes[n..m] – Example
• Find all prime numbers in a specified interval
public static ArrayList<Integer>
getPrimes(int start, int end) {
List<Integer> primesList =
new ArrayList<Integer>();
for (int num = start; num <= end; num++) {
boolean prime = true;
for (int div = 2; div <= Math.sqrt(num); div++) {
if (num % div == 0) {
prime = false;
break;
}
}
if (prime) {
primesList.add(num);
}
}
return primesList;
}
Primes[n..m]
Live Demo
Union and Intersection of Lists
– Example
public static Integer[] union(Integer[] firstArr,
Integer[] secondArr) {
List<Integer> union = new ArrayList<Integer>();
for (Integer item : firstArr) {
union.add(item);
}
for (Integer item : secondArr) {
if (!union.contains(item)) {
union.add(item);
}
}
}
return union.toArray(new Integer[union.size()]);
//Example continues...
Union and Intersection of Lists
– Example(2)
public static Integer[] intersect(Integer[] firstArr,
Integer[] secondArr) {
List<Integer> intersect =
new ArrayList<Integer>();
for (Integer item : firstArr) {
if (Arrays.binarySearch(secondArr, item) >= 0) {
intersect.add(item);
}
}
}
return intersect.toArray(
new Integer[intersect.size()]);
Union and Intersection
Live Demo
What is a Stack?
The Stack ADT
• LIFO (last in first out) structure
• Elements inserted (push) at “top”
• Elements removed (pop) from “top”
• Can be implemented in several ways
• Statically (using array)
• Dynamically (linked implementation)
• Using the Stack class
Static Stack
• Array-based (static) implementation
• Usually has limited capacity
• Has top variable, pointing to the top
• IsEMPTY(S)
• Check if S.top = -1
S
0
1
11
7
2
3
18 14
top
4
5
6
7
8
Linked Stack
• Dynamic (pointer-based) implementation
• Each “object” has “value” and “next” fields
• Dynamically create and delete objects
11
7
18
14
next
next
next
next
null
top
Using the Stack class
The Stack Class – Overview
• Implements the stack data structure using an
array whose size is dynamically increased as
needed
• Major methods:
• push(object) – inserts elements to the
stack
• pop() – removes and returns the top element
from the stack
• peek() – returns the top element of the stack
without removing it
The Stack Class – More
Methods
• Other methods:
• size() – returns the number of elements
• clear() – removes all elements
• contains(object) – determines whether
given element is in the stack
• toArray() – converts the stack to array
Using the Stack class
Examples
Stack – Example
• Using push(), pop() and peek() methods
public static void main(String[] args) {
Stack<String> stack = new Stack<String>();
stack.push("1.
stack.push("2.
stack.push("3.
stack.push("4.
Ivan");
Nikolay");
Maria");
George");
System.out.println("Top = " + stack.peek());
while (stack.size() > 0) {
String personName = stack.pop();
System.out.println(personName);
}
}
Using the Stack class
Live Demo
Matching Brackets – Example
• We are given an arithmetical expression with
brackets that can be nested. We want to
extract all parts of the expression that are
closed in brackets.
• Example: 1 + (3 + 2 - (2+3) * 4 - ((3+1)*(4-2)))
• Result:
•
•
•
•
•
(2+3)
(3+1)
(4-2)
((3+1)*(4-2))
(3 + 2 - (2+3) * 4 - ((3+1)*(4-2)))
Matching Brackets – Solution
with a Stack
String expression =
"1 + (3 + 2 - (2+3) * 4 - ((3+1)*(4-2)))";
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < expression.length(); i++) {
char ch = expression.charAt(i);
if (ch == '(') {
stack.push(i);
} else if (ch == ')') {
int startIndex = (int) stack.pop();
String contents =
expression.substring(startIndex, i + 1);
System.out.println(contents);
}
}
Matching Brackets
Live Demo
What is a Queue?
The Queue ADT
•
•
•
•
FIFO (first in first out) structure
Elements inserted at tail (enqueue)
Elements removed from head (dequeue)
Useful in many situations
• Processing jobs, print queues, messages
• Can be implemented in several ways
• Statically (using array)
• Dynamically (using pointers)
• Using the LinkedList class
Static Queue
• Static (array-based) implementation
• Queue has limited (fixed) capacity
• Implement as a “circular array”
• Maintain Q.Capacity and Q.Length
• Has head and tail variables, pointing
to the head and the tail
0
Q
1
2
3
4
5
11
7
18 14
head
6
7
tail
8
Linked Queue
• Dynamic (pointer-based) implementation
• Each “object” has “value” and “next” fields
• Dynamically create and delete objects
11
7
18
14
next
next
next
next
null
head
tail
Using the LinkedList class
The LinkedList Class –
Overview
• Implements the queue data structure using
a doubly-linked list
• Major methods:
• offer(object) – adds an object to the
end of the queue
• poll() – removes and returns the object at
the beginning of the queue
• peek() – returns the object at the
beginning of the queue without removing it
The LinkedList Class – More
Methods
• Other methods:
• size() – gets the number of elements
contained in the queue
• clear() – removes all elements from the
queue
• contains(object) – determines whether
given element is in the queue
• toArray() – converts the queue to array
Using the
LinkedList class
Examples
Queue – Example
• Using offer() and poll() methods
public static void main(String[] args) {
Queue<String> queue = new LinkedList<String>();
queue.offer("Message
queue.offer("Message
queue.offer("Message
queue.offer("Message
queue.offer("Message
One");
Two");
Three");
Four");
Five");
while (queue.size() > 0) {
String msg = queue.poll();
System.out.println(msg);
}
}
Using the
LinkedList class
Live Demo
Sequence N, N+1, 2*N
• We are given the sequence:
+1
+1
+1
S = N, N+1, 2*N, N+2, 2*(N+1), 2*N+1, 4*N, ...
*2
*2
*2
• Write a program to find the first index of
given number P
• Example: N = 3, P = 16
S = 3, 4, 6, 5, 8, 7, 12, 6, 10, 9, 16, 8, 14, ...
Index of P = 11
Sequence – Solution
int n = 3;
int p = 16;
Queue<Integer> queue = new LinkedList<Integer>();
queue.offer(n);
int index = 0;
while (queue.size() > 0) {
index++;
int current = queue.poll();
if (current == p) {
System.out.println("Index = " + index);
return;
}
queue.offer(current + 1);
queue.offer(2 * current);
}
Sequence N, N+1, 2*N
Live Demo
What is Tree?
Definition, Types of Trees
Trees
• Terminology
• Node, edge, root, child, children, siblings,
parent, ancestor, descendant, predecessor,
successor, internal node, leaf, depth, height
Depth 0
17
Height = 2
9
6
15
14
5
8
Depth 1
Depth 2
Binary Trees
• Binary trees: most used form
• Each node has at most 2 children
“root”
“right child”
“left subtree”
17
9
6
15
5
8
10
“left child”
Binary Trees Traversals
• Traversal can be done in pre-order, in-order
and post-order
17
9
6
19
12
25
• Pre-order: left, root, right – 6, 9, 12, 17, 19, 25
• In-order: root, left, right – 17, 9, 6, 12, 19, 25
• Post-order: left, right, root – 6, 12, 9, 25, 19, 17
Binary Search Trees
• Binary search trees are ordered
• A binary tree in which binary-search-tree
property holds:
• For each node x in the tree
• All the elements of the left subtree of x are ≤ x
• All the elements of the right subtree of x are >
x
• Binary search trees can be balanced
• Balanced trees has low height
Binary Search Trees
• Example of binary search tree
17
9
6
19
12
25
• If the tree is balanced, adding, searching, and
deletion operations take approx. log(n) steps
What is a
Dictionary (Map)?
The Dictionary (Map) ADT
• The ADT "dictionary" maps key to values
• Also known as "map" or "associative array"
• Contains a set of (key, value) pairs
• Dictionary ADT operations:
• ADD(key, value)
• FIND_BY_KEY(key)  value
• DELETE(key)
• Can be implemented in several ways
• List, array, hash table, balanced tree, ...
What is a Hash
Table?
Hash Table
• A hash table is an array that holds a set of
(key, value) pairs
• The process of mapping a key to a position
in a table is called hashing
T
0
1
2
3
4
5
m-1
...
... ...
...
...
...
...
h(k)
Hash Functions and Hashing
• A hash function maps keys to positions
• It is denoted by h
• The hash table has m slots, indexed from 0
to m-1
• For any value k in the key range and some
hash function h
h(k) = i
0i<m
T
0
1
2
3
4
5
m-1
...
... ...
...
...
...
...
h(k)
Mapping Functions
• Perfect hashing function (PHF)
• h(k) : one-to-one mapping from each key k to
integers in [0, m-1]
• The PHF maps each key to a distinct integer
within some manageable range
• Finding a perfect hashing function is in most
cases impossible
• More realistically
• Hash functions h(k) map most of the keys
onto unique integers, but not all
Collisions in Hash Tables
• Collision is the situation when different keys
can have the same hash value
h(k1) = h(k2) for k1 ≠ k2
• When the number of collisions is sufficiently
small, the hash tables work quite well (fast)
• Several collisions resolution strategies
• Chaining in a list, re-hashing, using the
neighboring slots (linear probing), ...
Collision Resolution - Chaining
h("Pesho") = 4
h("Kiro") = 2
h("Mimi") = 1
h("Ivan") = 2
0
T
chaining
h("Lili") = n-1
collision
1
2
null
3
4
null
Mimi Kiro
null
Ivan
null
5
null
n-1
...
Pesho
Lili
null
null
Using the
HashMap class
The HashMap Class – Overview
• Implements the ADT dictionary as array
dynamically increased as needed
• Contains a collection of key-and-value pairs
arranged by the hash code of the key
• Collisions are resolved by chaining
• The HashMap class relies on
• Object.hashCode() method for calculating
the hash codes of the elements
• Object.equals() method for comparing
elements
The HashMap Class – Major
Operations
• Major operations:
• put(key, value) – adds an element with
the specified key and value into the hash
table
• remove(key) – removes the element with the
specified key from the hash table
• get(key) – returns element by key
• clear() – removes all elements from the
hash table
The HashMap Class – More
Operations
• More operations:
• size() – returns the number of elements
• containsKey(key) – determines whether
the hash table contains given key
• containsValue(value) – determines
whether the hash table contains given value
• keySet() – returns a set of the keys
• values() – returns a collection of the values
Using the HashMap Class
Examples
Hashtable - Example
Map<String, Integer> studentsMarks =
new HashMap<String, Integer>();
studentsMarks.put("Ivan", 4);
studentsMarks.put("Peter", 6);
studentsMarks.put("Maria", 6);
studentsMarks.put("George", 5);
int peterMark = studentsMarks.get("Peter");
studentsMarks.remove("Peter");
System.out.println("Is Peter in the hash table: "
+ studentsMarks.containsKey("Peter"));
for (Map.Entry<String, Integer> studentMark :
studentsMarks.entrySet()) {
System.out.printf("%s --> %d%n",
studentMark.getKey(), studentMark.getValue());
}
Using the HashMap Class
Live Demo
Counting Words in a Text
String s = "Welcome to our Java course. In this "
+ "course you will learn how to write simple "
+ "programs in Java";
String[] words = s.split("[ ,.]");
Map<String, Integer> wordsCount =
new HashMap<String, Integer>();
for (String word : words)
if (!"".equalsIgnoreCase(word)) {
int count = 1;
if (wordsCount.containsKey(word))
count += wordsCount.get(word);
wordsCount.put(word, count);
}
for (String word : wordsCount.keySet())
System.out.printf("%s --> %d%n", word,
wordsCount.get(word));
Counting Words in a Text
Live Demo
Summary
• ADT are defined by list of operations
independent of the implementation
• The basic data structures in the computer
programming are
• List – ArrayList class in Java
• Stack – Stack class in Java
• Queue – LinkedList class in Java
• Trees – can be binary, balanced, search trees,
etc.
• Dictionaries – HashMap class in Java
Basic Data Structures
Questions?
Exercises
1. Write a program that reads from the console a
sequence of positive integer numbers. The
sequence ends when the number 0 is entered.
Calculate and print the sum and average of the
elements of the sequence. Use the ArrayList
class.
2. Write a method that finds the longest
subsequence of equal numbers in given array.
Use the ArrayList class.
3. Write a program that reads N integers from the
console and reverses them using a stack. Use
the Stack class.
Exercises (2)
4. We are given the following sequence:
S1 = N;
S2 = S1 + 1;
S3 = 2*S1 + 1;
S4 = S1 + 2;
S5 = S2 + 1;
S6 = 2*S2 + 1;
S7 = S2 + 2;
...
Write a program to print its first 100 elements
for given N. Use the LinkedList class.
Example: N=2
Sequence: 2, 3, 5, 4, 4, 7, 5, 6, 11, 7, 5, 9, 6, ...
Exercises (3)
5. Write a program that reads a sequence of
integers ending with 0 and sorts them in an
increasing order. Use the ArrayList class.
6. Write a program that finds in a given array of
integers how many times each of them
presents. Use HashMap and ArrayList.
Example: array = {3, 4, 4, 2, 3, 3, 4, 3, 2}
2  2 times
3  4 times
4  3 times
Exercises (4)
7. Write a program that removes from a given
sequence all negative numbers.
8. Write a program that removes from a given
sequence all the numbers that present in it
odd number of times. Example:
{4, 2, 2, 5, 2, 3, 2, 3, 1, 5, 2}  {5, 3, 3, 5}
9. By definition the majorant of an array is a
value that occur in the least half of the
elements of the array. Write a program to find
the majorant of given array (if any). Example:
{2, 2, 3, 3, 2, 3, 4, 3, 3}  3
Exercises (7)
10. Write a program that counts how many times
each word from a given text presents in it. The
casing differences should be ignored. The
result words should be ordered by their
number of occurrences in the text. Example:
This is the TEXT. Text, text, text – THIS TEXT!
Is this the text?
is  2
the  2
this  3
text  6
Exercises (5)
11. We are given numbers N and M and the
following operations:
a) N = N+1
b) N = N+2
c) N = N*2
Write a program that finds the shortest
sequence of operations from the list above
that starts from N and finishes in M
•
Example: N = 5, M = 16
•
Sequence: 5  7  8  16
Exercises (6)
12. We are given a labyrinth of size N x N. Some of
its cells are empty (0) and some are full (x). We
can move from an empty cell to another empty
cell if they share common wall. Given a
starting position (*) calculate and fill in the
array the minimal distance from this position
to any other cell in the array. Use "u" for the
unreachable cells. Example:
0
0
0
0
0
0
0
x
*
x
0
0
0
0
x
0
0
0
x
x
0
0
x
x
0
0
x
0
x
0
x
x
0
0
0
x
3
2
1
2
3
4
4
x
*
x
4
5
5
6
x
6
5
6
x
x
8
7
x
x
u x
u x
x 10
8 9
x 10
u x