Chapter 6
Using Arrays (Tables)
Programming Logic for Business
Copyright 2001 Laura Saret
Laura Saret EdD
Chapter Outline
 What Is an Array (Table)?
 Example: Array versus Nonarray Processing (PositionallyOrganized Arrays)
 How Do We Put Values into Arrays?
 Example: Arrays in Validation Programs (Compile-Time
Arrays)
 Example: Arrays in Validation Programs (Execution-Time
Arrays)
 What Is the Difference Between a Sequential Search and a
Binary Search?
 Example: Binary Search
 How Do We Work with Multidimensional Arrays?
 Example: Finding Values in Two-Dimensional, ArgumentOrganized Arrays
 Example: Values as Part of a Range
 How Do Various Programming Languages Differ in How They
Work with Arrays?
Chapter Objectives
After completing this chapter you should be able to.…
 Explain the advantages of using arrays.
 Initialize and access entries in one- and twodimensional arrays using sequential and binary
search techniques.
 Indicate when data should be stored in compiletime arrays and when they should be stored in
execution-time arrays.
 Explain how corresponding arrays are used.
 Construct the logic for programs that use
positonally-organized and argument-organized
arrays.
 Discuss some of the differences in how various
programming languages work with arrays.
What Is an Array (Table)?
 A simple variable holds one value
 HEADING1
 EMPLOYEE-NAME
 TEST-SCORE
 COUNTER
 The value of the variable or field
may change during program
execution
 Arrays (also called tables) consist
of several data values maintained
under a common name
 Arrays let you easily manipulate
large amounts of related data
January
February
March
April
May
June
July
August
September
October
November
December
When Using arrays, We Can Refer to
Storage Locations by Their Positions
Third person in line
Second person in line
First person in line
Month-Array
 12 entries or items
 Month-Array refers to all
12 items
 Month-Array(1) refers to
January
 Month-Array(6) refers to
June
 The number in
parentheses is called a
subscript
 Arrays are often called
subscripted variables
January
February
March
April
May
June
July
August
September
October
November
December
Subscripts
 Can be a number (0,1,2,3,4…)
 Can be a field name in which
the content of the field is a
number
 Suppose that Row = 2
 What is Month-Array(Row)?
 Suppose that the month (11) is
entered by the user and stored
in Month-In
 What is Month-Array(Month-In)?
 Suppose the user enters 14 for
the month (Month-In)
 What is Month-Array(Month-In)?
January
February
March
April
May
June
July
August
September
October
November
December
Advantages of Arrays Over
Simple Variables
 No matter how many
values are stored, the
program only needs one
name to refer to the
values
 Program logic can be
shorter and, in many
cases, simpler
 Instead of using separate
field names, loops can be
used to reference the items
in an array
 During each pass of the loop,
the subscript changes
Arrays Require that Programmers
Do 3 Things
 Describe or define the
array
 Reserve storage
 Specify the type of data the
array contains
 Initialize the array
 Put values in array
 Access or lookup entries
 Find entries in array
 Argument-organized versus
positionally-organized arrays
Why Use Arrays?
 Suppose I am using 3 assignment
grades to determine an average
 Average = (Assn1 + Assn2 + Assn3) / 3
 What if the average was based on
25 assignment grades?
 Average = (Assn1 + Assn2 + Assn3 +
Assn4 + Assn5 + Assn6 + Assn7 +
Assn8 + Assn9 + Assn10 + Assn11 +
Assn12 + Assn13 + Assn14 + Assn15 +
Assn16 + Assn17 + Assn18 + Assn19 +
Assn20 + Assn21 + Assn22 + Assn23 +
Assn24 + Assn25) / 25
 What if the average was based on
100 assignment grades?
Calculate Average of 100 Grades
Using an Array
 In Initialize routine
ASSIGN names and initial values in work area
ASSIGNMENT-ARRAY (100 ENTRIES)
SUBSCRIPT = 1
SUM = 0
AVERAGE
 In Calculate routine
