Discussion :

[jhaythem]

Bonjour,

ca fait longtemps que j ai pas touche du C ou du C++, et la j ai besoin de faire des exercices pour me rafraichir la memoire .

Je dois ecrire une fonction qui retourne le 5eme avant dernier element d une liste chainee simple en une seule iteration.

J ai ecris un petit bout, mais je ne suis pas du tout fier de moi meme, c est la premiere pense que j ai eu.
Voila mon bout de code

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
 
int sll_get_five_before_Last(sll_s *p_sll){
	int p = 0, i =5;
	int temp[5];
	if(p_sll){
		p_sll->list = p_sll->p_start->next;
		while(p_sll->list != NULL){
			if(p-5 >= 0){
				for(i=0 ;i<4  ; i++){
					temp[i]=temp[i+1];
				}
				temp[4] = p_sll->list->value;
			}else{
				temp[p] = p_sll->list->value;
			}
			p_sll->list = p_sll->list->next;
			p++;
		}
		if(p-5>= 0){
			return temp[0];
		}else{
			//contains less than 5 elements
			return NULL;
		}	
	}else{
		return NULL;
	}
 
 
}

Merci je suis ouvert a toute optimisation, juste des petites suggestions me suffisent...

Cheers,

[Médinoc]

Si tu veux vraiment optimiser, il faudra faire de temp un buffer circulaire.

Mais commence par commenter ton code.

[jhaythem]

un buffer circulaire? mhh j aurais besoin d un coup de pouce sur ca

Mon algo est assez simpliciste, je traverse ma chaine et j ajoute que les 5 dernier elements de la liste et si la liste est plus courte que 5 je retourne la valeur 0.

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
 
int sll_get_five_before_Last(sll_s *p_sll){
	int p = 0, i =5;
	//create temp table that will hold only the last 5 values
	//temp look like after 6 values that we have gone throw lets says the value from 0 to 6
	// temp = {2,3,4,5,6}
	//when we go throw the 7th value of the list temp look like
	// temp = {3,4,5,6,7}
	int temp[5];
	if(p_sll){2
		p_sll->list = p_sll->p_start->next;
		while(p_sll->list != NULL){
			if(p-5 >= 0){
				//pop the last value from temp array
				for(i=0 ;i<4  ; i++){
					temp[i]=temp[i+1];
				}
				//add the last value from our List to the temp array
 
				temp[4] = p_sll->list->value;
			}else{
				temp[p] = p_sll->list->value;
			}
			p_sll->list = p_sll->list->next;
			p++;
		}
		if(p-5>= 0){
			return temp[0];
		}else{
			//contains less than 5 elements
			return NULL;
		}	
	}else{
		return NULL;
	}
 
 
}

[Médinoc]

Ce que je disais principalement, c'est qu'au lieu de décaler toute la liste, tu peux juste te souvenir de là où tu écris et écrire par-dessus les éléments précédents.

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
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
#include <assert.h>
 
/* Cette fonction écrit dans le buffer de manière circulaire.
   Arrivée à la fin, elle repart de zéro. */
void write_to_buf(
 int *buf,   /*[out] Buffer dans lequel écrire*/
 size_t n,   /*[in] Taille du buffer*/
 size_t *pi, /*[in/out] Index d'écriture dans le buffer. Avant et après l'appel, il indique le prochain endroit où la fonction écrira. */
 int val     /*[in] Valeur à écrire. */
 )
{
	/* Lit l'index */
	size_t i = *pi;
	assert(i < n);
 
	/* Ecrit dans le buffer */
	buf[i] = val;
 
	/* Incrémente l'index */
	i++;
	if(i==n)
		i = 0;
	assert(i < n);
 
	/* Met à jour */
	*pi = i;
}
 
int sll_get_five_before_Last(sll_s const *pc_sll) {
	/* create temp table that will hold only the last 5 values
	   temp look like after 6 values that we have gone through; lets says the values from 1 to 6 
	   temp = {6,2,3,4,5}
	   when we go throw the 7th value of the list temp look like
	   temp = {6,7,3,4,5} */
	int temp[5] = {0, 0, 0, 0, 0};
	size_t i = 0;
	if(pc_sll) {
		/* Utiliser un pointeur local, 
		   cela permet au pointeur de liste d'être const */
		item_s const * pc_l = pc_sll->p_start->next;
 
		while(pc_l != NULL) {
			//add the last value from our List to the temp array
			write_to_buf(temp, 5, &i, pc_l->value);
 
			pc_l = pc_l->next;
		}
		/* Là, i est l'index du prochain endroit où la fonction aurait écrit.
		   Donc, l'index du plus vieux entier du buffer, celui que l'on veut. */
		return temp[i];
	} else {
		return 0; /* N'utiliser NULL que pour les pointeurs */
	}
}

[jhaythem]

Merci Médinoc et diogene!!!
cava prendre un peu plus de temps pour me recycler java m a appris la paresse

Cheers,

[jhaythem]

Si tu veux vraiment optimiser, il faudra faire de temp un buffer circulaire.

Mais commence par commenter ton code.

non tu n aime pas mes commentaires en anglais ?

[diogene]

Si tu dois chercher le 5° avant dernier (et non pas les 5 derniers), tu n'as pas besoin d'un tableau. Il suffit de faire avancer en synchrone dans la liste deux pointeurs "distants" de 5 éléments.

Quelque chose du genre (non testé)

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
<type de p_sll->list> sll_get_five_before_Last(sll_s *p_sll)
{
  <type de p_sll->list>  temp ;
  int p = 0;
  if(p_sll)
  {
     temp = p_sll->list = p_sll->p_start->next;
     while(p_sll->list != NULL)	
     {	
          p_sll->list = p_sll->list->next;
          if(p<5)p++; 
          else temp = temp->next;
      }
  }
  return p<5 ? NULL : temp;
}