Chapter 26. Arrays
Newer versions of Bash support one-dimensional arrays. Array elements may be initialized with the variable[xx] notation. Alternatively, a script may introduce the entire array by an explicit declare -a variable statement. To dereference (find the contents of) an array element, use curly bracket notation, that is, ${variable[xx]}.
Example 26-1. Simple array usage
1 #!/bin/bash
2
3
4 area[11]=23
5 area[13]=37
6 area[51]=UFOs
7
8 # Array members need not be consecutive or contiguous.
9
10 # Some members of the array can be left uninitialized.
11 # Gaps in the array are o.k.
12
13
14 echo -n "area[11] = "
15 echo ${area[11]} # {curly brackets} needed
16
17 echo -n "area[13] = "
18 echo ${area[13]}
19
20 echo "Contents of area[51] are ${area[51]}."
21
22 # Contents of uninitialized array variable print blank.
23 echo -n "area[43] = "
24 echo ${area[43]}
25 echo "(area[43] unassigned)"
26
27 echo
28
29 # Sum of two array variables assigned to third
30 area[5]=`expr ${area[11]} + ${area[13]}`
31 echo "area[5] = area[11] + area[13]"
32 echo -n "area[5] = "
33 echo ${area[5]}
34
35 area[6]=`expr ${area[11]} + ${area[51]}`
36 echo "area[6] = area[11] + area[51]"
37 echo -n "area[6] = "
38 echo ${area[6]}
39 # This fails because adding an integer to a string is not permitted.
40
41 echo; echo; echo
42
43 # -----------------------------------------------------------------
44 # Another array, "area2".
45 # Another way of assigning array variables...
46 # array_name=( XXX YYY ZZZ ... )
47
48 area2=( zero one two three four )
49
50 echo -n "area2[0] = "
51 echo ${area2[0]}
52 # Aha, zero-based indexing (first element of array is [0], not [1]).
53
54 echo -n "area2[1] = "
55 echo ${area2[1]} # [1] is second element of array.
56 # -----------------------------------------------------------------
57
58 echo; echo; echo
59
60 # -----------------------------------------------
61 # Yet another array, "area3".
62 # Yet another way of assigning array variables...
63 # array_name=([xx]=XXX [yy]=YYY ...)
64
65 area3=([17]=seventeen [24]=twenty-four)
66
67 echo -n "area3[17] = "
68 echo ${area3[17]}
69
70 echo -n "area3[24] = "
71 echo ${area3[24]}
72 # -----------------------------------------------
73
74 exit 0 |
Example 26-2. Formatting a poem
1 #!/bin/bash
2 # poem.sh
3
4 # Lines of the poem (single stanza).
5 Line[1]="I do not know which to prefer,"
6 Line[2]="The beauty of inflections"
7 Line[3]="Or the beauty of innuendoes,"
8 Line[4]="The blackbird whistling"
9 Line[5]="Or just after."
10
11 # Attribution.
12 Attrib[1]=" Wallace Stevens"
13 Attrib[2]="\"Thirteen Ways of Looking at a Blackbird\""
14
15 for index in 1 2 3 4 5 # Five lines.
16 do
17 printf " %s\n" "${Line[index]}"
18 done
19
20 for index in 1 2 # Two attribution lines.
21 do
22 printf " %s\n" "${Attrib[index]}"
23 done
24
25 exit 0 |
Array variables have a syntax all their own, and even standard Bash commands and operators have special options adapted for array use.
1 array=( zero one two three four five )
2
3 echo ${array[0]} # zero
4 echo ${array:0} # zero
5 # Parameter expansion of first element.
6 echo ${array:1} # ero
7 # Parameter expansion of first element,
8 #+ starting at position #1 (2nd character).
9
10 echo ${#array} # 4
11 # Length of first element of array. |
In an array context, some Bash builtins have a slightly altered meaning. For example, unset deletes array elements, or even an entire array.
Example 26-3. Some special properties of arrays
1 #!/bin/bash
2
3 declare -a colors
4 # Permits declaring an array without specifying its size.
5
6 echo "Enter your favorite colors (separated from each other by a space)."
7
8 read -a colors # Enter at least 3 colors to demonstrate features below.
9 # Special option to 'read' command,
10 #+ allowing assignment of elements in an array.
11
12 echo
13
14 element_count=${#colors[@]}
15 # Special syntax to extract number of elements in array.
16 # element_count=${#colors[*]} works also.
17 #
18 # The "@" variable allows word splitting within quotes
19 #+ (extracts variables separated by whitespace).
20
21 index=0
22
23 while [ "$index" -lt "$element_count" ]
24 do # List all the elements in the array.
25 echo ${colors[$index]}
26 let "index = $index + 1"
27 done
28 # Each array element listed on a separate line.
29 # If this is not desired, use echo -n "${colors[$index]} "
30 #
31 # Doing it with a "for" loop instead:
32 # for i in "${colors[@]}"
33 # do
34 # echo "$i"
35 # done
36 # (Thanks, S.C.)
37
38 echo
39
40 # Again, list all the elements in the array, but using a more elegant method.
41 echo ${colors[@]} # echo ${colors[*]} also works.
42
43 echo
44
45 # The "unset" command deletes elements of an array, or entire array.
46 unset colors[1] # Remove 2nd element of array.
47 # Same effect as colors[1]=
48 echo ${colors[@]} # List array again, missing 2nd element.
49
50 unset colors # Delete entire array.
51 # unset colors[*] and
52 #+ unset colors[@] also work.
53 echo; echo -n "Colors gone."
54 echo ${colors[@]} # List array again, now empty.
55
56 exit 0 |
As seen in the previous example, either ${array_name[@]} or ${array_name[*]} refers to all the elements of the array. Similarly, to get a count of the number of elements in an array, use either ${#array_name[@]} or ${#array_name[*]}. ${#array_name} is the length (number of characters) of ${array_name[0]}, the first element of the array.
Example 26-4. Of empty arrays and empty elements
1 #!/bin/bash
2 # empty-array.sh
3
4 # An empty array is not the same as an array with empty elements.
5
6 array0=( first second third )
7 array1=( '' ) # "array1" has one empty element.
8 array2=( ) # No elements... "array2" is empty.
9
10 echo
11
12 echo "Elements in array0: ${array0[@]}"
13 echo "Elements in array1: ${array1[@]}"
14 echo "Elements in array2: ${array2[@]}"
15 echo
16 echo "Length of first element in array0 = ${#array0}"
17 echo "Length of first element in array1 = ${#array1}"
18 echo "Length of first element in array2 = ${#array2}"
19 echo
20 echo "Number of elements in array0 = ${#array0[*]}" # 3
21 echo "Number of elements in array1 = ${#array1[*]}" # 1 (surprise!)
22 echo "Number of elements in array2 = ${#array2[*]}" # 0
23
24 echo
25
26 exit 0 # Thanks, S.C. |
The relationship of ${array_name[@]} and ${array_name[*]} is analogous to that between $@ and $*. This powerful array notation has a number of uses.
1 # Copying an array.
2 array2=( "${array1[@]}" )
3 # or
4 array2="${array1[@]}"
5
6 # Adding an element to an array.
7 array=( "${array[@]}" "new element" )
8 # or
9 array[${#array[*]}]="new element"
10
11 # Thanks, S.C. |
 | The array=( element1 element2 ... elementN ) initialization operation, with the help of command substitution, makes it possible to load the contents of a text file into an array.
|
Arrays permit deploying old familiar algorithms as shell scripts. Whether this is necessarily a good idea is left to the reader to decide.
Example 26-5. An old friend: The Bubble Sort
1 #!/bin/bash
2 # bubble.sh: Bubble sort, of sorts.
3
4 # Recall the algorithm for a bubble sort. In this particular version...
5
6 # With each successive pass through the array to be sorted,
7 #+ compare two adjacent elements, and swap them if out of order.
8 # At the end of the first pass, the "heaviest" element has sunk to bottom.
9 # At the end of the second pass, the next "heaviest" one has sunk next to bottom.
10 # And so forth.
11 # This means that each successive pass needs to traverse less of the array.
12 # You will therefore notice a speeding up in the printing of the later passes.
13
14
15 exchange()
16 {
17 # Swaps two members of the array.
18 local temp=${Countries[$1]} # Temporary storage
19 #+ for element getting swapped out.
20 Countries[$1]=${Countries[$2]}
21 Countries[$2]=$temp
22
23 return
24 }
25
26 declare -a Countries # Declare array,
27 #+ optional here since it's initialized below.
28
29 # Is it permissable to split an array variable over multiple lines
30 #+ using an escape (\)?
31 # Yes.
32
33 Countries=(Netherlands Ukraine Zaire Turkey Russia Yemen Syria \
34 Brazil Argentina Nicaragua Japan Mexico Venezuela Greece England \
35 Israel Peru Canada Oman Denmark Wales France Kenya \
36 Xanadu Qatar Liechtenstein Hungary)
37
38 # "Xanadu" is the mythical place where, according to Coleridge,
39 #+ Kubla Khan did a pleasure dome decree.
40
41
42 clear # Clear the screen to start with.
43
44 echo "0: ${Countries[*]}" # List entire array at pass 0.
45
46 number_of_elements=${#Countries[@]}
47 let "comparisons = $number_of_elements - 1"
48
49 count=1 # Pass number.
50
51 while [ "$comparisons" -gt 0 ] # Beginning of outer loop
52 do
53
54 index=0 # Reset index to start of array after each pass.
55
56 while [ "$index" -lt "$comparisons" ] # Beginning of inner loop
57 do
58 if [ ${Countries[$index]} \> ${Countries[`expr $index + 1`]} ]
59 # If out of order...
60 # Recalling that \> is ASCII comparison operator
61 #+ within single brackets.
62
63 # if [[ ${Countries[$index]} > ${Countries[`expr $index + 1`]} ]]
64 #+ also works.
65 then
66 exchange $index `expr $index + 1` # Swap.
67 fi
68 let "index += 1"
69 done # End of inner loop
70
71
72 let "comparisons -= 1" # Since "heaviest" element bubbles to bottom,
73 #+ we need do one less comparison each pass.
74
75 echo
76 echo "$count: ${Countries[@]}" # Print resultant array at end of each pass.
77 echo
78 let "count += 1" # Increment pass count.
79
80 done # End of outer loop
81 # All done.
82
83 exit 0 |
--
Arrays enable implementing a shell script version of the Sieve of Eratosthenes. Of course, a resource-intensive application of this nature should really be written in a compiled language, such as C. It runs excruciatingly slowly as a script.
Example 26-6. Complex array application: Sieve of Eratosthenes
1 #!/bin/bash
2 # sieve.sh
3
4 # Sieve of Eratosthenes
5 # Ancient algorithm for finding prime numbers.
6
7 # This runs a couple of orders of magnitude
8 # slower than the equivalent C program.
9
10 LOWER_LIMIT=1 # Starting with 1.
11 UPPER_LIMIT=1000 # Up to 1000.
12 # (You may set this higher... if you have time on your hands.)
13
14 PRIME=1
15 NON_PRIME=0
16
17 let SPLIT=UPPER_LIMIT/2
18 # Optimization:
19 # Need to test numbers only halfway to upper limit.
20
21
22 declare -a Primes
23 # Primes[] is an array.
24
25
26 initialize ()
27 {
28 # Initialize the array.
29
30 i=$LOWER_LIMIT
31 until [ "$i" -gt "$UPPER_LIMIT" ]
32 do
33 Primes[i]=$PRIME
34 let "i += 1"
35 done
36 # Assume all array members guilty (prime)
37 # until proven innocent.
38 }
39
40 print_primes ()
41 {
42 # Print out the members of the Primes[] array tagged as prime.
43
44 i=$LOWER_LIMIT
45
46 until [ "$i" -gt "$UPPER_LIMIT" ]
47 do
48
49 if [ "${Primes[i]}" -eq "$PRIME" ]
50 then
51 printf "%8d" $i
52 # 8 spaces per number gives nice, even columns.
53 fi
54
55 let "i += 1"
56
57 done
58
59 }
60
61 sift () # Sift out the non-primes.
62 {
63
64 let i=$LOWER_LIMIT+1
65 # We know 1 is prime, so let's start with 2.
66
67 until [ "$i" -gt "$UPPER_LIMIT" ]
68 do
69
70 if [ "${Primes[i]}" -eq "$PRIME" ]
71 # Don't bother sieving numbers already sieved (tagged as non-prime).
72 then
73
74 t=$i
75
76 while [ "$t" -le "$UPPER_LIMIT" ]
77 do
78 let "t += $i "
79 Primes[t]=$NON_PRIME
80 # Tag as non-prime all multiples.
81 done
82
83 fi
84
85 let "i += 1"
86 done
87
88
89 }
90
91
92 # Invoke the functions sequentially.
93 initialize
94 sift
95 print_primes
96 # This is what they call structured programming.
97
98 echo
99
100 exit 0
101
102
103
104 # ----------------------------------------------- #
105 # Code below line will not execute.
106
107 # This improved version of the Sieve, by Stephane Chazelas,
108 # executes somewhat faster.
109
110 # Must invoke with command-line argument (limit of primes).
111
112 UPPER_LIMIT=$1 # From command line.
113 let SPLIT=UPPER_LIMIT/2 # Halfway to max number.
114
115 Primes=( '' $(seq $UPPER_LIMIT) )
116
117 i=1
118 until (( ( i += 1 ) > SPLIT )) # Need check only halfway.
119 do
120 if [[ -n $Primes[i] ]]
121 then
122 t=$i
123 until (( ( t += i ) > UPPER_LIMIT ))
124 do
125 Primes[t]=
126 done
127 fi
128 done
129 echo ${Primes[*]}
130
131 exit 0 |
Compare this array-based prime number generator with an alternative that does not use arrays, Example A-17.
--
Arrays lend themselves, to some extent, to emulating data structures for which Bash has no native support.
Example 26-7. Emulating a push-down stack
1 #!/bin/bash
2 # stack.sh: push-down stack simulation
3
4 # Similar to the CPU stack, a push-down stack stores data items
5 #+ sequentially, but releases them in reverse order, last-in first-out.
6
7 BP=100 # Base Pointer of stack array.
8 # Begin at element 100.
9
10 SP=$BP # Stack Pointer.
11 # Initialize it to "base" (bottom) of stack.
12
13 Data= # Contents of stack location.
14 # Must use local variable,
15 #+ because of limitation on function return range.
16
17 declare -a stack
18
19
20 push() # Push item on stack.
21 {
22 if [ -z "$1" ] # Nothing to push?
23 then
24 return
25 fi
26
27 let "SP -= 1" # Bump stack pointer.
28 stack[$SP]=$1
29
30 return
31 }
32
33 pop() # Pop item off stack.
34 {
35 Data= # Empty out data item.
36
37 if [ "$SP" -eq "$BP" ] # Stack empty?
38 then
39 return
40 fi # This also keeps SP from getting past 100,
41 #+ i.e., prevents a runaway stack.
42
43 Data=${stack[$SP]}
44 let "SP += 1" # Bump stack pointer.
45 return
46 }
47
48 status_report() # Find out what's happening.
49 {
50 echo "-------------------------------------"
51 echo "REPORT"
52 echo "Stack Pointer = $SP"
53 echo "Just popped \""$Data"\" off the stack."
54 echo "-------------------------------------"
55 echo
56 }
57
58
59 # =======================================================
60 # Now, for some fun.
61
62 echo
63
64 # See if you can pop anything off empty stack.
65 pop
66 status_report
67
68 echo
69
70 push garbage
71 pop
72 status_report # Garbage in, garbage out.
73
74 value1=23; push $value1
75 value2=skidoo; push $value2
76 value3=FINAL; push $value3
77
78 pop # FINAL
79 status_report
80 pop # skidoo
81 status_report
82 pop # 23
83 status_report # Last-in, first-out!
84
85 # Notice how the stack pointer decrements with each push,
86 #+ and increments with each pop.
87
88 echo
89 # =======================================================
90
91
92 # Exercises:
93 # ---------
94
95 # 1) Modify the "push()" function to permit pushing
96 # + multiple element on the stack with a single function call.
97
98 # 2) Modify the "pop()" function to permit popping
99 # + multiple element from the stack with a single function call.
100
101 # 3) Using this script as a jumping-off point,
102 # + write a stack-based 4-function calculator.
103
104 exit 0 |
--
Fancy manipulation of array "subscripts" may require intermediate variables. For projects involving this, again consider using a more powerful programming language, such as Perl or C.
Example 26-8. Complex array application: Exploring a weird mathematical series
1 #!/bin/bash
2
3 # Douglas Hofstadter's notorious "Q-series":
4
5 # Q(1) = Q(2) = 1
6 # Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), for n>2
7
8 # This is a "chaotic" integer series with strange and unpredictable behavior.
9 # The first 20 terms of the series are:
10 # 1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12
11
12 # See Hofstadter's book, "Goedel, Escher, Bach: An Eternal Golden Braid",
13 # p. 137, ff.
14
15
16 LIMIT=100 # Number of terms to calculate
17 LINEWIDTH=20 # Number of terms printed per line
18
19 Q[1]=1 # First two terms of series are 1.
20 Q[2]=1
21
22 echo
23 echo "Q-series [$LIMIT terms]:"
24 echo -n "${Q[1]} " # Output first two terms.
25 echo -n "${Q[2]} "
26
27 for ((n=3; n <= $LIMIT; n++)) # C-like loop conditions.
28 do # Q[n] = Q[n - Q[n-1]] + Q[n - Q[n-2]] for n>2
29 # Need to break the expression into intermediate terms,
30 # since Bash doesn't handle complex array arithmetic very well.
31
32 let "n1 = $n - 1" # n-1
33 let "n2 = $n - 2" # n-2
34
35 t0=`expr $n - ${Q[n1]}` # n - Q[n-1]
36 t1=`expr $n - ${Q[n2]}` # n - Q[n-2]
37
38 T0=${Q[t0]} # Q[n - Q[n-1]]
39 T1=${Q[t1]} # Q[n - Q[n-2]]
40
41 Q[n]=`expr $T0 + $T1` # Q[n - Q[n-1]] + Q[n - ![n-2]]
42 echo -n "${Q[n]} "
43
44 if [ `expr $n % $LINEWIDTH` -eq 0 ] # Format output.
45 then # mod
46 echo # Break lines into neat chunks.
47 fi
48
49 done
50
51 echo
52
53 exit 0
54
55 # This is an iterative implementation of the Q-series.
56 # The more intuitive recursive implementation is left as an exercise.
57 # Warning: calculating this series recursively takes a *very* long time. |
--
Bash supports only one-dimensional arrays, however a little trickery permits simulating multi-dimensional ones.
Example 26-9. Simulating a two-dimensional array, then tilting it
1 #!/bin/bash
2 # Simulating a two-dimensional array.
3
4 # A two-dimensional array stores rows sequentially.
5
6 Rows=5
7 Columns=5
8
9 declare -a alpha # char alpha [Rows] [Columns];
10 # Unnecessary declaration.
11
12 load_alpha ()
13 {
14 local rc=0
15 local index
16
17
18 for i in A B C D E F G H I J K L M N O P Q R S T U V W X Y
19 do
20 local row=`expr $rc / $Columns`
21 local column=`expr $rc % $Rows`
22 let "index = $row * $Rows + $column"
23 alpha[$index]=$i # alpha[$row][$column]
24 let "rc += 1"
25 done
26
27 # Simpler would be
28 # declare -a alpha=( A B C D E F G H I J K L M N O P Q R S T U V W X Y )
29 # but this somehow lacks the "flavor" of a two-dimensional array.
30 }
31
32 print_alpha ()
33 {
34 local row=0
35 local index
36
37 echo
38
39 while [ "$row" -lt "$Rows" ] # Print out in "row major" order -
40 do # columns vary
41 # while row (outer loop) remains the same.
42 local column=0
43
44 while [ "$column" -lt "$Columns" ]
45 do
46 let "index = $row * $Rows + $column"
47 echo -n "${alpha[index]} " # alpha[$row][$column]
48 let "column += 1"
49 done
50
51 let "row += 1"
52 echo
53
54 done
55
56 # The simpler equivalent is
57 # echo ${alpha[*]} | xargs -n $Columns
58
59 echo
60 }
61
62 filter () # Filter out negative array indices.
63 {
64
65 echo -n " " # Provides the tilt.
66
67 if [[ "$1" -ge 0 && "$1" -lt "$Rows" && "$2" -ge 0 && "$2" -lt "$Columns" ]]
68 then
69 let "index = $1 * $Rows + $2"
70 # Now, print it rotated.
71 echo -n " ${alpha[index]}" # alpha[$row][$column]
72 fi
73
74 }
75
76
77
78
79 rotate () # Rotate the array 45 degrees
80 { # ("balance" it on its lower lefthand corner).
81 local row
82 local column
83
84 for (( row = Rows; row > -Rows; row-- )) # Step through the array backwards.
85 do
86
87 for (( column = 0; column < Columns; column++ ))
88 do
89
90 if [ "$row" -ge 0 ]
91 then
92 let "t1 = $column - $row"
93 let "t2 = $column"
94 else
95 let "t1 = $column"
96 let "t2 = $column + $row"
97 fi
98
99 filter $t1 $t2 # Filter out negative array indices.
100 done
101
102 echo; echo
103
104 done
105
106 # Array rotation inspired by examples (pp. 143-146) in
107 # "Advanced C Programming on the IBM PC", by Herbert Mayer
108 # (see bibliography).
109
110 }
111
112
113 #-----------------------------------------------------#
114 load_alpha # Load the array.
115 print_alpha # Print it out.
116 rotate # Rotate it 45 degrees counterclockwise.
117 #-----------------------------------------------------#
118
119
120 # This is a rather contrived, not to mention kludgy simulation.
121 #
122 # Exercises:
123 # ---------
124 # 1) Rewrite the array loading and printing functions
125 # + in a more intuitive and elegant fashion.
126 #
127 # 2) Figure out how the array rotation functions work.
128 # Hint: think about the implications of backwards-indexing an array.
129
130 exit 0 |
A two-dimensional array is essentially equivalent to a one-dimensional one, but with additional addressing modes for referencing and manipulating the individual elements by "row" and "column" position.
For an even more elaborate example of simulating a two-dimensional array, see Example A-11.