Einfach Verkettete Liste von hinten durchlaufen!

[Thes-One]

Dann bleibt A bei der 1 und B geht weiter runter!
Ja werde mir das gleich mal anschauen nur leider ist eine einfach verkettete Liste vorgegeben!

[mit list und tücke]

Thes-One schrieb:

Dann bleit A bei der 1 und geht weiter runter!

wohin? 1 ist doch das erste element.

[Vorden]

wie wärs, wenn du einfach first und last umdefinierst und damit first last ist und last first

*duck*

ok, blöde Antwort, aber ohne die Rekursion hast eigentlich keine Chance

[Thes-One]

Ich will es ja mit der Rekursion machen doch das Problem ist doch kalr oder???
Ich muss in zwei listen bis an das letzte Element absteigen und dann Element für Element in beiden Listen bis zum Anfang hochsteigen!
Das ist das Problem!
Ich bekomme das einfach nicht hin!

[supertux]

Das Problem ist weder klar noch kalr

Guck dir die Rekursion genauer an, da steht es ja. Aber wir können nicht hellsehen und deinen Code bzw. was du versucht hast, kennen wir nicht, also können wir nur raten, was du falsch machst. Hilf uns dir zu helfen

[Thes-One]

Ja würd ich an deiner Stelle mal die vorherigen Posts lesen!
Das Problem ist das ich zwei Listen in einer Funktion bearbeiten muss und zwar von hinten!
Und nochmal:
Wenn ich eine Menge A und B haben mit den folgenden Elementen!
A->(1,2,3)
B->(1,2,3,4)

Muss ich in der Funktion zu erst die beiden Listen bis zum Ende durchlaufen, dann will ich die beiden Elemente vergleichen und dann eine Operation durchführen!

Wenn ich es aber so mache wie schon gesagt wurde , läuft als erstes die Liste B zurück zum ersten Element und dann A und genau das will ich nicht!

Ich will das beide Parallel laufen!

Soll heißen ich will 4 mit 3 , 3 mit 2 und 2 mit 1 und 1 mit 1 vergleichen,(bis halt beide Listen wieder am Anfang sind)

Jetzt verstanden?????

[list but not least]

Thes-One schrieb:

Soll heißen ich will 4 mit 3 , 3 mit 2 und 2 mit 1 und 1 mit 1 vergleichen,(bis halt beide Listen wieder am Anfang sind)

dann dupliziere in der kürzeren liste das erste element so lange, bis sie so viele elemente hat wie die lange liste (immer vorn anhängen) und dann nimm z.b. diese rekursive funktion da ^^

[supertux]

Thes-One schrieb:

Ja würd ich an deiner Stelle mal die vorherigen Posts lesen!

*ich* hab alle Post gelesen, sogar welche geschrieben, nur du kannst dich nicht so gut ausdrucken, das ist aber ein anderes Problem.

Dass du die Liste paralell durchlaufen willst, ist uns schon klar, es gab sogar eine Antwort darauf, die Antwort von "kobold der 5. dimension" (Antwort Nummer 6).

Thes-One schrieb:

Soll heißen ich will 4 mit 3 , 3 mit 2 und 2 mit 1 und 1 mit 1 vergleichen,(bis halt beide Listen wieder am Anfang sind)

1 mit 1? Wieso soll 1 mit 1 verglichen werden? Wenn die eine Liste weniger Elemente enthält als die andere, dann wird immer passieren, dass eine Liste fertig ist, während die andere noch Elemente hat.

Du sagst "Ich bekomme das einfach nicht hin!" und ich sagte, dass wir auch keine Ahnung haben, warum du es nicht schaffst, und zwar weil wir keine Ahnung haben, was *du* bereits versucht hast. Wie sieht deinen Code aus? Vielleicht liegt der Fehler an einer anderen Baustelle und du hast es nicht bemerkt. Also poste deinen Code bzw. was du bereits versucht hast. Fertige Lösungen kannst du von uns weder erwarten noch verlangen, außer du bist bereit Geld dafür zu zahlen.

