Transcript Data Structures

Data Structures
Grade 12
Computer Studies HG
Data Types
An important concept in most
programming languages is that of data
types
 Each variable or attribute that is declared
needs an associated type
 A type identifies a certain set or
collection of values that a variable can
store

Type Examples

For instance if we want to store counting numbers we
could declare a variable of type int
 We do this because the int (or integer) data type can
store any whole number from -2,147,483,648 to
2,147,483,647
 Another example is if we wanted to represent whether
someone is married or not we could declare a variable
of type boolean
 We choose boolean because we can store two values
with a boolean (true or false) which is all we need in
this particular case
Java numeric data types

Java has the following data types:
byte
 short
 int
 long
-128 to 127
-32768 to 32767
-2,147,483,648 to 2,147,483,647
-9,223,372,036,854,775,808 to
9,223,372,036,854,775,807
 float
1.4 x 10-45 to 3.4 x 1038
 double4.9 x 10-324 to 1.7 x 10308
 char
any unicode character

Strings






The type String in Java is not really one of the basic
data types
The type String is actually a class in Java
This class has the necessary attributes and methods
to manipulate a String object e.g. substring(), length(),
charAt()
The designers of Java made an exception in the case
of Strings – you don’t have to declare a new string
object as you would with other objects.
String myStr = “Hello World”; // this is fine
String myStr = new String(); // this is also fine
Dynamic Variable Declaration

Programming languages that support dynamic
variable declaration can have variable
declarations anywhere in the program
 Java supports this type of variable declaration
 You can have the line int num1; anywhere in
your program so long as it is in scope when it
is needed
 In other words the only restriction for
declaration is that the variable is visible when
it is needed
Static Variable Declaration
Believe it or not some languages don’t
use dynamic declaration like Java does
 Instead all variables need to be declared
in a predefined section of the code.
 This section is usually above all other
code and all variables need to be
declared in that section

The need for multi-valued variables





Sometimes we need to store a collection of data of the
same type
Often having a separate variable for each value is
cumbersome
For instance if we wanted to store the temperature for
everyday in June we don’t want to declare 30 separate
variables (temp1, temp2… temp30)
The ideal situation would be to have one variable that
could store 30 values such that we can choose which
value we want to retrieve or store/change
Luckily most programming languages provide us with
this feature.
Arrays 1





An array is one variable
The array can store as many data items as
the programmer chooses
Each data item must be of the same type
(homogenous)
Every data item is stored separately in the
array
We can specify the location of the data item
we want to change or look at
Arrays 2

We can represent an array called fiveInt of 5 integers
as follows:
position



23
34
6
56
72
0
1
2
3
4
The data in position 2 is the number 6 and the data in
position number 4 is 72
Notice how the numbering of the positions starts
at 0 and ends at 4
So even though the array has 5 data items there is no
position 5 in the array
Arrays 3

We can represent an array called myStrings of
4 Strings as follows:
“dog” “cat”
position
0
1
null
“frog”
2
3
The data in position 0 is the word “dog” and
the data in position number 3 is “frog”
 Position 2 has a null value. Note that this is not
the word “null” but a way of indicating that the
2nd position in the array is empty

Arrays in Java 1

Arrays are declared in a similar way to
normal integers:
int[] myArray = new int[4];
An array of int’s
allocates memory
holds 4 items
called myArray
Arrays in Java 2

The array from the following slide can be
filled with values as follows:
myArray[3]
myArray[1]
myArray[0]
myArray[2]
=
=
=
=
Position in the array
to place the data
34;
23;
87;
33;
The int’s to place in
each position
Arrays in Java 3

We can use the values in the arrays as
follows:
myArray[0] = myArray[2] + 34 * 69;
adds the data in position 2 to 34 * 69 and stores
the result in position 0
System.out.println(myArray[0]);
prints out the value of the integer in position 0 of
the array (that is 2433)
Arrays in Java 4

Why would the following lines of code
not work with the previously declared
array?
myArray[4] = 78;
myArray[0] = “bob”;
myArray = 45;
Can you correct the lines?
Static Structures






Arrays are static data structures because their size is
determined when the code is being written
The size of the array cannot be changed during the
execution of the program
If we declare an array of 12 integers then once the
program starts running we cannot store any more than
12 integers in the array
Once memory has been allocated for the array it is
fixed during execution of the program
Static data structures are like hose-pipes. If you get a
bigger garden then too bad. Buy a new hose-pipe!
Static means motionless or inactive
Dynamic Data Structures





These data structures can change size during
execution of a program
Dynamic data structures grow and shrink as
required by the program
The size of the structure is determined during
run-time
Dynamic data structures are like KreepyKrauly pipes. Getting a bigger pool? Just add
more pipes :)
Dynamic means active or changing
Example

If we wanted to write a school database and
we wanted to declare a structure to store
Student objects what size would we make it?



Option 1 – 1300? This is fine but what if we get
more students next year?
Option 2 – 5000? This is way too big. We might
never get that many students
Option 3 – Dynamic Data Structure. Perfect this
would grow and shrink depending on the amount of
data items needed
The story so far…

We’ve looked at the basic data types in Java





We’ve looked at the sizes of data structures


int, float, double, byte, long
char
String
Arrays of all of the above
Static and Dynamic
In the next episode of Data Structures

Advanced Data Types (ADT’s)
Advanced Data Types (ADT’s)
ADT’s provide us with extra functionality
in programming languages.
 Some ADT’s come standard with Java
