Einfach verkettete Liste



  • Ich habe mich ein wenig an verketteten Listen versucht (durch Experimentieren)
    Sieht das hier nach einer (einigermaßen) annehmbaren Lösung aus?

    #define TRUE 1
    #define FALSE 0
    
    typedef struct list{	//Listenelement
    	int value;
    	struct list *next;
    }LIST;
    
    LIST *createList(int value){
    	LIST *new = malloc(sizeof(LIST));
    	if (!new) return NULL;
    	new->value = value;
    	new->next = NULL;
    	return new;
    }
    
    int add_left(LIST **l, int value){ //Am Anfang einfügen
    	LIST *n = createList(value);
    	if (!n) return FALSE;
    	n->next = *l;
    	*l = n;
    	return TRUE;
    }
    
    int add_right(LIST *l, int value){ // Am Ende der Liste einfügen
    	LIST *n = l;
    	while (n){
    		if (!(n->next)){
    			n->next = createList(value);
    			if (!(n->next)) return FALSE;
    			break;}
    		n = n->next;}
    	return TRUE;
    }
    
    int add_position(LIST *l, int pos, int value){ //hinzufügen an best. Position
    	LIST *n = l, *p = l->next;
    	for (int i = 0; i < pos - 1; ++i){
    		if (!n) return FALSE;
    		if (!p) return FALSE;
    		n = n->next;
    		p = p->next;}
    	n->next = createList(value);
    	if (!(n->next)) return FALSE;
    	n->next->next = p;
    	return TRUE;
    }
    
    void destroy_list(LIST *l){ //liste freigeben
    	LIST *next;
    	while (l){
    		next = l->next;
    		free(l);
    		l = next;}
    }
    

    Zumindest funktioniert der Code soweit.
    Als nächstes habe ich mir eine "Index-variable" gebastelt, damit ich auf alle Elemente direkt zugreiffen kann, z.B um sie zu sortieren.
    Das 'indizieren' funktioniert wunderbar, beim Sortieren hat sich aber wohl irgendwo ein Fehler eingeschlichen, auf den Ich einfach nicht komme.

    typedef struct sort{ 	//Variable um Liste zu 'indizieren'
    	int count;
    	int *value;			//Werte der Listenelemente
    	LIST **liste;		//Adressen der einzelnen Elemente
    }SORT;
    
    SORT* get_index(LIST *anchor){ //Speichert Adressen und Werte der Liste in 'Index' Variable
    	LIST *new = anchor;
    	int i = 0;
    	SORT *p = malloc(sizeof(SORT));
    	p->value = malloc(sizeof(int));
    	p->liste = malloc(sizeof(LIST*));
    	p->count = 0;
    	while (new){
    		p->value[i] = new->value;
    		p->liste[i] = new;
    		p->count += 1;
    		new = new->next;
    		++i;
    		p->value = realloc(p->value, sizeof(int) * (i + 1));
    		if(!(p->value)) return NULL;
    		p->liste = realloc(p->liste, sizeof(LIST*) * (i + 1));
    		if(!(p->liste)) return NULL;}
    	return p;
    }
    
    void sort_list(LIST* list, SORT* index){ //'sortiert' die Liste um
    	int i;
    	LIST *p = index->liste[0];
    	LIST *q = p;
    	for (i = 1; i < index->count; ++i){
    		q->next = index->liste[i];
    		q = q->next;}
    	q->next = NULL;
    	list = q;
    }
    
    void sort_array(int *arr, int length, LIST **list){ //sortier int array aufsteigend
    	int i;
    	for (i = length; i > 1; --i){
    		int maxpos = array_max(arr, i);
    		if (maxpos != i - 1) _swap(arr, list, i, maxpos, i - 1);}
    }
    
    int array_max(int *arr, int length){ //sucht größtes Element eines int Arrays
    	int i, pos = 0, max = arr[0];
    	for (i = 1; i < length; i++){
    		if (arr[i] > max){
    			max = arr[i];
    			pos = i;}}
    	return pos;
    }
    
    void _swap(int *arr, LIST **list, int length, int n, int m){ //tauscht Werte und Adressen
    	int help = arr[n];
    	arr[n] = arr[m];
    	arr[m] = help;
    	LIST *help2 = list[n];
    	list[n] = list[m];
    	list[m] = help2;
    }
    
    int main(){
    	LIST *p = NULL;
    	SORT *q = NULL;
    	int i;
    	p = createList(99);
    	if (!p) return -1;
    	if (!add_right(p, 0)) return -1;
    	if (!add_right(p, 5)) return -1;
    	if (!add_right(p, 100)) return -1;
    	print_list(p);					//Ausgabe: 99, 0, 5, 12
    	q = get_index(p);				//Funktioniert soweit wunderbar
    	if (!q) return -1;
    	sort_array(q->value, q->count, q->liste); //soll den Array in q mit den Werten der Liste sortieren
    	sort_list(p, q);
    	print_list(p);					//Ausgabe: 99, 100...alle Elemente, die kleiner sind
    							//als das des Ankers 'verschwinden'
    	return 0;
    

    Ich bin etwas ratlos, da die Sortierfunktion Beispielsweise bei int arr[5] = {2, 5, 1, 0, 77}; funktioniert...

    Tut mir Leid für den langen Text und schon mal vielen Dank für die Antworten 🙂



  • Warum gibt createList einen Zeiger auf eine Liste zurück?
    Warum bekommt add_left einen Doppelzeiger auf ein Liste?

    Weil sie den Anfang der Liste verändern.

    Warum hat sort_list nichts von den beiden genannten Merkmalen?
    Weil sie den Anfang der Liste nicht verändert.
    Mmm, kann sie ja doch, wenn das erste Element nicht das kleinste ist.
    Dann müsste ja sort_list auch .... oder ....

    Meinst du nicht, dass das kopieren der Liste in eine neu struct zu aufwendig ist?
    Zähle die Anzahl der Knoten in der Liste.
    Besorge Speicher für diese Anzahl Zeiger auf die Liste (malloc(sizeof(LIST*)*anz)).
    Schreibe in das Array die Anfangsadressen von den Knoten.
    Jetzt kannst du über dieses Array auf die Knoten zugreifen und damit auch das Array sortieren.
    Dafür gibt es übrigens qsort aus der Standardlibrary.
    Du musst nur die Vergleichsfunktion richtig machen.

    Nach dem Sortieren kannst du mithilfe von dem Array die Liste wieder neu verketten.

    Wo gibst Du eigentlich den Speicher vom Sortieren frei?



  • mit

    void free_sort(SORT* p){
    	free(p->value);
    	free(p->liste);
    	free(p);
    }
    

    hatte ich nur aus Platzgründen weggelassen 😉
    Ja hab's jetzt mit LIST** und ich habe auch den Fehler gefunden..

    *list = q
    

    ....q zeigt immer auf das letzte Listenelement, also auf das größte..muss natürlich

    *list = p
    

    heissen 🙄

    Gibt es denn eigentlich eine Möglichkeit herauszufinden von welchem Typ ein Pointer ist, also damit ich beispielsweise char* und int* (per Fallunterscheidung) mit der selben Funktion vergleichen kann? scanf müsste sowas in der Art ja eigentlich auch machen oder..?



  • KJoke schrieb:

    Gibt es denn eigentlich eine Möglichkeit herauszufinden von welchem Typ ein Pointer ist, also damit ich beispielsweise char* und int* (per Fallunterscheidung) mit der selben Funktion vergleichen kann?

    Nein. C kann das nicht.

    KJoke schrieb:

    scanf müsste sowas in der Art ja eigentlich auch machen oder..?

    scanf erkennt das an den Formatspecifiern im Formatstring.

    Du kannst deiner Vergleichsfunktion einen Parameter mitgeben. Aber letztendlich schreibst du dann ja auch für jeden Zeigertyp den Vergleich neu.

    C++ kann das aber.


Log in to reply