Dynamische Ringliste

[C++ Forumbot]

Dieser Thread wurde von Moderator/in evilissimo aus dem Forum C++ in das Forum ANSI C verschoben.

Im Zweifelsfall bitte auch folgende Hinweise beachten:
C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

Dieses Posting wurde automatisch erzeugt.

[namespace invader]

movco schrieb:

Ein Listenelement besteht aus einem Datenfeld (char*) und einem Zeiger auf das nächste Element.

Also so:

struct element {
    char *data;
    struct element *next;
};

Mit Ringpuffern hat das nichts zu tun.

Die Liste selbst ist dann einfach ein Zeiger auf irgendein Element. Neue Elemente erzeugst du mit malloc.

[knivil]

Sortiertes Einfügen eines neuen Datenelements (nach Datenfeld alphabetisch)

Erklaere das mal. Um zu sortieren, braucht man ein maximales und ein minimales Element. Dann hat man aber auch einen Anfang und ein Ende. Wo ist das bei einem Ring?

[mngbd]

movco schrieb:

Schreiben Sie eine dynamische Ringliste in C (das letzte Element zeigt wieder auf das
erste).
...
e) Den Inhalt der Liste ab einem gewissen Knoten ausgeben

Das ist nicht so einfach wie der Rest. Wie man das macht, ohne in eine Endlosschleife zu laufen, ist schon mannigfaltig untersucht worden. Ich empfehle, zB hier nachzulesen:
http://en.wikipedia.org/wiki/Cycle_detection#Algorithms

edit:
Muss das relativieren. Es reicht natürlich, sich einfach den ersten Zeiger zu merken und aufzuhören, wenn man wieder bei dem vorbeikommt.

[namespace invader]

knivil schrieb:

Sortiertes Einfügen eines neuen Datenelements (nach Datenfeld alphabetisch)

Erklaere das mal. Um zu sortieren, braucht man ein maximales und ein minimales Element. Dann hat man aber auch einen Anfang und ein Ende. Wo ist das bei einem Ring?

Am besten durchläufst du die (nichtleere) Liste einfach so lange, bis

- das vorhergehende Element kleinergleich und das nachfolgende Element größergleich dem einzufügenden Element ist,
- oder das nachfolgende Element kleiner als das vorhergehende ist, und entweder beide größergleich oder beide kleinergleich dem einzufügenden Element sind,
- oder du merkst, dass du einmal rum bist, das bedeutet dass alle Elemente bisher in der Liste gleich sind.

Und dort fügst du es ein.

[mngbd]

namespace invader schrieb:

Am besten durchläufst du die (nichtleere) Liste einfach so lange, bis

- das vorhergehende Element kleinergleich und das nachfolgende Element größergleich dem einzufügenden Element ist,
- oder das nachfolgende Element kleiner als das vorhergehende ist, und entweder beide größergleich oder beide kleinergleich dem einzufügenden Element sind,
- oder du merkst, dass du einmal rum bist, das bedeutet dass alle Elemente bisher in der Liste gleich sind.

Und dort fügst du es ein.

Das geht aber nur mit Ganzzahlen.

[namespace invader]

Wieso? Das müsste doch mit allem gehen was total geordnet ist, also auch mit mit strcmp() verglichenen Strings.

[mngbd]

namespace invader schrieb:

Wieso? Das müsste doch mit allem gehen was total geordnet ist, also auch mit mit strcmp() verglichenen Strings.

Aber nicht mit IEEE 754-Floats, die sind nämlich nicht total geordnet.

[movco]

Also danke mal, ich werde das Samstag versuchen zu implementieren.

Aber was ich noch nicht verstehe ist, wobei ist da der Ring?
Außer ich verschiebe dann den Pointer die ganze Zeit.
Und neue Elemente mit malloc:
Also für ein int oder was auch immer, einen Speicher reservieren? Und dann auf den Speicher schreiben?
LG

[lustig]

Der Zeiger des letzten Elements zeigt auf das erste Element. Bei einer normalen Liste ist der letzte Zeiger null.

[mngbd]

movco schrieb:

Und neue Elemente mit malloc:
Also für ein int oder was auch immer, einen Speicher reservieren? Und dann auf den Speicher schreiben?

Nehmen wir an, dass du die Struktur von namespace invader verwendest. Dann kannst du Speicher für ein neues Element so holen:

struct element *neu;
neu = malloc(sizeof struct element);
// oder einfach (und schlauer)
neu = malloc(sizeof *neu);

// jetzt zeigt 'neu' auf einen Bereich, den du als 'struct element' verwenden kannst:
neu->data = 42;
neu->next = /* was auch immer */;

[movco]

Aber tut mir leid Jungs, ich versteh noch immer nicht wo da dann ein Ring ist

LG

