Po pierwsze, nie rozumiem czemu zawsze robisz tak:
node *temp = new node;
temp = head;
gdyż jest to po prostu sztandarowy przykład wycieku pamięci. Alokujesz node na stercie i w kolejnej linijce zapominasz wskaźnik, przez co już tego node nie zwolnisz, bo go zapomniałeś. Jak już chcesz tego tempa czymś zainicjować to proponuje nieszkodliwy null_ptr czy tam NULL.
int i = 1;
...
i++;
if(i%m == 0)
Czemu zaczynasz od drugiego elementu w tak dziwny sposób? Czemu wgl zaczynasz od drugiego? Jeśli ktoś poda deleteM(1) to pominiesz pierwszy element.
if (current->data > sum / eli)
Dzielenie int przez int obcina końcówkę. Nie jest to porządane np w sytuacji 2 < 5/2 gdzie wyjdzie fałsz mimo ze to prawda.
while (current != NULL) {
if (current -> data > sum/eli) {
previous = current;
}
previous -> next = current -> next;
current = current -> next;
}
Prawdziwy błąd jest tutaj. Wyobraź sobie taką listę: 1,50,1,1,1,1,1,1,1,1. Wywołujemy deleteM(2). W drugim obiegu pętli ustawia wskaźnik previous na drugi element listy i już do samego końca nie wchodzi do ifa, więc przypisuje do drugiElementListy->next kolejne elementy. Tak do samego końca czyli NULLa. Więc efektywnie uciąłeś liste za drugim elementem.
No i nigdzie nie zwalniasz pamięci. Każdemu new musi odpowiadać delete (przynajmniej jeśli mówimy o surowych wskaźnikach). U Ciebie nie widziałem delete nigdzie. Ale to pewnie dlatego, że to wersja robocza.
Co do refaktoryzacji to nazwa zmiennej eli nic nie mówi. Wydaje mi się, że w nienaturalny sposób napisałeś tą pętlę:
while (current -> next != NULL) {
current = current -> next;
i++;
if (i%m == 0) {
eli++;
sum += current -> data;
}
}
Chodzi o to, że jako programiści wszyscy przywykliśmy do sekwencji iteracji z pętli for. Tzn: sprawdzasz warunek, jesli prawdziwy wykonujesz ciało i dopiero potem robisz i++, czy tam przesuwasz wskaźnik. U ciebie nie wiadomo czemu ten iterator jest zwiększany na samym poczatku. W ten sam sposób przesuwany jest current. Może akurat wskaźnik był przesuwany celowo na początku, bo przez to pomijałeś pierwszy element (celowo lub nie), ale miejsce i++ nie miało znaczenia. Tak czy siak wg mnie jest to niepotrzebne odstępstwo od standardu, do którego wszyscy przywykliśmy i który jest logiczniejszy.
Gdybyś faktycznie chciał pominąć pierwszy to trzeba było przed pętlą zrobić current = head->next i już, wszystko czytelne jak na dłoni - startujemy od drugiego elementu.
Co do samego rozwiązania - gratuluje, bo chyba był to najtrudniejszy algorytm na listach z jakim spotkałem się na tym forum :D. Tak ja widzę rozwiązanie
#include <iostream>
using namespace std;
struct node {
int data;
node *next;
};
class List {
private:
node * head, *tail;
double MthElementsAverage(int m) {
//przyjalem, ze elementy listy indeksujemy od 1
//bo nie bylo sprecyzowane
int i = 1;
int mthElementsCounter = 0;
int sum = 0;
node *current = head;
while (current != NULL) {
if (i%m == 0) {
mthElementsCounter++;
sum += current->data;
}
current = current->next;
i++;
}
return sum / (double)mthElementsCounter;
}
void deleteNext(node* toDeleteAfter) {
if (toDeleteAfter->next == NULL)
return;
else {
node* oneAfterDeleted = toDeleteAfter->next->next;
delete toDeleteAfter->next;
toDeleteAfter->next = oneAfterDeleted;
}
}
void deleteFromBeggining() {
node* oneAfterHead = head->next;
delete head;
head = oneAfterHead;
}
void deleteNodesGreaterThanThreshold(double threshold) {
if (head == NULL)
return;
node *current = head;
node *previous = NULL;
while (current != NULL) {
if (current->data > threshold) {
//przypadek usuwania z poczatku jest inny
//bo trzeba przestawic head
if (current == head) {
deleteFromBeggining();
current = head;
}
//przypadek gdy jestesmy gdzies w srodku listy
else {
//jesli weszlismy tu, to znaczy ze co najmniej jednego
//node minelismy, a to znaczy, ze previous jest ustawiony
//i nie jest nullem, wiec nie trzeba sprawdzac
deleteNext(previous);
current = previous->next;
}
}
else {
//zwykle przesuniecie
previous = current;
current = current->next;
}
}
}
public:
List() {
head = NULL;
tail = NULL;
}
void print() {
node *temp = new node;
temp = head;
while (temp != NULL) {
cout << temp->data << "\t";
temp = temp->next;
}
cout << endl;
}
void insertEnd(int value) {
node *temp = new node;
temp->data = value;
temp->next = NULL;
if (head == NULL) {
head = temp;
tail = temp;
}
else {
tail->next = temp;
tail = temp;
}
}
void deleteM(int m) {
deleteNodesGreaterThanThreshold(MthElementsAverage(m));
}
};
int main()
{
List l;
//test wielokrotnego usunięcia z poczatku
l.insertEnd(50);
l.insertEnd(50);
l.insertEnd(1);
//standardowy test usunięcia ze środka
l.insertEnd(50);
l.insertEnd(2);
l.insertEnd(3);
l.insertEnd(4);
//usunięcie kilku pod rzad ze srodka
l.insertEnd(50);
l.insertEnd(50);
l.insertEnd(5);
//usuniecie dwoch z konca
l.insertEnd(50);
l.insertEnd(50);
l.print();
l.deleteM(2);
l.print();
}
Przy okazji dodałem kolejny element refaktoryzacji, który do Twojego kodu też bym zastosował. Jest taki zbiór 5 zasad pisania solidnego kodu (SOLID) i pierwsza mówi, że funkcja powinna mieć jedną odpowiedzialność. Co generalnie w wielkim uproszczeniu streszcza się do robienia wielu małych funkcji. Co na tym zyskujemy: np
double average = MthElementsAverage(m)
i od razu wiemy czym jest average, gdyby nie było tu wywołania funkcji to osoba czytająca kod musiałaby przeanalizować pętlę i sama dojść do tego, że pierwsza połowa metody deleteM liczy średnią, a tak to ma ten kawałek kodu nazwany w postaci funkcji i kod jest o wiele czytelniejszy. Zauważ, że metody pomocnicze zrobiłem prywatne. Robi się tak, żeby na zewnątrz klasa pozostała taka sama - tzn żeby jej zestaw publicznych metod (interfejs) się nie zmienił, gdyż poszatkowanie funkcjonalności której od klasy wymagamy na zewnątrz jest jej szczegółem implementacyjnym.
