Les tableaux d'indices (et de références)

L'auteur de ce sujet a trouvé une solution à son problème.
Auteur du sujet

Bonjour tout le monde ! Je vous propose ce premier exercice dans la continuité de ceux déjà proposer pour vous entrainer et constituer une petite base sympa ! Il est possible de faire l'exercide dans n'importe quel langage ! Veuillez m'excuser pour la froideur de l'énoncé, je ne suis pas un grand rédacteur xD

Les tableaux d'indices (et de références)

Pour tout les niveaux vous devrez respecter certaines contraintes :

  • Il faut toujours vérifier que les données sont valides (que le telephone ne soit composé que de chiffre par exemple)

  • Il faut que l'ensemble des fonctionnalité demandées dans les niveaux précédents fonctionnent encore !

Les objectifs sont là pour vous donner des conseils et ce que vous devez faire puisqu'il existe parfois d'autre façon de faire mais l'exercice est fait pour faire travailler certains concepts (les tableaux d'indices notamment), ne pas les suivre reviendraient à ne pas faire l'exercice

Si vous postez du code, merci de le mettre dans la balise secret (ici si vous ne savez pas faire) pour ne pas avoir une page trop grande et ne pas spoiler ceux qui réfléchissent encore !

Niveau 1

Enoncé

Lire les noms, prénoms et téléphones. Arrêt de la lecture au caractère *. Afficher le tableau dans l'ordre alphabétique (nom puis prénom)

Données
Pour le langage C

1
2
3
4
5
typedef struct Pers {
  char nom[256];
  char prenom[256];
  char tel[10];
} Contact;

Pour le langage Java

1
2
3
4
5
public class Contact{
       String nom;
       String prenom;
       String tel;
}

Objectifs

Faire un tri au fur et a mesure

Exemple

Entrée :

1
2
3
4
Toto tata 0123456789
Titi toto 0123654789
ToTo titi 0321456987
Tata TuTu 0321654789

Tableau trié :

1
2
3
4
tata tutu 0321654789
titi toto 0123654789
toto tata 0123456789
toto titi 0321456987

Niveau 2

Énoncé

Lire une commande et exécuter une commande

Donnée
  • m nom prenom : modification du contact nom prenom

  • s nom prenom : suppression du contact nom prenom

  • a nom prenom telephone : ajout du contact nom prenom

  • A : affichage de la liste des contact

  • A nom [prenom] : affichage des contacts ayant le nom (ou prenom si indiqué)

  • r nom [prenom] : recherche du ou des contacts ayant le nom (et optionnellement le prenom)

Niveau 2.1

Données
  • mn : modification nom

  • mp : modification prenom

  • mt : modification telephone

Objectif

Récupérer et interpréter un code commande

Exemple

(Avec les entrées précédentes) Entrée :

1
2
3
4
5
a toto titi
a toto tutu
s ToTO TAtA
A TOTo
A

Sortie :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
Contact [Toto, Titi, 0321456987] a été ajouté avec succès

Erreur 253 : Le contact [Toto, tutu] n'existe pas

Suppression du contact [Toto, Tata, 0123456789] effectuée

{[Toto, Tata, 0123456789],
 [Toto, Titi, 0321456987]}

{[Tata, Tutu, 0321654789],
 [Titi, Toto, 0123654789],
 [Toto, Tata, 0123456789],
 [Toto, Titi, 0321456987]}

