Discussion :

[simplyc]

bonjour
en fait hier j ai commencé un autre projet en c ,un projet qui me resemble un peu compliqué parce que on va utulisé plusieurs pointeurs dans le projet
en gros le but de projet c est de manipuler une matrice creuse qui contient plusieurs zero
il faut pas stoker des valeurs nulles

j ai commencé a suivre ces détails qui c est écrit dans le projet
1-un tableau de ligne dont chaque case pointe vers le premier élément non nul de la ligne


2-un tableau de colone dont chaque case pointe vers le premier élément non nul de la colone

3-une cellule est un élément de la matrice elle contient une valeur réel(double)non nulle et deux pointeurs un vers le prochain élément non nul de la ligne un autre vers le prochain élément non nul de la colone

d aprés ces donnée jai conclu ca

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
typedef struct s_cellule {
      int nb_zero;
      double valeur;
      struct s_cellule *ligne;
      struct s_cellule *ligne;
}t_cellule;
 
typedef struct {
    t_cellule *ligne;
    t_cellule *col;
    size_t nb_lig;
    size_t nb_col;
} t_matrice

maintenant je voudrai créer une matrice avec les valeurs dedans en utulisant ces deux structures bien sur!!!!
comment ca????

[diogene]

Code :

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

1
2
3
4
5
6
typedef struct s_cellule {
      int nb_zero;
      double valeur;
      struct s_cellule *ligne;
      struct s_cellule *ligne col;
}t_cellule;

Quelques questions qui se posent :
Dans ton idée
- Quel est le rôle de nb_zero ?
- Comment savoir le numéro de ligne et de colonne correspondant à un tel élément ?
- Comment déterminer la position d'un nouvel élément par rapport à un élément de la matrice déjà placé dans les listes chainées, avant, après, la même ? (pour pouvoir l'insérer en bonne place). Ceci rejoint la question précédente.

[simplyc]

en fait je le meme question que vous ,parce que moi j ai suivie c est qui est dans l énoncé de sujet,peut etre que c est faux
j espere que vous avez comprisle probleme

Code :

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

1
2
3
4
5
6
7
typedef struct s_cellule {

      int nb_zero;
      double valeur;
      struct s_cellule *ligne;
      struct s_cellule *ligne col;
}t_cellule;

Quelques questions qui se posent :
Dans ton idée
- Quel est le rôle de nb_zero ?
- Comment savoir le numéro de ligne et de colonne correspondant à un tel élément ?
- Comment déterminer la position d'un nouvel élément par rapport à un élément de la matrice déjà placé dans les listes chainées, avant, après, la même ? (pour pouvoir l'insérer en bonne place). Ceci rejoint la question précédente.

[diogene]

C'est quand même toi qui a défini ces structures.
Alors tu as mis le champ nb_zero pour représenter quoi ?

[matafan]

Il y a comme un problème dans tes structures de données puisqu'on ne sait pas à quelles coordonnées se trouvent tes cellules.

[simplyc]

C'est quand même toi qui a défini ces structures.
Alors tu as mis le champ nb_zero pour représenter quoi ?

ca serre a rien aparament,j ai mal reflechie

[simplyc]

Il y a comme un problème dans tes structures de données puisqu'on ne sait pas à quelles coordonnées se trouvent tes cellules.

oui je sais qu il ya des problemes , cest pour ca je posé mon question pour me trouver une solution

[matafan]

Je sais, c'est pour ça que j'ai pris la peine d'expliquer quel est le problème.

[Steph_ng8]

Bonjour,

maintenant je voudrai créer une matrice avec les valeurs dedans en utulisant ces deux structures bien sur!!!!
comment ca????

Ça dépend un peu de la manière dont tu récupères tes données.
Mais d'une manière générale je dirais qu'il faut faire une fonction qui, en fonction des coordonnées d'une valeur donnée, insère cette valeur à la bonne place dans la matrice.

Sauf que vu comment c'est parti, ça ne fonctionnera pas.
Il te faudra au préalable résoudre le problème pointé par diogene et matafan.

Bon courage !

[simplyc]

Bonjour,


Ça dépend un peu de la manière dont tu récupères tes données.
Mais d'une manière générale je dirais qu'il faut faire une fonction qui, en fonction des coordonnées d'une valeur donnée, insère cette valeur à la bonne place dans la matrice.