LOOP UNTIL SUBSCRIPT > 100
SUM = SUM + ASSIGNMENT-ARRAY (SUBSCRIPT)
SUBSCRIPT = SUBSCRIPT + 1
ENDLOOP
AVERAGE = SUM / 100
 What changes would have to be made to find the average of
1000 grades?
Assignment-Array is
Positionally-Organized
 The subscript that points to the array position is…
 The same as a field in the input or
 The counter in a counter-controlled loop
 The example in 6.2 (page 245) also uses a
positionally-organized array
 The subscript is the same as a field in the input (Stu-No)
 Look at the flowchart on page 249-250
 What does the Build-Array routine do?
 What does this instruction do?
Add Stu-Points
To Points-Array
(Stu-No)
Points-Array is
Positionally-Organized
 Look at the Loop in Terminate
(page 250)
 How many times is Write-ArrayEntry done?
 What is Student?
Write-Array-Entry
Write Student,
Points-Array
(Student)
Add 1 to Student
Return
Do
Write-Array-Entry
Student: 25
>
 Look at Write-Array-Entry
 What is the subscript?
<=
How Do We Put Values into Arrays?
 Execution-time arrays
 Values are put into an array during program execution
 To modify the array, the input value must be changed
 Compile-time arrays
 Values are put into an array when the program is written
 To modify the array, a programmer must change the
program, and it must be retranslated
 Disadvantages
 Programs that use execution-time arrays take longer to
execute than program with compile-time arrays
 Changing a compile-time array requires involving a
programmer
So, Should You Use a Compile-Time
or Execution-Time Array?
 Depends on frequency of changes
 Frequently changed arrays should
be defined as execution-time
 Grocery store prices
 Credit card balances
 Infrequently-changed arrays
should be defined as compile-time
 Mathematical tables
 States and zip codes
Compiletime or
executio
n-time?
Example 6.4 (page 252) Uses an
Argument-Organized,
Compile-Time Array to Validate
Input
 Why is the array argument-organized?
 Why is it compile-time?
CUSTOMER-ARRAY(1) = 14516
CUSTOMER-ARRAY(2) = 12725
CUSTOMER-ARRAY(3) = 12825
CUSTOMER-ARRAY(4) = 16265
CUSTOMER-ARRAY(5) = 17172
CUSTOMER-ARRAY(6) = 18291
CUSTOMER-ARRAY(7) = 12000
CUSTOMER-ARRAY(8) = 11400
CUSTOMER-ARRAY(9) = 14421
CUSTOMER-ARRAY(10) = 13222
CUSTOMER-ARRAY(11) = 12546
CUSTOMER-ARRAY(12) = 18931
CUSTOMER-ARRAY(13) = 19211
CUSTOMER-ARRAY(14) = 17645
CUSTOMER-ARRAY(15) = 11001
CUSTOMER-ARRAY(16) = 11235
CUSTOMER-ARRAY(17) = 11762
CUSTOMER-ARRAY(18) = 11984
CUSTOMER-ARRAY(19) = 11111
CUSTOMER-ARRAY(20) = 12156
Let’s Search
the Array
Raise your hand
when you are
through searching
for customer
11235
Did you find the
customer
number?
Where did you find
it? (What was the
subscript?)
CUSTOMER-ARRAY(1) = 14516
CUSTOMER-ARRAY(2) = 12725
CUSTOMER-ARRAY(3) = 12825
CUSTOMER-ARRAY(4) = 16265
CUSTOMER-ARRAY(5) = 17172
CUSTOMER-ARRAY(6) = 18291
CUSTOMER-ARRAY(7) = 12000
CUSTOMER-ARRAY(8) = 11400
CUSTOMER-ARRAY(9) = 14421
CUSTOMER-ARRAY(10) = 13222
CUSTOMER-ARRAY(11) = 12546
CUSTOMER-ARRAY(12) = 18931
CUSTOMER-ARRAY(13) = 19211
CUSTOMER-ARRAY(14) = 17645
CUSTOMER-ARRAY(15) = 11001
CUSTOMER-ARRAY(16) = 11235
CUSTOMER-ARRAY(17) = 11762
CUSTOMER-ARRAY(18) = 11984
CUSTOMER-ARRAY(19) = 11111
CUSTOMER-ARRAY(20) = 12156
Let’s Search
the Array
Again
Raise your hand
when you are
through searching
for customer
13847
Did you find the
customer
number?
Process
Customer
-Sub
=1
Move
"NO" to
SearchFinished
Do
Look-ForEntry
Search-Finished is given
an initial value before
doing Look-For-Entry
Look-For-Entry must
change Search-Finished
to “YES”. Why?
Entry-Found is given a
value in Look-For-Entry
SearchFinished
"NO"
=?
"YES"
Move
"Customer
EntryNumber
Found =
Invalid" to
"NO"
?
"YES" Error-Message
Do
WriteError
The Program
Uses 2
Indicators
 Look at the
