MATRICE / LISTE chainée

Version imprimable

12/05/2011, 20h26
sali2801

MATRICE / LISTE chainée

SALU à tous
je demande juste comment peut_on representer une matrice avec les listes linaires chainée..... je parle du chainage entre les maillons. je serai tres reconnaissante si quelqu'un m'aide
merci pour l'aide
12/05/2011, 22h50
Elijha

Bonsoir,

Tu trouveras un très bon cours sur les listes chainées ici : "Les listes chaînées en langage C".
13/05/2011, 00h50
Sve@r

Salut

Généralement le but d'une liste chainée est de pouvoir insérer facilement des éléments au milieu de la liste. On modifie juste 2 pointeurs. Alors que pour insérer un élément au milieu d'un tableau, il faut agrandir le tableau puis décaler tous les éléments qui suivent l'insertion.

Dans une matrice, je ne vois pas trop l'utilité d'implanter une liste chainée vu que la matrice est généralement quelque chose de figé dans sa taille. Et donc je ne comprends pas que tu ailles te priver des possibilités du tableau (pouvoir balayer tout un tableau avec un simple décalage) parce que tu t'orientes sur une technologie peu utilisée habituellement dans les objets que tu manipules.

Tu voudrais bien nous apporter quelques précisions STP ?
13/05/2011, 13h13
sali2801

Citation:

Envoyé par Sve@r

Salut

Généralement le but d'une liste chainée est de pouvoir insérer facilement des éléments au milieu de la liste. On modifie juste 2 pointeurs. Alors que pour insérer un élément au milieu d'un tableau, il faut agrandir le tableau puis décaler tous les éléments qui suivent l'insertion.

Dans une matrice, je ne vois pas trop l'utilité d'implanter une liste chainée vu que la matrice est généralement quelque chose de figé dans sa taille. Et donc je ne comprends pas que tu ailles te priver des possibilités du tableau (pouvoir balayer tout un tableau avec un simple décalage) parce que tu t'orientes sur une technologie peu utilisée habituellement dans les objets que tu manipules.

Tu voudrais bien nous apporter quelques précisions STP ?

TOUT à fait d'accord avec toi mais ce travaille ma était imposé je peux rien dire!!! c'est pour ça je cherche des idéés!!!

avant que j'oublie la matrice que j'ai n'est pas gifée... elle est en fonction des (l,L) largeur*longueur entré par l'utilisateur
13/05/2011, 13h20
sali2801

Citation:

Envoyé par Elijha

Bonsoir,

Tu trouveras un très bon cours sur les listes chainées ici : "Les listes chaînées en langage C".

merci pour le lien mais c'est dommage je cherche pas ça ........ je cherche UNE matrice en liste chainé!!!!!
13/05/2011, 14h18
Elijha

1 pièce(s) jointe(s)

Bonjour,

Serait-ce plus ça (voir miniature) ?
13/05/2011, 19h35
Mat.M

Salut,

Citation:

Envoyé par sali2801

TOUT à fait d'accord avec toi mais ce travaille ma était imposé je peux rien dire!!! c'est pour ça je cherche des idéés!!!

avant que j'oublie la matrice que j'ai n'est pas gifée... elle est en fonction des (l,L) largeur*longueur entré par l'utilisateur

eh bien il faut faire des listes chainées...de listes chainées..

