Code-Schnipsel

Linked List Lib mit den typischen Operationen (push, pop, reverse, move, sub, insert, remove, get, size, join, print, split, merge, sort).

int
list_push(node **_x, int _data) {
	node *n = NULL;

	if(_x == NULL)
	        return(-1);

	if((n = (node *)malloc(sizeof(node))) == NULL) {
		return(-1);
	} else {
		n->data = _data;
		n->next = *_x;

		*_x = n;
		return(0);
	}
}

int
list_pop(node **_x) {
	node *n = NULL;
	int data;
	
	if(_x == NULL)
	        return(-1);

	if(*_x == NULL)
		return(-1);
		
	n = *_x;
	*_x  = n->next;
	data = n->data;
	free(n);

	return(data);
}

int
list_move(node **_x, node **_y) {
	node *n = NULL;
	
	if((_x == NULL) || (_y == NULL))
		return(-1);

	if(*_y == NULL)
		return(-1);

	n = *_y;
	*_y = n->next;
	n->next = *_x;
	*_x = n;

	return(0);
}

int
list_reverse(node **_x) {
	node *n = NULL;

	if(_x == NULL)
		return(-1);

	while(list_move(&n, _x) >= 0);
	*_x = n;

	return(0);
}

node *
list_sub(node *_x, int _n) {
	int i = 0;

	if(_x == NULL)
		return(NULL);

	if(_n < 0)
		return(NULL);
	
	while(i++ < _n) {
		if((_x = _x->next) == NULL)
			return(NULL);
	}

	return(_x);
}

int
list_insert(node **_x, int _pos, int _data) {
	node *p;

	if(_x == NULL)
		return(-1);
	        
	if(_pos < 0)
		return(-1);

	if(_pos == 0)
	        return(list_push(_x, _data));

	if((p = list_sub(*_x, _pos-1)) == NULL)
		return(-1);

	return(list_push(&(p->next), _data));
}

int
list_remove(node **_x, int _pos) {
	node *current = *_x;
	node *next = NULL;
	int data;

	if(_x == NULL)
	        return(-1);
	        
	if(*_x == NULL)
	        return(-1);

	if(_pos < 0)
	        return(-1);

	if(_pos == 0)
	        return(list_pop(_x));

	while(--_pos) {
		current = current->next;
	}

	if((next = current->next) == NULL)
	        return(-1);
	        
	data = next->data;
	current->next = next->next;

	free(next);
	return(data);
	
	return(0);
}

int
list_get(node *_x, int _n) {
	int i = 0;

	while(_x != NULL) {
		if(_n == i++)
		        return(_x->data);
		_x = _x->next;
	}

	return(-1);
}

size_t
list_size(node *_x) {
	size_t s = 0;

	for(; _x != NULL; s++, _x = _x->next);
	return(s);
}

node *
list_join(node *_x, node *_y) {
	node *n = _x;

	if(_x == NULL)
	        return(_y);
	        
	while(_x->next != NULL)
	        _x = _x->next;
	        
	_x->next = _y;

	return(n);
}

void
list_print(node *_x) {
        while(_x != NULL) {
		printf("%d\n", _x->data);
		_x = _x->next;
        }
}

/* hare and tortoise approach / classic Floyd’s Cycle Finding Algorithm */
int
list_split(node **_src, node **_front, node **_back) {
	node *fast, *slow;

	if((_src == NULL) || (_front == NULL) || (_back == NULL))
	        return(-1);

	if((*_src == NULL) || ((*_src)->next == NULL)) {
		*_back = NULL;
	} else {
		slow = *_src;
		fast = slow->next;
		
		while(fast != NULL) {
			fast = fast->next;
			if(fast != NULL) {
				slow = slow->next;
				fast = fast->next;
			}
		}
		*_back = slow->next;
		slow->next = NULL;
	}

	*_front = *_src;
	*_src = NULL;
	return(0);
}

int cmp(int a, int b) {
	if(a < b) return(-1);
	if(a > b) return(1);
	return(0);
}

int
list_merge(node **_dest, node **_a, node **_b, int _cmp(int, int)) {
	node *ret = NULL;
	node **last = &ret;

	if((_dest == NULL) || (_a == NULL) || (_b == NULL))
		return(-1);

	for(;;) {
		if(*_a == NULL) {
			*last = *_b;
			break;
		}

		if(*_b == NULL) {
		        *last = *_a;
		        break;
		}
		
		if(_cmp((*_a)->data, (*_b)->data) <= 0) {
			list_move(last, _a);
		} else {
			list_move(last, _b);
		}
		
		last = &((*last)->next);
	}

	*_dest = ret;
	return(0);
}