Process routine
on page 254 to
see how the
indicators are
used
 Search-Finished
 Entry-Found
Let’s Look for Customer
Number 12825
CUSTOMER-ARRAY(1) = 14516
CUSTOMER-ARRAY(2) = 12725
CUSTOMER-ARRAY(3) = 12825
CUSTOMER-ARRAY(4) = 16265
CUSTOMER-ARRAY(5) = 17172
CUSTOMER-ARRAY(6) = 18291
CUSTOMER-ARRAY(7) = 12000
CUSTOMER-ARRAY(8) = 11400
CUSTOMER-ARRAY(9) = 14421
CUSTOMER-ARRAY(10) = 13222
CUSTOMER-ARRAY(11) = 12546
CUSTOMER-ARRAY(12) = 18931
CUSTOMER-ARRAY(13) = 19211
CUSTOMER-ARRAY(14) = 17645
CUSTOMER-ARRAY(15) = 11001
CUSTOMER-ARRAY(16) = 11235
CUSTOMER-ARRAY(17) = 11762
CUSTOMER-ARRAY(18) = 11984
CUSTOMER-ARRAY(19) = 11111
CUSTOMER-ARRAY(20) = 12156
Look-For-Entry
Is CustomerArray
(CustomerSub) = AcctNum
no
CustomerSub = 1
SearchFinished =
“NO”
Move "YES"
to Searchyes
Finished
Move "YES"
to EntryFound
Add 1 to
CustomerSub
CustomerSub: 20
>
Move "YES"
to SearchFinished
Move "YES"
to EntryFound
Return
<=
Let’s Look for Customer
Number 12825CUSTOMER-ARRAY(1) =
Look-For-Entry
Is CustomerArray
(CustomerSub) = AcctNum
no
Move "YES"
to Searchyes
Finished
Move "YES"
to EntryFound
Add 1 to
CustomerSub
CustomerSub: 20
>
Move "YES"
to SearchFinished
Move "YES"
to EntryFound
Return
<=
CustomerSub = 2
SearchFinished =
“NO”
14516
CUSTOMER-ARRAY(2) = 12725
CUSTOMER-ARRAY(3) = 12825
CUSTOMER-ARRAY(4) = 16265
CUSTOMER-ARRAY(5) = 17172
CUSTOMER-ARRAY(6) = 18291
CUSTOMER-ARRAY(7) = 12000
CUSTOMER-ARRAY(8) = 11400
CUSTOMER-ARRAY(9) = 14421
CUSTOMER-ARRAY(10) = 13222
CUSTOMER-ARRAY(11) = 12546
CUSTOMER-ARRAY(12) = 18931
CUSTOMER-ARRAY(13) = 19211
CUSTOMER-ARRAY(14) = 17645
CUSTOMER-ARRAY(15) = 11001
CUSTOMER-ARRAY(16) = 11235
CUSTOMER-ARRAY(17) = 11762
CUSTOMER-ARRAY(18) = 11984
CUSTOMER-ARRAY(19) = 11111
CUSTOMER-ARRAY(20) = 12156
Let’s Look for Customer
Number 12825
CUSTOMER-ARRAY(1) = 14516
CUSTOMER-ARRAY(2) = 12725
CUSTOMER-ARRAY(3) = 12825
CUSTOMER-ARRAY(4) = 16265
CUSTOMER-ARRAY(5) = 17172
CUSTOMER-ARRAY(6) = 18291
CUSTOMER-ARRAY(7) = 12000
CUSTOMER-ARRAY(8) = 11400
CUSTOMER-ARRAY(9) = 14421
CUSTOMER-ARRAY(10) = 13222
CUSTOMER-ARRAY(11) = 12546
CUSTOMER-ARRAY(12) = 18931
CUSTOMER-ARRAY(13) = 19211
CUSTOMER-ARRAY(14) = 17645
CUSTOMER-ARRAY(15) = 11001
CUSTOMER-ARRAY(16) = 11235
CUSTOMER-ARRAY(17) = 11762
CUSTOMER-ARRAY(18) = 11984
CUSTOMER-ARRAY(19) = 11111
CUSTOMER-ARRAY(20) = 12156
CustomerSub = 3
SearchFinished =
“NO”
Look-For-Entry
Is CustomerArray
(CustomerSub) = AcctNum
no
Move "YES"
to Searchyes
Finished
Move "YES"
to EntryFound
Add 1 to
CustomerSub
CustomerSub: 20
>
Move "YES"
to SearchFinished
Move "YES"
to EntryFound
Return
<=
The Example in Section 6.5 (page 258)
Uses an Execution-Time Array
 Initialize calls Load-Array to read and store values in the array
 CUSTOMER-SUB is the subscript
 NUMBER-OF-ENTRIES counts the entries in the array
 It is initialized to 1
