Cours de Java : gestion et organisation de l'information

Résumé du document

Cours de programmation Java présentant les techniques nécessaires pour l'organisation et la gestion de l'information.

Extraits

[...] Techniques pour l'organisation et la gestion d'information Objectif d'apprentissage:Structures de données Quelques techniques pour l'organisation et la gestion d'information Comprendre: Collections dans Java Type de donnée abstraite / Abstract Data Types (ADTs) Structures dynamiques et listes chaînées Structures de données linéaires: queues et piles Qu'est-ce une Collection? Une collection est un objet qui sert à stocker autres objets, e.g. [...]

[...] collection d'étudiants, CD, magazines, nourriture Une collection offre des services tels que l'addition, la suppression, et la gestion des éléments qu'elle contient Parfois les éléments dans une collection sont ordonnés, parfois ils ne le sont pas Parfois les collections sont homogènes, parfois elles sont hétérogènes Type de Donnée Abstraite :Implantation d'une collection Un type de donnée abstraite (ADT) est une collection d'information organisée et un ensemble d'opérations utilisé pour gérer cette information L'ensemble d'opérations définit l'interface à l'ADT On implante un ADT en utilisant une structure de donnée dynamique Une structure de donnée dynamique grandit et rétrécit lors de l'exécution comme nécessaire Une structure de donnée dynamique est implantée avec des liens Question: Est-ce qu'un tableau est une structure de donnée dynamique? [...]

[...] MagazineList.java Creates a new MagazineNode object and adds it to the end of the linked list. public void add (Magazine mag) MagazineNode node = new MagazineNode MagazineNode current; if (list null) list = node; else current = list; we are at the list's beginning while (current.next null) walk through the list to the end current = current.next; current.next = node; } } Continued . [...]

[...] MagazineList.java public class MagazineList continued An inner class that represents a node in the magazine list. The public variables are accessed by the MagazineList class. private class MagazineNode public Magazine magazine; public MagazineNode next; Sets up the node public MagazineNode (Magazine mag) magazine = mag; next = null; Magazine.java public class Magazine private String title; Sets up the new magazine with its title. public Magazine (String newTitle) { title = newTitle; Returns this magazine as a string. public String toString return title; Collection Magazine Une méthode appelée insert peut être défini pour ajouter un nœud n'importe où dans la liste, pour la garder trié, par exemple Collection Magazine Une méthode appelée delete peut être défini pour enlever un noeud de la liste Autres représentations des listes dynamiques Parfois c'est adéquat d'implanter une liste comme une liste chaînée double, avec des références next et previous Autres implantations des listes dynamiques Parfois c'est adéquat d'utiliser un nœud “entête” avec un compteur et deux références à la tête (front) et la queue (rear) de la liste Autres implantations pour listes dynamiques Une liste chaînée peut être une liste circulaire, où le dernier élément de la liste est lié au premier élément de la liste Si la liste chaînée est doublement chaînée, le premier élément dans la liste est aussi lié au dernier élément de la liste Choix pour faire les liens: La représentation doit faciliter les opérations et les rendre facile à implanter Autres structures de donnée classiques Structures de donnée linéaires classiques, les queues et les piles Structures de donnée non-linéaires classiques, y compris les arbres, les arbres binaires, les graphes et les digraphes CSI2514 présente les structures de donnée en plus de détails Structure de donnée linéaire : Files Une queue (ou file) est similaire à une liste mais ajoute des éléments seulement au début de la liste et enlève des éléments seulement a la fin de la liste On parle d'une structure de donnée FIFO: First-In, First-Out (premier-entré-premier-sorti ) Analogie: une ligne d'attente à la banque Utilisée très souvent dans les systèmes d'exploitation Les files sont souvent utiles dans les simulations ou les situations où des éléments sont sauvegardés en attendant d'être traité Files (suite) On peut définir des opérations pour File enqueue - ajoute un élément début de la file dequeue (ou serve) - enlève un élément à la fin de la file empty - retourne vrai (true) si la file est vide Une file peut être représentée par une liste chaînée simple (singly-linked list); c'est plus performant si les références pointent du début vers la fin de la file Structure de donnée linéaire:Piles Un type de donnée abstraite pile est aussi linéaire, comme une liste ou une file Les éléments sont ajoutés et enlevés du bout de la pile seulement C'est donc LIFO: Last-In, First-Out Analogies: une pile d'assiettes dans un placard, une pile de factures à payer, ou une pile de balles de foin dans une grange Piles (suite) Quelques opérations pour les piles: push - ajoute un élément au sommet de la pile pop - enlève un élément du sommet de la pile peek (or top) - extrait l'élément au sommet de la pile sans l'enlever de la pile empty - retourne vrai (true) si la pile est vide Le package java.util contient une classe Stack Voir Decode.java (page 649) Decode.java import java.util.Stack; import cs1.Keyboard; public class Decode { Decodes a message by reversing each word in a string. [...]

[...] MagazineList.java Returns this list of magazines as a string. public String toString String result = MagazineNode current = list; while (current null) result current.magazine + current = current.next; return result; } Continued . [...]