Tableaux uni-dimensionnels creux

**iziwschi** · 15/06/2010, 10h25

Bonjour tout le monde.

j'ai essayé de résoudre un exercice sur les tableaux représentés par une structure. je vous soumis l'exo et ma correction. merci de me dire ce que vous en pensez. Cet exo me trouble car je ne sais vraiment pas si ma solution est bonne ou complètement fausse. Merci pour votre aide.

Dans cet exercice, on nous propose de définir des fonctions permettant de compresser des tableaux et des fonctions permettant de manipuler ces tableaux.

La compression élimine le '0' (zéro) contnus dans un tableau afin d'économiser de l'espace mémoire.
Le Tableau compressé sera représenté par une structure nommée "creux" . elle contient trois informations :
une tableau d'indice ind et un tableau de valeurs réelles Val, et un entier nb.

Les règles pour créer un tableau compressé C à partir d'un tableau T sont les suivantes:

-- Pour le tableau d'indices, C.ind[p]=i si T[i] est le (p+1)ème élément de T différent de 0 (C.ind [0] étant le 1er élément de T différent de 0).
-- Pour le tableau de valeurs val, C.val[p] = T[i].
-- nb est le nombre d'élément non nuls du tableau T.

Exemple: soit le Tableau T = |0|1.6|0| 9|7|
La structure Creuse lui correspondant sera :
pour le tableau d 'indice C.ind = |1|3|4|.
Pour le tableau de Valeurs C.val = |1.6|9|7|.

Questions:

Q1) Déclarez le type struct creux.Les tableaux val et ind sont alloués dynamiquement .

Q2) Faites une fonction struct creux *new(int n). qui alloue dynamiquement une structure creuse où les tableaux ind et val seront de taille n.Cette fonction retourne un pointeur vers cette structure.

Q3) Faites une fonction struct creux *initialise(float T[N]) , qui, à partir d'un tableau T, crée dynamiquement la structure creuse correspondante et initialise celle ci à l'aide du tableau T. Cette fonction retourne un pointeur vers cette structure.

Mes Réponses: :
//*********************************************************
Code : C

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
 
#include <stdio.h>
 
typedef struct creux
{
 int *ind;
 float *val;    // Q1
 int nb;
 
}Creux;
 
 
Creux *new (int n)</couleur>        //Q2
 
{
 Creux *C;
 
  C->ind= malloc(n* sizeof (int));
  C->val= malloc(n* sizeof (float));
 
       if(C==NULL)
           printf("ALLOCATION MEMOIRE ECHOUEE !");
 
 
return C;
 
 
        }
 
 
Creux *Initialise (float T[taille], int taille)    //Q3
{
int i;
Creux *C;
 
C=new(taille);
  C.nb=0;
          For (i=0;i<taille;i++) 
            {   
               if(T[i]!=0){
                   C.nb++; // on incrémente le nombre de valeur non nulles
                   C->(ind+i)=C.nb;// on range ici, dans le tableau inb, le num des indices des            valeurs non nulles
                   C->val=T[(ind+i)];//on rempli le tableau C.val des valeur non nulles de T[].
 
                      printf("les valeurs du tableau compressées sont: %d\n ",C->(val+i));
 
                             }
 
 
            }

**diogene** · 15/06/2010, 11h55

Q1 - Correct.
Une alternative est d'associer valeur et indice (ce sont des données étroitement associées) en une structure et faire un tableau de ces structures. Ce n'est pas plus économique que la solution que tu as adoptée, c'est selon la manière dont on veut voir les choses. Par exemple :

Code :

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

1
2
3
4
5
6
7
8
9
10
typedef struct
{
  float valeur;
  int indice;
} Data;
typedef struct
{
  Data* element;
  int nb;
} Creux;

Q2 - Incorrect. Tu n'as pas alloué un Creux.

Code :

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

1
2
3
4
5
6
1 - Allouer un Creux
2 - Si l'allocation a réussi (il est impératif de tester le réussite des allocations)
        2.1 - Allouer un tableau d'indice et un tableau de valeurs
        2.2 - Si les deux allocations ont réussi, initialiser le champ nb du Creux et retourner l'adresse du Creux
              Sinon, libérer les allocations réussies (sans oublier celle du Creux) et retourner NULL
    Sinon retourner NULL

- Ne pas faire de printf() dans cette fonction, l'information d'échec est transmise non par un message mais par le retour de la fonction à NULL. A la liberté de celui qui a invoqué la fonction de choisir ce qu'il doit faire dans cette éventualité.

Q3 - Incorrect : Tu crées un Creux qui a la même taille que le tableau d'origine. C'est oublier ce à quoi le Creux doit servir : économiser de la mémoire pour les vecteurs creux. Dans ton cas, ton Creux occupe plus de mémoire que le tableau ! Il faut d'abord calculer le nombre d'éléments différents de 0 pour obtenir la taille nécessaire et suffisante.
Autre remarques :
- Tester si il a été possible d'obtenir un Creux (donc que newCreux() n'a pas renvoyé NULL)
- Pour accéder aux éléments du tableau des valeurs ou des indices du Creux, on doit écrire C->val[i] ou C->ind[i] (C->val et C->ind sont les tableaux)
- ne pas faire de printf() dans cette fonction. Laisser à l'utilisateur le soin de choisir ce qu'il doit faire des données obtenues.

