Copier une partie d'une liste doublement chaînée

**ChrisNilson** · 30/11/2013, 22h11

Bonjour,

Je travaille actuellement sur un projet et je dois copier une partie d'une liste de structure doublement chaînée. Cette manipulation doit forcément être possible mais je ne vois pas comment y arriver...

Admettons la structure suivante

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
typedef struct e
{
    char* name;
    int nbr;
} ELEMENT;
 
 
 
typedef struct node
{
    ELEMENT data;
    struct node* prev;
    struct node* next;
}*Liste

Je cherche à copier à partir d'un noeud de la liste, le reste de la liste, puis de mettre cette copie en bout de liste. Schématiquement ça donnerait :

A <-> Z <-> E <-> R <-> T <-> Y -> NULL , copie à partir de T, A <-> Z <-> E <-> R <-> T <-> Y <-> T <-> Y -> NULL

d'après ce que j'ai pu voir, je ne pense pas que la fonction memecop puisse réaliser ceci.

Et la fonction suivante ne marche pas :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
void coy_part(Liste l, ELEMENT source)
{
 
    Liste buffer = calloc(1,sizeof(source));
 
    while(strcmp(l->data.name,source.name) !=0) //source.name = T
    {
        l = l->suiv;
    }
 
    buffer = l;
 
    while(l->suiv ! = NULL)
    {
        l = l->suiv;
    }
 
    l->suiv = buffer;
 
}

Dans ce cas là, le 2ème élement "T" aura pour prev toujours "R" et non "Y"

Je cherche donc ) me placer en "T", copier tout ce qui suit, et remplacer le "prev" du nouveau "T". Je sens que c'est un truc bête mais je ne le vois pas...

Auriez vous une solution ?

**EpiTouille** · 01/12/2013, 09h14

Voila l'approche que j'aurais suivi :

Code :

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

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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct e {
	char *name;
	int nbr;
}t_elem;
 
typedef struct node {
	t_elem data;
	struct node *prev;
	struct node *next;
}t_node;
 
 
//Une fonction pour remplir la liste, mais pas d'interret pour toi
void add_elem(t_node **list, char *name) {
	t_elem e;
	t_node *elem;
	t_node *ptr_debut;
 
	ptr_debut = *list;
	e.name = name;
	elem = malloc(sizeof(t_node));
	elem->data = e;
	if (*list == NULL) {
		*list = elem;
		elem->next = NULL;
		elem->prev = NULL;
	} else {
		while ((*list)->next != NULL) {
			*list = (*list)->next;
		}
		(*list)->next = elem;
		elem->prev = *list;
		elem->next = NULL;
		*list = ptr_debut;
	}
}
 
//La fonction pour tester si tout a bien marché
void afficher_list(t_node *l) {
	while (l != NULL) {
		printf("%s", l->data.name);
		l = l->next;
	}
}
 
 
 
int nb_elem_a_copier(t_node *l) {
	int  i = 0;
	while (l != NULL) {
		++i;
		l = l->next;
	}
	return i;
}
 
 
//La fonction interessante
void copy_part(t_node *list, t_elem source) {
	t_node *ptr_debut = list;
 
	//on parcours notre liste
	while (list != NULL) {
 
		//Si l'element match
		if (strcmp(list->data.name, source.name) == 0) {
 
 
			//On doit forement enregistrer le nombre d'element
			//car plus on va en ajouter, plus la liste va s'agrandir
			int nb = nb_elem_a_copier(list);
			while (nb != 0) {
				add_elem(&ptr_debut, list->data.name);
				list = list->next;
				nb--;
			}
			return;
		}
		list = list->next;
	}
 
}
 
int main(void) {
 
	t_node *list = NULL;
 
	add_elem(&list, "a");
	add_elem(&list, "z");
	add_elem(&list, "e");
	add_elem(&list, "r");
	add_elem(&list, "t");
	add_elem(&list, "y");
 
	afficher_list(list);
 
	t_elem e;
 
	e.name = "t";
 
	copy_part(list, e);
 
	printf("\n");
 
	afficher_list(list);
 
	printf("\n");
 
	return EXIT_SUCCESS;
}

C'est le code complet de ton exemple, je ne le poste pas pour que tu le recopie mais que tu t'en inspires (si ça te convient). Je poste la sortie sur idone afin de voir le resultat.
Comme à chaque fois, je précise, y'a pas de free, de verification ect... mais c'est pas le sujet

http://ideone.com/5cGyai

Bonne journée

**Sve@r** · 01/12/2013, 10h51

Salut
Je suppose que ton programme est bien découpé et donc tu dois sûrement avoir une fonction dédiée à la création d'un maillon ; puis une autre dédiée à l'insertion d'un maillon au bon endroit.
Ce qui est sûr, c'est que si tu balayes ta liste à partir de T et que tu insères ce T en fin de liste, ton balayage ne s'arrêtera plus jamais.
Ce qu'il faut faire, c'est balayer ta liste à partir de T mais insérer ce T dans une seconde liste chainée. Et continuer ainsi jusqu'à la fin de ta première liste.
Ensuite, tu as en main ce début de seconde liste chainée ; te suffit de mettre ce pointeur en fin de première liste...

