Dynamische Ringliste

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.