[Optimisation] singly linked list one pass

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 :oops: .

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 :oops:

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

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,

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

Mais commence par commenter ton code.

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:

---

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; }     }

---

Citation:

---

Envoyé par Médinoc

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 :cry:?

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:

---

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; }

---

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:

---

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 */ } }

---

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

Cheers,