Sauf que vu comment c'est parti, ça ne fonctionnera pas.
Il te faudra au préalable résoudre le problème pointé par diogene et matafan.

Bon courage !

aucune reponse positive depuis le matin
que de blablabla

[matafan]

Tu veux pas qu'on te fasse ton exercice non plus ? Si tu veux des répondes précises, pose des questions précises. Il me semble qu'avec ce qu'on t'a dit tu as de quoi démarrer.

Toi, est-ce que tu as avancé depuis ce matin ?

[diogene]

1- Dire à ceux qui essayent de t'aider que leur contribution est du blablabla est discourtois et ne les encourage pas à continuer. Personne ici n'est payé pour t'aider.

2- Essayer de poser les éléments du problème, ce n'est pas du blablabla si on veut pouvoir le résoudre correctement

3- Tu dis que tu as suivi l'énoncé pour déclarer cette structure. Cette structure est-elle imposée par l'énoncé ou est-ce toi qui l'a imaginée ? Si tu as la liberté du choix de la structure, y stocker aussi les indices de la ligne et de la colonne de l'élément est une possibilité à envisager.

[Sve@r]

3- Tu dis que tu as suivi l'énoncé pour déclarer cette structure. Cette structure est-elle imposée par l'énoncé ou est-ce toi qui l'a imaginée ?

Ouais, déjà ce serait là une super info. Eventuellement, mettre l'énoncé entier serait encore mieux...

[simplyc]

Ouais, déjà ce serait là une super info. Eventuellement, mettre l'énoncé entier serait encore mieux...

ok ,oublion c est qui j ai mis dans mes structures
je vous dis exactment c est qui est dans le projet
l objectif c est réaliser en c une bibliotheque permettnt la mainipulation de matrice creuse c est a dire une matrice contenant une majorité de zero
en gros il est inutile de stocker ces valeurs nulles
Détails:
un tableau de lignes dont chaque case pointe vers le premiers élément non nul de la ligne
un tableau de colonnes dont chaque case pointe vers le premiers élément non nul de la colonnes
une cellule est un élément de la matrice elle contien une valeur réelle non nulless et deux pointeurs un vers le prochain élément non nul de la ligne un aute vers le prochain élément non nul de la colonne

le but c est de faire un saisie depuis le clavier pour entrer une matrice,addition deux matrices,multiplication.....
voila
j espere que c est claire

[matafan]

Ok oublie ma remarque "on ne sait pas à quelles coordonnées se trouvent tes cellules", parce qu'en fait si, on sait. Pas directement, mais on a toutes les informations nécessaires pour trouver les coordonnées de chaque cellule.

Est-ce que tu as compris la façon dont sera codée la matrice ? Si on prend un exemple (les chiffres ne sont pas les valeurs de la matrice, ce sont juste des index qui me serviront à référencer les cellules. Les espaces représentent des 0) :

Code :

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

1
2
3
|1 2    |
|  3 4  |
|  5 6  |

Dans cet exemple tu as 6 cellules, qui seront représentées comme ceci :

Code :

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

1
2
3
4
5
6
1: value = X    next_in_row = 2       next_in_col = NULL
2: value = X    next_in_row = NULL    next_in_col = 3
3: value = X    next_in_row = 4       next_in_col = 5
4: value = X    next_in_row = NULL    next_in_col = 6
5: value = X    next_in_row = 6       next_in_col = NULL
6: value = X    next_in_row = NULL    next_in_col = NULL

En supposant qu'une cellule est déclarée comme ceci :

Code :

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

1
2
3
4
5
struct cell {
    double value;
    struct cell *next_in_row;
    struct cell *next_in_col;
};

En plus de ces cellules tu as deux tableaux "rows" et "cols" de respectivement 3 et 4 struct cell * :

Code :

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

1
2
rows: 1, 3, 5
cols: 1, 2, 4, NULL

Tu remarqueras que ces informations sont suffisantes pour coder entièrement ta matrice. En effet tu sais que :