Thes-One schrieb:

Jetzt verstanden?????

ja, dass deine ?-Taste klemmt.

[forschlag]

dann machs do so dass wenn du in der kuerzeren liste beim ersten element angelangt bis,
du einfach mit diesem die rekursion wieder aufrufst bis auch die 2. liste beim
ersten element angekommen bist.

also hier jetzt fuer eine liste:

void show_reverse (struct list *l)
{
    if (l->next)
        show_reverse (l->next);
    else
        show_reverse (l);
    printf ("%d\n", l->wert);
}

[Thes-One]

Ok dann werde ich euch jetzt mal schreiben was genau mein Problem ist mit Beispiel!

Also ich habe zwei Funktionen bei denen ich Probleme habe, vielleicht löst sich das zweite Problem aber von selbst wenn ich weiß woran das erste liegt!!!

Also, wir machen Mengenoperationen die wir intern in Listen darstellen!
Eine Menge ist eine Liste!

Nun muss ich eine Funktion schreiben die eine Invertierte Menge erstellt, also alle Elemente enthält die nicht in der Menge enthalten sind!
Dazu wurde vorher ein Wert festgelegt, was das Maximale Element in der Menge sein darf.
Das ist die 150!

Nun will ich das ganze Rekursiv und von hinten durchlaufen lassen, da man dann das Element einfach am Anfang anfügen kann und nicht erst die Liste durchlaufen und dann einfuegen.
So hat man dann gleich eine sortiere Invertierte Liste!

Das ist mein bissheriger code.....

->head(Alt) == Alt->Wert;
->cons(Element,Neu) == Wird ein Element vorne angefügt
->Maximum == 150, muss aber runter gezählt werden!

Liste InvertierteMenge(Liste Neu,Liste Alt, int Maximum){

	if (Alt->next)
		InvertierteMenge(Neu,Alt->next,Maximum);

	if (Maximum > head(Alt)))
		Neu = cons(Maximum,Neu);

	InvertierteMenge(Neu,Alt,--Maximum);
}

Das Problem ist das das soo garnicht klappt und es kommt ein Stack Overflow error!
Ich hoffe ihr habt verstanden was da jetzt das Problem ist(???)

[make list not war]

du hast die seltene begabung, einen sachverhalt total wirr rüberzubringen
zeig doch mal den *kompletten* code, einschliesslich der listenverwaltung...

[Thes-One]

Das gibt es nicht!

So jetzt kurz und knapp!

"Ich will eine Liste(A) mit den Werten zwischen 150 und 0 die nicht in einer Liste(B) enthalten sind füllen"!
Das ganze möchte ich Rekursiv und von hinten durchlaufend haben!
Da ja das hinterste Element in einer meiner Listen das größte Element ist!

PS: Ich kann hier nicht meinen kompletten Code reinstellen da es ein Schulprojekt ist(evntl. EMAIL)!

[Daniel E.]

Also, ich hab dein Problem immer noch nicht so ganz verstanden, aber welche weiteren Listenoperationen hast Du denn noch zur Verfügung? Sind die Listen immer sortiert?

Ich würde eine Komplementärmenge M = A\B so hinschreiben, wenn A und B als sortierte Listen vorliegen:

struct list *complement(const struct list *a, const struct list *b) {
    struct list *m = newlist();

    struct list *p = m;

    while (! endof(a)) {
        if (endof(b) || b->key > a->key) { p = insert(a->key, p); p = next(p); a = next(a); }
        else if (b->key < a->key) b = next(b); 
        else { b = next(b); a = next(a); } /* Das ist der Fall: a->key == b->key */
    }

    return m;
}

Das ist jetzt so ungetestet hingeschmiert, aber eigentlich eine ziemlich direkte Kopie der Vorgehensweise, wie ich's auch auf dem Papier machen würde. Und das Inverse einer Menge ist doch auch nichts anderes als eine geschickt gewählte Menge A. Programmiertechnisch kannst Du das Beispiel von oben einfach anders hinschreiben, nämlich ohne die Liste A sondern mit einem Zähler.