int
list_sort(node **_x, int _cmp(int, int)) {
	node *l, *r;

	if(_x == NULL)
	        return(-1);
	        
	if(*_x == NULL || (*_x)->next == NULL)
	        return(0);

	list_split(_x, &l, &r);

	list_sort(&l, _cmp);
	list_sort(&r, _cmp);
	
	list_merge(_x, &l, &r, _cmp);

	return(0);
}

Ich bin zur Zeit damit beschäftigt, mir eine Bibliothek zusammenzubauen, die alle häufig verwendeten Operationen unterstützt (hauptsächlich Array- und List-Handling, später auch Bäume und simpler File-I/O).

Wäre nett, wenn ihr mal drüberschaut und mir sagt ob etwas fehlt.

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Hallo Philip.

Ärgerlich, denn einige dieser Funktionen habe ich mir vor wenigen Tagen mühsam erstellt.

Ein paar Fragen habe ich:
Woher kommt das node? Ist das ein per typedef erstellter Bezeichner?
Und was ist mit solchen else-Blöcken?

	if((n = (node *)malloc(sizeof(node))) == NULL) {
		return(-1);
	} else {
		n->data = _data;
		n->next = *_x;

		*_x = n;
		return(0);
	}

Seit Pronix versuche ich daraus ehr soetwas zu bauen:

	if((n = (node *)malloc(sizeof(node))) == NULL)
		return(-1);
	n->data = _data;
	n->next = *_x;

	*_x = n;
	return(0);

Begründen kann ich das aber nicht, deshalb ist meine zweite Frage, wie man´s machen sollte?

Und dann habe ich noch Vorschläge/Wünsche für eine weitere Funktionen:
exists und defined


Gruß,
Patrick-Oliver

--
To follow the path: look to the master, follow the master, walk with the master, see through the master, become the master.

 

Huhu,

Patrick, die else Blöcke sind Geschmacksache mehr nicht.

Bis denne

Martin

--
0xC0FFEE

 

Hi Patrick,

die else-Blöcke sind wie gesagt syntaktischer Schnickschnack.

Ich schreibe sie gerne explizit hin, damit die Verzweigung auf den ersten Blick deutlich wird.

Ausnahme sind Error-Checks am Beginn einer Funktion, wenn also auf NULL-Pointer usw. getestet wird (weil der else-Block jeweils der Rest der Funktion ist).

Zitat:

Woher kommt das node? Ist das ein per typedef erstellter Bezeichner?

Oops... "node" steht noch im Header:

typedef struct _node {
	struct _node *next;
	int data;
} node;

Statt "int data" werd ich wohl demnächst auf "void *data" umstellen... mit ein paar ints liess sich aber leichter testen als jedesmal wild rumzucasten.

Falls es noch niemand aufgefallen ist: die obige Definition einer Liste (ohne "Head"-Element) hat den Vorteil, dass jede Teilliste wieder eine eigenständige Liste ist. Das kann manchmal von Vorteil sein...

Zitat:

exists und defined

Was macht exists()? Prüfen ob ein Element in der Liste ist? Gute Idee!

Was macht defined()? Prüfen ob eine gegebene Liste existiert bzw. nicht leer ist? Das geht so:

if(my_list == NULL) {   // ...

Die leere Liste wird durch den NULL-Pointer repräsentiert und ist in jeder Listenoperation ein gültiges Argument.

Es ist bei meiner Konstruktion technisch nicht möglich, eine "undefinierte" Liste zu bauen, ausser man weisst einem Listenpointer eine lustige Adresse zu.

Eine copy()-Funktion wäre noch sinnvoll, fällt mir gerade ein... flat copy sowieso, deep copy (Kopie der Nutzerdaten selbst) kann man im Prinzip auch den Benutzer machen lassen. Naja, mal sehen.

Also fehlen noch: exists(), copy()

Danke für den Vorschlag!

Gruss,
Philip

--
The C Programming Quiz - bitte Fragen einreichen :)

 

Zitat:

typedef struct _node {
	struct _node *next;
	int data;
} node;

Falls es noch niemand aufgefallen ist: die obige Definition einer Liste (ohne "Head"-Element) hat den Vorteil, dass jede Teilliste wieder eine eigenständige Liste ist. Das kann manchmal von Vorteil sein...

Meinst Du mit "Head"-Element einen Zeiger auf das vorherige Element, denn die Struktur sieht mir wie eine normale einfach verkettete Liste aus?