LOAD-ARRAY
READ an array entry (CUSTOMER-ENTRY)
LOOP UNTIL EOF
MOVE CUSTOMER-ENTRY to
CUSTOMER-ARRAY (CUSTOMER-SUB)
ADD 1 to CUSTOMER-SUB
ADD 1 to NUMBER-OF-ENTRIES
READ an array entry (CUSTOMER-ENTRY)
ENDLOOP
ENDLOAD-ARRAY
Look-For-Entry
Compares
Customer-Sub to
Number-Of-Entries
Instead of 20
Look-For-Entry
Is CustomerArray
(CustomerSub) = AcctNum
no
Move "YES"
to Searchyes
Finished
Add 1 to
CustomerSub
CustomerSub: NumberOf-Entries <=
>
Move "YES"
to SearchFinished
Move "YES"
to EntryFound
Return
Move "YES"
to EntryFound
Binary Search
 We have been doing sequential searches
 Binary searches are faster
Number of
Array Entries
Max. Comp. -Binary Search
Max. Comp.-Seq.Search
Ave. Comp.-Seq. Search
10
4
10
5
50
6
50
25
100
7
100
50
200
8
200
100
500
9
500
250
1,000
10
1,000
500
5,000
13
5,000
2,500
10,000
14
10,000
5,000
100,000
17
100,000
50,000
1,000,000
20
1,000,000
500,000
Prerequisite for Binary Search
 Array elements must be arranged in order