Bei deiner Rekursion fehlt übrigens irgendwie die Abbruchbedingung, von daher ist es kein Wunder, daß dir das Teil durch die Decke geht.

[Thes-One]

Ohhh man!
Ich bin euch ja sehr dankbar für eure Hilfe aber ich will nicht die Komplementärmenge bilden sondern das Inverse!

Wenn A = (1,2,3,4)

Und das Maximale Element bei mir 150 ist!

dann ist das Inverse von A

A = (0,5,6,7,8,9,10,11,12,13,.......,150)!

Alle Element die in A nicht enthalten sind!

[Daniel E.]

Pardon, ich verstehe den Unterschied zwischen Komplementmenge und inverser Menge in dem Zusammenhang nicht wirklich.

Du hast also "Grundmenge" M, die alle natürlichen Zahlen <= 150 enthält. Wenn Du das Komplement M \ A berechnest, dann kommst Du genau auf deine Menge A^-1. Die Schnittmenge von A^-1 und A ist leer, die Vereinigungsmenge ist M und M \ A^-1 ist wieder A. Was willst Du eigentlich noch?

Da die Struktur der Menge M aber so wahnsinnig einfach ist, brauchst Du dafür keine eigene Liste zu erzeugen, sondern kannst sie in meinem Algorithmus quasi eins zu eins durch eine Zählvariable ersetzen.

[supertux]

@Thes-One: moment mal, bring dich selber nicht durcheinander. Eine Komplementmenge K von A kann man nur dann berechnen, wenn es eine Grundmenge M gibt, so dass A Teilmenge von M ist. Die Inversmenge (so wie du sie beschreibst, hab aber noch nie von einer Inversmenge gehört) ist nämlich die Komplementmenge. Wirf nicht einfach so Grundbegriffen in die Gegend, wenn du sie nicht korrekt einsetzt.

Wenn deine Grundmenge M = {1, 2, 3, ..., 150}, dann benötigst du keine Liste. Ein Int-Array mit 151 Elementen genügt, wobei das erste Element die Anzahl der Elemente der Menge speichert. Das i+1. Element des Arrays speichert das i. Element der Menge.

[Luk3]

Hallo!
ich stehe vor eigentlich genau dem gleichen Problem!

ich habe das hier mal soweit durchgelesen und bei mir funktioniert das ganze nur bis zu einem bestimmten punkt!
also ich habe eine Grundmenge:
{1,2,3,4,5,6,7,8,9,10}
die nur als integer wert dargestelt ist

int Element = 10;

und eine Menge die als Liste implementiert ist mit der gleichen Struktur wie Thes-One.
die zweite Menge ist bei mir: {1,2,5,8}

jetzt mache ich es so:

List get_invert(Set Ergebnis, Set A, int Element){  //<--- 10 zu anfang
	if (l_rest(A) != NULL) // l_rest liefert immer die liste ohne das erste Element
		get_invert(Ergebnis,l_rest(A),Element);
	if (Element > l_kopf(A))  //l_kopf liefert das erste Element ohne den rest
		Ergebnis = l_add(Element,Ergebnis); // l_add hängt fügt ein Element in die liste ein 
	get_invert(Ergebnis,A,--Element);

	return Ergebnis;	
}

So, die liste wird also von hinten durchlaufen und prüft immer ob das aktuelle Element größer ist als das aktuelle Element in der Liste A,
wenn ja dann soll das Element in die Ergebnisliste geschrieben werden.
das geht auch aber nur so lange das Aktuelle Element größer ist, sobald dieses kleiner oder gleich dem Element der Liste ist kann das ja nicht mehr funktionieren, da ich in der Liste ja nicht weiter absteige, aber wie mache ich das?
denn so wird ja das Element immer dekrementiert und ist dann ja immer kleiner als das Listenelement wenn da nicht weiter absteigt, somit gibts ne endlosschleife, bzw irgendwann einen Stack overflow...

kann mir da jemand helfen?
MFG
Luke