Linéarisation d'une matrice en zigzag

Version imprimable

1 pièce(s) jointe(s)

Bonjour,

Je dois coder la linéarisation d'une matrice en zigzag. Mais ça ne marche pas. J'ai des erreurs ac Purify, des Array Bounds Read, Array Bounds Write et des Zero Page Read.

Voici mon code source et mon test.

Code:

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
#include "vector.h"
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
 
 
matrice allouer_matrice(short int l,short int c){
	matrice m;
	short int k;
	m.hauteur=l;
	m.largeur=c;
	m.coeff=malloc(l*sizeof(short int*));
	for(k=0; k<l; k++){
		m.coeff[k]=malloc(c*sizeof(short int));
	}
	return m;
} 
 
 
vecteur creer_vecteur(const int capacite) {
    vecteur v;
    v.card= capacite;
    v.coeff= malloc(capacite*sizeof(Element));
    return v;
}
 
void liberer_matrice(matrice* m){
	short int k;
	for(k=0; k<m->hauteur; k++) free(m->coeff[k]);
} 
 
 
void detruire_vecteur(vecteur* v) {
    free(v->coeff);
}
 
int taille_vecteur(vecteur v) {
    return v.card;
}
 
bool est_pair(int i){
    return(i%2==0);
}
 
 
vecteur lineariser(matrice m){
	vecteur v;
	int i=0,j=0,k=0; // i= indice ligne matrice
					 //j= indice colonne matrice
					 //k= indice ligne vecteur 
 
	v=creer_vecteur(m.hauteur*m.largeur);
 
	v.coeff[k]=m.coeff[j][i];
    for (k=1; k<v.card-1; k++){
		if (((j == m.hauteur-1) && (!est_pair(i))) || ((j==0) && (est_pair(i)))){
			i++;
		}
		else if (((i == m.largeur-1) && (est_pair(j))) || ( (i==0) && (!est_pair(j)) ) ){
			j++;
		}
		else if (est_pair(i+j)){
	 	        i++;
			j--;
		}
		else if (!est_pair(i+j)){
			i--;
			j++;
		}
		v.coeff[k]= m.coeff[j][i];       // !!!!!!! ERREUR
	}
 
	return v;
}
 
 
void afficher_vecteur(vecteur v){
    printf("[ ");
    for (int i=0;i<v.card;i++){
	printf(" %d",v.coeff[i]);
    }
    printf(" ]\n");
}

et mon fichier test

Code:

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
88
89
90
91
92
93
94
95
96
int main(){
	matrice t;
	t=allouer_matrice(8,8);
	printf("ok\n");
 
	vecteur v;
	/**Allocation de mémoire**/
 
 
	//if (t.coeff != NULL){
 
		t.hauteur=8;
		t.largeur=8;
 
		t.coeff[0][0]=1;
		t.coeff[0][1]=3;
		t.coeff[0][2]=4;
		t.coeff[0][3]=10;
		t.coeff[0][4]=11;
		t.coeff[0][5]=21;
		t.coeff[0][6]=22;
		t.coeff[0][7]=36;
		t.coeff[1][0]=2;
		t.coeff[1][1]=5;
		t.coeff[1][2]=9;
		t.coeff[1][3]=12;
		t.coeff[1][4]=20;
		t.coeff[1][5]=23;
		t.coeff[1][6]=35;
		t.coeff[1][7]=37;
		t.coeff[2][0]=6;
		t.coeff[2][1]=8;
		t.coeff[2][2]=13;
		t.coeff[2][3]=19;
		t.coeff[2][4]=24;
		t.coeff[2][5]=34;
		t.coeff[2][6]=38;
		t.coeff[2][7]=49; 
		t.coeff[3][0]=7;
		t.coeff[3][1]=14;
		t.coeff[3][2]=18;
		t.coeff[3][3]=25;
		t.coeff[3][4]=33;
		t.coeff[3][5]=39;
		t.coeff[3][6]=48;
		t.coeff[3][7]=50;
		t.coeff[4][0]=15;
		t.coeff[4][1]=17;
		t.coeff[4][2]=26;
		t.coeff[4][3]=32;
		t.coeff[4][4]=40;
		t.coeff[4][5]=47;
		t.coeff[4][6]=51;
		t.coeff[4][7]=58;
		t.coeff[5][0]=16;
		t.coeff[5][1]=27;
		t.coeff[5][2]=31;
		t.coeff[5][3]=41;
		t.coeff[5][4]=46;
		t.coeff[5][5]=52;
		t.coeff[5][6]=57;
		t.coeff[5][7]=59;
		t.coeff[6][0]=28;
		t.coeff[6][1]=30;
		t.coeff[6][2]=42;
		t.coeff[6][3]=45;
		t.coeff[6][4]=53;
		t.coeff[6][5]=56;
		t.coeff[6][6]=60;
		t.coeff[6][7]=63;
		t.coeff[7][0]=29;
		t.coeff[7][1]=43;
		t.coeff[7][2]=44;
		t.coeff[7][3]=54;
		t.coeff[7][4]=55;
		t.coeff[7][5]=61;
		t.coeff[7][6]=62;
		t.coeff[7][7]=64;
 
		for (int i=0;i<=7;i++){
		    for(int j=0;j<=7;j++){
			printf("%3d ",t.coeff[i][j]);
		    }
		    printf("\n");      
 
		}
 
		v=lineariser(t);
		afficher_vecteur(v);
 
		detruire_vecteur(&v);
		liberer_matrice(&t);
 
	//}
	return EXIT_SUCCESS;
}

