desperacka próba posortowania elementów we własnej implementacji listy

Question

hej, temat pytania dużo mówi o problemie .Stworzyłem własną (co najlepsze działającą) implementacje listy w C++ .

Dodawanie ,usuwanie i pokazywanie elementów listy działa jak najbardziej ok ,teraz stwierdziłem że dodam jeszcze możliwość posortowania naszej struktury danych ,wykorzystałem do tego Bubble sort ponieważ ten algorytm jest bardzo prosty i najbardziej nadaje się dla początkujących do posortowania czegoś innego niż zwykła tablica . Algorytm nie działa pod tym względem że wykonuje się wiecznie :/ .Będę bardzo wdzięczny za pomoc ,pod spodem podam kod funkcji "sortującej" oraz całego programu (na wszelki wypadek) 

*wiem ,program napisany po polsku to zło ... ale to moja pierwsza jeszcze nie doskonała implementacja listy i pisząc po polsku było łatwiej mi się skupić i przeanalizować kod po chwili przerwy

funkcja sortująca:

//to jest sortowanie babelkowe na start bo najprostsze (jak to ogarne to dam quicksort ,lub mergesort)
void sort(lista *&pierwszy_element) { //dostajemy wskaznik na pierwszy element 
	lista *iterator = pierwszy_element; //okresla ile razy mamy powtarzac petle zewnetrzna jak to jest w tym algorytmie sortowania 
	lista *temp = pierwszy_element->nastepna; //zaczynamy od pierwszego elementu+1 (jakas symulacja tego jak sortujemy na normalnych tablicach)
	lista *bufor; //bufor do zamiany tablic

	while (iterator) { //powtarzamy wszystyko dla iloscy elementow 
		while (temp) { //powtarzamy dla temp zavczynajacego sie od 2 elementu (nie 1 bo numerujemy wlasnie od jedyni a nie od zera)
			if ((temp->poprzednia) > (temp)) { //jezeli wczesniejszy element bedzie wiekszy od tego obecnego to zamienamy : 
				bufor = temp; //biezocy element trafia do bufora 
				temp = temp->poprzednia; //zamiana 
				temp->poprzednia = bufor; //odcytanie z bufora 
			}

			temp = pierwszy_element->nastepna;
		}
	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

Cały program :

#include "stdafx.h" //NAPISANE POD VS ,biblioteki są w tym pliku 

using namespace std;

struct lista {
	int dane;
	lista *nastepna = nullptr;
	lista *poprzednia = nullptr;
};

void usun_poczatek(lista *&pierwszy_element) {
	lista *deleteBufor = pierwszy_element;
	pierwszy_element = pierwszy_element->nastepna;
	pierwszy_element->poprzednia = nullptr;
	delete deleteBufor;
}

void usun_koniec(lista *&ostatni_element) {
	lista *deleteBufor = ostatni_element;
	ostatni_element = ostatni_element->poprzednia;
	ostatni_element->nastepna = nullptr;
	delete deleteBufor;
}

void usun_wybrany_element(lista *&pierwszy_element, lista *&ostatni_element, int number) {
	int i = 1;
	lista *temp = pierwszy_element;

	do {
		if ((i < number) && (temp->nastepna)) { i++;  temp = temp->nastepna; }
		else if ((i < number) && (!temp->nastepna)) { cout << "error!" << endl;  break; }
		else if (i <= number) { break;  }
	} while (true);

	if (temp == pierwszy_element) {
		lista *deleteBufor = pierwszy_element;
		pierwszy_element = pierwszy_element->nastepna;
		pierwszy_element->poprzednia = nullptr;
		delete deleteBufor;
	}
	else if (temp == ostatni_element) {
		lista *deleteBufor = ostatni_element;
		ostatni_element = ostatni_element->poprzednia;
		ostatni_element->nastepna = nullptr;
		delete deleteBufor;
	}
	else {
		lista *deleteBufor = temp;
		temp = temp->poprzednia;
		temp->nastepna = temp->nastepna->nastepna;
		temp = temp->nastepna->nastepna;
		temp->poprzednia = temp->poprzednia->poprzednia;
		delete deleteBufor;
	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////

void dodaj_na_poczatek(lista *&pierwszy_element, lista *&ostatni_element, int wartosc) {

	lista *nowy_element = new lista;
	nowy_element->dane = wartosc;

	if (!pierwszy_element) {
		nowy_element->nastepna = nowy_element->poprzednia = nullptr;
		pierwszy_element = ostatni_element = nowy_element;
	}
	else {
		nowy_element->nastepna = pierwszy_element; //biezaczy pierwszy eleemnt 
		nowy_element->poprzednia = nullptr; //nic jeszcze nie ma prze nia 
		pierwszy_element->poprzednia = nowy_element; //biuezacy pierwszy eleemnt 
		pierwszy_element = nowy_element; //staje sie on pierwszym pierwszym elementem listy 
	}
}

void dodaj_na_koniec(lista *&ostatni_element, lista *&pierwszy_element, int wartosc) {

	lista *nowy_element = new lista;
	nowy_element->dane = wartosc;

	if (!pierwszy_element) {
		nowy_element->nastepna = nowy_element->poprzednia = nullptr;
		pierwszy_element = ostatni_element = nowy_element;
	}
	else {
		nowy_element->nastepna = nullptr;
		nowy_element->poprzednia = ostatni_element;
		ostatni_element->nastepna = nowy_element;
		ostatni_element = nowy_element;
	}
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////

void pokaz_cala_lista(lista *pierwszy_element) {

	lista *temp = pierwszy_element;

	while (temp) {
		cout << temp->dane << " ";
		temp = temp->nastepna;
	}
}

int pracuj_na_numerze_listy(lista *pierwswzy_element, int number) {
	int i = 1;
	lista *temp = pierwswzy_element;

	do {
		if ((i < number)&&(temp->nastepna)) { i++;  temp = temp->nastepna; } //jezeli jwszcze nie doszlismy do wyznaczonego numeru i sa nastepne szufladki struktory to szukaj dalej 
		else if ((i < number) && (!temp->nastepna)) { return 0; break; } //jezeli jeszcze nie dotarlismy do konca a szufladki sie skonczyly to blad i zwracamy 0
		else if (i <= number) { return temp->dane; break; } //jezeli dotarlismy do konca to zwracamy dane 
	} while (true);
}

//////////////////////////////////////////////////////////////////////////////////////////////////////////

//to jest sortowanie babelkowe na start bo najprostsze (jak to ogarne to dam quicksort ,lub mergesort)
void sort(lista *&pierwszy_element) { //dostajemy wskaznik na pierwszy element 
	lista *iterator = pierwszy_element; //okresla ile razy mamy powtarzac petle zewnetrzna jak to jest w tym algorytmie sortowania 
	lista *temp = pierwszy_element->nastepna; //zaczynamy od pierwszego elementu+1 (jakas symulacja tego jak sortujemy na normalnych tablicach)
	lista *bufor; //bufor do zamiany tablic

	while (iterator) { //powtarzamy wszystyko dla iloscy elementow 
		while (temp) { //powtarzamy dla temp zavczynajacego sie od 2 elementu (nie 1 bo numerujemy wlasnie od jedyni a nie od zera)
			if ((temp->poprzednia) > (temp)) { //jezeli wczesniejszy element bedzie wiekszy od tego obecnego to zamienamy : 
				bufor = temp; //biezocy element trafia do bufora 
				temp = temp->poprzednia; //zamiana 
				temp->poprzednia = bufor; //odcytanie z bufora 
			}

			temp = pierwszy_element->nastepna;
		}
	}
}

///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

int main()
{
	lista *pierwszy_element = nullptr;
	lista *ostatni_element = nullptr;
	dodaj_na_poczatek(pierwszy_element, ostatni_element, 10);
	dodaj_na_poczatek(pierwszy_element, ostatni_element, 134);
	dodaj_na_poczatek(pierwszy_element, ostatni_element, 98);
	dodaj_na_poczatek(pierwszy_element, ostatni_element, 956);
	dodaj_na_poczatek(pierwszy_element, ostatni_element, 9);
	dodaj_na_poczatek(pierwszy_element, ostatni_element, 74);
	dodaj_na_poczatek(pierwszy_element, ostatni_element, 908);

	pokaz_cala_lista(pierwszy_element);
	cout << endl;

	sort(pierwszy_element);

	pokaz_cala_lista(pierwszy_element);
	cout << endl;

	_getch();
	return 0;
}

 

Answer 1

Unknown ma rację, tylko że pominął jeszcze jedną istotną rzecz, mianowicie ty zamieniasz (o zgrozo) miejscami wskaźniki! I to prawdopodobnie jest powód nieskończonej pętli. Zamieniaj miejscami wartości nie wskaźniki.

Comments

dzięki za pomoc ;) ,ale dalej nie działa (ten sam problem co przedtem) . Oto kod:

void sort(lista *&pierwszy_element) { 
	lista *iterator = pierwszy_element; 
	lista *temp = pierwszy_element->nastepna;
	int bufor; 

	while (iterator) { 
		while (temp) { 
			if ((temp->poprzednia->dane) > (temp->dane)) {
				bufor = temp->dane; 
				temp->dane = temp->poprzednia->dane; 
				temp->poprzednia->dane = bufor; 
			}

			temp = pierwszy_element->nastepna;
		}
	}
}

dokonałem kilku zamian ,jak mi sprawia tyle problemów posortowanie listy buble sort-em to ja się boje co będzie z Merge sort...

---

Pierwsza pętla while (iterator) będzie zawsze spełniona więc pętla się nigdy nie skończy bo nigdy iteratora nie modyfikujesz (musiałby w pewnym momencie mieć wartość ustawioną na NULL). W takim układzie jak tu masz z wskaźnikami będzie ci ciężko to poprawnie obsłużyć. Może lepiej by było dodać metodę, która zwróci ci liczbę elementów w twojej tablicy i tyle razy robić przejścia sortowania, ale to nie będzie optymalne rozwiązanie.

---

dzięki za długą cierpliwość i ciągłą pomoc  ,sorry że dawałem masę komentarzy a potem je ukrywałem ale co chwilę znajdywałem nowe błędy i je rozwiązywałem ;) Teraz już ostatecznie sortowanie działa . Musiałem dokonać masę zmian i się dziwie czemu ja byłem taki głupi że wcześniej nie wpadłem na dokonanie tych poprawek ... . Gotowy kod sortowania wygląda tak:

void sort(lista *pierwszy_element) { //znak & chyba nie jest potrzeby bo tylko zminiamy wartosci a nie dodajemy ani nie suswamy zadnych elementow 
	lista *iterator = pierwszy_element;
	lista *temp = pierwszy_element->nastepna;
	int bufor;

	while (iterator) { //sprawdzenie stanu iteratora (w ten sposob petle zwnetrzna *wykona się dla iloscie elementów w liscie*) -czyli tyle razy 
		while (temp) { //pojedyncze przejscie przez liste i dokonanie zamian
			if ((temp->poprzednia->dane) > (temp->dane)) { //zamiany wartosci 
				bufor = temp->dane;
				temp->dane = temp->poprzednia->dane;
				temp->poprzednia->dane = bufor;
			}
			temp = temp->nastepna; //petla wewnetrza tez porusza sie do przosu (coś w rodzju j++)
		}
		temp = pierwszy_element->nastepna; //z powrotem ustawiamy temp na element poczatek listy+1
		iterator = iterator->nastepna; //przesuniecie iteratora do przodu (to co wczesniej nie dopatrzylem)
	}
}

użycie sortowania na liście jest dosyć trudne ,wpadłem na pomysł by zamiast stosować potem algorytmy sortowania szybkiego to użyć drzewa poszukiwań binarnych by wykorzystać procedurę przejścia przez drzewo ( inOrder ), co o tym sądzisz ? 

Jeszcze raz za wszystko dziękuje i pozdrawiam ,dziękuje też z pomoc użytkownikowi unknown ale obu nie mogę dać naj :( 

Answer 2

Tak na szybko: porównujesz adresy a nie wartości.

Comments

Dzięki za ważna wskazówkę ,teraz straciłem dostęp do komputera więc sprawdzę jutro czy będzie działać wszystko ok ,jak wyjdzie lub nie to dam znać

---

znalazłem jednak jeszcze trochę czasu ,zmieniłem warunek w pętli na coś takiego :

if ((temp->poprzednia->dane) > (temp->dane))

jednak dalej pozostaje ten sam problem co wcześniej (aczkolwiek myślę że jestem bliżej poprawnego rozwiązania)