4. Listen Element einfuegen!

Listen Element einfuegen!

  • T

    Hi!

    Ich habe mir eine kleine Listenstruktur gebaut mit natürlich einem Inhalt und einem Verweis auf Next!
    Dann hab ich mir gedanken gemacht und überlegt wie ich ein Element einfuegen kann!
    Natuerlich sollen die Elemente in einer Sortierten Reihenfolge eingetragen werden, das heißt z.B (1->5->10) oder (10->100->1000)!
    Das klappt auch so weit aber irgendwie nicht richtig!
    Das heißt wenn ich eine 1 einfuege ist irgendwie jedes Element 1!
    Also das Problem scheint zu sein das ich irgendetwas falsch mache mit den Zeigern!

    Liste Einfuegen (Inhalt i, Liste MyList){
	/*VERARBEITUNG*/
	if (istListeLeer(MyList) || i < MyList->value)
		return list_cons(i,MyList);
        /*WENN DAS ELEMENT SCHON ENTHALTEN*/
	if (i == MyList->value) return MyList; 
		MyList->next = Einfuegen (i,MyList->next);
	return MyList;
}

    Vielleicht kann mir ja einer nen Tip geben was ich falsch mache!

    0
  • C

    Wie sieht denn die Funktion list_cons() aus? (wenn ich das überblicke, ist die dafür zuständig, das neue Element tatsächlich einzutragen)

    (btw, für sortierte Datenmengen sind (balancierte) Bäume besser geeignet als Listen)

    0
  • T

    So sieht list_cons aus!!

    Liste list_cons (Inhalt i, Liste MyList){
	/*VERARBEITUNG*/
	/*ZUSICHERUNG EINES NODES*/
	List res=malloc(sizeof(*MyList)); 
	if (!res) {
		exit(1); 
	}
	/*ELEMENT FUELLEN*/
	res->value = i;
	res->next = MyList;
	return res;	
}

    Ja es kann gut sein das Bäume besser geignet sind aber ich will und "muss" Listen nutzen!

    0
  • M

    Ich habe mir mal deine Funktionen angeschaut und da keinen
    Fehler finden können. Vielleicht hast du in der Benutzung
    deiner Funktionen einen Fehler gemacht.

    Vielleicht ist die Liste nicht richtig initialisiert,
    oder du hast dich mit den Pointer an anderer Stelle vertan.

    So ist dein Fehler jedenfalls nicht zu finden.

    Hast du mal versucht, dir ein paar Hilfsfunktionen wie print
    oder so zu schreiben?

    Hier mal mein Code, mit dem ich deine Implementierung
    überprüft habe, vielleicht findest du ja, wenn du vergleichst,
    einen Fehler bei dir.

    #include <stdio.h>
#include <malloc.h>
#include <stdlib.h>

typedef int inhalt;

typedef struct liste_t {
    inhalt value;
    struct liste_t* next;
} *liste;

static void print_list(liste l) {
    while (l) {
        printf("val: %4d    next: %p\n", l->value, (void*)l->next);
        l = l->next;
    }
}

liste list_cons(inhalt i, liste l) {
    liste res = malloc(sizeof*res);
    if (!res) exit(1);
    res->value = i;
    res->next = l;
    return res;
}

liste einfuegen( inhalt i, liste l) {
    if (!l || i < l->value) return list_cons(i, l);
    if (i == l->value) return l;
    l->next = einfuegen(i, l->next);
    return l;
}

liste ein (inhalt i, liste l) {
    liste tmp1 = NULL, tmp2 = l;
    while (tmp2 && tmp2->value < i) {
        tmp1 = tmp2;
        tmp2 = tmp2->next;
    }
    if (tmp2 && tmp2->value == i) return l;
    else {
        liste new_el  = malloc(sizeof(*new_el));
        new_el->value = i;
        new_el->next  = tmp2;
        if (tmp1) {
            tmp1->next = new_el;
            return l;
        } 
        return new_el;
    }
    return NULL;
}

int main (void) {
    liste l = NULL, l2 = NULL;

    l = einfuegen(5, l);
    l = einfuegen(1, l);
    l = einfuegen(10, l);
    l = einfuegen(1, l);
    print_list(l);

    l2 = ein(5, l2);
    l2 = ein(1, l2);
    l2 = ein(10,l2);
    l2 = ein(1, l2);
    print_list(l2);

    return 0;
}

    Gruß mcr

    PS: die Funktion ein() ist eine iterative Variante deiner Einfuegen().

    0
  • T

    Wie würde man den eine Liste am besten als Leer initialisieren???
    Wurzel = NULL oder next = NULL???
    Die Wurzel NULL setzen kommt mir etwas unlogisch vor!

    ?????

    0
  • T

    Beim letzten Element ist 'next' ja immer NULL, und wenn die Liste nur ein Element hat, dann ist ja auch gleich Liste->next = NULL, daher ist eine leere Liste am besten als NULL darzustellen (denn dadurch reservierst du ja keinen zusätzlichen Speicher).

    Bei einer doppelt-verketteten Liste oder einem Ringpuffer arbeitet man aber häufig mit einem sog. Sentinel, d.h. ein vordefiniertes Element.
    Bzw. beim Suchen kann man dieses auch einsetzen, indem man das zu suchende Element temporär an das Ende der Liste dranhängt (dann entfällt der Vergleich auf das Listenende, d.h. l->next != NULL).

    0
Anmelden zum Antworten