Discussion :

[rikudou]

salut,
Qui peut m'aider à comprendre le fonctionnement des Vecteur creux .
J'ai cherché sur google pour comprendre ce sujet mais je n'ai rien trouvé .
Voilà le sujet :
1er partie :



2eme partie :



Merci d'avance .

[kwariz]

Salut,

il me semble en fait que ce soit le but de l'exercie

Dans ton exercice, on part d'un très grand vecteur qui en fait contient beaucoup de 0 et quelques valeurs non nulles éparses. Le but d'un vecteur est d'associer un index et une valeur, on veut pouvoir accéder à la valeur en position 0, 4, ou n.
On constate que beaucoup de ces valeurs sont nulles et on se pose la question "est-il possible de ne stocker que les valeurs non nulles et garder les mêmes fonctionnalités en utilisant moins de mémoire ?"
La réponse est oui, il suffit de garder l'indice où se trouve une valeur non nulle et cette valeur.
Si on met dans un tableau ce couple (indice, valeur) on obtient le VEC_COMP de ton exercice. Si on utilise une liste chaînée on obtient le VEC_LIST de ton exercice.

[rikudou]

Merci pour votre indication ;
voila j'ai deja commencé le programme qui suprimme tout les zeros qui sont dans un tableau .

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
int suprrim_zero(int *tab) {
    int i = 0, j = 0;
    int *tmp=tab;
    while (*(tab + i)!=NULL) {
        if (*(tab + i) != 0) {
            *(tmp + j++) = *(tab + i);
        }
 i++;
    }
    return ?; /* Est-ce que je dois retourner tab ou quoi */
}

[kwariz]

Bon, il ne s'agit pas supprimer de les 0. Il s'agit déjà de définir les 3 type de la question 2.1, as-tu fait cela ?

[Obsidian]

J'ajoute que, dans ton énoncé, « vecteur creux » doit se comprendre de la même manière que « matrice creuse », par exemple : c'est un vecteur tout-à-fait ordinaire mais qui contient majoritairement des zéros (qui sont généralement eux-mêmes des valeurs par défaut pour des termes non spécifiés).

Il n'est pas précisé à partir de tel taux de zéros, par rapport au reste, un vecteur est considéré comme creux. On utilisera simplement ce terme lorsqu'un objet mathématique contient suffisamment de zéros par rapport au reste pour qu'il devienne pertinent de faire un traitement particulier.

[rikudou]

Bon, il ne s'agit pas supprimer de les 0. Il s'agit déjà de définir les 3 type de la question 2.1, as-tu fait cela ?

pardon mais j'ai pas bien compris ce truc .

[kwariz]

Tu as trois structures différentes : VECTEUR, VEC_COMP et VEC_LIST.
Tu va devoir définir ces types, les fonctions pour les manipuler pour finalement pouvoir transformer un VECTEUR en VEC_COMP ou en VEC_LIST, en aucun cas il n'est demandé de supprimer les 0 de VECTEUR.
Donc avant de coder quoi que ce soit il faut déjà que tu définisses ces types = la question 2.1.1.

[rikudou]

Tu as trois structures différentes : VECTEUR, VEC_COMP et VEC_LIST.
Tu va devoir définir ces types, les fonctions pour les manipuler pour finalement pouvoir transformer un VECTEUR en VEC_COMP ou en VEC_LIST, en aucun cas il n'est demandé de supprimer les 0 de VECTEUR.
Donc avant de coder quoi que ce soit il faut déjà que tu définisses ces types = la question 2.1.1.

mais je vais faire quoi .
est ce que je dois cree des structures .
ou :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
#define VECT_LIST(V)
#define VECT_COMP(x) .x

[kwariz]

Il faut que tu crées un type qui va représenter ces donnée. Quel est ton niveau en c ?

Par exemple, VECTEUR est clairement un tableau de taille fixe contenant MAX(=1000) éléments de type réels, cela doit donner quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
#define MAX 1000
typedef double VECTEUR[MAX];

VEC_COMP est un tableau de taille fixe contenant MAX_SIGNIF éléments qui sont une structure à deux champs, un pour l'indice et un autre pour la valeur ... cela donne donc ...

[rikudou]

Il faut que tu crées un type qui va représenter ces donnée. Quel est ton niveau en c ?

Par exemple, VECTEUR est clairement un tableau de taille fixe contenant MAX(=1000) éléments de type réels, cela doit donner quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
#define MAX 1000
typedef double VECTEUR[MAX];

VEC_COMP est un tableau de taille fixe contenant MAX_SIGNIF éléments qui sont une structure à deux champs, un pour l'indice et un autre pour la valeur ... cela donne donc ...

ah bon
Je suis entrain de finir les structures

[rikudou]

salut ,
Voici ce que j'ai fait

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
 
/*    1-                 definitions des types                             */
/**********************************************/
 
#define MAX 1000
#define MAX_SIGNIF 50
 
typedef double VECTEUR[MAX];
 