(Ce sont des exemples d'affichage tout moisi, faites un truc un peu plus beau !)

Niveau 3

Énoncé

On veut différencier deux types de contact : les professionnels, les personnels

Au moment de l'ajout d'un contact, j'indique "pro" s'il s'agit d'un contact professionnel, "pers" pour personnel

On veut aussi pouvoir afficher, toujours dans l'ordre alphabétique, les contacts pro uniquement, perso uniquement, tout les contacts

Données
  • a nom prenom tel type : Même façon que pour le niveau 1 ; type par defaut : pro
  • A pro/pers : Affichage de contacts pro ou perso
Objectifs

Gérer plusieurs tableaux.

Il est INTERDIT de modifier la structure !

Exemple

Entrée :

1
2
3
4
5
6
7
a TATA TurlUTUTu 0147852369 pro
a TatA CHAPEAUpointU 0369852147 pers
a TOTO tututu 0159874236

A
A pro
A pers

Sortie :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
Contact [Tata, Turlututu, 0147852369, professionnel] a été ajouté avec succès

Contact [Tata, Chapeaupointu, 0369852147, personnel] a été ajouté avec succès

Contact [Toto, Tututu, 0159874236, personnel] a été ajouté avec succès

{[Tata, Chapeaupointu, 0369852147, personnel],
 [Tata, Turlututu, 0147852369, professionnel],
 [Toto, Tututu, 0159874236, personnel]}

{[Tata, Turlututu, 0147852369, professionnel]}

{[Tata, Chapeaupointu, 0369852147, personnel],
 [Toto, Tututu, 0159874236, personnel]}

Niveau 4

Énoncé

Votre utilisateur a rentrer 3millions de contact et trouve votre programme lent. Allez plus vite !

Objectif

Utiliser les tableaux d'indice

Niveau 4.1

Objectif

Utiliser des tableaux de références (pointeurs en C/C++, références en Java par exemple)

Explications

Explication : Les tableaux de références (ou d'indices) permettent de trier plus rapidement. A chaque copie de variable, l'ensemble de son contenu est copié. Si c'est un int, peu de données sont copiées. En revanche, il peut s'agir d'un tableau variable contenant un tableau d'un milliard de case qui chacune contient une structure ayant 30 chaines de caractères de taille un million. Ce n'est plus la même histoire. Les tableaux permettent d'accéder à leur valeur avec des indices (de 0 à n - 1, n étant la taille du tableau) ainsi il est possible de conserver les indices pour chacune des valeurs. Donnons un exemple :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
// On stockera dans indicesDeCinq l'ensemble des cases de tab contenant 5
int indicesDeCinq[30],
  tab[30],
  i, index;

for(i = 0; i < 30; i = i + 1){
  tab[30] = *valeur aléatoire entre 0 et 30*;
}

index = 0;
for(i = 0; i < 30; i = i + 1){
  if(tab[i] == 5){
      indicesDeCinq[index] = i;
      index = index + 1;
  }
}

Ici dans le tableau indicesDeCinq on aura les indices du tableau tab contenant 5. Si on veut récupérer la valeur du tableau tab avec l'indice du tableau indicesDeCinq, il faut faire :

1
2
3
4
5
int indiceDeTab = indicesDeCinq[0];
int resultat = tab[indiceDeTab];

// Ou encore
int resultat = tab[indicesDeCinq[0]];

Si vous avez compris avec les indices, le faire avec des pointeurs ou des références sera un jeu d'enfant !

N'hésitez pas a critiquer ma présentation et m'aider à l'améliorer envoyez moi un mp, c'est la première fois que je rédige un truc long ! Et si vous n'importe quelle remarque, envoyez moi un mp aussi, ça évitera de polluer ceux qui veulent faire l'exercice :p

Édité par Ricocotam

+0 -0
Staff

Il serait peut être interessant que tu fournisse des données de tests. Genre au niveau 1 "Lire les noms, prénoms et téléphones. Arrêt de la lecture au caractère *. Afficher le tableau dans l'ordre alphabétique (nom puis prénom)", fournir un fichier typique que la personne doit lire lui permettrait a minima de tester son code et de lever les ambiguité. Car là par exemple on sait qu'on doit s'arreter quand on voit un * mais on ne sais pas quel(s) caractère(s) sépare chacun des champs.

+0 -0

Bon, j'ai quelques critiques à propos de l'énoncé :

Je ne suis pas sûr de bien comprendre les contraintes de l'exercice. Un tableau n'est clairement pas adapté pour résoudre ce problème : on ne sais pas à l'avance combien de contacts va saisir l'utilisateur, et on va devoir sans arrêt réallouer le tableau. Ou alors, le tableau est de taille fixe et il y a un nombre maximal de contacts (mais dans ce cas, il faut une valeur "par défaut" pour les indices ne correspondant pas à un contact, ce qui n'est pas très élégant puisqu'on veut faire des tris ensuite).

De plus, je trouve la conclusion de l'exercice assez décevante. La structure contact utilisée a une taille constante : utiliser un tableau de références plutôt qu'un tableau de contacts permet effectivement de gagner du temps lors des copies, mais ça ne modifie pas la complexité des différents algorithmes sur le tableau.

Ce que j'aurais bien vu pour améliorer ça :

Déjà, expliquer ce que tu appelles tableau d'indices et tableau de références si c'est l'objet de l'exercice.

Mais honnêtement, je trouverai ça bien plus pertinent de parler d'arbres binaires de recherche (éventuellement arbres rouge-noir et B-arbres). Un tableau, c'est pratique pour s'exercer sur les algorithmes de tri, mais ce n'est vraiment pas une structure de données adaptée à la situation que tu proposes, où la structure doit pouvoir évoluer au cours du temps (On retrie le tableau à chaque insertion? Où alors à chaque affichage? Pourquoi ne pas maintenir une structure de données déjà triée?).

Auteur du sujet

Bonjour Bibibye ! J'ai édité pour le nombre de contacts maximal que j'ai totalement zapper !

Sinon le but c'est d'apprendre aux débutant à se débrouiller avec des tableaux, pour bien comprendre comment ça fonctionne, m'adressant à des débutants, parler d'ABR ou d'autres structures (bien plus adaptés et rapides) n'est pas pertinent :)

Pour ce qui est des tableaux d'indices et de référence j'explique dans le spoiler à la fin, si les explications ne sont pas claires je les referait avec pourquoi pas un schema :)

