IN102-08 Tableaux.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {
    "slideshow": {
     "slide_type": "slide"
    },
    "toc": true
   },
   "source": [
    "<h1>Sommaire<span class=\"tocSkip\"></span></h1>\n",
    "<div class=\"toc\"><ul class=\"toc-item\"><li><span><a href=\"#Les-tableaux\" data-toc-modified-id=\"Les-tableaux-1\"><span class=\"toc-item-num\">1&nbsp;&nbsp;</span>Les tableaux</a></span><ul class=\"toc-item\"><li><span><a href=\"#Tableaux-statiques-en-C\" data-toc-modified-id=\"Tableaux-statiques-en-C-1.1\"><span class=\"toc-item-num\">1.1&nbsp;&nbsp;</span>Tableaux statiques en C</a></span></li><li><span><a href=\"#Tableaux-à-longueur-variable\" data-toc-modified-id=\"Tableaux-à-longueur-variable-1.2\"><span class=\"toc-item-num\">1.2&nbsp;&nbsp;</span>Tableaux à longueur variable</a></span></li><li><span><a href=\"#Accès-à-un-tableau\" data-toc-modified-id=\"Accès-à-un-tableau-1.3\"><span class=\"toc-item-num\">1.3&nbsp;&nbsp;</span>Accès à un tableau</a></span></li><li><span><a href=\"#Tableaux-et-arithmétique-des-pointeurs\" data-toc-modified-id=\"Tableaux-et-arithmétique-des-pointeurs-1.4\"><span class=\"toc-item-num\">1.4&nbsp;&nbsp;</span>Tableaux et arithmétique des pointeurs</a></span></li><li><span><a href=\"#Débordement\" data-toc-modified-id=\"Débordement-1.5\"><span class=\"toc-item-num\">1.5&nbsp;&nbsp;</span>Débordement</a></span></li><li><span><a href=\"#Tableaux-et-fonctions\" data-toc-modified-id=\"Tableaux-et-fonctions-1.6\"><span class=\"toc-item-num\">1.6&nbsp;&nbsp;</span>Tableaux et fonctions</a></span></li><li><span><a href=\"#Tableaux-de-struct\" data-toc-modified-id=\"Tableaux-de-struct-1.7\"><span class=\"toc-item-num\">1.7&nbsp;&nbsp;</span>Tableaux de struct</a></span></li></ul></li></ul></div>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Attention:** Pour activer le langage C, executer le code suivant avec Shift+Entrée où avec le bouton \"Run\"."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Collecting git+git://github.com/frehseg/gcc4jupyter\n",
      "  Cloning git://github.com/frehseg/gcc4jupyter to /tmp/pip-req-build-q812wzsk\n",
      "  Running command git clone -q git://github.com/frehseg/gcc4jupyter /tmp/pip-req-build-q812wzsk\n",
      "Requirement already satisfied (use --upgrade to upgrade): GCCPlugin==0.0.6 from git+git://github.com/frehseg/gcc4jupyter in /opt/conda/lib/python3.7/site-packages\n",
      "Building wheels for collected packages: GCCPlugin\n",
      "  Building wheel for GCCPlugin (setup.py) ... \u001b[?25ldone\n",
      "\u001b[?25h  Created wheel for GCCPlugin: filename=GCCPlugin-0.0.6-cp37-none-any.whl size=2931 sha256=7a6ff6d686b9e07ec0ca7419a796a1639760ffd0384351d987d22294688c0071\n",
      "  Stored in directory: /tmp/pip-ephem-wheel-cache-t3e123s9/wheels/a6/ff/b4/023d42d3ec7c36b10e15db2a808aae8b2475e19fa6e370f85c\n",
      "Successfully built GCCPlugin\n"
     ]
    }
   ],
   "source": [
    "!pip install git+git://github.com/frehseg/gcc4jupyter\n",
    "%load_ext gcc_plugin"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {
    "raw_mimetype": "text/markdown"
   },
   "source": [
    "<script>\n",
    "    console.log(\"Hello. You'll see this printed in your browser's DevTools / Console. Feel free to delete this line.\");\n",
    "    document.querySelector('head').innerHTML += '<style>.slides { zoom: 1.0 !important; }</style>';\n",
    "</script>"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# Les tableaux\n",
    "Un tableau est un ensemble de ≪ cases ≫ mémoire consécutives.\n",
    "Toutes les ≪ cases ≫ ont le même type.\n",
    "On accède immédiatement à une case particulière (≪ élément ≫) par indexation.\n",
    "Un tableau répond au besoin de stocker plusieurs données de même type et d’accéder rapidement (en temps constant) à n’importe quel élément.\n",
    "\n",
    "## Tableaux statiques en C\n",
    "Par statique, on entend ≪ dont la taille est connue à la compilation ≫. La taille des tableaux statiques est un nombre fixe au lieu d'une variable.\n",
    "\n",
    "Comme les variables, les tableaux doivent être déclarés : \n",
    "\n",
    "   _type-élément_ nom `[` _taille-constant_ `];`\n",
    "\n",
    "Voici un programme :\n",
    "```\n",
    "int main () {\n",
    "  float tf [10] ; // Tableau de 10 flottants.\n",
    "  int ti [5] ; // Tableau de 5 entiers signés. \n",
    "  return (0) ;\n",
    "}\n",
    "```\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tableaux à longueur variable\n",
    "Si la taille d'un tableau est spécifiée par une variable, on parle d'un __tableaux à longueur variable__. Ceci est permis seulement depuis le standard C99, introduit en 1999.\n",
    "Attention: ça ne veut pas dire qu'on peut\n",
    "changer la taille du tableau après l'avoir défini.\n",
    "\n",
    "Déclaration d'un tableau à longueur variable :\n",
    "\n",
    "   _type-élément_ nom `[` _variable-entier_ `];`\n",
    "\n",
    "Voici un programme :\n",
    "\n",
    "```\n",
    "int main () {\n",
    "  int n =17;\n",
    "  float tf [n] ; // Tableau de 17 flottants.\n",
    "  int ti [n+1] ; // Tableau de 18 entiers signés.\n",
    "  return (0) ;\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Accès à un tableau\n",
    "L’élément d’indice `i` d’un tableau `t` est dénoté par `t[i]`.\n",
    "Les indices de tableaux (≪ numéros de cases ≫) commencent à 0! Donc un tableau de taille `n` a\n",
    "des ≪numéros de cases ≫ de 0 à `n−1`."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "int main() {\n",
    "    int T[3];\n",
    "    T[0]=17;\n",
    "    printf(\"%d\\n\",T[0]);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tableaux et arithmétique des pointeurs\n",
    "\n",
    "Si on declare un tableau `T` avec\n",
    "```int T[3]```\n",
    "la variable `T` est un pointeur qui pointe vers la première case du tableau. On peut accéder au premier élément du tableau avec `*T`, comme avec tout autre pointeur."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 24,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "int main() {\n",
    "    int T[3];\n",
    "    T[0]=17;\n",
    "    printf(\"%d\\n\",*T); // on peut utiliser T comme pointeur\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour accéder à l'élément d'index `i`, on peut calculer son adresse avec la formule:\n",
    "> adresse de `T[i]` = adresse stocké dans `T` + `i`*(taille des éléments de `T`)\n",
    "\n",
    "Dans C, ceci s'écrit simplement avec \n",
    "> `adresse = T+i`\n",
    "\n",
    "car le compilateur replace automatiquement le `+i` avec\n",
    ">`i`*(taille des éléments de `T`.\n",
    "\n",
    "Ce calcul s'appele **l'arithmétique des pointeurs**."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 25,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0x7ffe5d720754\n",
      "0x7ffe5d720754\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "int main() {\n",
    "    int T[3];\n",
    "    int* adresse = T+2; // calcul de l'adresse de T[2]\n",
    "    printf(\"%p\\n\",&T[2]); // l'adresse de T[2]\n",
    "    printf(\"%p\\n\",adresse); // l'adresse calculé est la même\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "On peut accéder à un élément du tableau en utilisant un pointeur dont l'adresse était calculé."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 26,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "3\n",
      "3\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "int main() {\n",
    "    int T[3];\n",
    "    T[2]=3;\n",
    "    int* adresse = T+2; // calcul de l'adresse de T[2]\n",
    "    printf(\"%d\\n\",T[2]); \n",
    "    printf(\"%d\\n\",*adresse); // accès à T[2] via le pointeur\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici un exemple pour illustrer que les cases du tableau se suivent. On peut le voir en affichant leur adresses:"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 44,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "0x7ffe284493fc\n",
      "0x7ffe28449400\n",
      "0x7ffe28449404\n",
      "0x7ffe28449404\n",
      "22\n",
      "0x7ffe284493f0\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "int main() {\n",
    "    int T[3];\n",
    "    T[0]=17;\n",
    "    T[1]=31;\n",
    "    T[2]=22;\n",
    "    int* adr = T+2; // calcul de l'adresse de T[2]\n",
    "    printf(\"%p\\n\",&T[0]); // l'adresse de T[0]\n",
    "    printf(\"%p\\n\",&T[1]); // l'adresse de T[1]\n",
    "    printf(\"%p\\n\",&T[2]); // l'adresse de T[2]\n",
    "    printf(\"%p\\n\",adr);   // le contenu du pointer adr\n",
    "    printf(\"%d\\n\",*adr);  // accès à T[2] via le pointeur\n",
    "    printf(\"%p\\n\",&adr);  // l'adresse où est stocké le pointer adr\n",
    "                          // (peut être avant ou après T)\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| variable  | adresse | contenu |\n",
    "| -- | -- | -- |\n",
    "| adr |1036 | 1032 |\n",
    "| T[2] |1032 | 22 |\n",
    "| T[1] |1028 |  31  |\n",
    "| T[0] | 1024 | 17 | "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Débordement\n",
    "Pour être le plus rapide possible, C ne véfifie pas si l'indice dépasse la taille du tableau.\n",
    "Si on accède au tableau avec un indice trop grand (ou négatif), le programme peut s'arrêter brutalement quand on accède à une zone de mémoire interdite (\"segmentation fault\"). Mais tant qu'on reste à l'intérieur de la zone mémoire du programme, on n'a pas d'erreur. Il se peut alors qu'un bug du programme reste indétecté."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 14,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "17\n",
      "1700068352\n",
      "-1354721888\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "int main() {\n",
    "    int T[3];\n",
    "    T[0]=5;\n",
    "    T[1]=11;\n",
    "    T[2]=17;\n",
    "    printf(\"%d\\n\",T[2]);\n",
    "    printf(\"%d\\n\",T[3]); // pas d'erreur, mais résultat aléatoire\n",
    "    printf(\"%d\\n\",T[-1]); // pas d'erreur, mais résultat aléatoire\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si on dépasse un tableau, on peut (sans se rendre compte) accéder à d'autres variables du même programme."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "11\n",
      "23\n",
      "47\n",
      "23\n",
      "47\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "int main() {\n",
    "    int T[2];\n",
    "    T[0]=5;\n",
    "    T[1]=11;\n",
    "    int X[2];\n",
    "    X[0]=23;\n",
    "    X[1]=47;\n",
    "    printf(\"%d\\n\",T[1]); // le dernier élément de T\n",
    "    printf(\"%d\\n\",T[2]); // en dépassant T, on accède X, qui suit\n",
    "    printf(\"%d\\n\",T[3]); // en dépassant T, on accède X, qui suit\n",
    "    printf(\"%d\\n\",X[0]); \n",
    "    printf(\"%d\\n\",X[1]); \n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Pour accéder à `T[2]`, le compilateur calcule l'adresse avec la formule  `T+2 * sizeof(int)`, puisque T est un tableau de `int`. Typiquement, `sizeof(int)` vaut 4. Dans l'exemple ci-dessous, c'est l'adresse 1024+2*4=1032, ci qui est l'adresse de `X[0]`. "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "| variable  | adresse | contenu |\n",
    "| -- | -- | -- |\n",
    "| X[1] | 1036 | 47 |\n",
    "| X[0] | 1032 | 23 |\n",
    "| T[1] | 1028 |  11  |\n",
    "| T[0] | 1024 | 5 | "
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tableaux et fonctions\n",
    "\n",
    "Pour passer un tableau `T` à une fonction il y a deux façons équivalents : comme un tableau, suivi par `[]`, ou comme un pointeur, précédé par `*`. Par exemple :\n",
    "\n",
    "> ```void afficher(int T[], int n)```\n",
    "\n",
    "> ```void afficher(int* T, int n)```\n",
    "\n",
    "Dans les deux cas, le corps de la fonction est le même. Voici un exemple pour afficher un tableau d'entiers de longueur `n`:\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 46,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "11\n",
      "17\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "void afficher(int T[], int n) {\n",
    "    for (int i = 0; i<n; ++i) {\n",
    "        printf(\"%d\\n\",T[i]);\n",
    "    }\n",
    "}\n",
    "int main() {\n",
    "    int T[3];\n",
    "    T[0]=5;\n",
    "    T[1]=11;\n",
    "    T[2]=17;\n",
    "    afficher(T,3);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Si on passe `T` comme pointeur, ça ne change rien :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 47,
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "5\n",
      "11\n",
      "17\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "void afficher(int* T, int n) {\n",
    "    for (int i = 0; i<n; ++i) {\n",
    "        printf(\"%d\\n\",T[i]);\n",
    "    }\n",
    "}\n",
    "int main() {\n",
    "    int T[3];\n",
    "    T[0]=5;\n",
    "    T[1]=11;\n",
    "    T[2]=17;\n",
    "    afficher(T,3);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## Tableaux de struct\n",
    "\n",
    "Un tableau de struct se déclare de façon analogue aux tableau des types de base."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 37,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "1,2\n",
      "\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "struct point {\n",
    "    int x;\n",
    "    int y;\n",
    "};\n",
    "int main(){\n",
    "    struct point T[3];\n",
    "    T[0].x=1;\n",
    "    T[0].y=2;\n",
    "    printf(\"%d,%d\\n\",T[0].x,T[0].y);\n",
    "}"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Voici un exemple où on passe un tableau de struct à une fonction :"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 53,
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "(1,2)(3,4)(5,6)\n"
     ]
    }
   ],
   "source": [
    "%%c\n",
    "#include <stdio.h>\n",
    "struct point {\n",
    "    int x,y;\n",
    "};\n",
    "void afficher_point(struct point P) {\n",
    "    printf(\"(%d,%d)\",P.x,P.y);\n",
    "}\n",
    "void afficher_tableau(struct point T[], int n) {\n",
    "    for (int i=0;i<n;++i) {\n",
    "        afficher_point(T[i]);\n",
    "    }\n",
    "}\n",
    "int main(){\n",
    "    struct point T[3];\n",
    "    T[0].x=1;\n",
    "    T[0].y=2;\n",
    "    T[1].x=3;\n",
    "    T[1].y=4;\n",
    "    T[2].x=5;\n",
    "    T[2].y=6;\n",
    "    afficher_tableau(T,3);\n",
    "}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "celltoolbar": "Raw Cell Format",
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  },
  "rise": {
   "enable_chalkboard": true,
   "theme": "simple",
   "transition": "none"
  },
  "toc": {
   "base_numbering": 1,
   "nav_menu": {},
   "number_sections": true,
   "sideBar": true,
   "skip_h1_title": false,
   "title_cell": "Sommaire",
   "title_sidebar": "Sommaire",
   "toc_cell": true,
   "toc_position": {
    "height": "calc(100% - 180px)",
    "left": "10px",
    "top": "150px",
    "width": "261px"
   },
   "toc_section_display": true,
   "toc_window_display": false
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}