arrays.html

Shall高级编程

 107 echo '- - in versions of Bash newer than version 2.05b - -'
 108 
 109 # MSZ: Sorry about any earlier confusion folks.
 110 
 111&nbsp;exit 0</PRE
></TD
></TR
></TABLE
><HR></DIV
><P
>--</P
><P
>Arrays permit deploying old familiar algorithms as shell scripts.
        Whether this is necessarily a good idea is left to the reader to
	decide.</P
><P
><A
NAME="BUBBLESORT"
></A
></P
><DIV
CLASS="EXAMPLE"
><HR><A
NAME="BUBBLE"
></A
><P
><B
>Example 26-11. The Bubble Sort</B
></P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>   1&nbsp;#!/bin/bash
   2&nbsp;# bubble.sh: Bubble sort, of sorts.
   3&nbsp;
   4&nbsp;# Recall the algorithm for a bubble sort. In this particular version...
   5&nbsp;
   6&nbsp;#  With each successive pass through the array to be sorted,
   7&nbsp;#+ compare two adjacent elements, and swap them if out of order.
   8&nbsp;#  At the end of the first pass, the "heaviest" element has sunk to bottom.
   9&nbsp;#  At the end of the second pass, the next "heaviest" one has sunk next to bottom.
  10&nbsp;#  And so forth.
  11&nbsp;#  This means that each successive pass needs to traverse less of the array.
  12&nbsp;#  You will therefore notice a speeding up in the printing of the later passes.
  13&nbsp;
  14&nbsp;
  15&nbsp;exchange()
  16&nbsp;{
  17&nbsp;  # Swaps two members of the array.
  18&nbsp;  local temp=${Countries[$1]} #  Temporary storage
  19&nbsp;                              #+ for element getting swapped out.
  20&nbsp;  Countries[$1]=${Countries[$2]}
  21&nbsp;  Countries[$2]=$temp
  22&nbsp;  
  23&nbsp;  return
  24&nbsp;}  
  25&nbsp;
  26&nbsp;declare -a Countries  #  Declare array,
  27&nbsp;                      #+ optional here since it's initialized below.
  28&nbsp;
  29&nbsp;#  Is it permissable to split an array variable over multiple lines
  30&nbsp;#+ using an escape (\)?
  31&nbsp;#  Yes.
  32&nbsp;
  33&nbsp;Countries=(Netherlands Ukraine Zaire Turkey Russia Yemen Syria \
  34&nbsp;Brazil Argentina Nicaragua Japan Mexico Venezuela Greece England \
  35&nbsp;Israel Peru Canada Oman Denmark Wales France Kenya \
  36&nbsp;Xanadu Qatar Liechtenstein Hungary)
  37&nbsp;
  38&nbsp;# "Xanadu" is the mythical place where, according to Coleridge,
  39&nbsp;#+ Kubla Khan did a pleasure dome decree.
  40&nbsp;
  41&nbsp;
  42&nbsp;clear                      # Clear the screen to start with. 
  43&nbsp;
  44&nbsp;echo "0: ${Countries[*]}"  # List entire array at pass 0.
  45&nbsp;
  46&nbsp;number_of_elements=${#Countries[@]}
  47&nbsp;let "comparisons = $number_of_elements - 1"
  48&nbsp;
  49&nbsp;count=1 # Pass number.
  50&nbsp;
  51&nbsp;while [ "$comparisons" -gt 0 ]          # Beginning of outer loop
  52&nbsp;do
  53&nbsp;
  54&nbsp;  index=0  # Reset index to start of array after each pass.
  55&nbsp;
  56&nbsp;  while [ "$index" -lt "$comparisons" ] # Beginning of inner loop
  57&nbsp;  do
  58&nbsp;    if [ ${Countries[$index]} \&#62; ${Countries[`expr $index + 1`]} ]
  59&nbsp;    #  If out of order...
  60&nbsp;    #  Recalling that \&#62; is ASCII comparison operator
  61&nbsp;    #+ within single brackets.
  62&nbsp;
  63&nbsp;    #  if [[ ${Countries[$index]} &#62; ${Countries[`expr $index + 1`]} ]]
  64&nbsp;    #+ also works.
  65&nbsp;    then
  66&nbsp;      exchange $index `expr $index + 1`  # Swap.
  67&nbsp;    fi  
  68&nbsp;    let "index += 1"  # Or,   index+=1   on Bash, ver. 3.1 or newer.
  69&nbsp;  done # End of inner loop
  70&nbsp;
  71&nbsp;# ----------------------------------------------------------------------
  72&nbsp;# Paulo Marcel Coelho Aragao suggests for-loops as a simpler altenative.
  73&nbsp;#
  74&nbsp;# for (( last = $number_of_elements - 1 ; last &#62; 0 ; last-- ))
  75&nbsp;##                     Fix by C.Y. Hunt          ^   (Thanks!)
  76&nbsp;# do
  77&nbsp;#     for (( i = 0 ; i &#60; last ; i++ ))
  78&nbsp;#     do
  79&nbsp;#         [[ "${Countries[$i]}" &#62; "${Countries[$((i+1))]}" ]] \
  80&nbsp;#             &#38;&#38; exchange $i $((i+1))
  81&nbsp;#     done
  82&nbsp;# done
  83&nbsp;# ----------------------------------------------------------------------
  84&nbsp;  
  85&nbsp;
  86&nbsp;let "comparisons -= 1" #  Since "heaviest" element bubbles to bottom,
  87&nbsp;                       #+ we need do one less comparison each pass.
  88&nbsp;
  89&nbsp;echo
  90&nbsp;echo "$count: ${Countries[@]}"  # Print resultant array at end of each pass.
  91&nbsp;echo
  92&nbsp;let "count += 1"                # Increment pass count.
  93&nbsp;
  94&nbsp;done                            # End of outer loop
  95&nbsp;                                # All done.
  96&nbsp;
  97&nbsp;exit 0</PRE
></TD
></TR
></TABLE
><HR></DIV
><P
>--</P
><P
><A
NAME="ARRAYNEST"
></A
></P
><P
>Is it possible to nest arrays within arrays?</P
><P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>   1&nbsp;#!/bin/bash
   2&nbsp;# "Nested" array.
   3&nbsp;
   4&nbsp;#  Michael Zick provided this example,
   5&nbsp;#+ with corrections and clarifications by William Park.
   6&nbsp;
   7&nbsp;AnArray=( $(ls --inode --ignore-backups --almost-all \
   8&nbsp;	--directory --full-time --color=none --time=status \
   9&nbsp;	--sort=time -l ${PWD} ) )  # Commands and options.
  10&nbsp;
  11&nbsp;# Spaces are significant . . . and don't quote anything in the above.
  12&nbsp;
  13&nbsp;SubArray=( ${AnArray[@]:11:1}  ${AnArray[@]:6:5} )
  14&nbsp;#  This array has six elements:
  15&nbsp;#+     SubArray=( [0]=${AnArray[11]} [1]=${AnArray[6]} [2]=${AnArray[7]}
  16&nbsp;#      [3]=${AnArray[8]} [4]=${AnArray[9]} [5]=${AnArray[10]} )
  17&nbsp;#
  18&nbsp;#  Arrays in Bash are (circularly) linked lists
  19&nbsp;#+ of type string (char *).
  20&nbsp;#  So, this isn't actually a nested array,
  21&nbsp;#+ but it's functionally similar.
  22&nbsp;
  23&nbsp;echo "Current directory and date of last status change:"
  24&nbsp;echo "${SubArray[@]}"
  25&nbsp;
  26&nbsp;exit 0</PRE
></TD
></TR
></TABLE
></P
><P
>--</P
><P
>Embedded arrays in combination with <A
HREF="bash2.html#VARREFNEW"
>indirect references</A
> create some fascinating
	possibilities</P
><P
><A
NAME="ARRAYINDIR"
></A
></P
><DIV
CLASS="EXAMPLE"
><HR><A
NAME="EMBARR"
></A
><P
><B
>Example 26-12. Embedded arrays and indirect references</B
></P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>   1&nbsp;#!/bin/bash
   2&nbsp;# embedded-arrays.sh
   3&nbsp;# Embedded arrays and indirect references.
   4&nbsp;
   5&nbsp;# This script by Dennis Leeuw.
   6&nbsp;# Used with permission.
   7&nbsp;# Modified by document author.
   8&nbsp;
   9&nbsp;
  10&nbsp;ARRAY1=(
  11&nbsp;        VAR1_1=value11
  12&nbsp;        VAR1_2=value12
  13&nbsp;        VAR1_3=value13
  14&nbsp;)
  15&nbsp;
  16&nbsp;ARRAY2=(
  17&nbsp;        VARIABLE="test"
  18&nbsp;        STRING="VAR1=value1 VAR2=value2 VAR3=value3"
  19&nbsp;        ARRAY21=${ARRAY1[*]}
  20&nbsp;)       # Embed ARRAY1 within this second array.
  21&nbsp;
  22&nbsp;function print () {
  23&nbsp;        OLD_IFS="$IFS"
  24&nbsp;        IFS=$'\n'       #  To print each array element
  25&nbsp;                        #+ on a separate line.
  26&nbsp;        TEST1="ARRAY2[*]"
  27&nbsp;        local ${!TEST1} # See what happens if you delete this line.
  28&nbsp;        #  Indirect reference.
  29&nbsp;	#  This makes the components of $TEST1
  30&nbsp;	#+ accessible to this function.
  31&nbsp;
  32&nbsp;
  33&nbsp;        #  Let's see what we've got so far.
  34&nbsp;        echo
  35&nbsp;        echo "\$TEST1 = $TEST1"       #  Just the name of the variable.
  36&nbsp;        echo; echo
  37&nbsp;        echo "{\$TEST1} = ${!TEST1}"  #  Contents of the variable.
  38&nbsp;                                      #  That's what an indirect
  39&nbsp;                                      #+ reference does.
  40&nbsp;        echo
  41&nbsp;        echo "-------------------------------------------"; echo
  42&nbsp;        echo
  43&nbsp;
  44&nbsp;
  45&nbsp;        # Print variable
  46&nbsp;        echo "Variable VARIABLE: $VARIABLE"
  47&nbsp;	
  48&nbsp;        # Print a string element
  49&nbsp;        IFS="$OLD_IFS"
  50&nbsp;        TEST2="STRING[*]"
  51&nbsp;        local ${!TEST2}      # Indirect reference (as above).
  52&nbsp;        echo "String element VAR2: $VAR2 from STRING"
  53&nbsp;
  54&nbsp;        # Print an array element
  55&nbsp;        TEST2="ARRAY21[*]"
  56&nbsp;        local ${!TEST2}      # Indirect reference (as above).
  57&nbsp;        echo "Array element VAR1_1: $VAR1_1 from ARRAY21"
  58&nbsp;}
  59&nbsp;
  60&nbsp;print
  61&nbsp;echo
  62&nbsp;
  63&nbsp;exit 0
  64&nbsp;
  65&nbsp;#   As the author of the script notes,
  66&nbsp;#+ "you can easily expand it to create named-hashes in bash."
  67&nbsp;#   (Difficult) exercise for the reader: implement this.</PRE
></TD
></TR
></TABLE
><HR></DIV
><P
>--</P
><P
><A
NAME="PRIMES0"
></A
></P
><P
>Arrays enable implementing a shell script version of the
	<I
CLASS="FIRSTTERM"
>Sieve of Eratosthenes</I
>. 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.</P
><DIV
CLASS="EXAMPLE"
><HR><A
NAME="EX68"
></A
><P
><B
>Example 26-13. The Sieve of Eratosthenes</B
></P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>   1&nbsp;#!/bin/bash
   2&nbsp;# sieve.sh (ex68.sh)
   3&nbsp;
   4&nbsp;# Sieve of Eratosthenes
   5&nbsp;# Ancient algorithm for finding prime numbers.
   6&nbsp;
   7&nbsp;#  This runs a couple of orders of magnitude slower
   8&nbsp;#+ than the equivalent program written in C.
   9&nbsp;
  10&nbsp;LOWER_LIMIT=1       # Starting with 1.
  11&nbsp;UPPER_LIMIT=1000    # Up to 1000.
  12&nbsp;# (You may set this higher . . . if you have time on your hands.)
  13&nbsp;
  14&nbsp;PRIME=1
  15&nbsp;NON_PRIME=0
  16&nbsp;
  17&nbsp;let SPLIT=UPPER_LIMIT/2
  18&nbsp;# Optimization:
  19&nbsp;# Need to test numbers only halfway to upper limit (why?).
  20&nbsp;
  21&nbsp;
  22&nbsp;declare -a Primes
  23&nbsp;# Primes[] is an array.
  24&nbsp;
  25&nbsp;
  26&nbsp;initialize ()
  27&nbsp;{
  28&nbsp;# Initialize the array.
  29&nbsp;
  30&nbsp;i=$LOWER_LIMIT
  31&nbsp;until [ "$i" -gt "$UPPER_LIMIT" ]
  32&nbsp;do
  33&nbsp;  Primes[i]=$PRIME
  34&nbsp;  let "i += 1"
  35&nbsp;done
  36&nbsp;#  Assume all array members guilty (prime)
  37&nbsp;#+ until proven innocent.
  38&nbsp;}
  39&nbsp;
  40&nbsp;print_primes ()
  41&nbsp;{
  42&nbsp;# Print out the members of the Primes[] array tagged as prime.
  43&nbsp;
  44&nbsp;i=$LOWER_LIMIT
  45&nbsp;
  46&nbsp;until [ "$i" -gt "$UPPER_LIMIT" ]
  47&nbsp;do
  48&nbsp;
  49&nbsp;  if [ "${Primes[i]}" -eq "$PRIME" ]
  50&nbsp;  then
  51&nbsp;    printf "%8d" $i
  52&nbsp;    # 8 spaces per number gives nice, even columns.
  53&nbsp;  fi
  54&nbsp;  
  55&nbsp;  let "i += 1"
  56&nbsp;  
  57&nbsp;done
  58&nbsp;
  59&nbsp;}
  60&nbsp;
  61&nbsp;sift () # Sift out the non-primes.
  62&nbsp;{
  63&nbsp;
  64&nbsp;let i=$LOWER_LIMIT+1
  65&nbsp;# We know 1 is prime, so let's start with 2.
  66&nbsp;
  67&nbsp;until [ "$i" -gt "$UPPER_LIMIT" ]
  68&nbsp;do
  69&nbsp;
  70&nbsp;if [ "${Primes[i]}" -eq "$PRIME" ]
  71&nbsp;# Don't bother sieving numbers already sieved (tagged as non-prime).
  72&nbsp;then
  73&nbsp;
  74&nbsp;  t=$i
  75&nbsp;
  76&nbsp;  while [ "$t" -le "$UPPER_LIMIT" ]
  77&nbsp;  do
  78&nbsp;    let "t += $i "
  79&nbsp;    Primes[t]=$NON_PRIME
  80&nbsp;    # Tag as non-prime all multiples.
  81&nbsp;  done
  82&nbsp;
  83&nbsp;fi  
  84&nbsp;
  85&nbsp;  let "i += 1"
  86&nbsp;done  
  87&nbsp;
  88&nbsp;
  89&nbsp;}
  90&nbsp;
  91&nbsp;
  92&nbsp;# ==============================================
  93&nbsp;# main ()
  94&nbsp;# Invoke the functions sequentially.
  95&nbsp;initialize
  96&nbsp;sift
  97&nbsp;print_primes
  98&nbsp;# This is what they call structured programming.
  99&nbsp;# ==============================================
 100&nbsp;
 101&nbsp;echo
 102&nbsp;
 103&nbsp;exit 0
 104&nbsp;
 105&nbsp;
 106&nbsp;
 107&nbsp;# -------------------------------------------------------- #
 108&nbsp;# Code below line will not execute, because of 'exit.'
 109&nbsp;
 110&nbsp;#  This improved version of the Sieve, by Stephane Chazelas,
 111&nbsp;#+ executes somewhat faster.
 112&nbsp;
 113&nbsp;# Must invoke with command-line argument (limit of primes).
 114&nbsp;
 115&nbsp;UPPER_LIMIT=$1                  # From command line.
 116&nbsp;let SPLIT=UPPER_LIMIT/2         # Halfway to max number.
 117&nbsp;
 118&nbsp;Primes=( '' $(seq $UPPER_LIMIT) )
 119&nbsp;
 120&nbsp;i=1
 121&nbsp;until (( ( i += 1 ) &#62; SPLIT ))  # Need check only halfway.
 122&nbsp;do
 123&nbsp;  if [[ -n $Primes[i] ]]
 124&nbsp;  then
 125&nbsp;    t=$i
 126&nbsp;    until (( ( t += i ) &#62; UPPER_LIMIT ))
 127&nbsp;    do
 128&nbsp;      Primes[t]=
 129&nbsp;    done
 130&nbsp;  fi  
 131&nbsp;done  
 132&nbsp;echo ${Primes[*]}
 133&nbsp;
 134&nbsp;exit $?</PRE
></TD
></TR
></TABLE
><HR></DIV
><DIV
CLASS="EXAMPLE"
><HR><A
NAME="EX68A"
></A
><P
><B
>Example 26-14. The Sieve of Eratosthenes, Optimized</B
></P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR