tableaux de listes chainées

Version imprimable

06/07/2014, 09h19
dafirami

1 pièce(s) jointe(s)

tableaux de listes chainées

bonjour,
SVP aidez moi je suis bloqué, qui a un code de construction et remplissage d'un tableau statique dont chaque case contient une liste chaînée ?
comme montre cette figure:
Pièce jointe 150473
06/07/2014, 10h25
Ehonn

Bonjour

(Il y a exactement le même sujet sur l'ex SdZ.)

Ce que tu demande est:

Code:

std::array<std::list<ton_type>, nombre_de_listes_chaînées> nom_variable;

Mais je te conseille :

Code:

std::vector<std::vector<ton_type>> nom_variable(nombre_de_listes_chaînées);

Documentation : std::vector, std::array, std::list.
07/07/2014, 10h09
ternel

Sinon, comme ça ressemble beaucoup à un exercice, comment t'y prendrais-tu, conceptuellement?
08/07/2014, 01h13
dafirami

Non leternel ce n'est pas un exercice c'est une petite chose que je dois comprendre et je vais effectuer beaucoup de modifications, et en me basant dessus je peux faire 0.00005 % de mon exercice ! Car mon exercice est un algorithme génétique, qui est très long et ce n'est pas ce petit code et je ne fais pas de copier coller attention à ce que tu dis !! Et tout au long de ma vie j'explique aux gens qui viennent et ne comprennent rien et le jour où j'ai besoin d'une aide en ligne j'ai pas compris pourquoi je trouve beaucoup des gens qui ont un problème sur que j'ai publié !
08/07/2014, 09h21
LittleWhite

Bonjour,

Procédons par étape.

Avez vous une classe implémentant une liste chainée ? (ou une structure, mais en C++, je verrai plus une classe). De plus, pourquoi ne pas utiliser std::list ? (Exemple ici : http://chgi.developpez.com/dblist/ )
Ensuite, le tableau, conceptuellement, c'est juste un tableau statique de pointeur sur la classe de liste chainée (je conseille un std::array en C++11, ou une std::vector), donc une fois que vous avez la liste chainée, vous n'avez presque plus gérer.

On remarquera donc que ainsi, je rejoins beaucoup la réponse de Ehonn :ccool:
08/07/2014, 09h50
ternel

Citation:

Envoyé par dafirami

je ne fais pas de copier coller attention à ce que tu dis !!

Ce n'était que ma signature, elle ne te vise pas particulièrement.:aie:

C'est exacte que l'implémentation d'une liste chainée est très très rarement nécessaire. On préfère std::list, qui a des dizaines d'années d'optimisation.

ton problème correspond très bien à un st::vector de st::list, ou une st::array de st::list.
éventuellement, un vector de set ou de vector. sont envisageable.

Cela dépend de la raison pour laquelle tu as des listes, et de la notion mathématique qu'elle représente.
Le set est trié, permettant un accès plus direct, et garantit l'unicité des valeurs qu'il contient
08/07/2014, 10h21
Bousk

Donc je résume
- on voit apparaître un graph sans aucune explication
- non ce n'est pas un exercice comme il semblerait l'être
-- pourtant c'est typiquement un modèle d'exercice basique du langage
- tu ne sais pas remplir un vector et utiliser une list
- tu en as besoin pour un algorithme génétique (je connais pas ces bestioles, mais ça a l'air complexe non ?)

Avant de courir on apprend à marcher normalement :roll:

Nan parce que bon,

Citation:

tableau statique dont chaque case contient une liste chaînée

Ca revient à.. std::vector<std::list<Item> > vec(5); et voilà tu as un tableau de 5 list d'Item :weird:

http://www.cplusplus.com/reference/v...vector/vector/
08/07/2014, 12h05
ternel
Un algo génétique est un algo de type apprentissage.
Il s'agit de chercher quels paramètres optimisent un calcul.
C'est utile essentiellement avec des paramètres continus.

On se base sur une analogie avec l'adn et ses mutations.

On fait le calcul avec un jeu de paramètres, estime son optimalité.
Puis on modifie ce jeu de paramètres, et on refait les calculs.
répéter jusqu'à plus soif...

(du moins, ce sont mes souvenirs...)

Invoquer de telles choses implique en général d'être dans la recherche en IA et/ou en apprentissage, ou bien d'être dans les domaines d'application correspondant.

MAIS!

Quel que soit le travail qu'on fait, on ne peut le faire correctement et avoir confiance dans le résultat qu'en maîtrisant les outils utilisés.
Pour du C++, savoir ce que contient la STL, et quand l'utiliser est la base.

Puisque, dafirami, tu es étudiante, et que tu poses des questions sur comment écrire des fonctionnalités de base, je te conseille de faire un tour sur:
- notre faq C++: lis tout c'est instructif.
- nos cours, même si tu ne vas pas tout lire maintenant, c'est bon de savoir qu'ils existent, et de quoi ils parlent.
- cppreference.com: une des documentations du langage, et ma préférée

Bonsoir SVP, j'ai écrit ce code (tableau de liste chaînées) pour un exemple d'un tableau statique de de taille 5 dont chaque case contient une liste chaînée de taille 2, dont le but que le programme me donne ça lors de l’exécution:

1. remplir et afficher le tableau initialisé de liste.
2. remplir et afficher le tableau de liste après ajout.
1 // càd si je choisi 1
initialiser les différentes case:3
initialiser les différentes case:4
initialiser les différentes case:7
initialiser les différentes case:9
initialiser les différentes case:6

afficher:
3
4
7
9
6

2 // càd si je choisi 2
ajouter autres elements dans chaque celleule(liste) du tableau:5
ajouter autres elements dans chaque celleule(liste) du tableau:2
ajouter autres elements dans chaque celleule(liste) du tableau:1
ajouter autres elements dans chaque celleule(liste) du tableau:8
ajouter autres elements dans chaque celleule(liste) du tableau:4

afficher
3 5
4 2
7 1
9 8
6 4

Je teste mon code et je le corrige jusqu'à qu'il ne contient aucune erreur, mais je ne comprend pas pourquoi tous les fonctions d'initialisation, ajout et affichage ne fonctionnent pas! qui peut m'aider SVP !

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
#include <iostream>
 
using namespace std;
 
struct Node{
 int num;
 Node *nextNode;
 Node *prevNode;
};
 
void initializeLists(Node* head, Node* Arraylist[], int MAX_INDEX);
void addNode(int num, int arrayIndex, Node* Arraylist[], int countArray[]);
void affiche_apres_initialisation (Node *p, Node* Arraylist[]);
void affiche_apres_ajout (Node *ptr, Node* Arraylist[]);
 
int main()
{
    int MAX_INDEX(5);
    Node* Arraylist[5];
    int num;
    int arrayIndex;
    int countArray [2];                      // taille de chaque list.
    Node* head ;
    head = NULL;
 
while (1){
  int n;
  cout << "1. remplir et afficher le tableau initialisé de liste." << endl;
  cout << "2. remplir et afficher le tableau de liste apres ajout." << endl;
  cin >> n;
 
if(n==1){
 
     cout << "initialiser les differentes case: ";
     cin >> num;
     initializeLists( head, Arraylist, MAX_INDEX);
     cout << "afficher:";
     affiche_apres_initialisation (head, Arraylist);
    }
 
else if (n==2){
 
    cout << "ajouter autres elements dans chaque celleule(liste) du tableau: ";
    cin >> Arraylist[arrayIndex]->num;
    addNode( num, arrayIndex, Arraylist, countArray);
    cout << "afficher:";
    affiche_apres_ajout (head, Arraylist);
    }
else{
    cout << "BY"<< endl;
    break;
    }
 
    return 0;
}
}
 
void initializeLists(Node* head, Node* Arraylist[], int MAX_INDEX) {
 
    int idx;
    int num;
 
    for (idx = 0; idx < MAX_INDEX; idx++) {    //pour chaque liste du tableau.
        Node* newNode = new Node;              //créer un nouveau noeud.
        Arraylist[idx] = newNode;               //affecter ce noeud à un indice du tableau.
        head = newNode;                         //affecter ce noeud à la tete de la liste.
        newNode->nextNode = NULL;               //initialiser à null.
        newNode->prevNode = NULL;               //initialiser à null.
        newNode->num = num;                     //donner la valeur initial de la tete de chaque liste.
 
    }
    return;
}
 
void addNode(int num, int arrayIndex, Node* Arraylist[], int countArray[]) {
 
  int MAX_INDEX;
  for (arrayIndex = 0; arrayIndex < MAX_INDEX; arrayIndex++) {
    Node* newNode = new Node;                    //créer un nouveau noeud.
    Node* head = Arraylist[arrayIndex];           //affecter la tete de la liste à chaque case du tableau
 
       if (head->num == NULL) {
 
        head->num = num;
 
        }
        else {                                    
 
 
        newNode->nextNode = head->nextNode;       // inserer un noeud à une liste.
        head->nextNode = newNode;
        newNode->prevNode = head;
 
 
        if (newNode->nextNode != NULL) {
            newNode->nextNode->nextNode = newNode;
        }
        newNode->num = num;
        }
    countArray[arrayIndex]++;                      //incrementer le compteur de la liste.
    }
    return;
}
 
 void affiche_apres_initialisation (Node *p, Node* Arraylist[])
  {
 
    int MAX_INDEX(5);
 
    for (int idx = 0; idx < MAX_INDEX; idx++){
      while (p != NULL){
      cout << Arraylist[idx]->num << endl ;
        p = p->nextNode;
        p = p->prevNode;
     }
  }
  }
 
  void affiche_apres_ajout (Node *ptr, Node* Arraylist[])
  {
    int arrayIndex (5);
 
    while (ptr != NULL){
     cout << ptr->num << endl << endl;
     Arraylist[arrayIndex]->nextNode;
     ptr = ptr->nextNode;
     ptr = ptr->prevNode;
     }
  }

12/07/2014, 03h12
dafirami

Peut être il ya quelqu’un qui peut détecter l'erreur dans une minute. car je suis débutante. et dans tous les forum je vois des personnes qui postent leurs codes et d'autres personnes qui lui corrige !
12/07/2014, 11h57
LittleWhite

La précision utilse est :
"Qu'entendez-vous par cela ne fonctionne pas " ? Il se passe quoi ?
Qu'est ce que vous voyez et que pouvez vous en conclure ?

De plus, vous pouvez ajouter des printf, ou même mieux, utiliser un débogueur, pour comprendre ce que fait le programme.
12/07/2014, 15h33
dafirami

1 pièce(s) jointe(s)

ne fonctionne pas càd les fonctions d'ajout et d’initialisation n'affiche pas le tableau pour que je peut entrer les éléments de chaque case voila le debogueur qu'est ce qu'il affiche:
Pièce jointe 151018

Tableaux de listes chainées

Bonjour
Je vais probablement faire du hors sujet sur un forum C++ je m'en excuse d'avance mais, comme je vois qu'il a du mal à comprendre certains mécanismes, je vais donc proposer une approche en langage C pour représenter à peu près son schéma et surtout son exercice.
Ton conteneur doit jouer le rôle d'un tableau de pointeur, en résumé c'est un moyen économique de référencer tout l'ensemble de tes listes en une seule structure afin de les manipule aisément.
Pour que tu puisses comprendre ce que j'avance je poste le code en langage C ci-dessous
bien entendu j'invite les expert à me corrigé si j'ai émis des erreurs.
Cordialement.

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
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
 
#include <stdio.h>
#include <stdlib.h>
 
/* Macro Bool */
typedef enum{false,true}bool;
 
/***
* Structure Simple d'une Pile
***/
typedef struct _Pile{
 
	unsigned int iVal;
 	struct _Pile *pPrec;
}ts_Pile;
 
/***
*       Fonction vérification 
*   de la pile
***/
bool f_isEmpty(ts_Pile **pIn){
 
	return ( (*pIn == NULL ) ? true : false );
}
 
/***
* Fonction qui ajoute un élement
* dans la Pile
***/
void f_addPile(ts_Pile **pIn, unsigned int const iVal){
 
	ts_Pile *tmp = malloc( sizeof( ts_Pile ) );
 	if( !tmp ){
  		perror( "Erreur interne d'allocation\n" );
  		exit( 1 );
 	}
 
	/*	Ajout de l'élément	*/
 	tmp->iVal = iVal;
 	tmp->pPrec = *pIn;
 	*pIn = tmp;
}
 
/***
* fonction qui retire un élement
* de la Pile
***/
unsigned const int f_PopPile(ts_Pile **pIn){
 
	unsigned int iVal = 0;
 
 	ts_Pile *tmp = NULL;
 	if( !*pIn  )
  		return ( -1 );
 
 	tmp  = (*pIn)->pPrec;
 	iVal = (*pIn)->iVal;
 
 	free( *pIn );
 	*pIn = tmp;
 
 	return ( iVal );
}
 
/***
* Fonction qui libère
* la mémoire allouer
***/
void f_FreeAlloc( ts_Pile **pIn){
 
	ts_Pile *tmp = NULL;
 
	if( f_isEmpty( pIn ) != true ){
 
		while( *pIn ){
			tmp = (*pIn)->pPrec;
			free ( *pIn );
			*pIn = tmp;
		}
 
		*pIn = NULL;
		tmp = NULL;
	}
}
 
 
/***
* Fonction principale
***/
int main( void ) {
 
	int i = 0;	
 
	/* Déclaration des piles & initialisation */
 
 	ts_Pile *pile_1 = NULL;	/*	Pile (1)	*/
 	ts_Pile *pile_2 = NULL;	/*	Pile (2) 	*/
 	ts_Pile *pile_3 = NULL;	/*	Pile (3)	*/
 
 	/*	tableau de Pointeur */
 	ts_Pile (**pTabAddr[3]) = { &pile_1, &pile_2, &pile_3 };
 
 	/*	Ajouts des valeurs à la pile	*/
 	for(; i < 20 ; i++){
 		f_addPile(	pTabAddr[0], i );
 		f_addPile(	pTabAddr[1], (i*2) );
 		f_addPile( 	pTabAddr[2], (i*4) );
 	}
 
 	/*	Affichage des Piles	*/
 	for(i = 0; i < 20 ; i++)
 		printf("Pile (1)\t= %d\n", f_PopPile(&pile_1) );
 
 	for(i = 0; i < 20 ; i++)
 		printf("Pile (2)\t= %d\n", f_PopPile(&pile_2) );
 
 	for(i = 0; i < 20 ; i++)
 		printf("Pile (3)\t= %d\n", f_PopPile(&pile_3) );
 
 	/*	Désalocation mémoire */
 	f_FreeAlloc( pTabAddr[0] );
 	f_FreeAlloc( pTabAddr[1] );
 	f_FreeAlloc( pTabAddr[2] );
 
 
 	return ( 0 );
}