Chapitre 26. Tableaux

#!/bin/bash


aire[11]=23
aire[13]=37
aire[51]=UFOs

# Les membres d'un tableau peuvent ne pas être consécutifs ou contigus.

# Certains membres peuvent rester non initialisés.
# Les trous dans le tableau sont OK.


echo -n "aire[11] = "
echo ${aire[11]}    #  {accolades} nécessaires

echo -n "aire[13] = "
echo ${aire[13]}

echo "Le contenu de aire[51] est ${aire[51]}."

# Le contenu d'une variable non initialisée d'un tableau n'affiche rien.
echo -n "aire[43] = "
echo ${aire[43]}
echo "(aire[43] non affecté)"

echo

# Somme de deux variables tableaux affectée à une troisième.
aire[5]=`expr ${aire[11]} + ${aire[13]}`
echo "aire[5] = aire[11] + aire[13]"
echo -n "aire[5] = "
echo ${aire[5]}

aire[6]=`expr ${aire[11]} + ${aire[51]}`
echo "aire[6] = aire[11] + aire[51]"
echo -n "aire[6] = "
echo ${aire[6]}
# Ceci échoue car ajouter un entier à une chaîne de caractères n'est pas permis.

echo; echo; echo

# -----------------------------------------------------------------
# Autre tableau, "aire2".
# Autre façon d'affecter les variables d'un tableau...
# nom_tableau=( XXX YYY ZZZ ... )

aire2=( zero un deux trois quatre )

echo -n "aire2[0] = "
echo ${aire2[0]}
# Aha, indexage commençant par 0 (le premier élément du tableau est [0], et non
# pas [1]).

echo -n "aire2[1] = "
echo ${aire2[1]}    # [1] est le deuxième élément du tableau.
# -----------------------------------------------------------------

echo; echo; echo

# -----------------------------------------------
# Encore un autre tableau, "aire3".
# Encore une autre façon d'affecter des variables de tableau...
# nom_tableau=([xx]=XXX [yy]=YYY ...)

aire3=([17]=dix-sept [24]=vingt-quatre)

echo -n "aire3[17] = "
echo ${aire3[17]}

echo -n "aire3[24] = "
echo ${aire3[24]}
# -----------------------------------------------

exit 0

#!/bin/bash
# poem.sh

# Lignes d'un poème (simple stanza).
Ligne[1]="I do not know which to prefer,"
Ligne[2]="The beauty of inflections"
Ligne[3]="Or the beauty of innuendoes,"
Ligne[4]="The blackbird whistling"
Ligne[5]="Or just after."

# Attribution.
Attrib[1]=" Wallace Stevens"
Attrib[2]="\"Thirteen Ways of Looking at a Blackbird\""

for index in 1 2 3 4 5    # Cinq lignes.
do
  printf "     %s\n" "${Ligne[index]}"
done

for index in 1 2          # Deux lignes d'attribution.
do
  printf "          %s\n" "${Attrib[index]}"
done

exit 0

#!/bin/bash

declare -a colors
# Permet de déclarer un tableau sans spécifier sa taille.

echo "Entrez vos couleurs favorites (séparés par un espace)."

read -a couleurs  #  Entrez au moins trois couleurs pour démontrer les
                  #+ fonctionnalités ci-dessous.
#  Option spéciale pour la commande 'read',
#+ permettant d'affecter les éléments dans un tableau.

echo