Merci d'éclairer ma lanterne.

Principe du zigzag!
Pièce jointe 48419

11/06/2009, 19h06
diogene

On ne peut pas dire grand chose si on n'a pas la définition des types matrice et vecteur (sans doute le code de vector.h)
11/06/2009, 19h13
scarabee10
Oups! j'ai omis de joindre vector.h pour éviter la redondance des fonctions, mais j'ai oublié les types!
Alors
Code:

1 2 3 4 5 6 7 8 9 typedef struct{ int** coeff; int taille; } matrice; typedef struct{ int* coeff; int card; } vecteur;
Voilà..

Salut,

Déjà, il y a un problème avec ton allocation...
Code:

1 2 3 4 5 6 7 8 9 10 11 matrice allouer_matrice(short int l,short int c){ matrice m; short int k; m.hauteur=l; m.largeur=c; m.coeff=malloc(l*sizeof(short int*)); for(k=0; k<l; k++){ m.coeff[k]=malloc(c*sizeof(short int)); } return m; }
Tu crées (sur la pile) une matrice m, et tu la renvoies comme résultat de ta fonction. Comme m est sur la pile, la zone de mémoire correspondante va être rendu au système à la sortie de la fonction allouer_matrice, puis éventuellement utilisée pour autre chose (puisque le système croit qu'elle est libre). Alors, forcément, il va arriver quelque chose d'horrible un peu plus loin...

Pour éviter cela, tu as en gros deux options

Soit créer la matrice sur le tas, avec malloc(), dans alloue_matrice, et renvoyer un pointeur dessus...
Code:

1 2 3 4 5 6 7 8 9 matrice *alloue_matrice() { matrice *m=(matrice*)malloc(sizeof(matrice)); /* ton code d'allocation */ m.coeff=malloc()... return m; }
Ou alors, créer la matrice avant (dans la fonction appelante, main() par exemple, et passer un pointeur vers celle ci à ta fonction d'allocation...
Code:

1 2 3 matrice m; alloue_matrice(matrice *m,int hauteur,int largeur);
Ca devrait déjà régler une partie de tes problèmes...

Et tu as exactement le même problème avec tes vecteurs...

Francois

12/06/2009, 11h19
diogene

Citation:

Envoyé par fcharton

...
Tu crées (sur la pile) une matrice m, et tu la renvoies comme résultat de ta fonction. Comme m est sur la pile, la zone de mémoire correspondante va être rendu au système à la sortie de la fonction allouer_matrice, puis éventuellement utilisée pour autre chose (puisque le système croit qu'elle est libre). Alors, forcément, il va arriver quelque chose d'horrible un peu plus loin...
...

Bien que j'approuve la méthode de création que tu proposes ensuite, il faut souligner que le problème ne doit pas venir de ça.
Il a le droit de renvoyer m : une fonction peut renvoyer une structure et cette structure peut être recopiée dans une autre en sortie de la fonction (autrement dit l'opérateur = est défini pour les structures).

Il n'a pas le droit par contre de renvoyer l'adresse de m (comme l'adresse de toute variable locale).
12/06/2009, 14h01
Invité

Citation:

Envoyé par diogene

(autrement dit l'opérateur = est défini pour les structures).

Oh? Je vais regarder alors. Merci beaucoup, Diogène, j'apprends un truc par jour, ces temps ci.

Si le pb n'est pas là, c'est sans doute un indice négatif ou abberrant dans la boucle de linéarisation. Ce que je ferais, pour débuguer ca, ce serait d'imprimer, à chaque pas de la boucle, les indices i,j et k. On devrait voir tout de suite.

Quant à la linéarisation elle même, à mon avis, la bonne méthode doit consister à calculer explicitement (sur le papier) les indices que l'on veut parcourir.

En gros, on cherche une formule donnant de 0 à n^2, les indices (ligne et colonne) de la cellule à visiter. On doit pouvoir raisonner de la manière suivante :
1- le parcours en zigzag est symétrique, si on a une formule pour la première moitié, on peut en déduire une formule pour la seconde
2- dans la première moitié la i-ième diagonale a des indices (dans le vecteur linéarisé) qui vont de i(i-1)/2 à i(i+1)/2.
3- sur chaque diagonale, l'invariant est i+j (somme des indices lignes et colonnes)
4- les diagonales sont parcourues dans un sans alterné (donc (i+j)%2 va jouer un role)

Donc, pour la première moitié, on va avoir des indices (i-ieme diagonale) de type soit (k,i(i+1)/2-k) soit (i(i+1)/2-k,k), suivant la parité de i, k variant entre 0 et i, et l'indice du vecteur linéarisé étant i(i-1)/2+k.

Moyennant cette boucle et quelques essais et erreurs...

Francois

La remarque de fcharton est pertinente :

Citation:

sur chaque diagonale, l'invariant est i+j (somme des indices lignes et colonnes)

Soit k cet invariant. Ses valeurs vont de 0 à Nlignes+Ncolonnes-2.
Faisons abstraction du sens de parcours des pseudo-diagonales et supposons que pour toutes, l'indice de ligne, iligne, est croissant. (Le sens de parcours sera ensuite déterminé par la parité de k).

A priori, pour une valeur de k, iligne doit varier de 0 à k. Naturellement, il faut que cet indice reste dans les limites du tableau : 0<=iligne< Nlignes et l'indice des colonnes icol= k-ilignes également 0<=icol<Ncolonnes.
Ceci permet de limiter les variations de iligne pour un k donné. iligne doit donc varier entre deux limites Debiligne et Endiligne avec un incrément de Stepiligne. Tout se résume à déterminer ces trois paramètres.

Sur ces bases, on peut avoir l'algorithme suivant qui "linéarise" le tableau Tab dans le tableau Dest:
Code:

1 2 3 4 5 6 7 8 idest = 0; Pour k variant de 0 à Nlignes+Ncolonnes-2 avec un incrément de 1 : Si k < Ncolonnes : Debiligne = 0 sinon : Debiligne = k-(Ncolonnes-1) Si k < Nlignes : Endiligne = k sinon : Endiligne = Nlignes-1 Stepiligne = 1 Si k est pair : Echangez Debiligne et Endiligne et mettre Stepiligne à -1 Pour iligne = Debiligne à Endiligne avec un incrément de Stepiligne: Dest[idest] = Tab[iligne][k-iligne]

12/06/2009, 21h50
Invité

En fait, dans le cas d'une matrice rectangulaire (j'avais bêtement considéré qu'elle était forcément carrée...), on pourrait regarder la taille des diagonales en fonction de l'invariant i+j (qui lui augmente de 1 en 1, de 0 à Nlig+Ncol-2).

Cette longueur, qui part de 1 pour i+j=0, va augmenter de 1 jusqu'à ce que la diagonale en cours rencontre un des coins de la matrice (celui en bas à gauche si elle a moins de lignes que de colonnes, celui en haut à droite sinon).

Après, cette longueur va rester constante, jusqu'à ce qu'on rencontre l'autre "coin", puis va diminuer de 1 en 1...

Donc, si n et p sont les deux dimensions, et n < p (je ne precise pas laquelle est les lignes, et laquelle est les colonnes, ca simplifie le raisonnement)

on va donc avoir; pour une matrice non carrée
- n diagonales de longueurs croissantes allant de 1 à n, (débutant en position k(k+1)/2 )
- p-n-1 diagonales "constantes" de longueur n (débutant en position n(n+1)/2+(k-n)n )
- n diagonales de longueurs décroissantes allant de n à 1 débutant en position (n(n+1)/2+n(n-p-1)+(k-p)(k-p+1)/2 ?)

ce qui donne les positions successives des éléments dans le vecteur "déplié".

Pour une matrice carrée le calcul est légèrement différent, mais je pense qu'avec un peu de réflexion, on doit arriver à une formule presque sans if().

Francois