typedef struct VEC_COMP {
int indice[MAX_SIGNIF]; 
double val[MAX_SIGNIF]; 
} VEC_COMP;
 
typedef struct VEC_LIST {
int indice;
double valeur;
VEC_LIST * next;
} VEC_LIST;
 
/*    1-                  Mize a zero                                        */
/**********************************************/
 
void Mise_a_zero_1(VECTEUR V)
{
int i;
for (i=0;i<MAX;i++)
V[i]=0;
}
 
 
void Mise_a_zero_2(VEC_COMP* V)
{
int i;
for(i=0;i<MAX_SIGNIF;i++){
(*v).indice[i] = 0;
(*v).valeur[i] = 0;
}
}
 
VEC_LIST ????
 
/*    1-                  Valeur                                        */
/******************************************/
 
int Valeur_1(VECTEUR V, int indice)
{
return V[indice];
}
 
int Valeur_2(VEC_COMP V, int indice)
{
int i, pos=-1;
for(i=0;i<MAX_SIGNIF;i++)
{
if((*v).indice[i]==indice)
pos=i;
}
if(pos==-1) return -1;
else return (*v).valeur[pos];
}

[kwariz]

Bon, on va commencer par VECTEUR.

Le type était évident, ce n'est qu'un tableau tout ce qu'il y de plus normal. La mise a zéro me semble correcte, la récupération de la valeur aussi (tu pourrais éventuellement rajouter un test pour vérifier que l'indice passé en paramètre est valide). Il faudrait que tu écrives aussi Affecte.

