Dynamische Ringliste

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.

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

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.

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.