rekursive Funktion - Gestaltungsprobleme

The architect 0

Guten Abend liebe C++ Freunde,

Ich habe eine Schwierigkeit beim erstellen der folgenden rekursiven Funktion (ordnen), wäre nett wenn ihr mir dabei etwas helfen könntet.

typedef struct element_sammlung * sammlung ;
typedef struct element_sammlung {
							int			wert ;
							sammlung	naechste ;
} element_sammlung ;

Fragt mich nicht warum die Struktur so definiert wurde, für Anfänger soll das wohl so einfacher sein. (laut Professor)

//Rekursive Funktion
Ziel der Funktion "ordnen" ist es eine bestehende Sammlung (in Form einer Liste mit dynamisch allokierten Elementen.) aufsteigend zu ordnen. Dabei muss nicht betrachtet werden ob die Zahl mehrmals vorkommt denn das Elimieren mehrfacher gleicher Zahlen übernimmt später eine andere Funktion.

Kurzes Beispiel:

Gegeben: A = { 2 3 5 1 1}

ordnen (A);

A = {1 1 2 3 5}

void ordnen (sammlung& S)
{

	if(S!=NULL)
		{
			sammlung temp = erstelle_leer();
			// Ich muss eine Temporäre Sammlung erstellen um einfuegen anwenden zu können,
			// aber das klappt mit der rekursivität dann nicht mehr.
			// Wie kann ich es anders machen?

			einfuegen(S->Wert,temp);
			ordnen(S->naechste);
			loeschen(S);
			S=temp;	
		}
	else
	{}
}

**Fals die Unterfunktion einfuegen und loeschen benötigt werden, kann ich diese auch noch gerne posten.
**
Beschreibung der beiden Funktionen (einfuegen und loeschen).

einfuegen: Fügt ein neues Element in die Liste an richtiger Stelle ein, richtige Stelle -> in geordneter Reihenfolge.

loeschen: Gibt dynamischen Speicherplatz des verwendeten Elements frei.

Vielen Dank für eure Hilfe

Und seiet nachsichtig mit mir Ich lerne noch.

Die Funktion zum Ordnen kannst du eigentlich recht einfach programmieren. Dazu probierst du der Einfachheit halber einfach mal den Bubblesort-Algorithmus aus.

Der ist nicht sehr schnell, aber sollte ausreichen, denke ich. Du musst ihn eben nur auf dein Problem anwenden und deine Elemente durch löschen und einfügen tauschen bzw. die Zeiger tauschen.

http://de.wikipedia.org/wiki/Bubblesort

Achso... Muss es denn rekursiv sein? Wenn nicht, machs mit Bubblesort.

The architect 0

Ja es muss rekursiv sein, denke iterativ wäre für mich kein Problem.

Also wenn du es mit dem Bubblesort-Algorithmus machst, brauchst du im Prinzip nichts löschen sondern kannst einfach die Werte/Zeiger austauschen.

Du kannst ja mal deinen kompletten Source hereinstellen, dann würde sich sicherlich noch eher jeman dazu bereit erklären, dir zu helfen

The architect 0

Ich habe das nun mal mit dem Bubblesort Algo probiert,

Das ist von Algo-Wiki:

void swap(int& a, int& b)
{
	int z=a;
	a=b;
	b=z;
}

int main()
{
	int size;
	cout<<"Wie viele Elemente wollen sie eingeben?"<<endl;
	cin>>size;
	int* arr=new int[size];

	for(int i=0; i<size; i++)
	{
		cout<<">";
		cin>>arr[i];
	}

	cout<<"\n\nBeginne Ausgabe\n\n"<<endl;

	for(int i=0; i < size; i++)
	{
		for(int j=1; j < size-i; j++)
			if(arr[j] > arr[j-1])
				swap(arr[j], arr[j-1]);
	}

	for(int i=0; i<size; i++) cout<<i<<endl;  //Ausgeben

	return 0;
}

Meine Anpassung:

void change(sammlung& A, sammlung& B){

	sammlung tempo=A;
	tempo->naechste=A->naechste;	
	A=B;
	A->naechste = B->naechste;
	B=tempo;
}

void sortieren (sammlung& C)
{
//iterativ
sammlung laeufer_C_1 = C;
sammlung laeufer_C_2 = C;

	while(laeufer_C_1!=NULL){
		while(laeufer_C_2->naechste!=NULL){

			if(laeufer_C_1->wert < laeufer_C_2->naechste->wert)
				change(laeufer_C_1, laeufer_C_2->naechste);

			laeufer_C_2=laeufer_C_2->naechste;
		}
		laeufer_C_1=laeufer_C_1->naechste;
	}
}

Leider funktioniert meine Anpassung nicht richtig.
Ich konnte diese if Bedingung nicht umsetzen,

if(arr[j] > arr[j-1])
				swap(arr[j], arr[j-1]);

Weil ich verwende bei meiner Sammlung, eine dynamische Allokierung, deshalb kann ich nicht sagen welches Element vor einem anderen Element liegt.
Auf die Gefahr hin das nun jemand sagt, kein Prob.. mach noch einen Zeiger auf das vorherige Element in die Struktur. Das könnte ich machen, aber laut Aufgabenstellung nicht erlaubt.

Wie könnte ich das Problem lösen?

Desweiteren, wie realisiert man den Bubblesort rekursiv? Weil ich will/muss das Rekursiv machen.

Ich schätze man kann Bubblesort nur indirekt Rekursiv machen:

bool bsort(Element *root)
{
	Element *ptr = root;

	while (ptr->next)
	{
		if (ptr->value < ptr->next->value)
		{
			std::swap(ptr->value, ptr->next->value);

			return true;
		}

		ptr = ptr->next;
	}

	return false;
}

void sort(Element *root)
{
	Element *ptr = root;

	if (bsort(root))
	{
		sort(root);
	}
}

Ich depp... Dabei liegt die Lösung vor den Füßen. Rekursiv:

void bsort(Element *root)
{
	Element *ptr = root;

	while (ptr->next)
	{
		if (ptr->value < ptr->next->value)
		{
			std::swap(ptr->value, ptr->next->value);

			bsort(root);
		}

		ptr = ptr->next;
	}
}

Rekursiv. Et Voilà.

Auf die While-Schleife wirst du wohl nicht verzichten können. Ich habs ohne versucht, aber das geht nur bei sehr(!) kleinen Listen:

void bsort_r(Element *root, Element *pos)
{
	if (pos && pos->next)
	{
		if (pos->value < pos->next->value)
		{
			std::swap(pos->value, pos->next->value);

			bsort_r(root, root);
		}
		else
		{
			bsort_r(root, pos->next);
		}
	}
}