Je te propose, pour plus de lisibilité (1,2, 3 ... on finit par ne plus savoir ce que c'est) , de nommer les fonctions

Mise_a_zero_VECTEUR
Mise_a_zero_VEC_COMP
Mise_a_zero_VEC_LIST

Ensuite, avant de coder VEC_COMP, il faut juste penser à comment tu vas l'utiliser. Tu gardes les 50 premiers indices des valeurs significatives. Comment pourrais-tu faire s'il n'y en a aucune ? Comment comptes-tu placer les indices dans ton tableau d'indice (par ordre croissant, décroissant, sans ordre précis) ? S'il n'y a que 20 valeur significatives comment fais-tu pour savoir que tu n'as stocké que 20 valeurs ?
Essaye de te faire quelques exemples à la main pour te familiariser avec cette méthode.

Pour VEC_LIST ... si tu veux on y viendra par la suite.

[rikudou]

D'accord senpai

[rikudou]

pardon ,
J'ai besoin d'appeler la fonction main ,
Est ce QUE c'est correcte?

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
 
typedef struct VECTEUR{
    double VEC[MAX];
} VECTEUR ;
 
int main()
{
    VECTEUR V;
    V.VEC={1,2,3,4,5,6};
    printf("%lf",V.VEC);
}

[kwariz]

Non, ce n'est pas correct, d'ailleur si tu as compilé tu as du avoir un mesage d'erreur.

Pourquoi mettre le tableau dans une structure ?

Si tu veux utiliser cette syntaxe, il vaut mieux dire au compilateur que tu initialises une struct dans laquelle tu as un tableau (cf le code) ; pour imprimer un tableau il faut parcourir tous les éléments un par un et les afficher :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <stdlib.h>
#define MAX 1000
 
typedef struct VECTEUR {
  double VEC[MAX];
} VECTEUR;
 
int main()
{
  int i;
 
  /*          +------------ une  structure ------------+
              |                                        |
              v                                        v */
  VECTEUR V = { { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f, 6.0f } };
  /*            ^                                    ^
                |                                    |
                +-- un tableau contenant des reels --+ */
  /*
  printf("%lf", V.VEC);
           ^    ^
           |    +- Je donne un tableau |
           |                           |-> ERREUR
           +- Je veux imprimer un reel |           */
 
  /* la bonne solution est : je parcours un tableau dont
     chaque element est un reel et je l'affiche */
 
  for(i=0;i<MAX;i++) {        /* je parcours */
    printf("%lf ", V.VEC[i]); /* j'affiche   */
  }
 
  /* la ligne suivante permet de sortir proprement
     du programme, elle ne coute rien */
  return 0;
 
}

Mais ce genre de code ne va pas te servir ...

[denispir]

@Ridoku. Voici un petit indice pour t'aider comprendre où ton prof veut en venir, si je le suis bien. (Plutôt que les problèmes de codage.) Imagine un problème dans lequel tu as d'un côté un ensemble de données "origine" et de l'autre une ensemble de données "destination". Et il y a une relation entre ces deux ensembles qui associe une destination à chaque origine. Exemple:

"marco" --> 01.23.45.67.89
"maria" --> 11.23.45.67.89
"margo" --> 21.23.45.67.89

Comment représenter cela de façon simple, pratique, et efficace en programmation? Comme tu as l'air curieux, va peut-être fouiller internet avec "programmation liste d'associations" (ou en anglais "association list").

Ton cas est particulier du fait que les données origine sont des entiers naturels. Donc, ils peuvent être les indices d'un tableau ordinaire. Mais alors on a plein de trous qui ne servent à rien, à chaque que fois que la données origine est 0. Pour éviter le gâchis, on utilise donc d'autres types de structures de données que les tableaux ordinaires.

Pourquoi mettre le tableau dans une structure ?

En fait, ça ne me semble pas si mal, car cela pourra ensuite lui permettre d'avoir une interface similaire pour les trois types. Notamment, probable que la version liste aura besoin d'être englobée dans une structure qui contient le compte d'entrées ; donc chaque structure peut avoir au moins un compte et en champ avec ls données. Ensuite, les fonctions de manip peuvent être assez semblables. Mais on en est pas (encore) là , tu as certainement raison de rester simple pour l'instant..

Denis

[rikudou]

Merci Pour Votre aide

[rikudou]

aide svp je suis bloqué :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIGNIF 50
 
typedef struct VEC_COMP {
   int ind[MAX_SIGNIF];
   double Val[MAX_SIGNIF];
   double nb[MAX_SIGNIF]; /* les nombres non nulles */
} VEC_COMP;
 
int main()
{
   VEC_COMP i;
   int j;
   VEC_COMP V = { { 1.0f, 2.0f, 3.0f, 4.0f, 5.0f, 6.0f, 0.0f, 7.0f } };
   while(V.Val[j] != 0){
       V.nb[j]=V.Val[j];
       i.ind[j]=j;
       printf("%lf  ",V.nb[j]);
       printf("\n\n");
       printf("%d",i.ind[j]);
       j++;
   }
   return 0;
}

[rikudou]

Ca y est! J'ai trouvé!!!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <stdio.h>
#include <stdlib.h>
#define MAX_SIGNIF 50
 
typedef struct indval{
    double Valeur[MAX_SIGNIF];
    double nb[MAX_SIGNIF]; /* nombres non nuls */
}indval ;
 
typedef struct VEC_COMP {
    indval Val;
    int ind[MAX_SIGNIF];
} VEC_COMP;
 
int main()
{
    int i;
   VEC_COMP V = { { 1.0f, 0.0f, 0.0f, 4.0f, 0.0f, 6.0f, 0.0f, 7.0f } };
   for(i=0;i<8;i++){
       if(V.Val.Valeur[i] != 0){
        V.Val.nb[i]=V.Val.Valeur[i];
       printf("\n%0.1lf    ",V.Val.nb[i]);
       V.ind[i]=i;
       printf("%d  \n ", V.ind[i]);
       }
   }
   return 0;
}

[kwariz]

Salut,

tu es en train de t'éparpiller complètement, tu essayes de bidouiller un truc pour que ça tombe en marche ...

Ton type VECTEUR doit ressembler à quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+                                                       
|  i    |0    |1    |2    |3    |4    |5    |6    |7    |8    |                                                       
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+                                                       
| V[i]  |0.1  |0    |0    |3.4  |0    |5.6  |0    |0    |8.9  |                                                       
+-------+-----+-----+-----+-----+-----+-----+-----+-----+-----+

Ton type VEC_COMP à quelque chose comme :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+--------------+                                        
|  i          |0    |1    |2    |3    |4    | ... | ... | ... | MAX_SIGNIF-1 |                                        
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+--------------+                                        
| C[i].indice |0    |3    |5    |8    |-1   |/    |/    |/    |/             |                                        
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+--------------+                                        
| C[i].valeur |0.1  |3.4  |5.6  |8.9  |/    |/    |/    |/    |/             |                                        
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+--------------+

Et pour passer de l'un à l'autre :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+                                     
|  i          |0    |1    |2    |3    |4    |5    |6    |7    |8    |...  |MAX-1|                                     
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+                                     
| V[i]        |0.1  |0    |0    |3.4  |0    |5.6  |0    |0    |8.9  |...  |/    |                                     
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+-----+                                     
                 |                 |           |                 |                                                    
                 |     +-----------+           |                 |                                                    
                 |     |     +-----------------+                 |                                                    
                 |     |     |     +-----------------------------+                                                    
                 |     |     |     |                                                                                  
                 v     v     v     v                                                                                  
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+--------------+                                        
|  j          |0    |1    |2    |3    |4    | ... | ... | ... | MAX_SIGNIF-1 |                                        
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+--------------+                                        
| C[j].indice |0    |3    |5    |8    |-1   |/    |/    |/    |/             |                                        
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+--------------+                                        
| C[j].valeur |0.1  |3.4  |5.6  |8.9  |/    |/    |/    |/    |/             |                                        
+-------------+-----+-----+-----+-----+-----+-----+-----+-----+--------------+

Tu comprends pour le second se nomme VEC_COMP (vecteur compressé), tu vois pourquoi il y a une -1 dans le second partie indice ? Tu vois pourquoi les deux exemples représentent la même suite de réels ?

Une valeur égale à / signifie que la valeur n'a pas d'importance.