Usuwanie duplikatów - Lista jednokierunkowa

Question

Cześć

Napisałem taki oto kod, którego zadaniem jest usunięcie duplikatów z listy jednokierunkowej. Niestety otrzymuję błąd "naruszenie dostępu do odczytu". Co w tym kodzie jest nie tak i gdzie powinienem szukać błędu gdy ta sytuacja powtórzy się w przyszłości, w innych programach.

struct lista {
	int dane;
	lista* nastepny;
};

void duplikaty(lista*& head) {
	for (lista* i = head; i != NULL; i = i->nastepny) {
		lista* poprzedni = i;
		for (lista* j = i->nastepny; j != NULL; j = j->nastepny) {
			if (i->dane == j->dane) {
				poprzedni->nastepny = j->nastepny;
				lista* tmp = j;
				delete tmp;
			}
			else poprzedni = j;
		}
		
	}
}

 

Comments

Pytania pomocnicze: A masz w ogóle jakiś pomysł jak pozbyć się duplikatów? Chcesz sortować elementy na liście? Czy w jakiś inny sposób?

Zamieniłbym nazwę lista na węzeł :)

Zrób sobie funkcje dodaj_element(), usun_element(), itd. itd.  Łatwiej będzie pracować na liście.

---

Trzymam pierwszy element listy (element bieżący) i potem sprawdzam po całej liście czy ten element ma jakieś duplikaty jeśli tak to usuwam duplikat i kontynuuje przeglądanie aż do końca listy potem zmieniam element bieżący o jeden itd...

---

@reaktywny, Przepraszam bardzo ale nie pytam oto jak poprawić estetykę kodu, jak nazwać węzły itp. Chce się dowiedzieć jak poprawić błąd programu...

---

Musisz pamiętać. że nieco inaczej kasujesz element z końca, z środka i z początku listy. U ciebie oczywiście odpada przypadek kasowania pierwszego elementu. Po skasowaniu jednego elementu lista musi pozostać prawidłowo funkcjonującą listą.

Answer 1

Spójrz na linie 12 i 13 - w sumie kasujesz element wskazywany przez j, a zaraz w ramach pętli wykonujesz j=j->następny.

Answer 2

Trzymam pierwszy element listy (element bieżący) i potem sprawdzam po całej liście czy ten element ma jakieś duplikaty jeśli tak to usuwam duplikat i kontynuuje przeglądanie aż do końca listy potem zmieniam element bieżący o jeden itd...

Kod wydaje się próbować usuwać duplikaty, ale jego działanie nie zawsze będzie poprawnie  W momencie usunięcia j-tego elementu, nie powinieneś przesuwać poprzedni na j, ponieważ teraz poprzedni i j wskazują na ten sam element, co może prowadzić do problemów.

Co ważne w takim podejściu twój kod nie uwzględnia usuwania duplikatów z pierwszego elementu, druga sprawa kod ma złożoność czasową O(n^2), co może być kosztowne dla dłuższych list.
Kolejna sprawa, że poo usunięciu elementu z listy, tworzysz tymczasowy wskaźnik tmp, ale nadal używasz wskaźników do elementów, które zostały już usunięte

Zakładając liste np. : 
 

1 -> 1 -> 2 -> 2 -> 3