( c'est comme en C++ pour faire des std::vector<std::vector>> )

Quand tu construits la liste il faut allouer un pointeur qui va pointer sur un autre pointeur d'une première liste chainée puis une deuxième etc..en fait des pointeurs de pointeurs.
13/05/2011, 20h00
sali2801

Citation:

Envoyé par Elijha

Bonjour,

Serait-ce plus ça (voir miniature) ?

OUI C'est EXACTEMENT ce que je cherche à realiser.....peux_ tu m'aider
13/05/2011, 20h04
sali2801

Citation:

Envoyé par Mat.M

Salut,

eh bien il faut faire des listes chainées...de listes chainées..

( c'est comme en C++ pour faire des std::vector<std::vector>> )

Quand tu construits la liste il faut allouer un pointeur qui va pointer sur un autre pointeur d'une première liste chainée puis une deuxième etc..en fait des pointeurs de pointeurs.

votre reponse me parait interessante mais j'arrive pas à imaginer ce que vous voulez dire...une explication s'il vous plait
13/05/2011, 20h13
Mat.M

Eh bien selon l'exemple du tutoriel il faut déclarer un node **p;
par contre il faut modifier la fonction pour ajouter des éléments.
:D

Citation:

Envoyé par Mat.M

Eh bien selon l'exemple du tutoriel il faut déclarer un node **p;

Sûrement pas. Un node **p suppose que tu pointes vers quelque chose pointant vers l'élément utile (donc 2 indirections) alors que dans le schéma, chaque item possède deux flèches chacune d'elle pointant vers un item identique donc chaque flèche étant une simple indirection...

Citation:

Envoyé par sali2801

OUI C'est EXACTEMENT ce que je cherche à realiser.....peux_ tu m'aider
Code:

1 2 3 4 5 6 7 8 9 10 11 typedef struct s_item { int valeur; struct s_item *next_col; struct s_item *next_lig; } t_item; typedef struct { t_item *first; unsigned int nb_lig; unsigned int nb_col; } t_matrice;

Citation:
Envoyé par Sve@r
Code:

1 2 3 4 5 6 7 8 9 10 11 typedef struct s_item { int valeur; struct s_item *next_col; struct s_item *next_lig; } t_item; typedef struct { t_item *first; unsigned int nb_lig; unsigned int nb_col; } t_matrice;
DESOLé mais le problem persiste encore je crois que c'est plus un problem de declaration de structure mais plutot du chainage .:cry:.....
j'ai décidé par exemple de créé le premeir maillon qui a deux tetes ( vertical/horizontal) ces deux tetes seront sauvegarder dans deux tableaux dynamique de taille colonne/ligne
à partir de ce fameux maillon je fais une boucle qui vas me créer la premier liste horizontale chaque maillon a une tete sauvegardeé dans le tableauLigne

ET ouppps je sais plus comment finir mon idéé

mes idéés sont_elles bonnes???? aide moi

15/05/2011, 19h07
Sve@r

Citation:

Envoyé par sali2801

j'ai décidé par exemple de créé le premeir maillon qui a deux tetes ( vertical/horizontal) ces deux tetes seront sauvegarder dans deux tableaux dynamique de taille colonne/ligne

Mouais. Tant qu'à utiliser des tableaux, autant alors mettre toute ta matrice en simple tableau 2D quoi...

Citation:

Envoyé par sali2801

ET ouppps je sais plus comment finir mon idéé

Ben c'est un peu la preuve qu'elle est pas terrible. Déjà tu dis que chaque maillon a 2 têtes. Or, un maillon n'a qu'une adresse. Ensuite tu veux stocker ces 2 têtes dans des tableaux. Ce n'est alors plus de la liste chainée mais simplement du tableau.

Elijha t'a montré le schéma. Chaque maillon possède l'adresse du maillon suivant situé sur la même ligne et du maillon suivant situé sur la même colonne. Et j'ai codé ce schéma en C pour te montrer le principe. Maintenant si tu ne veux plus faire de la liste chainée c'est toi qui voit...

1 pièce(s) jointe(s)

Bonsoir,

Il y a peut-être un moyen plus simple. C'est de ne pas lier les toutes les colonnes ensembles, mais seulement la première. En gros tu te retrouves avec une liste chainée pour la première colonne et une liste chainé par ligne. Un petit dessin ? (voir miniature).
La gestion en sera simplifiée, par contre il faudra changer ton algorithme de parcours de ton tableau.

Décompose ton programme en fonctions de plus bas niveau. Par exemple, tu peux te créer deux fonctions; une qui te créer une liste simplement chainée (ligne), et une autre qui te libère la liste.
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 s_item *newLigne(int nbCellule) { // Retourne un pointeur sur une liste de nbCellules } void freeLigne(s_item **ligne) { // Libère la mémoire d'une liste } int newMatrix(int nbLigne, int nbColonne, t_matrice *matrix) { // Pour nbColonne (liées) allouer nbLignes } void freeMatrix(t_matrice *matrix) { // Libère la mémoire d'une matrice } int main(void) { t_matrice matrix ; newMatrix(10, 10 &matrix) ; // Ici tu peux naviguer dans ta matrice freeMatrix(&matrix) ; return 0 ; }