Matrice en liste simplement chaînées - C

[Lusheez]

Bonjour !

 

J'ai un projet à rendre la semaine prochaine pour mes cours et j'aimerais bien un peu d'aide, surtout pour comprendre !

 

Alors voilà, l'énoncé est simple, je dois représenter et manipuler des matrices grâce à des listes simplement chaînées.

 

Une matrice contiendra une première liste qui correspondra aux lignes de la matrice. Chaque noeud de cette liste contiendra l’indice de la ligne et un pointeur vers la liste contenant la ou les valeurs non nulles de la ligne. Chaque ligne sera une liste ordonnée contenant dans chaque noeud l’indice de la colonne et la valeur réelle non nulle qui y est stockée.

 

 

Je précise bien que je ne veux pas une résolution de mon projet, j'ai vraiment envie de comprendre ce que je dois faire et pourquoi.

 

Alors, déjà, commençons par un petit schéma. SI j'ai bien compris l'énoncé, pour la matrice  3x3

[1 2 3]

[4 5 6]

[7 8 9]

 

Je devrais avoir le schéma correspondant :

 

 

avec la première colonne correspondant aux indices de la ligne, puis les autres, la case du dessus est l'indice de la colonne, la case du dessous la valeur.

 

Bon déjà faut voir si j'ai bon avec ce schéma !

 

Ensuite, comme première méthode à implémenter, les matrices sont stockées dans des fichiers, fichiers ayant une forme du style :

 

* Un fichier ne contient qu’une seule matrice et est stocke de la façon suivante:
* - le premier entier (int) contient le nombre de lignes
* - le deuxieme entier (int) contient le nombre de colonnes
* - les donnees suivantes sont les éléments de la matrice, ligne par ligne (chaque élément étant un double)

 

Donc ! Dans mon fichier .h je définis déjà les trois structs suivantes:

 

struct matrix {
    int nb_lignes;
    int nb_colonnes;
    ligne * l;    
/* A completer ` */
}

typedef struct ligne {
    int ind_ligne;
    colonne * c;
}


typedef struct colonne {
    int ind_colonne;
    double valeur;
    colonne * c;
}

 

 

et dans mon fichier .c j'ai la méthode sp_read

 

struct matrix *sp_read(char *path)
{
    
    int nb_lignes, nb_colonnes;
    int i = 0;
    int j = 0;
    FILE* fichier = NULL;
    fichier.fopen(*path, "r");
    if(fichier == NULL)
    {
        printf("Erreur lors de l'ouverture du fichier: %s"+ path);
        return NULL;
        
    }    
    fread(&nb_lignes, sizeof(nb_lignes),1, fichier);
    fread(&nb_colonnes, sizeof(nb_colonnes),1, fichier);

    struct matrix mat = (struct matrix *) malloc (sizeof(struct matrix));
    if(mat==NULL){
        fprintf(stderr,"Mallocation de matrice impossible \n");
        return NULL;
    }
    mat->l = (ligne *) malloc(sizeof(ligne*));    
    if(matrice->l==NULL) free(matrice);
    
    for(i=0;i<nb_lignes;i++)
    {
        for(j=0;j<nb_colonnes;j++)
        {
    
        }
    }
    
    fclose(fichier);
    return mat;
}

 

C'est là que je coince. Je suis vraiment très peu doué au niveau des pointeurs, et je ne sais pas trop comment accéder aux données. Idéalement, en avançant dans le fichier je dois mettre les valeurs dans le double valeur de la struct colonne, puis avancer, et ne faire ça que pour les valeurs non nulles (le but est de travailler avec des matrices creuses, donc des matrices avec beaucoup de 0), puis une fois arrivé au bout de la ligne, je dois retourner dans la première liste chaînée et avancer dans celle-là. Comment manipuler correctement les données ?

 

Ensuite, toutes les méthodes que je fais doivent être thread-safe. Je dois utiliser la libraire pthread. Est-ce que je peux me soucier du soucis des threads plus tard ? C'est à dire d'abord faire le "gros" du code, vérifier que ça fonctionne, puis entourer les sections critiques avec des mutex ?

 

Merci d'avance pour ceux qui seront arrivés au bout de ce post, et merci encore plus à celui qui acceptera de m'aider,

 

Un pauvre étudiant en désarroi,

 

Lusheez.

 

[Kernelcoffee]

Oula, ça va faire quelque années que je n'ai pas fais de C, il faudrait que je regarde dans mes archives.

 

