Chapter 26. Arrays
Newer versions of Bash support one-dimensional arrays. Array elements may be initialized with the variable[xx] notation. Alternately, 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
#!/bin/bash
area[11]=23
area[13]=37
area[51]=UFOs
# Array members need not be consecutive or contiguous.
# Some members of the array can be left uninitialized.
# Gaps in the array are o.k.
echo -n "area[11] = "
echo ${area[11]} # {curly brackets} needed
echo -n "area[13] = "
echo ${area[13]}
echo "Contents of area[51] are ${area[51]}."
# Contents of uninitialized array variable print blank.
echo -n "area[43] = "
echo ${area[43]}
echo "(area[43] unassigned)"
echo
# Sum of two array variables assigned to third
area[5]=`expr ${area[11]} + ${area[13]}`
echo "area[5] = area[11] + area[13]"
echo -n "area[5] = "
echo ${area[5]}
area[6]=`expr ${area[11]} + ${area[51]}`
echo "area[6] = area[11] + area[51]"
echo -n "area[6] = "
echo ${area[6]}
# This fails because adding an integer to a string is not permitted.
echo; echo; echo
# -----------------------------------------------------------------
# Another array, "area2".
# Another way of assigning array variables...
# array_name=( XXX YYY ZZZ ... )
area2=( zero one two three four )
echo -n "area2[0] = "
echo ${area2[0]}
# Aha, zero-based indexing (first element of array is [0], not [1]).
echo -n "area2[1] = "
echo ${area2[1]} # [1] is second element of array.
# -----------------------------------------------------------------
echo; echo; echo
# -----------------------------------------------
# Yet another array, "area3".
# Yet another way of assigning array variables...
# array_name=([xx]=XXX [yy]=YYY ...)
area3=([17]=seventeen [24]=twenty-four)
echo -n "area3[17] = "
echo ${area3[17]}
echo -n "area3[24] = "
echo ${area3[24]}
# -----------------------------------------------
exit 0 |
Arrays variables have a syntax all their own, and even standard Bash commands and operators have special options adapted for array use.
array=( zero one two three four five )
echo ${array[0]} # zero
echo ${array:0} # zero
# Parameter expansion of first element.
echo ${array:1} # ero
# Parameter expansion of first element,
#+ starting at position #1 (2nd character).
echo ${#array} # 4
# 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-2. Some special properties of arrays
#!/bin/bash
declare -a colors
# Permits declaring an array without specifying its size.
echo "Enter your favorite colors (separated from each other by a space)."
read -a colors # Enter at least 3 colors to demonstrate features below.
# Special option to 'read' command,
#+ allowing assignment of elements in an array.
echo
element_count=${#colors[@]}
# Special syntax to extract number of elements in array.
# element_count=${#colors[*]} works also.
#
# The "@" variable allows word splitting within quotes
#+ (extracts variables separated by whitespace).
index=0
while [ "$index" -lt "$element_count" ]
do # List all the elements in the array.
echo ${colors[$index]}
let "index = $index + 1"
done
# Each array element listed on a separate line.
# If this is not desired, use echo -n "${colors[$index]} "
#
# Doing it with a "for" loop instead:
# for i in "${colors[@]}"
# do
# echo "$i"
# done
# (Thanks, S.C.)
echo
# Again, list all the elements in the array, but using a more elegant method.
echo ${colors[@]} # echo ${colors[*]} also works.
echo
# The "unset" command deletes elements of an array, or entire array.
unset colors[1] # Remove 2nd element of array.
# Same effect as colors[1]=
echo ${colors[@]} # List array again, missing 2nd element.
unset colors # Delete entire array.
# unset colors[*] and
#+ unset colors[@] also work.
echo; echo -n "Colors gone."
echo ${colors[@]} # List array again, now empty.
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-3. Of empty arrays and empty elements
#!/bin/bash
# empty-array.sh
# An empty array is not the same as an array with empty elements.
array0=( first second third )
array1=( '' ) # "array1" has one empty element.
array2=( ) # No elements... "array2" is empty.
echo
echo "Elements in array0: ${array0[@]}"
echo "Elements in array1: ${array1[@]}"
echo "Elements in array2: ${array2[@]}"
echo
echo "Length of first element in array0 = ${#array0}"
echo "Length of first element in array1 = ${#array1}"
echo "Length of first element in array2 = ${#array2}"
echo
echo "Number of elements in array0 = ${#array0[*]}" # 3
echo "Number of elements in array1 = ${#array1[*]}" # 1 (surprise!)
echo "Number of elements in array2 = ${#array2[*]}" # 0
echo
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.
# Copying an array.
array2=( "${array1[@]}" )
# or
array2="${array1[@]}"
# Adding an element to an array.
array=( "${array[@]}" "new element" )
# or
array[${#array[*]}]="new element"
# 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-4. An old friend: The Bubble Sort
#!/bin/bash
# bubble.sh: Bubble sort, of sorts.
# Recall the algorithm for a bubble sort. In this particular version...
# With each successive pass through the array to be sorted,
#+ compare two adjacent elements, and swap them if out of order.
# At the end of the first pass, the "heaviest" element has sunk to bottom.
# At the end of the second pass, the next "heaviest" one has sunk next to bottom.
# And so forth.
# This means that each successive pass needs to traverse less of the array.
# You will therefore notice a speeding up in the printing of the later passes.
exchange()
{
# Swaps two members of the array.
local temp=${Countries[$1]} # Temporary storage
#+ for element getting swapped out.
Countries[$1]=${Countries[$2]}
Countries[$2]=$temp
return
}
declare -a Countries # Declare array,
#+ optional here since it's initialized below.
Countries=(Netherlands Ukraine Zaire Turkey Russia Yemen Syria Brazil Argentina Nicaragua Japan Mexico Venezuela Greece England Israel Peru Canada Oman Denmark Wales France Kenya Xanadu Qatar Liechtenstein Hungary)
# "Xanadu" is the mythical place where, according to Coleridge,
#+ Kubla Khan did a pleasure dome decree.
clear # Clear the screen to start with.
echo "0: ${Countries[*]}" # List entire array at pass 0.
number_of_elements=${#Countries[@]}
let "comparisons = $number_of_elements - 1"
count=1 # Pass number.
while [ "$comparisons" -gt 0 ] # Beginning of outer loop
do
index=0 # Reset index to start of array after each pass.
while [ "$index" -lt "$comparisons" ] # Beginning of inner loop
do
if [ ${Countries[$index]} \> ${Countries[`expr $index + 1`]} ]
# If out of order...
# Recalling that \> is ASCII comparison operator
#+ within single brackets.
# if [[ ${Countries[$index]} > ${Countries[`expr $index + 1`]} ]]
#+ also works.
then
exchange $index `expr $index + 1` # Swap.
fi
let "index += 1"
done # End of inner loop
let "comparisons -= 1" # Since "heaviest" element bubbles to bottom,
#+ we need do one less comparison each pass.
echo
echo "$count: ${Countries[@]}" # Print resultant array at end of each pass.
echo
let "count += 1" # Increment pass count.
done # End of outer loop
# All done.
exit 0 |
--
Arrays enable implementing a shell script version of the Sieve of Erastosthenes. 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-5. Complex array application: Sieve of Erastosthenes
#!/bin/bash
# sieve.sh
# Sieve of Erastosthenes
# Ancient algorithm for finding prime numbers.
# This runs a couple of orders of magnitude
# slower than the equivalent C program.
LOWER_LIMIT=1 # Starting with 1.
UPPER_LIMIT=1000 # Up to 1000.
# (You may set this higher... if you have time on your hands.)
PRIME=1
NON_PRIME=0
let SPLIT=UPPER_LIMIT/2
# Optimization:
# Need to test numbers only halfway to upper limit.
declare -a Primes
# Primes[] is an array.
initialize ()
{
# Initialize the array.
i=$LOWER_LIMIT
until [ "$i" -gt "$UPPER_LIMIT" ]
do
Primes[i]=$PRIME
let "i += 1"
done
# Assume all array members guilty (prime)
# until proven innocent.
}
print_primes ()
{
# Print out the members of the Primes[] array tagged as prime.
i=$LOWER_LIMIT
until [ "$i" -gt "$UPPER_LIMIT" ]
do
if [ "${Primes[i]}" -eq "$PRIME" ]
then
printf "%8d" $i
# 8 spaces per number gives nice, even columns.
fi
let "i += 1"
done
}
sift () # Sift out the non-primes.
{
let i=$LOWER_LIMIT+1
# We know 1 is prime, so let's start with 2.
until [ "$i" -gt "$UPPER_LIMIT" ]
do
if [ "${Primes[i]}" -eq "$PRIME" ]
# Don't bother sieving numbers already sieved (tagged as non-prime).
then
t=$i
while [ "$t" -le "$UPPER_LIMIT" ]
do
let "t += $i "
Primes[t]=$NON_PRIME
# Tag as non-prime all multiples.
done
fi
let "i += 1"
done
}
# Invoke the functions sequentially.
initialize
sift
print_primes
# This is what they call structured programming.
echo
exit 0
# ----------------------------------------------- #
# Code below line will not execute.
# This improved version of the Sieve, by Stephane Chazelas,
# executes somewhat faster.
# Must invoke with command-line argument (limit of primes).
UPPER_LIMIT=$1 # From command line.
let SPLIT=UPPER_LIMIT/2 # Halfway to max number.
Primes=( '' $(seq $UPPER_LIMIT) )
i=1
until (( ( i += 1 ) > SPLIT )) # Need check only halfway.
do
if [[ -n $Primes[i] ]]
then
t=$i
until (( ( t += i ) > UPPER_LIMIT ))
do
Primes[t]=
done
fi
done
echo ${Primes[*]}
exit 0 |
Compare this array-based prime number generator with with an alternative that does not use arrays, Example A-14.
--
Arrays lend themselves, to some extent, to emulating data structures for which Bash has no native support.
Example 26-6. Emulating a push-down stack
#!/bin/bash
# stack.sh: push-down stack simulation
# Similar to the CPU stack, a push-down stack stores data items
#+ sequentially, but releases them in reverse order, last-in first-out.
BP=100 # Base Pointer of stack array.
# Begin at element 100.
SP=$BP # Stack Pointer.
# Initialize it to "base" (bottom) of stack.
Data= # Contents of stack location.
# Must use local variable,
#+ because of limitation on function return range.
declare -a stack
push() # Push item on stack.
{
if [ -z "$1" ] # Nothing to push?
then
return
fi
let "SP -= 1" # Bump stack pointer.
stack[$SP]=$1
return
}
pop() # Pop item off stack.
{
Data= # Empty out data item.
if [ "$SP" -eq "$BP" ] # Stack empty?
then
return
fi # This also keeps SP from getting past 100,
#+ i.e., prevents a runaway stack.
Data=${stack[$SP]}
let "SP += 1" # Bump stack pointer.
return
}
status_report() # Find out what's happening.
{
echo "-------------------------------------"
echo "REPORT"
echo "Stack Pointer = $SP"
echo "Just popped \""$Data"\" off the stack."
echo "-------------------------------------"
echo
}
# =======================================================
# Now, for some fun.
echo
# See if you can pop anything off empty stack.
pop
status_report
echo
push garbage
pop
status_report # Garbage in, garbage out.
value1=23; push $value1
value2=skidoo; push $value2
value3=FINAL; push $value3
pop # FINAL
status_report
pop # skidoo
status_report
pop # 23
status_report # Last-in, first-out!
# Notice how the stack pointer decrements with each push,
#+ and increments with each pop.
echo
# =======================================================
# Exercises:
# ---------
# 1) Modify the "push()" function to permit pushing
# + multiple element on the stack with a single function call.
# 2) Modify the "pop()" function to permit popping
# + multiple element from the stack with a single function call.
# 3) Using this script as a jumping-off point,
# + write a stack-based 4-function calculator.
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-7. Complex array application: Exploring a weird mathematical series
#!/bin/bash
# Douglas Hofstadter's notorious "Q-series":
# Q(1) = Q(2) = 1
# Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), for n>2
# This is a "chaotic" integer series with strange and unpredictable behavior.
# The first 20 terms of the series are:
# 1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12
# See Hofstadter's book, "Goedel, Escher, Bach: An Eternal Golden Braid",
# p. 137, ff.
LIMIT=100 # Number of terms to calculate
LINEWIDTH=20 # Number of terms printed per line
Q[1]=1 # First two terms of series are 1.
Q[2]=1
echo
echo "Q-series [$LIMIT terms]:"
echo -n "${Q[1]} " # Output first two terms.
echo -n "${Q[2]} "
for ((n=3; n <= $LIMIT; n++)) # C-like loop conditions.
do # Q[n] = Q[n - Q[n-1]] + Q[n - Q[n-2]] for n>2
# Need to break the expression into intermediate terms,
# since Bash doesn't handle complex array arithmetic very well.
let "n1 = $n - 1" # n-1
let "n2 = $n - 2" # n-2
t0=`expr $n - ${Q[n1]}` # n - Q[n-1]
t1=`expr $n - ${Q[n2]}` # n - Q[n-2]
T0=${Q[t0]} # Q[n - Q[n-1]]
T1=${Q[t1]} # Q[n - Q[n-2]]
Q[n]=`expr $T0 + $T1` # Q[n - Q[n-1]] + Q[n - ![n-2]]
echo -n "${Q[n]} "
if [ `expr $n % $LINEWIDTH` -eq 0 ] # Format output.
then # mod
echo # Break lines into neat chunks.
fi
done
echo
exit 0
# This is an iterative implementation of the Q-series.
# The more intuitive recursive implementation is left as an exercise.
# 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-8. Simulating a two-dimensional array, then tilting it
#!/bin/bash
# Simulating a two-dimensional array.
# A two-dimensional array stores rows sequentially.
Rows=5
Columns=5
declare -a alpha # char alpha [Rows] [Columns];
# Unnecessary declaration.
load_alpha ()
{
local rc=0
local index
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
do
local row=`expr $rc / $Columns`
local column=`expr $rc % $Rows`
let "index = $row * $Rows + $column"
alpha[$index]=$i # alpha[$row][$column]
let "rc += 1"
done
# Simpler would be
# 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 )
# but this somehow lacks the "flavor" of a two-dimensional array.
}
print_alpha ()
{
local row=0
local index
echo
while [ "$row" -lt "$Rows" ] # Print out in "row major" order -
do # columns vary
# while row (outer loop) remains the same.
local column=0
while [ "$column" -lt "$Columns" ]
do
let "index = $row * $Rows + $column"
echo -n "${alpha[index]} " # alpha[$row][$column]
let "column += 1"
done
let "row += 1"
echo
done
# The simpler equivalent is
# echo ${alpha[*]} | xargs -n $Columns
echo
}
filter () # Filter out negative array indices.
{
echo -n " " # Provides the tilt.
if [[ "$1" -ge 0 && "$1" -lt "$Rows" && "$2" -ge 0 && "$2" -lt "$Columns" ]]
then
let "index = $1 * $Rows + $2"
# Now, print it rotated.
echo -n " ${alpha[index]}" # alpha[$row][$column]
fi
}
rotate () # Rotate the array 45 degrees
{ # ("balance" it on its lower lefthand corner).
local row
local column
for (( row = Rows; row > -Rows; row-- )) # Step through the array backwards.
do
for (( column = 0; column < Columns; column++ ))
do
if [ "$row" -ge 0 ]
then
let "t1 = $column - $row"
let "t2 = $column"
else
let "t1 = $column"
let "t2 = $column + $row"
fi
filter $t1 $t2 # Filter out negative array indices.
done
echo; echo
done
# Array rotation inspired by examples (pp. 143-146) in
# "Advanced C Programming on the IBM PC", by Herbert Mayer
# (see bibliography).
}
#-----------------------------------------------------#
load_alpha # Load the array.
print_alpha # Print it out.
rotate # Rotate it 45 degrees counterclockwise.
#-----------------------------------------------------#
# This is a rather contrived, not to mention kludgy simulation.
#
# Exercises:
# ---------
# 1) Rewrite the array loading and printing functions
# + in a more intuitive and elegant fashion.
#
# 2) Figure out how the array rotation functions work.
# Hint: think about the implications of backwards-indexing an array.
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-8.