arrays.html

Shall高级编程

><TD
><PRE
CLASS="PROGRAMLISTING"
>   1&nbsp;#!/bin/bash
   2&nbsp;# Optimized Sieve of Eratosthenes
   3&nbsp;# Script by Jared Martin, with very minor changes by ABS Guide author.
   4&nbsp;# Used in ABS Guide with permission (thanks!).
   5&nbsp;
   6&nbsp;# Based on script in Advanced Bash Scripting Guide.
   7&nbsp;# http://tldp.org/LDP/abs/html/arrays.html#PRIMES0 (ex68.sh).
   8&nbsp;
   9&nbsp;# http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf (reference)
  10&nbsp;# Check results against http://primes.utm.edu/lists/small/1000.txt
  11&nbsp;
  12&nbsp;# Necessary but not sufficient would be, e.g.,
  13&nbsp;#     (($(sieve 7919 | wc -w) == 1000)) &#38;&#38; echo "7919 is the 1000th prime"
  14&nbsp;
  15&nbsp;UPPER_LIMIT=${1:?"Need an upper limit of primes to search."}
  16&nbsp;
  17&nbsp;Primes=( '' $(seq ${UPPER_LIMIT}) )
  18&nbsp;
  19&nbsp;typeset -i i t
  20&nbsp;Primes[i=1]='' # 1 is not a prime.
  21&nbsp;until (( ( i += 1 ) &#62; (${UPPER_LIMIT}/i) ))  # Need check only ith-way.
  22&nbsp;  do                                         # Why?
  23&nbsp;    if ((${Primes[t=i*(i-1), i]}))
  24&nbsp;    # Obscure, but instructive, use of numeric eval in subscript.
  25&nbsp;    then
  26&nbsp;      until (( ( t += i ) &#62; ${UPPER_LIMIT} ))
  27&nbsp;        do Primes[t]=; done
  28&nbsp;    fi
  29&nbsp;  done
  30&nbsp;
  31&nbsp;# echo ${Primes[*]}
  32&nbsp;echo   # Change to original script for pretty-printing (80-col. display).
  33&nbsp;printf "%8d" ${Primes[*]}
  34&nbsp;echo; echo
  35&nbsp;
  36&nbsp;exit $?</PRE
></TD
></TR
></TABLE
><HR></DIV
><P
>Compare these array-based prime number generators with an
        alternative that does not use arrays, <A
HREF="contributed-scripts.html#PRIMES"
>Example A-16</A
>.</P
><P
>--</P
><P
>Arrays lend themselves, to some extent, to emulating data
        structures for which Bash has no native support.</P
><P
><A
NAME="STACKEX0"
></A
></P
><DIV
CLASS="EXAMPLE"
><HR><A
NAME="STACKEX"
></A
><P
><B
>Example 26-15. Emulating a push-down stack</B
></P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>   1&nbsp;#!/bin/bash
   2&nbsp;# stack.sh: push-down stack simulation
   3&nbsp;
   4&nbsp;#  Similar to the CPU stack, a push-down stack stores data items
   5&nbsp;#+ sequentially, but releases them in reverse order, last-in first-out.
   6&nbsp;
   7&nbsp;BP=100            #  Base Pointer of stack array.
   8&nbsp;                  #  Begin at element 100.
   9&nbsp;
  10&nbsp;SP=$BP            #  Stack Pointer.
  11&nbsp;                  #  Initialize it to "base" (bottom) of stack.
  12&nbsp;
  13&nbsp;Data=             #  Contents of stack location.  
  14&nbsp;                  #  Must use global variable,
  15&nbsp;                  #+ because of limitation on function return range.
  16&nbsp;
  17&nbsp;declare -a stack
  18&nbsp;
  19&nbsp;
  20&nbsp;push()            # Push item on stack.
  21&nbsp;{
  22&nbsp;if [ -z "$1" ]    # Nothing to push?
  23&nbsp;then
  24&nbsp;  return
  25&nbsp;fi
  26&nbsp;
  27&nbsp;let "SP -= 1"     # Bump stack pointer.
  28&nbsp;stack[$SP]=$1
  29&nbsp;
  30&nbsp;return
  31&nbsp;}
  32&nbsp;
  33&nbsp;pop()                    # Pop item off stack.
  34&nbsp;{
  35&nbsp;Data=                    # Empty out data item.
  36&nbsp;
  37&nbsp;if [ "$SP" -eq "$BP" ]   # Stack empty?
  38&nbsp;then
  39&nbsp;  return
  40&nbsp;fi                       #  This also keeps SP from getting past 100,
  41&nbsp;                         #+ i.e., prevents a runaway stack.
  42&nbsp;
  43&nbsp;Data=${stack[$SP]}
  44&nbsp;let "SP += 1"            # Bump stack pointer.
  45&nbsp;return
  46&nbsp;}
  47&nbsp;
  48&nbsp;status_report()          # Find out what's happening.
  49&nbsp;{
  50&nbsp;echo "-------------------------------------"
  51&nbsp;echo "REPORT"
  52&nbsp;echo "Stack Pointer = $SP"
  53&nbsp;echo "Just popped \""$Data"\" off the stack."
  54&nbsp;echo "-------------------------------------"
  55&nbsp;echo
  56&nbsp;}
  57&nbsp;
  58&nbsp;
  59&nbsp;# =======================================================
  60&nbsp;# Now, for some fun.
  61&nbsp;
  62&nbsp;echo
  63&nbsp;
  64&nbsp;# See if you can pop anything off empty stack.
  65&nbsp;pop
  66&nbsp;status_report
  67&nbsp;
  68&nbsp;echo
  69&nbsp;
  70&nbsp;push garbage
  71&nbsp;pop
  72&nbsp;status_report     # Garbage in, garbage out.      
  73&nbsp;
  74&nbsp;value1=23; push $value1
  75&nbsp;value2=skidoo; push $value2
  76&nbsp;value3=FINAL; push $value3
  77&nbsp;
  78&nbsp;pop              # FINAL
  79&nbsp;status_report
  80&nbsp;pop              # skidoo
  81&nbsp;status_report
  82&nbsp;pop              # 23
  83&nbsp;status_report    # Last-in, first-out!
  84&nbsp;
  85&nbsp;#  Notice how the stack pointer decrements with each push,
  86&nbsp;#+ and increments with each pop.
  87&nbsp;
  88&nbsp;echo
  89&nbsp;
  90&nbsp;exit 0
  91&nbsp;
  92&nbsp;# =======================================================
  93&nbsp;
  94&nbsp;
  95&nbsp;# Exercises:
  96&nbsp;# ---------
  97&nbsp;
  98&nbsp;# 1)  Modify the "push()" function to permit pushing
  99&nbsp;#   + multiple element on the stack with a single function call.
 100&nbsp;
 101&nbsp;# 2)  Modify the "pop()" function to permit popping
 102&nbsp;#   + multiple element from the stack with a single function call.
 103&nbsp;
 104&nbsp;# 3)  Add error checking to the critical functions.
 105&nbsp;#     That is, return an error code, depending on
 106&nbsp;#   + successful or unsuccessful completion of the operation,
 107&nbsp;#   + and take appropriate action.
 108&nbsp;
 109&nbsp;# 4)  Using this script as a starting point,
 110&nbsp;#   + write a stack-based 4-function calculator.</PRE
></TD
></TR
></TABLE
><HR></DIV
><P
>--</P
><P
>Fancy manipulation of array <SPAN
CLASS="QUOTE"
>"subscripts"</SPAN
> may require
        intermediate variables. For projects involving this, again consider
	using a more powerful programming language, such as Perl or C.</P
><DIV
CLASS="EXAMPLE"
><HR><A
NAME="QFUNCTION"
></A
><P
><B
>Example 26-16. Complex array application:
             <SPAN
CLASS="emphasis"
><I
CLASS="EMPHASIS"
>Exploring a weird mathematical series</I
></SPAN
></B
></P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>   1&nbsp;#!/bin/bash
   2&nbsp;
   3&nbsp;# Douglas Hofstadter's notorious "Q-series":
   4&nbsp;
   5&nbsp;# Q(1) = Q(2) = 1
   6&nbsp;# Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), for n&#62;2
   7&nbsp;
   8&nbsp;#  This is a "chaotic" integer series with strange
   9&nbsp;#+ and unpredictable behavior.
  10&nbsp;#  The first 20 terms of the series are:
  11&nbsp;#  1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 
  12&nbsp;
  13&nbsp;#  See Hofstadter's book, _Goedel, Escher, Bach: An Eternal Golden Braid_,
  14&nbsp;#+ p. 137, ff.
  15&nbsp;
  16&nbsp;
  17&nbsp;LIMIT=100     # Number of terms to calculate.
  18&nbsp;LINEWIDTH=20  # Number of terms printed per line.
  19&nbsp;
  20&nbsp;Q[1]=1        # First two terms of series are 1.
  21&nbsp;Q[2]=1
  22&nbsp;
  23&nbsp;echo
  24&nbsp;echo "Q-series [$LIMIT terms]:"
  25&nbsp;echo -n "${Q[1]} "             # Output first two terms.
  26&nbsp;echo -n "${Q[2]} "
  27&nbsp;
  28&nbsp;for ((n=3; n &#60;= $LIMIT; n++))  # C-like loop expressions.
  29&nbsp;do   # Q[n] = Q[n - Q[n-1]] + Q[n - Q[n-2]]  for n&#62;2
  30&nbsp;#    Need to break the expression into intermediate terms,
  31&nbsp;#+   since Bash doesn't handle complex array arithmetic very well.
  32&nbsp;
  33&nbsp;  let "n1 = $n - 1"        # n-1
  34&nbsp;  let "n2 = $n - 2"        # n-2
  35&nbsp;  
  36&nbsp;  t0=`expr $n - ${Q[n1]}`  # n - Q[n-1]
  37&nbsp;  t1=`expr $n - ${Q[n2]}`  # n - Q[n-2]
  38&nbsp;  
  39&nbsp;  T0=${Q[t0]}              # Q[n - Q[n-1]]
  40&nbsp;  T1=${Q[t1]}              # Q[n - Q[n-2]]
  41&nbsp;
  42&nbsp;Q[n]=`expr $T0 + $T1`      # Q[n - Q[n-1]] + Q[n - Q[n-2]]
  43&nbsp;echo -n "${Q[n]} "
  44&nbsp;
  45&nbsp;if [ `expr $n % $LINEWIDTH` -eq 0 ]    # Format output.
  46&nbsp;then   #      ^ modulo
  47&nbsp;  echo # Break lines into neat chunks.
  48&nbsp;fi
  49&nbsp;
  50&nbsp;done
  51&nbsp;
  52&nbsp;echo
  53&nbsp;
  54&nbsp;exit 0
  55&nbsp;
  56&nbsp;#  This is an iterative implementation of the Q-series.
  57&nbsp;#  The more intuitive recursive implementation is left as an exercise.
  58&nbsp;#  Warning: calculating this series recursively takes a VERY long time
  59&nbsp;#+ via a script. C/C++ would be more suitable.</PRE
></TD
></TR
></TABLE
><HR></DIV
><P
>--</P
><P
><A
NAME="ARRAYMULTIDIM"
></A
></P
><P
>Bash supports only one-dimensional arrays, though a little
        trickery permits simulating multi-dimensional ones.</P
><DIV
CLASS="EXAMPLE"
><HR><A
NAME="TWODIM"
></A
><P
><B
>Example 26-17. Simulating a two-dimensional array, then tilting it</B
></P
><TABLE
BORDER="0"
BGCOLOR="#E0E0E0"
WIDTH="100%"
><TR
><TD
><PRE
CLASS="PROGRAMLISTING"
>   1&nbsp;#!/bin/bash
   2&nbsp;# twodim.sh: Simulating a two-dimensional array.
   3&nbsp;
   4&nbsp;# A one-dimensional array consists of a single row.
   5&nbsp;# A two-dimensional array stores rows sequentially.
   6&nbsp;
   7&nbsp;Rows=5
   8&nbsp;Columns=5
   9&nbsp;# 5 X 5 Array.
  10&nbsp;
  11&nbsp;declare -a alpha     # char alpha [Rows] [Columns];
  12&nbsp;                     # Unnecessary declaration. Why?
  13&nbsp;
  14&nbsp;load_alpha ()
  15&nbsp;{
  16&nbsp;local rc=0
  17&nbsp;local index
  18&nbsp;
  19&nbsp;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
  20&nbsp;do     # Use different symbols if you like.
  21&nbsp;  local row=`expr $rc / $Columns`
  22&nbsp;  local column=`expr $rc % $Rows`
  23&nbsp;  let "index = $row * $Rows + $column"
  24&nbsp;  alpha[$index]=$i
  25&nbsp;# alpha[$row][$column]
  26&nbsp;  let "rc += 1"
  27&nbsp;done  
  28&nbsp;
  29&nbsp;#  Simpler would be
  30&nbsp;#+   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 )
  31&nbsp;#+ but this somehow lacks the "flavor" of a two-dimensional array.
  32&nbsp;}
  33&nbsp;
  34&nbsp;print_alpha ()
  35&nbsp;{
  36&nbsp;local row=0
  37&nbsp;local index
  38&nbsp;
  39&nbsp;echo
  40&nbsp;
  41&nbsp;while [ "$row" -lt "$Rows" ]   #  Print out in "row major" order:
  42&nbsp;do                             #+ columns vary,
  43&nbsp;                               #+ while row (outer loop) remains the same.
  44&nbsp;  local column=0
  45&nbsp;
  46&nbsp;  echo -n "       "            #  Lines up "square" array with rotated one.
  47&nbsp;  
  48&nbsp;  while [ "$column" -lt "$Columns" ]
  49&nbsp;  do
  50&nbsp;    let "index = $row * $Rows + $column"
  51&nbsp;    echo -n "${alpha[index]} "  # alpha[$row][$column]
  52&nbsp;    let "column += 1"
  53&nbsp;  done
  54&nbsp;
  55&nbsp;  let "row += 1"
  56&nbsp;  echo
  57&nbsp;
  58&nbsp;done  
  59&nbsp;
  60&nbsp;# The simpler equivalent is
  61&nbsp;#     echo ${alpha[*]} | xargs -n $Columns
  62&nbsp;
  63&nbsp;echo
  64&nbsp;}
  65&nbsp;
  66&nbsp;filter ()     # Filter out negative array indices.
  67&nbsp;{
  68&nbsp;
  69&nbsp;echo -n "  "  # Provides the tilt.
  70&nbsp;              # Explain how.
  71&nbsp;
  72&nbsp;if [[ "$1" -ge 0 &#38;&#38;  "$1" -lt "$Rows" &#38;&#38; "$2" -ge 0 &#38;&#38; "$2" -lt "$Columns" ]]
  73&nbsp;then
  74&nbsp;    let "index = $1 * $Rows + $2"
  75&nbsp;    # Now, print it rotated.
  76&nbsp;    echo -n " ${alpha[index]}"
  77&nbsp;    #           alpha[$row][$column]
  78&nbsp;fi    
  79&nbsp;
  80&nbsp;}
  81&nbsp;  
  82&nbsp;
  83&nbsp;
  84&nbsp;
  85&nbsp;rotate ()  #  Rotate the array 45 degrees --
  86&nbsp;{          #+ "balance" it on its lower lefthand corner.
  87&nbsp;local row
  88&nbsp;local column
  89&nbsp;
  90&nbsp;for (( row = Rows; row &#62; -Rows; row-- ))
  91&nbsp;  do       # Step through the array backwards. Why?
  92&nbsp;
  93&nbsp;  for (( column = 0; column &#60; Columns; column++ ))
  94&nbsp;  do
  95&nbsp;
  96&nbsp;    if [ "$row" -ge 0 ]
  97&nbsp;    then
  98&nbsp;      let "t1 = $column - $row"
  99&nbsp;      let "t2 = $column"
 100&nbsp;    else
 101&nbsp;      let "t1 = $column"
 102&nbsp;      let "t2 = $column + $row"
 103&nbsp;    fi  
 104&nbsp;
 105&nbsp;    filter $t1 $t2   # Filter out negative array indices.
 106&nbsp;                     # What happens if you don't do this?
 107&nbsp;  done
 108&nbsp;
 109&nbsp;  echo; echo
 110&nbsp;
 111&nbsp;done 
 112&nbsp;
 113&nbsp;#  Array rotation inspired by examples (pp. 143-146) in
 114&nbsp;#+ "Advanced C Programming on the IBM PC," by Herbert Mayer
 115&nbsp;#+ (see bibliography).
 116&nbsp;#  This just goes to show that much of what can be done in C
 117&nbsp;#+ can also be done in shell scripting.
 118&nbsp;
 119&nbsp;}
 120&nbsp;
 121&nbsp;
 122&nbsp;#--------------- Now, let the show begin. ------------#
 123&nbsp;load_alpha     # Load the array.
 124&nbsp;print_alpha    # Print it out.  
 125&nbsp;rotate         # Rotate it 45 degrees counterclockwise.
 126&nbsp;#-----------------------------------------------------#
 127&nbsp;
 128&nbsp;exit 0
 129&nbsp;
 130&nbsp;# This is a rather contrived, not to mention inelegant simulation.
 131&nbsp;
 132&nbsp;# Exercises:
 133&nbsp;# ---------
 134&nbsp;# 1)  Rewrite the array loading and printing functions
 135&nbsp;#     in a more intuitive and less kludgy fashion.
 136&nbsp;#
 137&nbsp;# 2)  Figure out how the array rotation functions work.
 138&nbsp;#     Hint: think about the implications of backwards-indexing an array.
 139&nbsp;#
 140&nbsp;# 3)  Rewrite this script to handle a non-square array,
 141&nbsp;#     such as a 6 X 4 one.
 142&nbsp;#     Try to minimize "distortion" when the array is rotated.</PRE
></TD
></TR
></TABLE
><HR></DIV
><P
>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
	<I
CLASS="FIRSTTERM"
>row</I
> and <I
CLASS="FIRSTTERM"
>column</I
>
	posi