- La ligne 0 contient les cellules 1 et 2 (déterminé en prenant rows[0] et en suivant le chainage "next_in_row")
- La ligne 1 contient les cellules 3 et 4 (déterminé en prenant rows[1] et en suivant le chainage "next_in_row")
- ...
- La colonne 0 contient la cellule 1 (déterminé en prenant cols[0] et en suivant le chainage "next_in_col")
- ...
- ...
- ...

Si on représente "graphiquement" les cellules contenues dans chaque ligne et dans chaque colonne :

Code :

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

1
2
3
4
5
6
7
8
+-------+
|? ? ? ?| 1 2
|? ? ? ?| 3 4
|? ? ? ?| 5 6
+-------+
 1 2 4
   3 6
   5

Ce qui nous permet bien de placer à chaque intersection la cellule présente à la fois dans la ligne et dans la colonne correspondante.

[simplyc]

franchement chapeau
une trés trés bonne explication,mais je des mal a traduire tous ca

[simplyc]

matafan ,comment faire exactement pour ajouter des valeurs dans une matrice
j ai pense a demander la taille de matrice,et demandé la valeur,mais pour savoir comment gerer le s-cellule *ligne et s_cellule *colonne au meme temps
la je sais pas

[matafan]

La façon dont tu vas générer tes données dépend de la façon dont tu vas demander à l'utilisateur de les entrer.

En supposant la façon la plus générale et la plus naïve, où on demande à l'utilisateur d'entrer, pour chaque valeur non nulle, la valeur (X), le numéro de ligne (I) et le numéro de colonne (J). Dans ce cas tu créé une nouvelle cellule, et ton problème est de l'insérer à la bonne position dans les deux listes chainées rows[I] et cols[J].

Pour insérer la nouvelle cellule dans rows[I], l'idée est de parcourir la liste rows[I] en regardant, pour chaque élément, dans quelle colonne se trouve l'élément. Tu va insérer ta nouvelle cellule juste avant le premier élément dont le numéro de colonne dépasse J.

Pour insérer dans cols[J], c'est exactement le même principe.

Le problème est donc simplement de savoir retrouver le numéro de ligne et de colonne d'une cellule donnée. C'est très simple : pour trouver le numéro de colonne d'une cellule données, tu parcours chacune les listes du tableau cols, à la recherche de la colonne qui contient la cellule. Pareille pour trouver le numéro de ligne, tu parcours chacune des listes du tableau rows à la recherche de la ligne qui contient la cellule.

[diogene]

@matafan
Tu as raison, c'est vrai j'avais zappé qu'on peut retrouver les numéros de ligne et de colonne en tenant compte du fait qu'on a une information supplémentaire : un élément est représenté de façon unique par l'adresse de son descripteur. J'édite la discussion pour supprimer cette intervention intempestive et laisser la discussion "propre".

Pour résumer :

1- Pour connaitre la valeur placée dans l'élément (i,j) de la matrice d'origine, c'est simple : pour chaque élément situé dans la liste des éléments de la ligne i , regarder si il existe dans la liste des éléments en colonne j un descripteur ayant la même adresse. Si oui, on a dans ce descripteur la valeur, si non la valeur est 0.

2- Pour savoir à quels indice (i,j) correspond un descripteur, c'est vraiment couteux. tu as bien décrit la méthode.
Pour obtenir l'indice de ligne, il faut parcourir chaque liste de lignes à la recherche de la ligne qui contient la cellule. Ceci peut amener, dans le pire cas, à explorer l'ensemble des cellules.
Pour obtenir l'indice de colonne, il faut parcourir chaque liste de colonnes à la recherche de la colonne qui contient la cellule. Ceci peut amener, dans le pire cas, à explorer l'ensemble des cellules.

L'ennui est que cette dernière opération est sans doute la plus utile pour des calculs sur matrices creuses et qu'on a intérêt à avoir une procédure rapide pour cela.

[matafan]

Je viens de réaliser qu'en fait l'ordre n'a pas d'importance dans les listes chainées (sauf que suivant comment on interprète l'énoncé on pourrait supposer qu'il est demandé que les listes soient dans l'ordre, mais c'est à toi te voir). Donc pour placer un nouvel élément aux cordonnées I et J, il suffirait d'insérer l'élément en tête des listes rows[I] et cols[J].

Ca c'est en supposant évidemment que l'utilisateur ne rentre pas plusieurs fois une valeur pour la même case.