Matrice creuse

Version imprimable

03/12/2005, 23h49
lamar

Matrice creuse

bonjour,
je voudrais savoir comment représenter une matrice creuse d enregistrements nommé "cellule", tenant en compte que les enregistrements ont comme champs: la valeur, et quatre pointeurs (haut, bas, gauche, droit) qui pointent sur "cellule" afin d'obtenir une structure qui ressemblent à un tableur excel.
04/12/2005, 09h41
Trap D

Tout dépend du genre de calcul que tu veux faire avec cette matricte.
Le problème est la représentation de la matrice, pas celui de "la valeur" de la matrice.
Pour cette valeur tu peux te contenter d'un pointeur vers une structure répresentant l'élément.
Pour la matrice creuse voic ce qu' j'ai trouvé qui paraît intéressant :

Citation:

Une matrice creuse est une matrice de grande dimension comportant beaucoup d’éléments nuls. Pour minimiser l’espace mémoire utilisé pour stocker de telles matrices, on peut les représenter par un vecteur dont le nombre de composantes est égal au nombre de lignes de la matrice creuse. Chaque composante du vecteur est une liste contenant les éléments non nuls de la ligne correspondante dans la matrice creuse. Un élément non nul est décrit par son numéro de colonne et sa valeur. Dans la liste, les éléments sont rangés par ordre croissant des numéros de colonne.

Trouve ici
Tu peux aussi faire une simple liste chaînée en indiquant pour chauqe noeud les numéros de cases correspondant, je me répète, tout dépend de ce que tu veux faire.
04/12/2005, 14h28
lamar

merci pr votre reponse,est ce qu il est possible d'utilliser un tableau de pointeurs qui pointent sur les elements (structures) de la matrice
04/12/2005, 14h29
Trap D

Tout à fait.
04/12/2005, 15h57
lamar

En fait ce que j 'arrive pas a saisir c qu'on utilise les pointeurs pour allouer une place mémoire de taille inconnue et en mm temps je vais declarer un tableau de pointeurs, ca me parait un peu bizzar.

Tu ne déclares pas un tableau de pointeurs mais un pointeur vers une zone où tu pourras ranger des adresse vers des zones de mémoires contenant les structures.
Pour le problème d'allouer une taille inconnus, voilà ce que l'on fait généralement :
On alloue une taille "raisonnable", puis si besoin est, on réalloue une autre taille (en général on double la précédente). En C, on est assuré que si la réallocation a réussi les anciennes valeurs mémorisée sont conservées.
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 // nb est la première taille du tableau my_struct *ptr = malloc(nb * sizeof(*pt)); if (ptr != NULL) // toujours tester l retour de malloc { // on suppose qu'on lit des enregistrements dans le fichier de descripteur myfile int i = 0; my_struct *tmp; my_struct buf; // buffer de lecture while (fread(&buf, sizef(buf), 1, myfile) > 0) { // on mémorise l'enregistrement, on regarde la taille du tableau if (i == nb) // la taille du tableau est atteinte { // on double la taille du tableau n *= 2; tmp = realloc(ptr, nb * sizeof(*ptr)); if (tmp != NULL) ptr = tmp; else { fprintf(stderr, "Pb realloc\n"); // a toi de voir ce que tu veux faire } memcpy(&ptr[i], &buf, sizeof(buf)); i++: } } }
Je ne sais pas si ça répond à tes questions :cry:

04/12/2005, 17h57
lamar

Merci pour tes réponses, tu m'a donné un bon coup de main.
04/12/2005, 21h50
lamar

mon tableau est un tableau de pointeurs qui pointent sur des structures contenant les coordonnées x, y ma question est la suivante: est ce que ce tableau peut etre trié suivant x ou y.
04/12/2005, 22h02
Trap D

Bien sur, tu adaptes le quick sort du C à ton cas perso avec la bonne fonction de tri, ça nécessite une bonne pratique des pointeurs.
08/12/2005, 18h51
lamar

bonjour,
le pb que je veux sauvegarder dans le tableau dynamique des pointeurs sur les structures alors que selon cet exemple je vais stocker les structures et non pas les pointeurs alors que moi j'ai besoin de sauvegarder les pointeurs.
08/12/2005, 19h05
Trap D