Compléments :
- Puisque tu as écrit une fonction de création d'un Creux, écris, dans la foulée, une fonction de destruction d'un Creux.
- Avant d'aller plus loin, teste l'ensemble de tes fonctions.

**iziwschi** · 16/06/2010, 20h40

Bonsoir diogene,
Merci d'avoir pris le temps pour me répondre. Et surtout merci pour toutes les indications. Après avoir suivi les indications je suis arrivé à cela:

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include <stdio.h>
#include <stdlib.h>
 
 
typedef struct creux
{
int *ind;
float *val;
int nb;
 
}Creux;
 
 
 
Creux *new_creux(int n)
{
Creux *C;
 
	C= malloc(sizeof(Creux));
 
		   if(C==NULL)
		      {printf("//!\\ERREUR D'ALLOCATION DU CREUX //!\\ \n");
		      return NULL;
		      }
 
	          else{
 
		           C->ind= malloc(n* sizeof (int));
 
 			       C->val= malloc(n* sizeof (float));
 
	              }	
 
      if ((C->ind==NULL)||(C->val==NULL))
		 {printf("//!\\ERREUR D'ALLOCATION DES DEUX TABLEAUX IND ET VAL //!\\ \n");
		  return NULL;
		 }
 
 
 
return C;
 
 
}
 
 
 
Creux *Initialise(float *T, int taille)
 
 {
int i;
Creux *C;
 
 C=new_creux(taille);
 
	 for (i=0;i < taille;i++)
	   {
		  if(T[i]!=0)
		     {
 
			 C->ind[i]=i;// on range ici, dans le tableau inb, le num des indices des valeures non nulles
 
			 C->val[i]=T[i];//on rempli le tableau C.val des valeur non nulles de T[].
 
			 C->nb+=1;    // on incrémente le nombre de valeur non nulles
			  printf("les valeur du tableau creux : %f\n ",C->val[i]);
 
			 }
      }	
return C;	
 
}
 
int main()
{
 Creux *C1;
 float tab[5]= {0,5,0,4,6};
 int i;
 int taille=5;
	C1=new_creux(taille);
	C1=Initialise(tab,taille);	
 
		printf("les valeures non nulles sont de : %d\n ",C1->nb);
 
free(C1);	
return 0;	
	}

Le programme compile sans erreurs.Et le résultat obtenu est bon. le tableau donné en paramètre est bien compressé.
je te prie de me dire ce que t'en pense. je vais essayer de rajouter quelques fonctions dont celle que tu m'as conseillé(supprimer un creux).

Merci encore. Bonne soirée

**diogene** · 17/06/2010, 00h14

Quelques critiques :

Creux *new_creux(int n) :

- supprime les printf() du message d'erreur. Laisse au programme appelant la fonction la liberté de ce qu'il doit faire en cas d'échec. Ne lui impose pas un affichage intempestif. C'est une contrainte inutile et qui restreint la généralité de ta fonction.

-

Code :

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

