Einfach Verkettete Liste von hinten durchlaufen!

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