and others need to be implemented by
the programmer. Either way they are
fairly complex to code.
 The ADT’s that we will examine are the
most widely used ADT’s in programming.

Lists

Lists are everyday occurences.





Telephone directories
Shopping lists
To Do lists
Class lists
Definition: A list is a sequence of items of
the same type
 Ordered lists have their items in a predefined
order. i.e. Alphabetically or numerically
 The size of a list is how many items it contains
at any given time
Linked Lists
Linked Lists are a dynamic data structure
 Each item in a linked list is referred to as
a node.
 Each node consists of two parts:

Data (Item) Field – This is the actually data
stored in that position of the list (e.g. “dog”,
23)
 Next Field – Contains a pointer to the next
node in the list

Diagram of a node
34
Data Field
Next Field
Design of a Linked List



Each node is connected to the next node via the
next field of each node.
The first node is indicated by a head node which
contains no data field but only a next field.
The last node’s next field always points to null.
head
45
67
89
99
null
Operations on a Linked List









Create an empty list
Check if list is empty
Get number of items in the list
Copy one list to another list
Traverse the list
Retrieve an item, given it’s position
Search for an item
Insert an item
Delete an item
Adding

We need to be careful when adding items to a linked list
because if we lose a next field of any of the nodes we lose
all nodes after that node.
 5 Steps:
 Create the new node with a pointer to it.
 Find the position where the node is to be inserted (call it
position x).
 Create a temporary pointer to the node after the
position (i.e. the node in position x + 1).
 Make the next field of node (x-1) point to the new item.
 Make the new items next field point to temporary
pointer.
Adding: Step 1
head
45
67
89
99
new
72
null
Adding: Step 2
position x
head
45
67
89
99
new
72
null
Adding: Step 3
temp
head
45
67
89
99
new
72
null
Adding: Step 4
temp
head
45
67
89
new
72
99
null
Adding: Step 5
temp
head
45
67
89
new
72
99
null
Deleting
Deleting is much easier
 2 Steps

Chose the item to be deleted (position x)
 Point the next field of node at (x-1) to the
node after position x (x+1)

Deleting: Step 1
position x
head
45
67
89
99
null
Deleting: Step 2
head
45
67
89
99
null
Stacks





Stacks are data structures that allow data items to
be added and removed at the top only.
For this reason stacks are called LIFO (Last In
First Out) structures because the last item to be
added to the stack is the first item to be removed.
Just like a stack of plates at a restaurant.
Inserting an item at the top of a stack is referred to
as pushing.
Removing an item off the top is referred to as
popping.
Example

Consider the following operations:
push “R”; push “T”; push “Y”; pop; push “J”; pop; pop;
Y
R
J
T
T
T
T
T
R
R
R
R
R
Output: Y J T
R
Stack Operations
Empty the stack
 Check if the stack is empty
 Determine size of the stack
 Look at the top item
 Push
 Pop

Uses of the Stack
Recursion
 Postfix Notation

Queues

Queues are structures that allow data items to
inserted at the rear and removed from the front
only.
 Known as FIFO (First In First Out) structures
because the first item to be inserted into the
queue will be the first item to be removed.
 These queues are no different from the
queues in everyday life (e.g. shopping centers)
Example

Consider the following operations
insert “A”
A
insert “B”
AB
insert “C”
ABC
remove an element
BC
remove an element
C
Output: A B
Uses



Print Queues
Real-life Simulation
Statistics:






Average number of element in queue
Average time spent in queue
Probability that queue will be longer than x
Probability that waiting time will be greater than x
Minimum and maximum length of a queue of a
period of time
Minimum and maximum waiting time over a period
of time
Implementation: Stacks and Queues

Option 1: Using arrays
Programmer has to keep track of where the
front (top) and rear of the structure is.
 Only homogenous items can be stored
 FIXED SIZE! Queues and stacks grow and
shrink during execution


Option 2: Using a dynamic structure

Linked list!
Trees
In a tree each node may have one or
more next field.
 This results in a tree-like structure.

N
F
E
Q
G
T
Naming Conventions
Root Node – The first node
 Child Node – Node beneath another
node (each node has only one parent)
 Parent Node – A node with nodes
beneath it
 Leaf Node – Nodes with no children
 Siblings – Adjacent nodes

Naming Conventions
Root node and parent of
F and Q
N
Sibling of Q
F
E
Child node of N and
Parent of T
Q
G
T
Leaf node
Binary Trees

Binary trees are trees in which each node may
have at most two sub trees. These are called
left and right sub trees.
 Each node has three elements:




Data (Item Field)
Left Pointer
Right Pointer
The left children of a parent always have
smaller values than their parents.
 The right children of a parent always have
larger values that their parents.
Example

Insert the following into a binary tree:
50, 34, 12, 78, 36, 30, 67, 44, 52

Insert the following into a binary tree:
N, A, Y, T, F, D, S, R, R
Binary Tree Traversal

Pre-Order




In-Order




Visit the root
Traverse the left sub-tree in pre-order
Traverse the right sub-tree in pre-order
Traverse the left sub-tree in in-order
Visit the root
Traverse the right sub-tree in in-order
Post-Order



Traverse the left sub-tree in post-order
Traverse the right sub-tree in post-order
Visit the root
Examples
Traverse both previous trees in in-order,
pre-order and post-order.
 What do you notice about in-order
traversals?

Uses
Representing mathematical expressions
 Compilers
 Searching
 Sorting

End