1
2
3
4
      if ((C->ind==NULL)||(C->val==NULL))
		 {//printf("//!\\ERREUR D'ALLOCATION DES DEUX TABLEAUX IND ET VAL //!\\ \n");
		  return NULL;
		 }

Ici, la libération n'est pas correcte : on sait que
- on ne peut pas créer le Creux
- on a déjà alloué un Creux par le premier malloc
- on a échoué dans un ou deux des deux derniers malloc
-> il faut libérer ce qui a été alloué et renvoyer NULL

Code :

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

1
2
3
4
5
6
7
if ((C->ind==NULL)||(C->val==NULL))
{
  free(C->ind); // on a le droit de faire un free(NULL) 
  free(C->val); // idem
  free(C);  
  return NULL;
}

ce qui donne par exemple en mettant un peu d'ordre

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
Creux *new_creux(unsigned int n) // n est positif ou nul ->unsigned
{
  Creux *C = malloc(sizeof(Creux));
  if(C != NULL)
  {
     C->nb = n;  //C->nb devrait être unsigned également
     C->ind = NULL; // pour le cas où n = 0;
     C->val = NULL; // idem
     if(n!=0)
     {     
        C->ind= malloc(n* sizeof (int));
        C->val= malloc(n* sizeof (float));
        if (C->ind == NULL||C->val == NULL)
        {
           free(C->ind); // Ou mieux, si elle est écrite delete_creux(C);
           free(C->val); // ....
           free(C);      // ....
           C = NULL; 
        }
     }
  }	     
  return C; 
}

Creux *Initialise(float *T, int taille) :

- Attention, telle que tu l'as écrite, cette fonction crée et initialise le Creux. Donc il ne faut pas le créer dans le main.
- Ne pas faire de printf() dans la fonction pour les mêmes raisons que précédemment. C'est une très mauvaise pratique.
- Cette fonction alloue trop de float et rend l'utilisation d'un Creux inutile. Voir mon message précédent. On devrait avoir quelque chose du genre :

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
Creux *Initialise_creux(float *T, int taille)
{
  int i;
  Creux *C;
  int cnt;
  for (i=0, cnt=0;i < taille;i++)if(T[i]!= 0) cnt ++ ; // compter le nombre d'éléments à allouer
  C=new_creux(cnt); // allouer le Creux
  if(C != NULL && cnt !=0 ) // tester l'allocation
  {
       // il y en a au moins 1 : Copier les données
       for (i=0, cnt =0 ;i < taille;i++) 
          if(T[i]!=0)
          {
             C->ind[i]=i;
             C->val[i]=T[i];
          }
  }	
  return C;
}

Le main ressemble alors à :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
int main(void)
{
 float tab[5]= {0,5,0,4,6};
 int taille=5;
 Creux * C1=Initialise_creux(tab,taille);
 if(C1 == NULL)  printf("ERREUR D'ALLOCATION\n");
 else
 {
    printf("les valeurs non nulles sont de : %d\n ",C1->nb);
    delete_creux(C1);	// a écrire absolument .cf new_creux()
 }
 return 0;	
}

**iziwschi** · 17/06/2010, 03h13

bonsoir diogene,
Une fois de plus merci pour ton aide. ton code est tellement bien écrit que j'en rêverai de maitriser comme toi.

Grâce à ta correction j'ai compris mes erreurs.j'ai recorrigé mon code initial.
j'ai aussi créer la fonction que tu m'as conseillé.

Code :

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

1
2
3
4
5
6
7
8
void delete_creux(Creux *C)
{
 
    free(C->ind); // on libere l'éspace alloué des deux tableau.
    free(C->val); 
    free(C);      //idem pour le creux
     C = NULL; 
}

Comme je t'avais dit dans mon précédent post, je souhaitais rajouter quelque fonctions pour vérifier un peu l'affichage et tester ce code. Ces fonctions compilent et s'exécutent correctement chez moi sauf peut-être la dernière.

les fonctions en plus:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
1)
float valeur(int i, Creux *C)// cette fonction retourne la valeur de la i ème valeur d'un tableau
// si i correspond à un indice conservé dans le tableau ind alors on retourn la valeur. sinon on retourne 0.