**ChrisNilson** · 04/12/2013, 01h32

Envoyé par EpiTouille

Voila l'approche que j'aurais suivi :

Code :

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

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
 
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct e {
	char *name;
	int nbr;
}t_elem;
 
typedef struct node {
	t_elem data;
	struct node *prev;
	struct node *next;
}t_node;
 
 
//Une fonction pour remplir la liste, mais pas d'interret pour toi
void add_elem(t_node **list, char *name) {
	t_elem e;
	t_node *elem;
	t_node *ptr_debut;
 
	ptr_debut = *list;
	e.name = name;
	elem = malloc(sizeof(t_node));
	elem->data = e;
	if (*list == NULL) {
		*list = elem;
		elem->next = NULL;
		elem->prev = NULL;
	} else {
		while ((*list)->next != NULL) {
			*list = (*list)->next;
		}
		(*list)->next = elem;
		elem->prev = *list;
		elem->next = NULL;
		*list = ptr_debut;
	}
}
 
//La fonction pour tester si tout a bien marché
void afficher_list(t_node *l) {
	while (l != NULL) {
		printf("%s", l->data.name);
		l = l->next;
	}
}
 
 
 
int nb_elem_a_copier(t_node *l) {
	int  i = 0;
	while (l != NULL) {
		++i;
		l = l->next;
	}
	return i;
}
 
 
//La fonction interessante
void copy_part(t_node *list, t_elem source) {
	t_node *ptr_debut = list;
 
	//on parcours notre liste
	while (list != NULL) {
 
		//Si l'element match
		if (strcmp(list->data.name, source.name) == 0) {
 
 
			//On doit forement enregistrer le nombre d'element
			//car plus on va en ajouter, plus la liste va s'agrandir
			int nb = nb_elem_a_copier(list);
			while (nb != 0) {
				add_elem(&ptr_debut, list->data.name);
				list = list->next;
				nb--;
			}
			return;
		}
		list = list->next;
	}
 
}
 
int main(void) {
 
	t_node *list = NULL;
 
	add_elem(&list, "a");
	add_elem(&list, "z");
	add_elem(&list, "e");
	add_elem(&list, "r");
	add_elem(&list, "t");
	add_elem(&list, "y");
 
	afficher_list(list);
 
	t_elem e;
 
	e.name = "t";
 
	copy_part(list, e);
 
	printf("\n");
 
	afficher_list(list);
 
	printf("\n");
 
	return EXIT_SUCCESS;
}

C'est le code complet de ton exemple, je ne le poste pas pour que tu le recopie mais que tu t'en inspires (si ça te convient). Je poste la sortie sur idone afin de voir le resultat.
Comme à chaque fois, je précise, y'a pas de free, de verification ect... mais c'est pas le sujet

http://ideone.com/5cGyai

Bonne journée

Wo merci beaucoup pour ton aide et le temps que tu as pris pour faire ce programme. Ça m'a bien aidé !

Salut
Je suppose que ton programme est bien découpé et donc tu dois sûrement avoir une fonction dédiée à la création d'un maillon ; puis une autre dédiée à l'insertion d'un maillon au bon endroit.
Ce qui est sûr, c'est que si tu balayes ta liste à partir de T et que tu insères ce T en fin de liste, ton balayage ne s'arrêtera plus jamais.
Ce qu'il faut faire, c'est balayer ta liste à partir de T mais insérer ce T dans une seconde liste chainée. Et continuer ainsi jusqu'à la fin de ta première liste.
Ensuite, tu as en main ce début de seconde liste chainée ; te suffit de mettre ce pointeur en fin de première liste...

Merci à toi aussi Sve@r. Oui tu as parfaitement raison.