nb_element=${#colors[@]}
# Syntaxe spéciale pour extraire le nombre d'éléments d'un tableau.
#     nb_element=${#colors[*]} fonctionne aussi.
#
#  La variable "@" permet de diviser les mots compris dans des guillemets
#+ (extrait les variables séparées par des espaces blancs).

index=0

while [ "$index" -lt "$nb_element" ]
do    # Liste tous les éléments du tableau.
  echo ${colors[$index]}
  let "index = $index + 1"
done
# Chaque élément du tableau est listé sur une ligne séparée.
# Si ceci n'est pas souhaité, utilisez echo -n "${colors[$index]} "
#
# Pour le faire avec une boucle "for":
#   for i in "${colors[@]}"
#   do
#     echo "$i"
#   done
# (Thanks, S.C.)

echo

#  Encore une fois, liste tous les éléments d'un tableau, mais en utilisant une
#+ méthode plus élégante.
  echo ${colors[@]}          # echo ${colors[*]} fonctionne aussi.

echo

# La commande "unset" supprime les éléments d'un tableau, ou un tableau entier.
unset colors[1]              # Supprime le deuxième élément d'un tableau.
                             # Même effet que   colors[1]=
echo  ${colors[@]}           # Encore un tableau liste, dont le deuxième
			     # élément est manquant.

unset colors                 # Supprime le tableau entier.
                             #  unset colors[*] et
                             #+ unset colors[@] fonctionnent aussi.
echo; echo -n "Colors gone."			   
echo ${colors[@]}            #  Liste le tableau une nouvelle fois, maintenant
                             #+ vide.

exit 0

#!/bin/bash
# empty-array.sh

# Un tableau vide n'est pas la même chose qu'un tableau avec des éléments vides.

tableau0=( first second third )
tableau1=( '' )   # "tableau1" a un élément vide.
tableau2=( )      # Pas d'éléments... "tableau2" est vide.

echo

echo "Elements in tableau0:  ${tableau0[@]}"
echo "Elements in tableau1:  ${tableau1[@]}"
echo "Elements in tableau2:  ${tableau2[@]}"
echo
echo "Length of first element in tableau0 = ${#tableau0}"
echo "Length of first element in tableau1 = ${#tableau1}"
echo "Length of first element in tableau2 = ${#tableau2}"
echo
echo "Number of elements in tableau0 = ${#tableau0[*]}"  # 3
echo "Number of elements in tableau1 = ${#tableau1[*]}"  # 1  (surprise!)
echo "Number of elements in tableau2 = ${#tableau2[*]}"  # 0

echo

exit 0  # Merci, S.C.

#!/bin/bash
# bubble.sh: Tri bulle, en quelque sorte.

# Rappelle l'algorithme de tri bulle. Enfin, une version particulière...

#  A chaque itération successive à travers le tableau à trier, compare deux
#+ éléments adjacents et les échange si ils ne sont pas ordonnés.
#  A la fin du premier tour, l'élémennt le "plus lourd" est arrivé tout en bas.
#  A la fin du deuxième tour, le "plus lourd" qui suit est lui-aussi à la fin
#+ mais avant le "plus lourd".
#  Et ainsi de suite.
#  Ceci signifie que chaque tour a besoin de se balader sur une partie de plus
#+ en plus petite du tableau.
#  Vous aurez donc noté un accélération à l'affichage lors des derniers tours.


echange()
{
  # Echange deux membres d'un tableau
  local temp=${Pays[$1]}      #  Stockage temporaire
                              #+ pour les éléments à échanger.
  Pays[$1]=${Pays[$2]}
  Pays[$2]=$temp
  
  return
}  

declare -a Pays  #  Déclaration d'un tableau,
                 #+ optionnel ici car il est initialisé tout de suite après.

#  Est-il permis de diviser une variable tableau sur plusieurs lignes en
#+ utilisant un caractère d'échappement?
#  Oui.

Pays=(Hollande Ukraine Zaire Turquie Russie Yémen Syrie \
Brésil Argentine Nicaragua Japon Mexique Vénézuela Grèce Angleterre \
Israël Pérou Canada Oman Danemark France Kenya \
Xanadu Qatar Liechtenstein Hongrie)

# "Xanadu" est la place mythique où, selon Coleridge,
#+ Kubla Khan a "pleasure dome decree".


clear                 # Efface l'écran pour commencer.

echo "0: ${Pays[*]}"  # Liste le tableau entier lors du premier tour.

nombre_d_elements=${#Pays[@]}
let "comparaisons = $nombre_d_elements - 1"

index=1 # Nombre de tours.

while [ "$comparaisons" -gt 0 ]          # Début de la boucle externe.
do

  index=0  #  Réinitialise l'index pour commencer au début du tableau à chaque
           #+ tour.

  while [ "$index" -lt "$comparaisons" ] # Début de la boucle interne.
  do
    if [ ${Pays[$index]} \> ${Pays[`expr $index + 1`]} ]
    #  Si non ordonné...
    #  Rappelez-vous que \> est un opérateur de comparaison ASCII à l'intérieur
    #+ de simples crochets.

    #  if [[ ${Pays[$index]} > ${Pays[`expr $index + 1`]} ]]
    #+ fonctionne aussi.
    then
      echange $index `expr $index + 1`  # Echange.
    fi  
    let "index += 1"
  done # Fin de la boucle interne.
  

let "comparaisons -= 1" #  Comme l'élément le "plus lourd" est tombé en bas,
                        #+ nous avons besoin de faire une comparaison de moins
			#+ à chaque tour.

echo
echo "$index: ${Pays[@]}"  # Affiche le tableau résultat à la fin de chaque tour
echo
let "index += 1"                # Incrémente le compteur de tour.

done                            # Fin de la boucle externe.
                                # Fini.

exit 0

#!/bin/bash
# sieve.sh

# Sieve of Eratosthenes
# Ancien algorithme pour trouver les nombres premiers.

# Ceci s'exécute bien moins rapidement que le programme équivalent en C.

LIMITE_BASSE=1       # Commençant avec 1.
LIMITE_HAUTE=1000    # Jusqu'à 1000.
# (Vous pouvez augmenter cette valeur...  si vous avez du temps devant vous.)

PREMIER=1
NON_PREMIER=0

let DIVISE=LIMITE_HAUTE/2
# Optimisation:
# Nécessaire pour tester les nombres à mi-chemin de la limite supérieure.


declare -a Premiers
# Premiers[] est un tableau.


initialise ()
{
# Initialise le tableau.

i=$LIMITE_BASSE
until [ "$i" -gt "$LIMITE_HAUTE" ]
do
  Premiers[i]=$PREMIER
  let "i += 1"
done
# Assume que tous les membres du tableau sont coupables (premiers) avant d'être
# reconnus innocent.
}

affiche_premiers ()
{
# Affiche les membres du tableau Premiers[] indiqués comme premiers.

i=$LIMITE_BASSE

until [ "$i" -gt "$LIMITE_HAUTE" ]
do

  if [ "${Premiers[i]}" -eq "$PREMIER" ]
  then
    printf "%8d" $i
    # 8 espaces par nombre rend l'affichage joli, avec colonne.
  fi
  
  let "i += 1"
  
done

}

examine () # Examine minutieusement les non premiers.
{

let i=$LIMITE_BASSE+1
# Nous savons que 1 est premier, donc commençons avec 2.

until [ "$i" -gt "$LIMITE_HAUTE" ]
do

if [ "${Premiers[i]}" -eq "$PREMIER" ]
#  Ne nous embêtons pas à examiner les nombres déjà examinés (indiqués comme
#+ non premiers).
then

  t=$i

  while [ "$t" -le "$LIMITE_HAUTE" ]
  do
    let "t += $i "
    Premiers[t]=$NON_PREMIER
    # Indiqué comme non premier tous les multiples.
  done

fi  

  let "i += 1"
done  


}


# Appeler les fonctions séquenciellement.
initialise
examine
affiche_premiers
# C'est ce qu'ils appelent de la programmation structurée.

echo

exit 0



# ----------------------------------------------- #
# Le code ci-dessous ne sera pas executé.

# Cette version améliorée de Sieve, par Stephane Chazelas,
# s'exécute un peu plus rapidement.

# Doit être appelé avec un argument en ligne de commande (limite des premiers).

LIMITE_HAUTE=$1                   # A partir de la ligne de commande.
let DIVISE=LIMITE_HAUTE/2         # Mi-chemin du nombre max.

Premiers=( '' $(seq $LIMITE_HAUTE) )

i=1
until (( ( i += 1 ) > DIVISE ))  # A besoin de vérifier à mi-chemin.
do
  if [[ -n $Premiers[i] ]]
  then
    t=$i
    until (( ( t += i ) > LIMITE_HAUTE ))
    do
      Premiers[t]=
    done
  fi  
done  
echo ${Premiers[*]}

exit 0

#!/bin/bash
# stack.sh: simulation d'une pile place-down

#  Similaire à la pile du CPU, une pile "place-down" enregistre les éléments
#+ séquentiellement, mais les récupère en ordre inverse, le dernier entré étant
#+ le premier sorti.

BP=100            # Pointeur de base du tableau de la pile.
                  # Commence à l'élément 100.

SP=$BP            # Pointeur de la pile.
                  # Initialisé à la base (le bas) de la pile.

Donnees=          # Contenu de l'emplacement de la pile.
                  #  Doit être une variable locale à cause de la limitation
                  #+ sur l'échelle de retour de la fonction.

declare -a pile


place()           # Place un élément dans la pile.
{
if [ -z "$1" ]    # Rien à y mettre ?
then
  return
fi

let "SP -= 1"     # Déplace le pointeur de pile.
pile[$SP]=$1

return
}

recupere()               # Récupère un élément de la pile.
{
Donnees=                 # Vide l'élément.

if [ "$SP" -eq "$BP" ]   # Pile vide ?
then
  return
fi                       #  Ceci empêche aussi SP de dépasser 100,
                         #+ donc de dépasser la capacité du tampon.

Donnees=${pile[$SP]}
let "SP += 1"            # Déplace le pointeur de pile.
return
}

rapport_d_etat()          # Recherche ce qui se passe
{
echo "-------------------------------------"
echo "REPORT"
echo "Stack Pointer = $SP"
echo "Just recupereped \""$Donnees"\" off the pile."
echo "-------------------------------------"
echo
}


# =======================================================
# Maintenant, amusons-nous...

echo

# Voyons si nous pouvons récupérer quelque chose d'une pile vide.
recupere
rapport_d_etat

echo

place garbage
recupere
rapport_d_etat     # Garbage in, garbage out.      

valeur1=23; place $valeur1
valeur2=skidoo; place $valeur2
valeur3=FINAL; place $valeur3

recupere              # FINAL
rapport_d_etat
recupere              # skidoo
rapport_d_etat
recupere              # 23
rapport_d_etat        # dernier entré, premier sorti !

#  Remarquez comment le pointeur de pile décrémente à chaque insertion et
#+ incrémente à chaque récupération.

echo
# =======================================================


# Exercices:
# ---------

# 1)  Modifier la fonction "place()" pour permettre le placement de plusieurs
#   + éléments sur la pile en un seul appel.

# 2)  Modifier la fonction "recupere()" pour récupérer plusieurs éléments de la
#   + pile en un seul palle de la fonction.

# 3)  En utilisant ce script comme base, écrire une calculatrice 4 fonctions
#   + basée sur une pile.

exit 0

#!/bin/bash

# Les célèbres "Q-series" de Douglas Hofstadter:

# Q(1) = Q(2) = 1
# Q(n) = Q(n - Q(n-1)) + Q(n - Q(n-2)), for n>2

#  C'est une série chaotique d'entiers avec un comportement étange et non
#+ prévisible.
# Les premiers 20 termes de la série étaient:
# 1 1 2 3 3 4 5 5 6 6 6 8 8 8 10 9 10 11 11 12 

# Voir le livre d'Hofstadter, "Goedel, Escher, Bach: An Eternal Golden Braid",
# p. 137, ff.


LIMITE=100        # Nombre de termes à calculer
LONGUEURLIGNE=20  # Nombre de termes à afficher par ligne.

Q[1]=1            # Les deux premiers termes d'une série sont 1.
Q[2]=1

echo
echo "Q-series [$LIMITE termes]:"
echo -n "${Q[1]} "             # Affiche les deux premiers termes.
echo -n "${Q[2]} "

for ((n=3; n <= $LIMITE; n++))  # Conditions de boucle style C.
do   # Q[n] = Q[n - Q[n-1]] + Q[n - Q[n-2]]  for n>2
# Nécessaire de casser l'expression en des termes intermédiaires.
# car Bash ne gère pas très bien l'arithmétique des tableaux complexes.

  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 % $LONGUEURLIGNE` -eq 0 ]    # Formatte la sortie.
then   #     mod
  echo # Retour chariot pour des ensembles plus jolis.
fi

done

echo

exit 0

# C'est une implémentation itérative la Q-series.
# L'implémentation récursive plus intuitive est laissée comme exercice.
# Attention: calculer cette série récursivement prend *beaucoup* de temps.

#!/bin/bash
# Simuler un tableau à deux dimensions.

# Un tableau à deux dimensions stocke les lignes séquentiellement.

Lignes=5
Colonnes=5

declare -a alpha     # char alpha [Lignes] [Colonnes];
                     # Déclaration inutile.

charge_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 ligne=`expr $rc / $Colonnes`
  local colonne=`expr $rc % $Lignes`
  let "index = $ligne * $Lignes + $colonne"
  alpha[$index]=$i   # alpha[$ligne][$colonne]
  let "rc += 1"
done  

# Un peu plus simple
#   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 )
# mais il manque néanmoins le "bon goût" d'un tableau à deux dimensions.
}

affiche_alpha ()
{
local ligne=0
local index

echo

while [ "$ligne" -lt "$Lignes" ]  # Affiche dans l'ordre des lignes -
do                                # les colonnes varient
                                  # tant que ligne (la boucle externe) reste
				  # identique
  local colonne=0
  
  while [ "$colonne" -lt "$Colonnes" ]
  do
    let "index = $ligne * $Lignes + $colonne"
    echo -n "${alpha[index]} "  # alpha[$ligne][$colonne]
    let "colonne += 1"
  done

  let "ligne += 1"
  echo

done  

# Un équivalent plus simple serait
#   echo ${alpha[*]} | xargs -n $Colonnes

echo
}

filtrer ()     # Filtrer les index négatifs du tableau.
{

echo -n "  "

if [[ "$1" -ge 0 &&  "$1" -lt "$Lignes" && "$2" -ge 0 && "$2" -lt "$Colonnes" ]]
then
    let "index = $1 * $Lignes + $2"
    # Maintenan, l'affiche après rotation.
    echo -n " ${alpha[index]}"  # alpha[$ligne][$colonne]
fi    

}
  



rotate ()  # Bascule le tableau de 45 degrés
{          # (le "balance" sur le côté gauche en bas).
local ligne
local colonne

for (( ligne = Lignes; ligne > -Lignes; ligne-- ))  # Traverse le tableau en
#	sens inverse.
do

  for (( colonne = 0; colonne < Colonnes; colonne++ ))
  do

    if [ "$ligne" -ge 0 ]
    then
      let "t1 = $colonne - $ligne"
      let "t2 = $colonne"
    else
      let "t1 = $colonne"
      let "t2 = $colonne + $ligne"
    fi  

    filtrer $t1 $t2   # Filtre les index négatifs du tableau.
  done

  echo; echo

done 

# Rotation du tableau inspirée par les exemples (pp. 143-146) de
# "Advanced C Programming on the IBM PC", par Herbert Mayer
# (voir bibliographie).

}


#-----------------------------------------------------#
charge_alpha     # Charge le tableau.
affiche_alpha    # L'affiche.
rotate           # Le fait basculer sur 45 degrés dans le sens contraire des
                 # aiguilles d'une montre.
#-----------------------------------------------------#


# C'est une simulation assez peu satisfaisante.
#
# Exercices:
# ---------
# 1)  Réécrire le chargement du tableau et les fonctions d'affichage
#   + d'une façon plus intuitive et élégante.
#
# 2)  Comprendre comment les fonctions de rotation fonctionnent.
#     Astuce: pensez aux implications de l'indexage arrière du tableau.

exit 0