2)Creux *somme(Creux *C1, Creux *C2, int i)
cette fonction effectue la somme de deux vecteur conservé dans une structure Creux. on retourne la valeur résultat.



3) cette fonction je crois que ne marche pas.enfin le résultat n'est pas bon remarque vu l'heure je devrais me coucher. 

float scalprod(float *Tab, Creux *B,int taille) cette fonction calcule le produit scalaire s=a.b de deux vecteur a et b. le premier vecteur correspond à un tableau et le second à une structure creuse. 
produit scalaire: s= somme de a*b jusqu'à n-1. ici n sera  la taille de mon tableau.

Je soumis ci-dessous mon code. j'espère ne pas trop prendre de ton temps.

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
 
1)
float valeur(int i, Creux *C)
{
 
  return C->val[i];
 
    if(i>C->nb)
    {
      return 0;
    }
 
}
 
 
 
2)	
Creux *somme(Creux *C1, Creux *C2, int i)// ici le i correspond a l'indice de valeur qu'on veux additioner
{
 
	float vect1,vect2; // les valeur qu'on veut addistion. dans le main on peut demander les valeur ou indice case valeur
 
Creux *C3;
      vect1=valeur(i,C1);
      vect2=valeur(i,C2);
 
 C3=Initialise(C3->val,C1->nb);
 
 C3->val[i]=vect1+vect2;
 
 return C3;
 
3)
 
 
float scalprod(float *Tab, Creux *B,int taille)
{
int i;
float prodSc;
 
    for(i=0;i<taille;i++)
    {
	 prodSc=Tab[i]*B->val[i]+Tab[i+1]*B->val[i+1];
 
    }
 
    return  prodSc;		  
}

qu'en pense tu? sont telle correcte.merci pour l'aide.
bonne nuit.

**diogene** · 17/06/2010, 13h02

*** delete_creux() :
- Attention, il faut bien avoir à l'esprit que C, dans la fonction, est une variable locale qui sera détruite en sortie de fonction. Par conséquent, le C=NULL ne sert strictement à rien.
Dans new_creux() il faudra avoir impérativement le C=NULL

Code :

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

1
2
3
4
5
        if (C->ind == NULL||C->val == NULL)
        {
           delete_creux(C);
           C = NULL; 
        }

- Il peut être intéressant que delete_creux(NULL) ne plante pas et ne fasse rien (en prenant pour modèle le comportement de free() dont on a vu l'avantage lors de new_creux()).

Code :

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

1
2
3
4
5
6
7
8
9
void delete_creux(Creux *C)
{
   if(C != NULL)
   {	
      free(C->ind); // on libere l'éspace alloué des deux tableau.
      free(C->val); 
      free(C);      //idem pour le creux
   } 
}

*** valeur() : Ne marche pas : dès qu'on rencontre un return, on sort de la fonction. Du coup le if()... ne sera jamais exécuté.
On doit se poser la question de l'utilité d'une telle fonction : Permet-elle d'obtenir la ième valeur stockée dans le tableau du Creux ? Mais à quoi peut bien servir de le savoir. Il est plus intéressant de récupèrer la valeur qui était présente en ième position dans le tableau de float avant qu'il soit codé dans le creux. Cela permet de reconstituer le vecteur d'origine. C'est ainsi que tu décris en commentaire la fonction mais pas du tout la façon dont tu la codes.

float valeur(int i, Creux *C);// cette fonction retourne la valeur de la i ème valeur d'un tableau
// si i correspond à un indice conservé dans le tableau ind alors on retourn la valeur. sinon on retourne 0.

Code :

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

1
2
3
- Chercher la valeur i dans le tableau d'indice C->ind du Creux
- Si il est trouvé en position j retourner C->val[j]
- sinon retourner 0

*** somme() :

2)Creux *somme(Creux *C1, Creux *C2, int i)
cette fonction effectue la somme de deux vecteur conservé dans une structure Creux. on retourne la valeur résultat.

On voit à quoi sert cette fonction d'après sa description, mais on ne voit pas à quoi sert le i comme paramètre.
Le code et le prototype de ta fonction sont à revoir.