Bon en gros pour les pointeurs y a openClassRoom qui explique ca assez bien et c'est un peu la base donc vaut mieux maitriser.

 

en gros pour accéder a un pointeur:

int *pointer = malloc(sizeof(int));*pointer = 42;printf("%d", pointer); // ca va afficher l'adresse du pointeur.printf("%d", *pointer); // ca va afficher le contenue du pointeur.

Pour les threads en C je suis un peu rouille mais normalement il faut que tu lock les mutex sur les parties qui impliquent de modifier la valeurs au seins de la matrice, en lecture ça devrait pas être un soucis.

[Lusheez]

C'est surtout au niveau de mes listes chaînées, qui s'imbriquent un peu. Comment accéder de manière correctes aux valeurs et les affecter ? J'aurai aussi besoin d'un avis sur ce que j'ai déjà fait... Histoire de voir que je me situe sur le bon chemin. Mais merci Kernelcoffee !

[Kernelcoffee]

Je peux pas trop ecrire un roman maintenant sur les listes chaines mais une explication rapide.

je fais ça de mémoire donc c'est pas forcement correct, mais au moins être proche de ce que tu veux.

 

Structure classique d'une liste;

typedef struct clist{ void *data; // tu va stocker tes valeur la dedans; clist *next; // pointeur vers la prochaine structure}

tu cree ta liste et tu imbrique en les reliant via *next.

donc :

clist *list = malloc(sizeof(clist)); // on cree le 1er élément de la listelist.data = (void*)<ce que tu veux> // la ou tu stock tes données.clist *first = list; // on sauvegarde le debut de la liste, pour s'y retrouverlist.next = mallot(sizeof(clist)); // on cree le 2e élément de la liste.list = list.next; // on assigne le 2e élément sur le pointeur list (on a sauvegarder le 1er de tout facon)list.data...         // et ainsi de suite

ca c'est la base.

ensuite tu construit des fonctions autour pour repondres a tes besoin (recuperer la structure numero x dans la liste)

et tu customize ta structure pour repondre a tes besoins

genre dans ton cas ca serais quelque chose comme

typedef struct clist{  int value;  clist* data;  clist* next;}clist *ligne = mallocligne.data = malloc // et ici sera ta colone.clist *colonne = ligne.data; // ca sera peut-etre plus clair comme ca;colonne.value = 42; // et tu stocke/lit tes valeurs

Dans ton cas, ça n'est pas vraiment la peine d'avoir deux structures séparés pour colonne et ligne, tu peux les combiner et ca te donnes la possibilité de gérer des matrices infini de facon plus simple vu que tu n'a qu'un seul type a gérer.

[RinDman]

Si je comprends bien tes structures, ça doit être un truc du genre :

 

colonne *cursor : la case courante quoi, désolé d'employer le terme curseur, c'était tentant

 

*cursor = cursor.c;

 

Bref,  il faut impérativement que tu modifies la valeur de l'adresse par celle de la case suivante/voisine, j'avais appris 2 styles de notation sur les pointeurs avec les listes chaînés en c qu'on pouvait "typer", ainsi on pouvait simplifier en quelque sorte en indiquant le pointeur avec le "->", modifier réellement la valeur du pointeur en faisant &(*colonne) , en clair jouer avec les * et &  ( c'est un beau bordel, désolé )

 

Et après vu que t'es sur la case suivante, lire la valeur qu'elle contient, bah voir ce qui a été dit précédemment

 

printf(" %f ", cursor.valeur );

 

Et pour les lignes, bah une fois compris avec c'est pareil ...

 