+0 -0

Un exercice doit donner l'exemple, je pense que des données présentées pour le C ne correspondent pas aux bonnes habitudes du débutant concernant tes typedef

1
2
3
4
5
6
7
8
typedef char[256] CH255;
typedef char[10] CH10;

typedef struct Pers {
  CH255 nom;
  CH255 prenom;
  CH10 tel;
} Contact;

Ricocotam

C'est quand même plus clair d'avoir un code comme ci-dessous

1
2
3
4
5
6
typedef struct
{
    char nom[256];
    char prenom[256];
    char tel[11];
} Contact;

non ?

Édité par fred1599

+0 -0

@fred1599 le nommage est pas top. en revanche, définir un type est bien plus malin :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
typedef char[256] NameText;
typedef char[10] PhoneNum;

typedef struct Pers {
  NameText nom;
  NameText prenom;
  PhoneNum tel;
} Contact;

bool check_PhoneNum(PhoneNum pn);
void change_PhoneNum(Contact* c, PhoneNum pn);

En définissant un type pour tes données, si un jour on doit changer la taille du tableau (par exemple, un numéro de téléphone c'est plus 10 mais 12 chiffres), on doit juste changer le typedef et les fonctions qui ont forcément besoin de la taille.

Dans l'autre cas, on doit aussi bien penser à changer l'argument de la fonction de 10 à 12 et on est sûr d'en oublier.

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein

+0 -0

Histoire de goût, je n'aime pas trop touché aux types de base dans le langage.

PhoneNum par exemple n'exprime pas si on veut un tableau de chars ou un nombre de 10 chiffres. Les goûts et les couleurs ça ne se discutent pas.

Après il faut aller voir à quoi correspond PhoneNum pour avoir sa réponse, je vais choper un torticolis :)

Pour un petit code ça passera, pour un plus grand, avec plusieurs types nommés, ça risque de devenir pénible.

+0 -0

PhoneNum par exemple n'exprime pas si on veut un tableau de chars ou un nombre de 10 chiffres. Les goûts et les couleurs ça ne se discutent pas.

Après il faut aller voir à quoi correspond PhoneNum pour avoir sa réponse, je vais choper un torticolis :)

Pour un petit code ça passera, pour un plus grand, avec plusieurs types nommés, ça risque de devenir pénible.

fred1599