Il s'agit de faire la somme de deux vecteurs. Les deux vecteurs sont des Creux et la somme doit être un Creux. Avant de se lancer dans le codage, il faut comme toujours réfléchir un peu.

Le problème est qu'on ne connait pas le nombre d'éléments du creux final.
Une solution envisageable est de reconstituer les vecteurs d'origine à partir des creux, de faire la somme des vecteurs et d'en déduire le creux final avec la fonction initialise_creux().
En toute rigueur, on ne peut pas reconstituer les vecteurs d'origine puisqu'on n'a pas stocké le nombre total d'éléments. On ne connait que le nombre d'éléments non nuls et leurs indices. Par contre, on connait le plus grand indice des éléments non nuls et donc, tous les éléments (en nombre inconnu) ayant un indice supérieur dans le vecteur d'origine sont nuls.
Si M1 et M2 sont les valeurs maximum des indices dans les creux1 et creux2, alors le vecteur final aura tous ses éléments nuls pour un indice supérieur à M=MAX(M1,M2).
On arrive à :

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
1- Créer par allocation dynamique un tableau tab de M+1 float
2- On peut envisager de faire ceci en utilisant notre fonction valeur() : 
      2(1)De i= 0 à M, lire la ième valeur du vecteur1 et celle du vecteur2 (fonction valeur()), 
           faire la somme et stocker dans le tableau en position i.
   Cette manière de faire peut être très couteuse en temps : 
   la fonction valeur() n'est pas une fonction rapide et devrait être réservée
   pour l'accès aléatoire à un élément. Ici, on a besoin d'accéder à tous les éléments. 
   On peut procéder de façon plus efficace ainsi :
      2(2)-a mettre à 0 les éléments de tab.
      2(2)-b Explorer la liste des indices de creux1. Pour chaque indice k = creux1->ind[i]
               trouvé dans la liste ajouter à tab[k] la valeur de creux1->val[i]
      2(2)-c Procéder de même avec creux2
3- Créer le Creux resultat à partir du tableau tab (fonction initialise_creux())
4- Détruire le tableau tab de float
5- Retourner l'adresse du Creux resultat.

*** scalprod () : on verra plus tard

**iziwschi** · 20/06/2010, 02h43

Bonsoir Diogene,
je viens de refaire les 3 fonctions en suivant tes indications. je soumis le code ci-dessous.cela compile sans sans problème. Après je ne suis pas certain de leur exactitudes.Notamment le fonction sur le produit scalaire.

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
63
64
65
66
67
68
69
70
71
72
73
 
 
// FONCTION 1
float valeur(int i,Creux *c)
{
        int b=0;
 
        for(b=0;b<c->nb;b++)
        {
                if(c->ind[b]==i)
                {
                        return c->val[b];
 
                }
 
 
        }
 
return 0;
}
 
//FONCTION POUR L'AFFICHAGE
void afficher(Creux *c)
{
int i=0;
    for(i=0;i<c->nb;i++)
        {
        printf("indice = %d val=%f \n",c->ind[i],c->val[i]);
        }
 
 
}
 
 
 
//FONCTION 3 SOMME
Creux *somme(Creux *c1,Creux *c2)
{
        Creux *c3=NULL;
        c3=new_creux((c1->nb+c2->nb));
        c3->nb=c1->nb;//c3 nb est la plus grande valeur entre c1 NB et C2 NB
 
        int i=0;
        for(i=0;i<c3->nb;i++)
        {
        c3->ind[i]=i;//indice c3 commence apartir du zero
        c3->val[i]=(c1->val[i])+(c2->val[i]);// valeur des tableau
        }
    return c3;
 
}
 
 
//FONCTION 4 PRODUIT SCALAIRE
float scalprod(float *Tab, Creux *B,int taille)
{
 
	int i;
	float prodSc;
	Creux *C;
	C=initialise_creux(Tab,taille);
 
 
	for(i=0;i<taille;i++)
	  {
 
		 prodSc=((C->val[i]*B->val[i])+(Tab[i+1]*B->val[i+1]));
 
   	  }
 
return  prodSc;		  
 
  }

Tableaux uni-dimensionnels creux

C

Discussions similaires

Partager

Partager