PS : Il est utile d'utiliser une variable temporaire qui garde le 1er élément de la ligne et de la matrice, faut pas oublier de retourner au début de l'index ( parce que si tu te perds, c'est fini )

[Kernelcoffee]

J'avais appris 2 styles de notation sur les pointeurs avec les listes chaînés en c qu'on pouvait "typer", ainsi on pouvait simplifier en quelque sorte en indiquant le pointeur avec le "->", modifier réellement la valeur du pointeur en faisant &(*colonne) , en clair jouer avec les * et & ( c'est un beau bordel, désolé )

En fait utiliser & permet de designer l'adresse d'une variable;

donc si tu as un variable (genre int a), et qui est declare en "dur" (j'aime pas ce terme pour signifier non alloue mais bon).

Tu peux passer passer cette variable en tant qu'adresse a une fonction (ex: foo(&a) ) et dans cette fonction tu peux modifier directement la valeur de la variable. Le but etant de d'eviter de faire des "deep copy" de la variable.

C'est surtout de la gestion de memoire et ca permet de modifier des variables dans des fonctions tout en permettant une valeur de retour sur cette fonction pour determiner si l'operation a reussi ou pas.

------

Bon ca m'a un peu pris la tete, mais j'ai code a l'arrache un exemple de liste chaine (sur mon linux);

au final j'ai passe plus de temps a faire en sorte que l'affichage soit propre que sur le code en lui meme mais ca devrait t'aider (vaguement)

 

https://github.com/kernelcoffee/sample_projects/blob/master/c/example_chained_list/main.c

 

ca se compile avec la commande

cc -std=c99 main.c

 

et s'execute avec

./a.out

 

et te donne le resultat suivant:

assigning

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

showing

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 0 1 2 3 4 5 6 7 8 9 10

 

Bon heuresement que je suis plus a l'ecole sinon je me serai fait fouete jusqu'au sang par mon prof pour le code (norme c90, printf, pas de free, 25 lignes).

[Lusheez]

Déjà, deux petites questions: est-ce que c'est pas mieux dans getNext(n) de mettre set->column = NULL; au lieu de set->column ='\0'; ? Idem avec le next évidemment. Mais '\0' c'est pour signaler la fin d'un string non ? Je vois pas trop l'intérêt du coup..

 

Aussi, c'est vrai qu'il serait plus facile de n'avoir qu'un seul type de structure, mais selon l'énoncé, je dois avoir une première liste contenant uniquement, à chaque noeud, l'indice de la ligne et un pointeur vers la liste contenant les valeurs non nulles de la dite ligne. Comme représenté dans mon schéma. A moins que je ne déclare une structure avec plusieurs variables mais en ne les utilisant pas forcément tout le temps ? Mais est-ce que ce n'est pas du gaspillage de mémoire ? Parce que du coup il me faudrait quelque chose comme

 

struct matrix

{

 double valeur;

 int indice;

 struct matrix * next;

 struct matrix * colonne;

}

 

Il faut que je gaspille la mémoire le moins possible idéalement. Merci en tout cas pour le temps que tu m'accordes !

 

J'aurais donc plutôt pensé à ça :

 

struct ligne

{

int indice_ligne;

colonne * c;

ligne * next;

}

 

struct colonne

{

int indice_colonne,

double valeur;

colonne * next;

}

[Kernelcoffee]

Ah tiens, je me souvenais plus qu'il y avait NULL en C, je ne fais plus que du C++ ces jours-ci et NULL est juste une macro sur 0 (et donc ça peut passer a travers certaine condition si on fait pas gaffe) mais une vrai définition de NULL est apparus avec C++11 : nullptr qui est un vrai NULL unique.

Du coup j'ai fait en sorte que ça doit reconnaissable autrement que part NULL, et je me souvenais de '\0' pour les fins de chaines..

 

bon c'est corrige..
.

Je pense que tu peux déjà t'en sortir avec ce que tu as a ta disposition, c'est pas obligatoire que ca soit parfait tout de suite.

Pour la gestion de la mémoire je te laisse découvrir ce qui est le mieux :

- Calcule le cout d'une ou deux structures

- le cout d'un double pour stocker des valeurs la ou un int ou un float peut etre suffissant

- Est ce que tu compte avoir 2^32-1 indice_ligne ou colonne ? est ce qu'un unsigned short ne serai pas plus économique ?

- Attention a l'alignement de la mémoire (a verifier si gcc le fait pas pour nous maintenant)

- Est ce que tu dois forcement garder l'indice dans la structure ou est ce que tu ne peux pas simplement utiliser le compteur comme j'ai fais pour déterminer ta position dans la matrice ?

- Regarder le cout mémoire/vitesse d’exécution et voir qu'est ce qui le plus important.

- Attention a la localité des données en mémoire et comment cela affecte la vitesse d’exécution. (quoi que c'est peut-être surtout en C++ ça)

- etc..

 

La route de l'optimisation est longue et rigoureuse

 

Ah aussi essaye plutôt de nommer tes variables en anglais, je trouve que c'est une habitude a prendre qui est assez utile quand il s'agit de bosser sur des projets internationaux (environ 95% des projets professionnel)

[Lusheez]

- La valeur en double est une consigne explicite du projet.

- Je vais travailler avec un unsigned int, tu as raison.

- En fait, le but est de travailler avec des matrices creuses, et les listes chaînées comprendront les valeurs non nulles (uniquement) de la matrice de départ.

 

Donc on peut avoir, pour la 5e ligne par exemple [4]-> [0/1.2] -> [5/0.8] -> [8/0.25].

 

Donc à la 5e ligne de la matrice les seules valeurs non nulles sont 1.2, 0.8 et 0.25 aux colonnes 0, 5 et 8. C'est important pour le parcours, et plus tard je dois pouvoir additionner des matrices entre elles, ainsi que les multiplier.

 

Et pour être honnête, je n'ai aucune idée de la différence du coût entre une ou deux structures. Mais avoir une grosse structure où on n'utilise pas toujours tout me paraît plus gourmand que deux plus petits structures plus "rentables". Mais, ce qui m'arrive plutôt souvent, je peux me tromper.

 

Merci encore !

 

Je posterai mon avancement demain !

 

PS: Ceux qui hésitent encore, Guardians of the Galaxy est un très très bon film.

[Kernelcoffee]

Bon j'ai verifie rapidement en fait le cout d'une structure est 0 (je pensais que c'etait 4 mais en fait non), cependant le compilateur va aligner la memoire afin d'optimiser en arondissant la taille a l'octet superieur.

[Lusheez]

Avec un peu de retard mon avancée.

 

J'ai un petit problème de mémoire que je n'arrive pas à résoudre. J'ai une erreur "double free or corruption (fasttop)" lorsque j'exécute mon programme.

 

J'ai recherché ce que ça pouvait bien vouloir dire mais j'ai pas très bien compris. Décidément le C n'est pas ma tasse de thé..

 

Voici matrix.c

#include <stdio.h>
#include <stdlib.h>
#include <pthread.h>
#include <time.h>
#include "sparsemat.h"

struct matrix *sp_read(char *path)
{
	
	int nb_lignes, nb_colonnes;
	double valeur;
	int i = 0;
	int j = 0;
	FILE* fichier = NULL;
	fichier = fopen(path, "r");
	if(fichier == NULL)
	{
		printf("Erreur lors de l'ouverture du fichier: %s", path);
		return NULL;
		
	}	
	fread(&nb_lignes, sizeof(nb_lignes),1, fichier);
	fread(&nb_colonnes, sizeof(nb_colonnes),1, fichier);

	struct matrix*  mat = malloc (sizeof(struct matrix));
	if(mat==NULL){
		fprintf(stderr,"Mallocation de matrice impossible \n");
		return NULL;
	}
	struct matrix * first = mat;
	for(i=0;i<nb_lignes;i++)
	{ 	
		colonne * col = malloc (sizeof(colonne));
        for(j=0;j<nb_colonnes;j++)
        {
            fread(&valeur, sizeof(valeur), 1, fichier);
            if(feof(fichier)) fclose(fichier);
            else if (valeur != 0.0)
            {
                mat->ind_ligne = i;
                colonne * nouveau = malloc (sizeof(colonne));
                nouveau->valeur = valeur;
                nouveau->ind_colonne = j;
                nouveau->next = NULL;
                if(col == NULL) col = nouveau;
                else
                {
                    colonne * temp = col;
                    while(temp->next != NULL)
                    { 
                        temp = temp->next;
                    }
                    temp->next = nouveau;
                    free(nouveau);
                    col = temp;
                }                     
            }          
        }
		mat->c = col;
        free(col);
        struct matrix * nouveauM = malloc (sizeof(struct matrix));
        mat->next = nouveauM;
        free(nouveauM);
        mat= mat->next;
	}
	return mat;
}

int sp_write(struct matrix *mat, char *path)
{
	
}

int sp_get(struct matrix *mat, unsigned int row, unsigned int col, double *val)
{
	
}

int sp_set(struct matrix *mat, unsigned int row, unsigned int col, double val)
{
	
}


struct matrix *sp_add(struct matrix *m1, struct matrix *m2)
{
	
}

struct matrix *sp_mul(struct matrix *m1, struct matrix *m2)
{
	
}
int main ( int argc, char *argv[] )
{
    char *c = "XXX";
    struct matrix * mat = sp_read(c);  
}

char *c = "XXX"; est bien évidemment le path.

 

Si quelqu'un voit ce qui cloche et veut bien me l'expliquer ce serait génial !

 

Bon après midi à tous.

[chaps]

Hello,

 

Je n'ai pas beaucoup de temps, du coup j'ai juste jeté un coup d'oeil rapide, et voici ce qui m'a sauté aux yeux :

1. Tu fais des "free" de tes objets au fur et à mesure que tu les ajoutes dans ta liste chainée. Du coup tu as une liste d'objets détruits, ce qui n'est certainement pas ce que tu veux. Tu ne dois détruire tes objets que lorsque tu n'en as plus besoin.
2. Tu testes "if(col == NULL)", ce qui ne peut (sauf erreur mémoire) pas être le cas puisque tu as fait "colonne * col = malloc(sizeof(colonne));" au dessus. Tu devrais donc tester "if(col->next == NULL)".
3. En C, contrairement au C++, il n'y a pas de constructeur appelé à la création de l'objet. Après avoir fait un "malloc" d'un nouvel objet, tu dois initialiser toi même les valeurs des différents champs de la structure, sinon ces valeurs seront indéterminées. Après avoir fait "colonne * col = malloc(sizeof(colonne));", rien ne t'assure que "col->next == NULL" à moins que tu n'ais explicitement fait toi même un "col->next = NULL" après le malloc. Du coup au lieu de faire des malloc directement, tu devrais faire une fonction de création de l'objet, qui l'initialise à des valeurs par défaut après l'avoir créé, et appeler cette fonction à chaque fois que tu créé un objet.
4. Si j'ai bien compris, dans ta boucle de parcours de colonnes, quand tu ajoutes une nouvelle colonne, tu initialise "col" à la valeur de cette nouvelle colonne. Du coup, "col" pointe toujours sur la dernière colonne de ta liste chainée. Comme ta liste est simplement chainée et que tu ne gardes pas le premier élément quelque part, tu n'as aucun moyen de le retrouver. Au final, toutes tes colonnes n'auront donc qu'un seul élément, à savoir le dernier créé. Et toutes les autres colonnes seront perdues en mémoire, tu ne pourras même plus les parcourir ou les détruire. En fait tu devrais concerver un pointeur sur le permier élément de la liste, et éventuellement un autre pointeur actualisé sur le dernier élément, ce qui te permettra d'ajouter les nouvelles colonnes sans être obligé de reparcourir toute la liste à chaque fois.

Voilà rapidement ce que j'ai vu, il y a peut-être d'autres trucs que je n'ai pas vu mais déjà si tu corriges tout ça, ça devrait mieux se passer . Et n'oublies pas d'utiliser des outils de debogage pour faire du pas à pas dans ton code et voir ce qui ne va pas, ça te permettra de mieux comprendre comment ça marche, et ce qui ne va pas le cas échéant

 

Bon courage !

[RinDman]

Faut jamais free(), pour ça tu crées une fonction pour nettoyer tes matrices qu' À LA FIN du programme.

 

Sinon en cours de route après l'allocation ( où on retourne le pointeur ), tu n'as pas spécialement besoin de mettre des free ... Tu as juste à veiller que le début de la zone mémoire est bien le premier à passer au nettoyage

 

Le pointeur se retrouvera NULL tout seul ...

[chaps]

Faut jamais free(), pour ça tu crées une fonction pour nettoyer tes matrices qu' À LA FIN du programme.

 

Ça dépend des cas.

Ici c'est effectivement ce qu'il faut faire (et à l’extrême du coup il pourrait carrément ne pas faire de free du tout, même si c'est "moins propre" ça ne changerait pas grand chose). Mais il existe plein de cas où viens un moment où tu n'as plus besoin d'un objet avant la fin du programme, et dans ce cas mieux vaut le libérer tout de suite. Sinon cela créé ce que l'on appelle des "memory leak", la consommation mémoire du programme ne fait qu'augmenter au cours du temps.

 

Le pointeur se retrouvera NULL tout seul ...

 

Non . La méthode free (tout comme le delete en C++) ne set pas à NULL le pointeur après l'avoir détruit ! C'est à toi de le faire si tu veux éviter les accidents (l'utilité de mettre le pointeur à NULL après sa destruction dépend des cas). Par contre tu peux sans problème faire un "free" ou un "delete" d'un pointeur NULL, c'est une action sans effet (et qui ne fait absolument pas planter le programme).

 

 

Sinon en cours de route après l'allocation ( où on retourne le pointeur ), tu n'as pas spécialement besoin de mettre des free ...

 

Ça dépend des cas. Ici non, en effet.

 

Tu as juste à veiller que le début de la zone mémoire est bien le premier à passer au nettoyage

Bah disons qu'il faut bien veiller à libérer le pointeur qui a été retourné par "malloc" et pas un autre, mais ça semble évident