:?:
Je ne comprends pas l'intérêt de sauvegarder les pointeurs, ou alors je n'ai pas compris ce que tu voulais dire :cry:
08/12/2005, 20h39
diogene

Citation:

le pb que je veux sauvegarder dans le tableau dynamique des pointeurs sur les structures

Si tes structures sont obtenues par allocation dynamique, ceci est justifié. Il suffit de créer un tableau (dynamique) de pointeur sur structure .
Pour reprendre l'exemple de Trap D

Code:

my_struct **ptr = malloc(nb * sizeof(*ptr));
08/12/2005, 21h58
fearyourself

Citation:

Envoyé par diogene

Si tes structures sont obtenues par allocation dynamique, ceci est justifié.

Je ne suis pas d'accord. Meme sur une allocation statique, une methode comme celle-ci peut se justifier. Il faut simplement faire attention a la duree de vie du tableau.

Le choix se fait surtout du point de vue algorithmiquement et cote performance. Un tri par indirection peut se faire pour eviter le cout des deplacement successives lors d'un tri. Ou parce que plusieurs tri par des criteres differents sont necessaires (on veut un tri par rapport au nom et un autre par rapport a la date d'inscription...)

J'ai par contre une preference pour l'indirection par indice a la place de celle par le pointeur lui-meme mais les deux se valent cote performance (du moins a quelque chose pres).
08/12/2005, 23h35
lamar

Merci a vs tous,
Je vais expliquer un peu l objectif
Dans un tableau dynamique je veux stocker des pointeurs sur des cellules (structures), chaque cellule a quatre pointeur (haut, bas, gauche, droite) qui pointent sur des cellules selon leurs positions par rapport à la cellule à créer.

l insertion d'une cellule peut se faire en haut , en bas, à droite ou àa gauche des cellules deja existantes.

Donc j'ai besoin de stocker des pointeurs sur les cellules d'une manière trièe suivant le x et le y de la cellule afin de pouvoir faire des recherches pour trouver (haut, bas, gauche, droite) de la cellule à inserer.

soit cel le tableau des pointeurs sur les cellules et ptr le pointeur sur la cellule à inserer,et i,j,k,h des position dans le tableau, je dois avoir quleque chose comme ca:

ptr->haut=ptr[i]
ptr->bas=ptr[k]
ptr->gauche=ptr[j]
ptr->droite=ptr[h]

Le deuxième problème: pour determiner (haut, bas, droite, gauche), je dois parcourir le tableau plusieurs fois selon x et y, donc je me suis retrouvé avec plusiers boucle tant que ce qui ralentit l 'exceution.

J' espère que j'ai bien expliqué le problème afin que vous puissiez m 'aider.

Merci.
09/12/2005, 16h46
fearyourself
- Est-ce que tu peux donner un exemple simple d'avant - après une insertion?
Utilises une image si tu peux, cela parle plus généralement...

Parce que mon plus grand problème de compréhension serait:
Code:

1 2 3 4 5 6 7 8 9 10 11 12 Avant: A -- C | | B -- D Si je veux insérer E entre A et C, qui se trouvent en dessous de E? A -- E -- C | | | B -- ? -- D
- Comment tu fais pour savoir où tu inséres ton élément?

Par contre, je sens qu'un modérateur va dire: "c'est plutôt un probléme algorithmique que C" ... Ils auraient sûrement raison...

Jc
09/12/2005, 17h09
diogene

fearyourself dit :

Citation:

diogene a écrit:

Citation:

Si tes structures sont obtenues par allocation dynamique, ceci est justifié.

Je ne suis pas d'accord. Meme sur une allocation statique, une methode comme celle-ci peut se justifier.

Le remplissage du tableau par l'adresse de variables obtenues par allocation automatique relève de l'enfer (si il y en a un peu beaucoup) sauf si elles sont elles-mêmes disposées en tableau
10/12/2005, 00h55
fearyourself

Citation:

Le remplissage du tableau par l'adresse de variables obtenues par allocation automatique relève de l'enfer (si il y en a un peu beaucoup) sauf si elles sont elles-mêmes disposées en tableau

Bien sur, je parlais de tableau... En fait,
:oops: , je n'avais meme pas pu imaginer qu'on puisse le considerer autrement!!

Le faire a la main? L'idee de tout ce travail me fatigue...