Listes chainées multiples

Version imprimable

16/01/2008, 20h59
Mister Jingles

Listes chainées multiples

Bonsoir tout le monde,

Je voudrais savoir s'il y a moyen de faire un nombre listes chainées defini par l'utilisateur?

:)
16/01/2008, 21h14
hegros

Tu veux dire que le nombre de maillons max soit défini par l'utilisateur ?
16/01/2008, 21h14
iMaTh

explique toi mieux j'ai pas tout compris.
16/01/2008, 21h23
Mister Jingles

L'utilisateur donne un nombre (exemple : 5)

Le programme crée 5 listes chainées pour y rentrer des données. Les données ne sont pas triés, et donc il faudrait un moyen pour acceder simplement a une liste, un peu comme un tableau à deux dimensions.
16/01/2008, 21h33
diogene

Citation:

Envoyé par Mister Jingles

L'utilisateur donne un nombre (exemple : 5)

Le programme crée 5 listes chainées pour y rentrer des données. Les données ne sont pas triés, et donc il faudrait un moyen pour acceder simplement a une liste, un peu comme un tableau à deux dimensions.

Tu veux une liste de listes ?
16/01/2008, 21h36
Mister Jingles

Justement, je sais pas si c'est possible, mais c'est un peu ça. Le problème c'est qu'il faut parcourir la première liste pour trouver la deuxième. C'est pas un peu lourd a faire?
16/01/2008, 21h42
diogene

Citation:

Envoyé par Mister Jingles

Justement, je sais pas si c'est possible, mais c'est un peu ça. Le problème c'est qu'il faut parcourir la première liste pour trouver la deuxième. C'est pas un peu lourd a faire?

Bien sur, c'est possible. C'est pas très difficile à faire non plus.
16/01/2008, 21h49
Mister Jingles

N'est t'il pas plus simple de faire un tableau de pointeur? Chaque case[i] du tableau pointe sur la ième liste?

Je voudrais faire un algo rapide et avec un minimum de memoire. :)

:roll: J'ai dis une connerie?

J'ai fais une base avec une liste chainée.

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
#include <stdio.h>
#include <stdlib.h>
 
typedef struct article
{
	int date;
	struct article* suivant;
}article;
 
typedef article* ll;
 
ll addArticles_(ll distributeur, int dateArticles)
{
	ll newArticle=malloc(sizeof(article));
	newArticle->date=dateArticles;
	newArticle->suivant=NULL;
	if(distributeur==NULL)
		return newArticle;
	else
	{
		ll tmp=distributeur;
		while(tmp->suivant!=NULL)
			tmp=tmp->suivant;
		tmp->suivant=newArticle;
		return distributeur;
	}
}
 
ll delArticles_(ll distributeur)
{
	if(distributeur!=NULL)
	{
		ll retour=distributeur->suivant;
		free(distributeur);
		return retour;
	}
	else
		return NULL;
}
 
int finDate_(ll distributeur)
{
	int date=distributeur->date;
	ll tmp=distributeur;
	while(tmp!=NULL)
	{
		if(tmp->date<date)
			date=tmp->date;
		tmp=tmp->suivant;
	}
	return date;
}
 
int main()
{
	int nbOperations=0, operation=0, i=0;
	int nombreArticles=0, dateArticles=0, date=0;
	ll distributeur=NULL;
	scanf("%d", &nbOperations);
	for(operation=0;operation<nbOperations;operation++)
	{
		scanf("%d%d", &nombreArticles, &dateArticles);
		if(nombreArticles>0)
		{
			for(i=0;i<nombreArticles;i++)
				distributeur=addArticles_(distributeur, dateArticles);
		}
		else
		{
			for(i=0;i>nombreArticles;i--)
				distributeur=delArticles_(distributeur);
		}
	}
	date=finDate_(distributeur);
	printf("%d\n", date);
	return 0;
}

Comment faire pour en avoir plusieurs??

Très simple:

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
/* Article */
typedef struct article
{
	int date;
} article;
 
/* Liste d'articles */
typedef struct chainon_article
{
	article a;
	struct chainon_article *pSuiv;
} chainon_article;
 
typedef struct liste_articles
{
	chainon_article *pPremier;
} liste_articles;
 
/* Liste de listes d'articles */
typedef struct chainon_liste_articles 
{
	liste_articles l;
	struct chainon_liste_articles *pSuiv;
} chainon_liste_articles;
 
typedef struct liste_listes_articles 
{
	chainon_liste_articles *pPremiere;
} liste_listes_articles;

Et les fonctions qui vont avec.

17/01/2008, 16h53
Mister Jingles

Merci.

Et dernière question:

J'ai fais un tableau dynamique de structure :

Code:

tableaull=malloc(nbDistributeurs*sizeof(ll));

Chaque case pointe vers le premier élément de la chaine.

Lequels des deux algos est le plus rentable, niveau memoire et temps?
17/01/2008, 17h56
diogene

Citation:

Envoyé par Mister Jingles

Merci.

Et dernière question:

J'ai fais un tableau dynamique de structure :

Code:

tableaull=malloc(nbDistributeurs*sizeof(ll));

Chaque case pointe vers le premier élément de la chaine.

Lequels des deux algos est le plus rentable, niveau memoire et temps?

Si le nombre de listes chaînées n'est plus susceptible de varier (ou pas souvent), c'est le plus économique en mémoire et en temps

Remarque : ll est un pointeur. Il est peu astucieux de masquer cette propriété dans un typedef ou alors l'identificateur doit la suggérer . Je préfère pour mon goût article*
17/01/2008, 18h58
Mister Jingles

Ok merci

Pour le coup du pointeur, j'ai pris l'habitude de faire comme ça. Et donc moi ça ne me choque pas. ;)