En fait la principale raison est que je voulais appliqué ceci à un arbre n-aire (qui peut etre vu comme un arbre binaire d'ailleurs) mais je cherchais en fait à copier un sous arbre de ce dernier puis le mettre à un autre endroit.
Mon problème maintenant et que je voudrais copier un sous arbre.

Bon maintenant il ne me reste plus qu'à pouvoir parcourir cette arbre et modifier tout les node portant le même nom que le node à modifier, s'il y a une modification à faire sur un node.

J'aurais une autre question ma structure a évolué et je me retrouve avec un "char* resultat". Je ne connais pas la taille du résultat tant que l'utilisateur ne rentre pas l'input. Résultat aura une taille max à n * strlen(input).

A cet input je devrais appliqué plusieurs calcul dans tout les noeuds de mon arbre en me servant des résultats que je trouve au fur et à mesure.

Comment puis je appliquer un strcpy sur le char* resultat ??

**Sve@r** · 04/12/2013, 16h10

Envoyé par ChrisNilson

J'aurais une autre question ma structure a évolué et je me retrouve avec un "char* resultat". Je ne connais pas la taille du résultat tant que l'utilisateur ne rentre pas l'input. Résultat aura une taille max à n * strlen(input).

Pourquoi "n*" ??? Si resultat doit contenir l'input, alors "resultat" aura une taille max à strlen(input) + 1 (pour pouvoir y stocker aussi le '\0').

Envoyé par ChrisNilson

Comment puis je appliquer un strcpy sur le char* resultat ??

Ben si l'input est une chaine (sous-entendu "terminée par un '\0'") il n'y a aucun souci. Le strcpy() copiera chaque octet de l'input dans la zone ciblée (ici "resultat") et y ajoutera le '\0' pour que cette zone puisse elle-aussi être considérée comme chaine.

Code c :

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

1
2
3
4
5
char *resultat;
char input[]="Hello world";
 
resultat=malloc(sizeof(char) * (strlen(input) + 1));
strcpy(resultat, input);

Autre possibilité

Code c :

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

1
2
3
4
char *resultat;
char input[]="Hello world";
 
resultat=strdup(input);

C'est le code le plus souple possible (le strdup se chargeant du malloc+strcpy) (ne pas oublier le free(resultat) une fois que l'on en n'a plus l'utilité).
Toutefois il arrive qu'on considère (arbitrairement) que l'input ne fera pas plus de (par exemple) 160 caractères (ou 2000 ou 5000)
Dans ce cas, on taille resultat à la taille choisie et on ne s'embête pas avec un malloc(). Surtout que si la saisie se fait par fgets() on peut alors la verrouiller à la taille désirée.
Bien entendu chaque nouveau maillon sera alloué avec une taille équivalente donc risque de surconsommation inutile de mémoire...

**ChrisNilson** · 04/12/2013, 16h25

Résultat doit une taille max à n * strlen(input), c'est une limitation du système je ne sais pas encore de combien je pense que ça sera autour de n=8 ou 10.

Et je ne connais pas la taille de l'input car c'est l'user qui le rentre.

Pour un char* resultat dans la structure, après avoir fait dans le main les initialisations suivantes :

Code :

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

char* input = "hey";

et plus loin pour un nouveau nœud

Code :

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

1
2
length = 10*strlen(input);
newNode->data.result = malloc(sizeof(char)*length);

j'avais essayé un strcpy(t->data.result, input); qui me renvoie une seg fault... J'ai du mal suivre ton explication :/

**Sve@r** · 04/12/2013, 18h19

Envoyé par ChrisNilson

Résultat doit une taille max à n * strlen(input), c'est une limitation du système je ne sais pas encore de combien je pense que ça sera autour de n=8 ou 10.

Mais c'est quoi ce "n" ? Ou (autre question) quel est le rôle de la variable "résultat" par rapport à la variable "input" ?

Envoyé par ChrisNilson

Et je ne connais pas la taille de l'input car c'est l'user qui le rentre.

Oui mais tu as le droit de considérer (ou d'imposer à l'user) que l'input sera limité en taille (et ça ça dépend de l'utilité de cet input). Par exemple quand sur le net tu as un formulaire où on te demande ton nom, généralement ce champ de saisie du nom est limité à 20 car. Maintenant si on te demande tes centres d'intérêts c'est plus pareil...

Envoyé par ChrisNilson

Pour un "char* resultat" dans la structure, après avoir fait dans le main les initialisations suivantes :

char* input = "hey";

et plus loin pour un nouveau noeud

length = 10*strlen(input);
newNode->data.result = malloc(sizeof(char)*length);

On reste sur une incompréhension. A quoi sert le champ "result" de ton objet "data" ? Parce que (peut-être que je me trompe) mais je pense que ce champ sert à stocker dans le noeud créé la donnée saisie à ce moment là. Dans ce cas s'il faut saisir "une donnée" je ne comprends pas pourquoi allouer de l'espace pour "dix fois" cette donnée ???)

Envoyé par ChrisNilson

j'avais essayé un strcpy(t->data.result, input); qui me renvoie une seg fault... J'ai du mal suivre ton explication :/

Vu ton exemple du dessus, cela aurait plutôt été strcpy(newNode->data.result, input). Mais ça suppose que

newNode soit un pointeur valide
newNode.data soit un type (et pas un pointeur)

Et ça, on n'en sais trop rien.

Envoyé par ChrisNilson

J'ai du mal suivre ton explication :/

C'est simple: en faisant abstraction de l'invalidité possible des pointeurs amenant au champ "result", si ce champ "result" a assez de place pour stocker le contenu du champ "input", et si le champ input" contient réellement une chaine de caractères (donc impérativement terminé par un '\0' qu'il ne faut pas oublier de comptabiliser), alors strcpy() fonctionne sans souci.

Voici un exemple minimaliste fonctionnel associé à cette explication qui reprend tes instructions éparses

Code c :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
typedef struct {
	char *result;
} t_data;
 
typedef struct {
	t_data data;
} t_node;
 
void remplir(t_node *newNode)
{
	char* input = "hey";
	newNode->data.result = malloc(sizeof(char) * (strlen(input) + 1));
	strcpy(newNode->data.result, input);
}
 
int main()
{
	t_node racine;
	remplir(&racine);
	printf("Résult: [%s]\n", racine.data.result);
}

Copier une partie d'une liste doublement chaînée

C

Vue hybride

Discussions similaires

Partager

Partager