[lustig]

Der Ring ist nicht einfach da. Den machst du beim Einfuegen neuer Elemente indem du beim letzten Element neu->next=erstesElement setzt.
Edit: Im Ring gibt es kein wirkliches letztes Elemnt, aber du stellst beim einfuegen immer sicher, dass die Elemente weiterhin einen Kreis bilden.

[Big Brother]

movco schrieb:

Aber tut mir leid Jungs, ich versteh noch immer nicht wo da dann ein Ring ist

LG

Wozu soll der Ring gut sein? Ich sehe darin keinen Vorteil gegenüber einer gewöhnlichen Liste, bei der das letzte Element auf NULL zeigt.

Gruß,
B.B.

[namespace invader]

Big Brother schrieb:

Wozu soll der Ring gut sein? Ich sehe darin keinen Vorteil gegenüber einer gewöhnlichen Liste, bei der das letzte Element auf NULL zeigt.

Na immer dann, wenn es gar kein erstes und letzes Element gibt, oder einen das zumindest nicht interessiert und man diesen Fall nicht gesondert behandeln will. Z.B. wenn man irgendeine Liste einfach immer reiherum abarbeiten will, etwa die Prozesse beim Multitasking o.ä.

[Genmutant]

Du kannst mit sowas auch einen Ringpuffer baun

EDIT: Wobei... das is ne blöde Idee das damit zu machen

[Big Brother]

namespace invader schrieb:

Na immer dann, wenn es gar kein erstes und letzes Element gibt, oder einen das zumindest nicht interessiert und man diesen Fall nicht gesondert behandeln will. Z.B. wenn man irgendeine Liste einfach immer reiherum abarbeiten will, etwa die Prozesse beim Multitasking o.ä.

Ich habe mich dabei auf die Aufgabenstellung des Threaderstellers bezogen.
Naja, manche Aufgaben muss man nehmen, wie sie sind.

[Big Brother]

movco schrieb:

Also ich muss eine dynamische Ringliste in C implementieren.
Wie würdet ihr das angehen? Ein simpler Pseudocode wäre hilfreich zu verstehen.

Hier ein Ansatz, vielleicht hilft es ja:

typedef struct element Element;
typedef unsigned int uint;

struct element { 
    char *data; 
    Element *next; 
}; 

Element* ring; // Ein beliebiges Element der Ringliste.
uint n; // Anzahl der Elemente in der Ringliste.

void free_ring() {
	Element* curr = ring; uint i;

	for ( i = 0; i < n; i++ )
		curr = curr->next, free ( ring ), ring = curr;
}

void view_ring ( Element* start ) {
	uint i;

	if ( start == NULL ) return;
	for ( i = 0; i < n; i++ )
		puts(start->data), start = start->next;
}

Element* new_element() {
	Element* _new = malloc ( sizeof *_new );

	if ( _new == NULL ) 
		puts ("Out of memory!");
	else
		_new->next = _new, _new->data = NULL;
	return _new;
}
// a equal or greater b
int a_eqgr_b ( Element* a, Element* b ) {
	return strcmp ( a->data, b->data ) >= 0; 
}

int a_less_b ( Element* a, Element* b ) {
	return strcmp ( a->data, b->data ) < 0;
}

Element* find_min() {
	Element* min = ring; uint i;

	for ( i = 0; i < n; i++ ) {
		if ( a_less_b ( ring, min ) )
			min = ring;
		ring = ring->next;
	}
	return min;
}

Element* find_max() { // Such max  :D
	Element* max = ring; uint i;

	for ( i = 0; i < n; i++ ) {
		if ( a_less_b ( max, ring ) )
			max = ring;
		ring = ring->next;
	}
	return max;
}

void insert ( Element* e ) {

	uint i;
	if ( e == NULL ) return;

	if ( ring == NULL )
	{
		ring = e; // Das erste Element in der Liste ist e.
	}
	else
	{
		for ( i = 0; i < n; i++ )
		{
			if ( a_eqgr_b ( e, ring ) && a_less_b ( e, ring->next ) )
				break;
			ring = ring->next;
		}
		// Sind im Ring alle gleich, oder ist e größer als alle im Ring?
		if ( i == n )
			ring = find_max();  // Jepp.
		e->next = ring->next, ring->next = e;
	}
	n++; // Die Anzahl der Elemente in der Ringliste ist um ein Element größer.
}  

int main() { 
	Element* e = NULL;
	char* data[] = { "jkl", "ghi", "mno", "def", "abc", NULL };
	uint i = 0;

	while ( data[i] != NULL ) {
		if ( NULL == ( e = new_element()))
			break;
		e->data = data[i], insert ( e ), i++;
	}
	view_ring ( find_min() );
	free_ring();
	return 0;
}

Gruß,
B.B.