Quand on veut manipuler un PhoneNumber, on utilise les fonctions prévues à cet effet, c'est à dire celles qui prennent en paramètre un PhoneNumber ou renvoient un PhoneNumber. De même que quand on manipule un contact, on utilise les fonctions prévues à cet effet. Si on commence à triturer les tronches des SDD en direct, on rend le code inutilement complexe : si on a besoin de faire une manipulation, il y a de bonnes chances que :

  • une fonction fournie par le header du type le fasse déjà
  • ce soit une bonne idée de l'ajouter au header (et auquel cas le type n'est pas bien loin).

Et si on passe pas par ce genre de raisonnement, on va disperser les endroits où l'on manipule la structure de données de manière non-contrôlée un peu partout et rendre les bugs associés extrêmement difficiles à traquer.

Les types c'est ce qui te permet de créer de la cohérence dans un programme, de donner un sens à tes données. Données que l'on manipule par des fonctions qui nous assure leur cohérence.

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein

+0 -0
Auteur du sujet

En fait j'ai repris mes cours de DUT 1, notre prof nous a expliquer les chaines de caractères comme ça, je trouve que ça simplifie beaucoup pour des débutants :). Si j'ai choisit les nom de CHRXXX c'est parce qu'on sait que c'est une chaine de caratere (CHR) qui contient XXX caractères (le '\0' enlevé).

Sinon, des trucs à corrigé ? Si vraiment vous trouvez ça trop degueu je change hein :p. Juste pour vous expliquer pourquoi j'ai fait comme ça :)

+0 -0

[…] qu'un typedef qui ne fait que semblant de masquer des tableaux.

lmghs

Sur ce point là, je suis d'accord, et c'est bien dommage d'ailleurs.

First : Always RTFM - "Tout devrait être rendu aussi simple que possible, mais pas plus." A.Einstein

+0 -0

Ricotam, Disons que c'est très Pascalien comme approche. La pertinence est discutable.

Imagine que tu te rendes comptes au bout d'un an qu'il faille non pas 20, mais 100 caractères dans le champs. Tu changes donc sa définition en Toto100 au lieu de Toto20. Et il te faut modifier toutes les utilisations du type pour ce champ particulier. C'est l'échec. L'idée des typedefs est de permettre de modifier la définition exacte à un endroit sans aller toucher au code partout ailleurs.

+0 -0
Auteur du sujet

Je sais très bien :) Et je ne code absolument pas comme ça, bien heureusement ! Mais encore une fois c'est un exercice pour les débutants, qui serait un gros tp (du genre le Plus ou Moins d'un tuto trop connu) mais pour les tableaux et les structures :). Donc à ce niveau là, faire abstraction d'allocation dynamique pour se concentrer sur autre chose est, je trouve, pas si débile. Mais encore une fois, si vraiment ovus trouvez que je dois mettre de l'alloc ou alors faire une définition comme Fred l'a proposé je peux !

+0 -0

Parenthèse.
Si tu poses la question sur ce qui convient pour des débutants, ma réponse reste inchangée sur tous les forums que je fréquente : tout sauf le C. Si tu veux faire travailler l'algorithmie, ne prends pas un langage qui oblige à se concentrer sur la gestion de la mémoire pour ne pas voir le programme planter.

Pour les débutants, j'estime important de montrer les bonnes pratiques et pas des pratiques qui ne doivent pas être utilisées une fois dans des vrais programmes. Les mauvaises pratiques perdurent. Et second problème du C, il est très complexe de montrer les bonnes pratiques à des débutants.

Après, cet exo de carnet d'adresse je l'avais fait pour moi-même en Pascal il y a bien longtemps, et il ne valait pas mieux pour les chaines.

Édité par lmghs

+0 -0
Auteur du sujet

Je change pour la chaines de caractères ! :)

J'ai écris le code en C et en Java parce que ce sont deux langages que je connais, mais je peux mettre d'autres langages dans mes données, je les connais pas donc si vous voulez me les donner ce sera volontier !

+0 -0
Vous devez être connecté pour pouvoir poster un message.
Connexion

Pas encore inscrit ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte