HCI 7. Array, List and Dictionary (2022) revised

Hwa Chong Institution H2 Computing 1 7 Array, List and Dictionary Learning Outcome 7.1 Array An array provides a convenient structure for storing data items of the same data type. As you will see, arrays allow for both easy reading of the data into memory and efficient accessing of the data for processing. We will consider two standard types of situations in which arrays are useful: (1) when a data list must be processed more than once and (1) when a large number of related summing or counting variables are needed. 7.1.1 One-Dimensional Array So far, all the variables that we have considered have been a simple data type. A variable of simple data type consists of a single memory cell that can hold only one value at a time. By contrast, a variable of structured data type consists of a collection of memory cells. An array consists of a collection of memory cells for storing a list of values that are all of the same data type -- for example, a list of integers, a list of real numbers, a list of characters, or a list of boolean values. The entire list is given a name. An array can be compared to an apartment building. The name of the array represents the name of the building. The elements of the array represent the building's apartments, each of which has a subscript or index, which corresponds to an apartment number. Assuming that the index starts with 1, Riser[1] is used to specify the first apartment in the building called Riser, while Riser[4] refers to apartment 4 in the building called Riser Riser[1] Riser[2] Riser[3] Riser[4] In order to specify an individual element of an array, you must give both the name of the array and the subscript. For example, for an array called scores, the statement scores[4] ← 86 assigns the value 86 to the memory cell scores[4]. Similarly, OUTPUT scores[6] outputs the contents of the memory cell scores[6]. The following pseudocode assigns values to be stored in an array's elements. Programming Elements and Constructs Understand the different data structures: array, list and dictionary; initialize arrays (1 - dimensional and 2-dimensional)

Hwa Chong Institution H2 Computing 2 // program drill BEGIN DECLARE X: ARRAY[1:4] of INTEGER x[1]←83 x[2]←59 x[3]←88 x[4]←72 OUTPUT x[4] OUTPUT x[2] OUTPUT x[2+1] OUTPUT x[2]+1 END In programming languages where static arrays are used, a declaration of the array would require the data -type, and the number of elements you want in the array. By specifying these information, memory cells memory cells are set aside for the array declared. In the above example, 4 memory cells, x[1], x[2], and x[3], x[4] are set aside, each enough storage for an integer value. By the time the four assignment statements have been executed, four numbers will be stored in array x as follows: x[1] x[2] x[3] x[4] 83 59 88 72 The output will be 72 59 88 60 Note (Array index out of range): In the above example, if 4 elements were assumed i.e. x[1..4], You should not access/assign values to x[5]. This may be accepted in some programming languages, however, it may cause unpleasant things to happen in the computer memory because the array ranges from x[1] to x[4]. Using a for Loop to read (access, write) values into the array The numbers 83, 59, 88, and 72 could be assigned interactively to the array x using a for loop. FOR i ← 1 TO 4 OUTPUT “Enter Element:” INPUT x[i] ENDFOR

Hwa Chong Institution H2 Computing 3 An important use of arrays is in processing a data list more than once. Example Suppose a program reads in list of up to 25 non-negative numbers. For example, the user may input enter list of non-negative integer: 41 enter list of non-negative integer: 68 enter list of non-negative integer: 32 enter list of non-negative integer: 74 enter list of non-negative integer: 55 enter list of non-negative integer: -999 The following program, in pseudocode, will print the numbers in their original order and then in reverse order. The printout will be original order: 41 68 32 74 55 reverse order: 55 74 32 68 41 BEGIN DECLARE numbs: ARRAY[1:25] of INTEGER DECLARE count: INTEGER DECLARE num: INTEGER count ← 0 // keeps track of the no. of input integers // read list of up to 25 non-negative integers into // array numbs // using input -999 to end list OUTPUT "enter non-negative integer:” INPUT num WHILE(num <> -999 AND count < 25) count ← count + 1 numbs[count] ← num OUTPUT "enter non-negative integer:” INPUT num ENDWHILE IF(count>0) //prints original order OUTPUT "original order:” FOR i ← 1 TO count OUTPUT numbs[i] ENDFOR // prints the reverse order OUTPUT "reverse order:” FOR i ← count DOWN TO 1 OUTPUT numbs[i] ENDFOR ENDIF END

Hwa Chong Institution H2 Computing 4 Remark (1) The numbs array was declared to hold up to 25 integers. In the while loop that reads values into the numbs array, count is used as the array subscript. (2) In the for loop that takes a second look at the array, count is not a subscript but rather the upper limit of the loop. (3) You may also assume that the array index starts from 0 ie. numbs[0..24]. In this case, the pseudocode above, would need to be updated accordingly. 7.1.2 Array of Counting Variables Arrays are particularly useful when you are tallying a number of related quantities. By using the array index, you can directly increment the appropriate counter instead of performing a tedious multiway selection. Example ( Vote Counting ) Suppose that in a recently held election, there were four candidates 1, 2, 3 and 4. Suppose the votes are entered such that 1 represents a vote for candidate 1, 2 a vote for candidate 2, 3 a vote for candidate 3, and 4 a vote for candidate 4. –999 will end the list. That is, the input may consists of a list like 1 3 1 4 2 1 2 3 etc We wish to write a program to process the input list. The printout should be of the form CANDIDATE NO. OF VOTES 1 17 2 38 3 24 4 32 We will use the array of voteCnts to keep track of the votes for each of the four candidates. By the time all the votes have been counted, voteCnts will have the following values: voteCnts [1] 17 [2] 38 [3] 24 [4] 32 At the start of the program, the four memory boxes of voteCnts should be initialized to 0.

Hwa Chong Institution H2 Computing 5 Here is the draft pseudocode. 1. initialize voteCnts to zeros 2. use a loop to read in and process each of the votes; for example, a vote of 3 will increase voteCnts[3] by 1. 3. use a for loop to print the final values for each of the memory boxes of voteCnts Processing a Single Vote The statement read vote will read in a vote from the user. The variable vote will have the value 1, 2, 3 or 4. The value of vote (1, 2, 3 or 4) gives the subscript for the element of voteCnts that should be increased by 1. So we can just use a single line to count the votes. voteCnts[vote] ← voteCnts[vote] + 1 Here is the detailed pseudocode. // program voting; // processes the votes and prints each candidate's tally BEGIN CONSTANT VOTERANGE = 4 DELARE vote: INTEGER DECLARE voteCnts: ARRAY [1: VOTERANGE] of INTEGER // initialize voteCnts to 0 FOR i ← 1 TO VOTERANGE voteCnts[i] ← 0 // process votes by reading in individual vote and updating // app