11001
11111
11235
11400
11762
11984
12000
12156
12546
12725
12825
13222
14421
14516
16265
17172
17645
18291
1931
Let’s Look for 12000
Using a Binary Search
Start with the middle entry
12000 is less than 12725
so we eliminate the
“bottom half” of the array
Let’s Look for 12000
Using a Binary Search
11001
11111
11235
11400
11762
11984
12000
12156
12546
Look at the middle entry
12000 is greater than
11762 so we eliminate
the “top half” of the array
Let’s Look for 12000
Using a Binary Search
11984
12000
12156
12546
Look at the middle entry
We found it!!!!
Process
Low-Subscript
=1
Binary
Search
Look-For-Entry
Customer-Sub =
(Low-Subscript +
High-Subscript) / 2
(page 264)
High-Subscript
= 20
<
Move "NO" to
SearchFinished
Acct-Num:
Customer-Array
(Customer-Sub)
=
>
High-Subscript =
Customer-Sub - 1
Low-Subscript =
Customer-Sub + 1
Do
Look-For-Entry
SearchFinished =
?
"NO"
"YES"
EntryFound =
"NO"
?
"YES"
Move "YES" to
Search-Finished
Is Low-Subscript
> HighSubscript? Yes
Move
"Customer
Number
Invalid" to
ErrorMessage
No
Do
Write-Error
Move "YES"
to SearchFinished
Move "NO"
to EntryFound
Return
Move "YES" to
Entry-Found
Working with Multidimensional
Arrays
 The dimension of the array is the number of subscripts
required to access the array
 We have been working with 1-dimensional arrays
 2-dimensional arrays
 The first subscript is the row
 The second subscript is the column
(1,1) (1,2)
(2,1) (2,2)
(3,1) (3,2)
3-Dimensional Array
(1,1,1)
(4,2,1)
(6,3,2)
Weather-Array
Ave. High Temp.Ave. Low Temp.
47
52
62
72
79
87
93
93
84
74
60
50
25
30
39
49
58
67
71
70
62
50
39
29
Ave. Precipitation
1.13
1.56
2.71
2.77
5.22
4.31
2.61
2.60
3.84
3.23
1.98
1.40
Ave. Wind
13.4
14.0
15.1
14.9
13.3
12.4
11.4
10.9
11.7
12.3
13.2
12.9
Sales-Array
Number
12987
29801
29991
30987
44563
48723
56560
57341
59992
60132
Name
Ronald Gupta
Sonal Desai
Miriam Abrams
Carol Burns
Eric Johnson
Peter Legardo
Alison Gaynor
Diana Chin
Michael Cernowitz
Marla Kaplan
What is Sales-Array (1,3)?
What is Sales-Array (4,2)?
What is Sales-Array (8,5)?
Code
2
1
3
4
5
1
3
3
2
4
Sales-Array
Number
12987
29801
29991
30987
44563
48723
56560
57341
59992
60132
Name
Ronald Gupta
Sonal Desai
Miriam Abrams
Carol Burns
Eric Johnson
Peter Legardo
Alison Gaynor
Diana Chin
Michael Cernowitz
Marla Kaplan
Code
2
1
3
4
5
1
3
3
2
4
If you know a salesperson’s number, how
do you find his her or name? How do you
find his or her code?
Sales-Array
Number
12987
29801
29991
30987
44563
48723
56560
57341
59992
60132
Name
Ronald Gupta
Sonal Desai
Miriam Abrams
Carol Burns
Eric Johnson
Peter Legardo
Alison Gaynor
Diana Chin
Michael Cernowitz
Marla Kaplan
Code
2
1
3
4
5
1
3
3
2
4
If the salesperson’s number is in row ROW-SUB,
where is his or her name? Code?
Let’s Look at the Example in
Section 6.9 (page 267)
 How is the array defined? (page 270)
 How is the billing calculated? (page 271)
PROCESS
MOVE 1 to ROW-SUB
MOVE “NO” to SEARCH-FINISHED
LOOP UNTIL SEARCH-FINISHED = “YES”
DO LOOK-FOR-ENTRY routine
ENDLOOP
IF ENTRY-FOUND = “NO” THEN
DO WRITE-ERROR routine
ELSE GROSS-BILLING = BILLING-ARRAY(ROW-SUB,2) *
HOURS-BILLED
DO WRITE-DETAIL routine
ENDIF
READ a record (EMP-NUMBER, EMP-NAME, BILL-CODE,
HOURS-BILLED)
ENDPROCESS
What Happens When Values Are
Part of a Range?
 See example on page 275
