Doppelt verkettete Liste in C

[CyborgBeta]

Also ich hab auch noch mal etwas dran “rumgepfuscht”:

void addNode(int val) {
	struct node * node = (struct node *) malloc(sizeof(struct node));
	node->next = NULL;
	node->prev = NULL;
	node->val = val;

	if (start == NULL) {
		start = node;
		end = node;
	} else {
		struct node * tmp = start;
		while (tmp->next != NULL) {
			tmp = tmp->next;
		}

		tmp->next = node;
		node->prev = tmp;
		end = node;
	}
}

void printList(void) {
	struct node * tmp = start;
	while (tmp != NULL) {
		printf("der Wert des Knotens lautet %d
", tmp->val);
		tmp = tmp->next;
	}
	printf("
");
	tmp = end;
	while (tmp != NULL) {
		printf("der Wert des Knotens lautet %d
", tmp->val);
		tmp = tmp->prev;
	}
	printf("
");
}

void clearList(void) {
	struct node * tmp = start;
	while (tmp != NULL) {
		struct node * tmp2 = tmp->next;
		free(tmp);
		tmp = NULL;
		tmp = tmp2;
	}

	start = NULL;
	end = NULL;
}

struct node * mid0(struct node * n1, struct node * n2) {
	while (n1 != n2) {
		n1 = n1->next;
		if (n1 != n2) {
			n2 = n2->prev;
		}
	}
	printf("%p
", (void *) n1);
	printf("lautet %d
", n1->val);
	return n1;
}

void ms1(struct node * n1, struct node * n2);

void ms1(struct node * n1, struct node * n2) {
	struct node * mid2 = mid0(n1, n2);
	struct node * mid1 = mid2->prev;
	if (n1 == n2) {
		return;
	}
	if (n1 == mid1 || n2 == mid2) {
		return;
	}
	ms1(n1, mid1);
	ms1(mid2, n2);
	/* swappen, n1 bis mid1  mit  mid2 bis n2 */
}

void ms0(void) {
	ms1(start, end);
}

int main(int argc, char ** argv) {
	int i = 11;

	printList();

	for (; i < 23; i++) {
		addNode(i);
	}

	printList();

	clearList();

	printList();

	addNode(111);
	addNode(222);
	addNode(333);
 	addNode(444);
	ms0();

	printList();

	return EXIT_SUCCESS;
}

/* swappen, n1 bis mid1 mit mid2 bis n2 */ an dieser Stelle hab ich jetzt das Problem, das wenn ich swappe, Pointer auf n1, n2, mid1 und mid2 nicht mehr stimmen.

[mogel]

@bisaflor

okay, was ich aber nicht verstehe, wenn der Speicher nach Programmende eh freigegeben wird. Brauch ich ja quasi auch keine Funktion clearList() aufrufen, weil Sie ja kurz vor Programmende läuft und der Speicher ja kurze Zeit später sowieso vom BS freigegeben würde oder?

:scheiterhaufen: IMMER RICHTIG AUFRÄUMEN !!!

Scheint bei dem kurzen Programm sinnlos, aber in größeren Programmen führt das definitiv zu Memoryleaks. Wie schon erwähnt: wehret den Anfängen.

[SlaterB]

in Java nicht wirklich Problem, außer man hält die alte Liste noch aktiv referenziert,
in Normalprogrammen kaum drüber nachzudenken

wenn dann noch Code wie struct node * node = (struct node *) malloc(sizeof(struct node)); dazukommt…,
gibt es irgendeinen Pluspunkt, hier überhaupt C zu lernen?

bisaflor klingt ja nicht gerade wie auf dem Weg, die evtl. vorhandenen x% Performancevorteil gegenüber Java professionell zu nutzen
(sorry )

[Marco13]

[ot]
Das kann ausufern, aber ich denke, dass es zumindest nicht schaden kann, zu wissen, was malloc/free machen, was passiert wenn man intPointer += 3 rechnet usw. Und wenn man meint, sich das Leben leichter machen zu können, und auf modernes C++ zurückgreift, und dann sowas wie ::std::shared_ptr<::com::myapp::Node> node; schreiben muss, um das zu haben, was man in Java mit Node node; hat, weiß man Java umso mehr zu schätzen
[/ot]

[mogel]

wenn man in C++ mit :: anfangen muss, dann hat irgend ein Depp in einem Header ein using namespace; gemacht.

[Timothy_Truckle]

[OT][quote=SlaterB]gibt es irgendeinen Pluspunkt, hier überhaupt C zu lernen?[/quote]Ja, BigData ist etwas, womit Java Perfoemanz-Probleme hat, die mit C (nicht C++) besser in den Griff zu bekommen sind.[/OT]
bye
TT

[CyborgBeta]

Ok, stale pointer und memory leak und Heap Analysis wurden genannt. Dazu passt gut, den Debugger nach/während gaaanz vielen Operations anzuschmeißen.

Noch was aus der Trickkiste: statt while (tmp != NULL) { überall while (tmp) {.

Konntet ihr denn oben keine Fehler entdecken? Ich auch nicht.

BigData: Das ist in Java auch möglich, wenn man etwas low level programmiert. new byte[4]; hat (ohne Overhead) auch nur 4 bytes, afaik.

[Marco13]

[ot]

@mogel

wenn man in C++ mit :: anfangen muss, dann hat irgend ein Depp in einem Header ein using namespace; gemacht.

AFAIK nicht notwendigerweise…

namespace foo {
    void fun();
}

namespace bar {
    namespace foo {
        void fun();
    }

    void wtf() {
        foo::fun(); // Zweideutig
        bar::foo::fun(); // Eineinhalbdeutig ;-)
        ::foo::fun(); // Eindeutig
        ::bar::foo::fun(); // Eindeutig
    }
}

Und ich nenne alle meine namespaces std

namespace std {
    namespace std {
        void trolling();
    }
}

:o) (Man kann schon arg viel Mist machen. Und wenn man es KANN, dann wird es auch gemacht ;-))

[/ot]

[mogel]

der Compiler hat alles geschluckt.

@Marco13

foo::fun(); // Zweideutig

nö - Du bist ja in dem Moment im Namespace bar und greifst auf fun() im Namespace foo zu, welcher in Deinem namespace liegt, in dem Du gerade bist. Das wird quasi auf ::bar::foo:fun(); abgebildet.

@Marco13;133506

bar::foo::fun(); // Eineinhalbdeutig

wieso der Compiler das schluckt ist mir schleierhaft. Nach der obigen Erklärung müsste das auf ::bar::bar::foo:fun(); abgebildet werden. Was nicht existiert. Möglich wäre das der erste Namespace einfach „ignoriert“ wird, da wir in dem Namespace gerade sind. Dann wird aber das Beispiel von Oben auf bar::foo:fun(); abgebildet.

Rest ist ja eindeutig.

[Marco13]

[ot]
Zugegeben, ich hatte es nicht ausprobiert oder anhand der Spec verifiziert, sondern nur zusammengefasst so hingeschrieben, wie ich es aus einem realen Fall in Erinnerung hatte: Normalerweise würde man ja foo::fun() schreiben, um auf foo::fun() zuzugreifen. Da es aber auch ein „lokales“ foo::fun() gibt, muss man mit ::foo::fun() auf das übergeordnete zugreifen. Ich finde das in vieler Hinsicht schlecht…

namespace foo {
    void fun() { playFunnyCatVideo(); }
}

namespace bar {

    void wtf() {
        foo::fun(); // Plays a funny cat video
    }

    // Added 2 months and 200 lines later by a different author:
    namespace foo {
        void fun() { killAllKittensWithPoison(); }
    }

}

Es ist (wie du auch mit dem "eigentlich… ::bar::bar::foo:fun();" angedeutet hast) einfach recht verwirrend und potentiell Fehleranfällig. Aber das ist ja nur eine von vielen Spitzen von vielen Eisbergen. Sowas wie C++ Frequently Questioned Answers ist recht unterhaltsam und liefert tolle Sprachenbashing-Munition

[/ot]

*** Edit ***
@bisaflor Sorry, zu dem OT hab’ ich jetzt sehr viel beigetragen. Wenn es noch etwas zum eigentlichen Thema zu besprechen gibt, trenne ich den OT-Teil mal ab (und vielleicht auch so, morgen, der Ordnung halber)