Transcript Arrays - University of Huddersfield

Introduction to Data Structures
Arrays, Stacks and Queues
What is an Array?
• An array is a data structure used for storing a
collection of data items that are all the same
type.
• By using an array, we can associate a single
variable name with an entire collection of data.
• This enables us to save the entire collection of
data in adjacent cells of main memory and to
easily reference individual items by an Index
number.
• To process an individual item, we need to
specify the array name and indicate which
array element is being manipulated.
Storage comparison
• Using normal variables
5
8
3
6
2
Var1
Var2
Var3
Var4
Var5
• Using an array
Index
5
(0)
8
(1)
3
(2)
6
(3)
2
(4)
MyArray
Array Example 1
Size
0
1
2
3
4
5
6
1.25
6.00
24.9
0.125
56
1.07
125
Declaration
Declare Size(6) as Single
Will allow 7 Single numbers
to be held (0 – 6)
Index
number
Size(0)
1.25
Size(1)
6.00
Size(2)
24.9
Size(3)
0.125
Array Example 2
Name
0
1
2
3
“Bob”
“Sue”
“Ali”
“Jaz”
Declaration
Declare Name(6) as String
Will allow 7 Strings to be
held (0 – 6)
4
5
6
“Udo” “Mick” “Gita”
Name(0)
“Bob”
Name(1)
“Sue”
Name(2)
“Ali”
Name(3)
“Jaz”
Array exercise
We are going to use an array to calculate the average of
a number of integer values that are entered by the user
To do this we must declare the array.
Note - It is important to put a value in the brackets to
give the upper bound index number the array has to
hold. The lower bound number defaults to 0
We are going to accept 10 numbers so we declare the
array:
VAR Number(9) as array of Integers
Set up a loop
We need to set up a loop to ask for ten numbers.
We will use the For structure so that we can stop after
the user enters the tenth number
The code will be:
For x := 1 to 10
Number(X) = Number input by user
End For
For x = 1 to 10
Number(X) = UserNum
Does x = 10?
No
Yes
End
Next Bit
We should now have all the numbers we entered stored
in the array.
The best way to add them up is by creating another loop
to add them together a pass at a time.
Total = 0
For Pass = 1 To 10
Total = Total + Number(Pass)
Next
Finally
We could calculate the average by dividing this total by
ten
Average = Total / 10
Table Look-Up
• A common application of arrays is
to use a value to look up another
value in a table
• For example – find the number of
days in a month given the month’s
number
• The array element numbers are
given on the right – these
correspond to the month number
• Algorithm for look-up
Enter MonthNum
Num_of_Days = Days(MonthNum)
Display Num_of_Days
1
31
2
28
3
31
4
30
5
31
6
30
7
31
8
31
9
30
10
31
11
30
12
31
Sequential Search
• We may not know the element number but know the
value of the element we are looking for
– e.g. when we know someone’s name and want to look them up in the
phone book
• The easiest way to do this would be to search
sequentially through the entire array looking for a
match
Sequential Search Algorithm
X := 1
While SearchName <> Array(X) and X <= ArraySize
X := X + 1
End While
If X < ArraySize
Then Display “Search name not found”
Else Display Array(X)
Binary Search
• A faster method for searching the array is the binary
search method
• This only works if the contents of the array have been
sorted – we will discuss algorithms for sorting later
• This algorithm is a bit more complex than the ones we
have considered so far so I will use three flowcharts
to describe it
• Each flowchart could be translated into a procedure in
the eventual program
Binary Search Flowchart 1 of 3
LB = 1
Enter From
Flowchart
No. 3
UB = N
Flag = 0
No
Does Flag = 0 ?
Go to
Flowchart
No. 2
Yes
R = Int ((LB + UB)/2)
No
Does Array (R) = S
Yes
Flag := 1
Go to
Flowchart
No. 3
Analysis of Flowchart No. 1
LB = 1
UB = N
Flag = 0
Does Flag = 0 ?
R = Int ((LB + UB)/2)
Does Array (R) = S
Flag := 1
The lower boundary is set to 1 (lowest
element number)
The upper boundary is set to the max.
number of elements in the array
The flag is set to 0. It will be set to 1 when the
element is found or 2 if the element could not
be found after an exhaustive search
We will loop whilever the flag is zero – if it
isn’t 0 we go to flowchart 2 to display the
result of the search
The mid-element number is calculated –
we use the Int function to round down.
If the mid-element is not the search term
we go to flowchart 3.
If the mid-element = search term we set
flag to 1 and drop out of the loop
Flowchart No 2 of 3
• We get to this flowchart because the flag is no longer
0 this means we have either found the search term or
failed to find it after an exhaustive search
Does Flag = 2 ?
Yes
No
Display “Search
Term not Found”
Display
“Search Successful”
End
Flowchart No 3 of 3
Is S > Array (R) ?
Yes
No
UB = R - 1
Return to
Flowchart 1
at indicated
entrance point
LB = R + 1
No
Is LB > UB
Yes
Flag := 2
Analysis of Flowchart No 3
• This flowchart how we determine where to look next
• If the search term is bigger (or comes alphabetically
later) than the array element we are currently
considering then the lower boundary is set to one
more than the current element number
• This means that we only consider the elements in the
top-half of the array
• Similarly if the search term is smaller (or comes
alphabetically earlier) than the current array element
we set the upper bound to one less than the current
element number
• This means that we will look for the desired element in
the bottom-half of the array
A Dry Run with the Algorithm
We are searching for 331
The number of comparisons made
will be:
1.
Check element 7 (UB = 13; LB = 1;
Element No = 7)
2.
Check element 10 (UB = 13, LB = 8;
Element No = 10)
3.
Check element 12 (UB = 13; LB = 11;
Element No = 12)
We have found 331 after three
comparisons – compared to the 12 that
would be needed in a sequential search
1
3
2
12
3
23
4
30
5
31
6
40
7
41
8
62
9
98
10
131
11
230
12
331
13
341
Parallel Arrays
Joe Bloggs
• We can store multiple pieces of
related information across a
number of parallel arrays
Bill Smith
Emily Wade
• For example - Student No. 3 has
the name Emily Wade, lives at 12
Saxton Gardens and is aged 23
12, Charlton Road
23, Brander Road
Tony Blair
Harry Truman
43
54
12, Saxton
Gardens
10 Downing Street
23
14, Sandon Grove
12
52
Multidimensional Arrays
• We can work with arrays of arrays
• So if we want to hold data for 10 homework scores
for 15 students we can create a structure like this:
•And refer to elements in the structure like this:
ClassHomework (3,2)
•To find the mark that student number 3 has been awarded
for homework number 2
Stacks
A Special Type of Array
What is a stack?
• An ordered collection of
homogeneous items.
• Like a stack of coins
We need algorithms
to add things to the
stack and to take
things off it
Stack Specification
• Procedures to be carried out on
stacks
– Push
»Add something to the stack
– Pop
»Take something off the stack
Algorithm for Pushing
If we assume an array called “MyStack” and a variable
called “Top” that holds the index of the last data item
pushed on to the stack
Obtain data item X
IF stack is full
THEN reply (“Unable to Push”)
ELSE Top := Top + 1
MyStack(Top) := X
Reply (“X has been pushed onto stack”)
ENDIF
Algorithm for Popping
IF stack is empty
THEN reply (“Unable to Pop”)
ELSE X := MyStack(Top)
Top := Top -1
Reply (“X has been obtained from the stack”)
ENDIF
Exercise: recognizing palindromes
• A palindrome is a string that reads the same
forward and backward.
Able was I ere I saw Elba
• Develop an algorithm to push this line of text a
character at a time onto a stack and then pop it to
reverse the string for comparison purposes
• Would your algorithm work for a palindrome like
this:
Stella won no wallets.
Interesting application of a stack
When you were at school
You were taught BODMAS or some other way of
remembering that:
Arithmetic Calculations are done in a particular order.
Work out contents of Brackets
Work out Orders, e.g. R2
Work out Divisions and or Multiplications
Work out Additions and/or Subtractions
Why is it important?
Programming languages follow the same rules as we
have just seen. It is called Arithmetical Syntax or the
order of calculation.
Imagine this situation.
A customer orders two items costing £20 and £80
We need to calculate the VAT at 17.5%
So we write a line that says VAT = 20 + 80 * 17.5%
This will give us a VAT of £34 which is too much
What went wrong?
It came to £34 by working out the VAT on £80 (£14) then
adding the £20 because multiplication occurs before
addition.
We should ensure that the two prices are added
together before the VAT is calculated by enclosing the
two figures in brackets.
The correct line should be:
VAT = (20 + 80) * 17.5%
This will give £17.50 which is correct
Another example
Work out the average of 3, 7, 9 and 5
Average = 3+7+9+5/4
This gives 20.25 – wrong again
It has divided 5 by 4 first as division comes before
addition in the rules.
We should have written
Average = (3+7+9+5)/4
This gives an answer of 6 which is correct.
Expressions represented this way are known as
infix expressions
Postfix Expressions
• Postfix notation is an alternative way of writing
arithmetic expressions.
• In postfix notation, the operator is written after the
two operands.
infix: 2+5
postfix: 2 5 +
• Expressions are evaluated from left to right.
• Precedence rules and parentheses are never
needed!!
Handling Postfix Expressions
An Algorithm using Stacks
WHILE more input items exist
Get an item
IF item is an operand
stack.Push(item)
ELSE
stack.Pop(operand2)
stack.Pop(operand1)
Compute result
stack.Push(result)
stack.Pop(result)
END IF
Another Application
• Another application of the stack data structure is the
history in a web browser
• Each time a user visits a new web page the address of
the page the user is leaving is pushed onto the top of a
stack
• Thus the stack ends up containing all the pages the
user has previously visited
• When the user eventually clicks on the back button an
address is popped off the top of the stack and the
browser navigates to that address
• The address popped off will be the one the user has
most recently visited
An Illustrative Example
• Use a stack to reverse a string of text entered by a
user.
• The string should have a maximum length of 500
characters.
• The reversed string should be displayed on the
screen.
Possible Algorithm
MakeSureStackisEmpty;
Obtain string from the user;
While there are still characters in the string do
Read a character;
Push it on to the stack
Move to next character
EndWhile
While there are characters on the stack do
Pop a character from the stack;
Write it to the screen
EndWhile
Possible Pascal Code
Data Declarations
program ReverseStringwithStack;
uses crt;
const maxstacksize = 500;
type
stack = record
elements: array[1..maxstacksize] of char;
NumItemsOnStack : integer;
end;
var
thestack: stack;
i: integer;
ch : char;
Possible Pascal Code
Procedures
procedure startstack;
begin
thestack.NumItemsOnStack := 0;
end;
procedure push;
begin
with thestack do
begin
if NumItemsOnStack = maxstacksize then
writeln('**ERROR** Trying to place element on full stack!')
else
begin
NumItemsOnStack := NumItemsOnStack + 1;
elements[NumItemsOnStack] := ch;
end;
end;
end;
Possible Pascal Code
Procedures
procedure pop;
begin
with thestack do
begin
if NumItemsOnStack = 0 then
writeln('**ERROR** Trying to remove element from empty
stack!')
else
begin
ch := elements[NumItemsOnStack];
NumItemsOnStack := NumItemsOnStack -1;
end;
end;
end;
Possible Pascal Code
Main Body
begin
clrscr;
startstack;
write('Enter a string: ');
while ch <> #10 do
begin
read(ch);
push;
end;
writeln;
writeln;
write('The string reversed is: ');
while thestack.NumItemsOnStack <> 0 do
begin
pop;
write(ch);
end;
end.
Two Example Outputs
Queues
What is a queue?
• An ordered group of homogeneous items of
elements.
• Unlike stacks queues have two ends:
– Elements are added at one end.
– Elements are removed from the other end.
• The element added first is also removed
first
– FIFO: First In, First Out
Enqueue
• Function: Adds newItem to the rear of
the queue.
• Preconditions: Queue is not full.
• Postconditions: newItem is at rear of
queue.
Dequeue
• Function: Removes front item from
queue
• Preconditions: Queue is not empty.
• Postconditions: Front element has been
removed from queue
Applications of Queues
• Queues are useful in any situation where a client’s
demands for services can exceed the rate at which
those services can be supplied
• For example in a local area network where a number
of computers share a printer or communications
channel
Review Questions
•
•
•
•
What is meant by an array element?
Why are stacks called LIFO structures?
What is infix notation and prefix notation?
Why are queues called FIFO structures?
Review Question
Trace the following pseudocode showing the contents of the stack
after each invocation:
Declare MyStack as Stack
MyStack.Push (“1”)
MyStack.Push (“2”)
MyStack.Push (“3”)
MyStack.Push (“4”)
MyStack.Pop
MyStack.Pop
MyStack.Push (“5”)
MyStack.Push (“6”)
MyStack.Pop
MyStack.Pop
MyStack.Pop
MyStack.Pop