Total Points
Grade
370-400
A
360-369
A-
330-359
B
320-329
B-
291-319
C
280-290
C-
251-279
D
240-250
D-
0-239
F
What Happens When Values Are
Part of a Range?
 The array contains the lowest value in each range
 F is not in the array
Total Points
Grade
370-400
A
370
A
360-369
A-
360
A-
330-359
B
330
B
320-329
B-
320
B-
291-319
C
291
C
280-290
C-
280
C-
251-279
D
251
D
240-250
D-
240
D-
0-239
F
What Happens When Values Are
Part of a Range?
LOOK-FOR-ENTRY
IF TOTAL-POINTS >= GRADE-ARRAY
(ROW-SUB,1) THEN
MOVE “YES” to SEARCH-FINISHED
MOVE “YES” to ENTRY-FOUND
ELSE ADD 1 to ROW-SUB
IF ROW-SUB > 8 THEN
MOVE “YES” to SEARCH-FINISHED
MOVE “NO” to ENTRY-FOUND
ENDLOOK-FOR-ENTRY
370
A
360
A-
330
B
320
B-
291
C
280
C-
251
D
240
D-
What does it mean if ENTRY-FOUND is “NO”?
Differences Among
Programming Languages
 Subscripts
 First subscript may be 0 or 1
 Specify range of subscripts
 Sales-Array subscripts ranging from 1980-2000
 Sales-Array(1999)
 Most languages require that all data in an array
contain the same type of data
 An array cannot contain both numbers and nonnumbers
 Use of corresponding arrays
Corresponding Arrays:
Suppose you want to find the code and name for number
44563
Number-And-Code-Array
12987
29801
29991
30987
44563
48723
56560
57341
59992
60132
2
1
3
4
5
1
3
3
2
4
Name-Array
Ronald Gupta
Sonal Desai
Miriam Abrams
Carol Burns
Eric Johnson
Peter Legardo
Alison Gaynor
Diana Chin
Michael Cernowitz
Marla Kaplan
Number-And-Code-Array(5,1) contains 44563
Number-And-Code-Array
12987
29801
29991
30987
44563
48723
56560
57341
59992
60132
2
1
3
4
5
1
3
3
2
4
Name-Array
Ronald Gupta
Sonal Desai
Miriam Abrams
Carol Burns
Eric Johnson
Peter Legardo
Alison Gaynor
Diana Chin
Michael Cernowitz
Marla Kaplan
Number-And-Code-Array(5,1) contains 44563
Where is the Code? Number-And-Code-Array (5,2)
Where is the Name? Name-Array (5)
Number-And-Code-Array
12987
29801
29991
30987
44563
48723
56560
57341
59992
60132
2
1
3
4
5
1
3
3
2
4
Name-Array
Ronald Gupta
Sonal Desai
Miriam Abrams
Carol Burns
Eric Johnson
Peter Legardo
Alison Gaynor
Diana Chin
Michael Cernowitz
Marla Kaplan
Suppose You Want to Find the Code and Name for
Number 44563




Number-And-Code-Array(5,1) contains 44563
The code is found in Number-And-Code-Array(5,2)
The name is found in Name-Array(5)
Notice that the row subscripts are all the same
Number-And-Code-Array
12987
29801
29991
30987
44563
48723
56560
57341
59992
60132
2
1
3
4
5
1
3
3
2
4
Name-Array
Ronald Gupta
Sonal Desai
Miriam Abrams
Carol Burns
Eric Johnson
Peter Legardo
Alison Gaynor
Diana Chin
Michael Cernowitz
Marla Kaplan
Corresponding Arrays (also
called Parallel Arrays) have row
subscripts that are the same in
each of the arrays, that is, they
correspond
Descargar

Chapter 1