einf. verkettete Liste u. Listhandler

andro

Haa,
das hilft mir in diesem Fall leider auch nichts, obwohl Du prinzipiell vollkommen recht hast.
Mein Problem ist es halt zu verstehen, wie die Funktion zum erzeugen der Liste (die ja wohl auch so noch keinen Sinn macht, da die anderen Funktionen zum Anhängen, Löschen etc.. fehlen) hauptsächlich mit dem Listhandler zusammen arbeiten. Der Listhandler tritt doch immer in Aktion, wenn sich etwas in der Liste an einer Stelle verändert, oder ? Warum steht da z.b. struct element *thisElement; /*Zeiger auf den Vorgänger*/. Warum sollte man den Zeiger auf ein Element davor zeigen lassen ?

Dill

hmmja ... sowas wie diese listhandler struktur hab ich noch nicht gesehen.
aber ich denke mal die erspart einige hilfszeiger wenn du etwa ein element einfügst.da brauchst du halt zeiger auf die elemente zwischen denen eingefügt werden soll.

poste doch mal was mehr code.

bei www.pronix.de ist die sache mit den verk. listen schön erklärt ...

aber ich bin ja immernoch für zeichen, dann wird auch klar für was du die zeiger brauchst.

andro

wie die verkette Liste für alle einzelnen Schritte arbeitet, habe ich mir bereits aufgezeichnet. Auf dieser Ebene (und das hab ich zuerst gemacht) habe ich die Listen soweit verstanden. Bei mir liegst eher an der Umsetzung (speziell bei der Pointer Manipulation) ... und am Listhandler s.u.

hier mal der gesamte quelltext, jetzt aber in seiner ursprünglichen form:

/* Einfach verkettete Liste */

/*-------------------------------------------------------------------------*/

#include <stdio.h>

// definiert einen Datentyp, mit dem die Daten
// der Liste gespeichert werden koennen
// key gibt den Schluesselwert des Elements 
// (damit die Elemente auch sortiert werden koennen)
// name sind die eigentlichen Daten
typedef struct {
    int key;
    char name[10];
} userdata_t;

/*-------------------------------------------------------------------------*/

// definiert einen Struktur, welche die Elemente
// der Liste bilden
// zunaechst werden die eigentlichen Daten benoetigt
// (zuvor definierter Datentyp)
// ausserdem muss das naechste Element der Liste gemerkt
// werden:
// Rekursive Datentypen: Der Zeiger
// next verweist auf einen Eintragen desselben Typs
// list_element_t
struct list_element_t {
    //eigentliche Daten
    userdata_t data;
    // Zeiger auf naechstes Listenelement (oder NULL)
    struct list_element_t *next;    
};

/*-------------------------------------------------------------------------*/

// ein Datentyp fuer die Verwaltung von Listen
// genannt Listhandler
typedef struct {
    // Zeiger auf Listenanfang
    struct list_element_t *head; 
    // Zeiger auf DEN VORGAENGER des aktuell zu
    //bearbeitenden Listenelements
    struct list_element_t *thisElement;
    // Zeiger auf das letzte Listenelement
    struct list_element_t *lastElement;
} list_handle_t;

/*-------------------------------------------------------------------------*/
/* Es folgen die Funktionen zur Verwaltung von Listen */
/*-------------------------------------------------------------------------*/

// Funktion zum Erzeugen einer Liste
// Rueckgabewert: Zeiger auf Listhandler
// keine Parameter
list_handle_t *createList(void) {
    // einen Zeiger auf einen Listhandler erzeugen
    list_handle_t *h;

    // malloc() erzeugt dynamisch Speicher
    // und gibt einen Pointer auf den Speicheranfang zurueck
    h =(list_handle_t *)malloc(sizeof(list_handle_t));

    // jetzt ist Platz im Speicher reserviert
    // markiere, dass Liste leer ist
    // Anfang, Ende und Vorgaenger des aktuelles Element sind NULL, 
    // d.h. vorerst nicht belegt
    h->head =NULL;
    h->thisElement = NULL;
    h->lastElement = NULL;

    // gib den neuen Handler zurueck
    return h;
}

/*-------------------------------------------------------------------------*/

//Funktion, die Elemente an die Liste anhaengt
//kein Rueckgabewert
//Parameter: Listhandler (fuer die Liste, an die angehaengt werden soll
//Datensatz, der im neuen Element der Liste stehen soll
void appendList(list_handle_t *h, userdata_t d) {

    //1. Schritt: Speicher fuer neues Listenelement
    // allokieren
    struct list_element_t *l;
    l =(struct list_element_t *)malloc(sizeof(struct list_element_t));

    // 2. Schritt: Nutzdaten d in neues Listenelement kopieren
    l->data = d;

    // 3. Schritt: Verkettung - bisher letztes
    // Listenelement muss neuen Eintrag l als
    // Nachfolger bekommen. l hat keinen Nachfolger
    l->next = NULL;

    // Unterscheide zwischen leerer und gefuellter Liste
    // 1. Fall: leere Liste
    if ( h->head == NULL ) {
    h->head = l;
        h->thisElement = NULL; // zu head existiert
                               // kein Vorgaenger
    }
    // 2. Fall: es existiert ein Element
    else {
    h->lastElement->next = l;
    }

    // nach dem Anhaengen ist das neue Element auch das letze
    h->lastElement = l;
}

/*-------------------------------------------------------------------------*/

// Funktion zum Einfuegen in die Liste
// kein Rueckgabewert
// Parameter: Listhandler fuer die Liste, in die eingefuegt werden soll
// Datensatz fuer das neue Element der Liste
void insertList(list_handle_t *h, userdata_t d) {

    //1. Schritt: Speicher fuer neues Listenelement allokieren
    struct list_element_t *l;
    struct list_element_t *temp;
    l = (struct list_element_t *)malloc(sizeof(struct list_element_t));

    // 2. Schritt: Nutzdaten d in neues Listenelement kopieren
    l->data = d;

    // 3. Schritt: Verketten des neuen Elements

    // 1. Fall: die Liste ist leer, das neue Element wird das erste
    // jetzt ist das neue Element sowohl das letzte als auch das erste
    // thisElement zeigt auf den Vorgaenger des aktuellen Elements,
    // beim ersten Element gibt es aber keinen Vorgaenger, deshalb NULL
    if ( h->head == NULL ) {
    h->head = l;
        h->thisElement = NULL;
        h->lastElement = l;
        l->next = NULL;
    }
    // 2. Fall: es gibt genau ein Element in der Liste
    // in diesem Fall sind head und lastElement gleich diesem Element
    // und thisElement ist NULL (siehe auch 1. Fall)
    // das neue Element wird also vor dem Element in der Liste eingehaengt
    // es ist damit der neue Kopf der Liste
    // ausserdem ist der Nachfolger des neuen Elements das alte Element in
    // der Liste 
    else if ( h->thisElement == NULL ) {
        l->next = h->head;
        h->head = l;
    }
    // 3. Fall: es gibt mehr als ein Element in der Liste
    // in diesem Fall wird der Nachfolger des neuen Elements das bisher
    // aktuelle (thisElement zeigt auf dessen Vorgaenger!)
    // der Nachfolger des Vorgaengers des aktuellen Elements muss jetzt auf
    // das neu eingefuegte Element zeigen
    else {
    l->next = h->thisElement->next;
        h->thisElement->next = l;
    }

    // zu guter Letzt wird der Vorgaenger des aktuellen Elements
    // auf das neu eingefuegte Element gesetzt
    h->thisElement = l;

    // falls hinten an die Liste angehaengt wurde:
    if ( h->lastElement->next ) 
    h->lastElement = l;
}

/*-------------------------------------------------------------------------*/

// eine Funktion, um ein Lesezeichen in der Liste zu setzen (Merker)
// Rueckgabewert: Zeiger auf das Listenelement, das gemerkt werden soll
// Parameter: Listhandler, fuer die entsprechende Liste
struct list_element_t* bookmarkList(list_handle_t *h) {
    // wenn der Listhandler ungueltig ist, gibt es keine Liste,
    // also Abbruch
    if ( !h ) return NULL;

    // wenn es nur ein Listenelement gibt, muss dies head sein
    // gib also head zurueck
    if ( !(h->thisElement) ) return h->head;

    // wenn das Vorgaenger des aktuellen Elements keinen Nachfolger hat
    // liegt ein Fehler vor, gib NULL zurueck
    if ( !(h->thisElement->next) ) return NULL;

    // in allen anderen Faellen, gib das aktuelle Element zurueck
    return h->thisElement->next;
}

/*-------------------------------------------------------------------------*/

// eine Funktion, um zur gemerketen Bookmark zurueckzugehen
// kein Rueckgabewert
// Parameter: Listhandler fuer die zu bearbeitende Liste,
// Bookmark, d.h. Zeiger auf ein  Element der Liste
void gotoBookmarkList(list_handle_t *h, struct list_element_t* b) {
    // temp Variable zum Merken eines Zeigers auf ein Element
    struct list_element_t *temp;

    // wenn der Listhandler ungueltig ist, verlasse die Funktion
    if ( !h ) return;

    // wenn das Bookmark der Anfang der Liste ist, muss das 
    // Vorgaenger des aktuellen Elements der Liste auf NULL gesetzt werden
    if ( b == h->head ) {
    h->thisElement = NULL;
    }
    else { 
    // ansonsten merke den aktuellen Head
    temp = h->head;
    // solange das aktuelle Element nicht NULL und nicht das
    // Bookmark ist, gehe ein Element weiter
    while ( temp != NULL && temp->next != b ) 
        temp = temp->next;
    // wenn ich das Bookmark gefunden habe
    // setze den Vorgaenger des aktuellen Element als Bookmark
    if ( temp ) 
        h->thisElement = temp;
    }
}

/*-------------------------------------------------------------------------*/

// Funktion, um Elemente aus der Liste zu lesen
// Rueckgabewert: gefundenes Nutzdaten
// Parameter: Listhandler der zu bearbeitenden Liste
userdata_t *readElementList(list_handle_t *h) {
    // wenn der Listhandler nicht gueltig ist
    // oder die Liste leer ist
    // oder der Vorgaenger des aktuellen Elements keinen Nachfolger hat
    // gib NULL zurueck, da ungueltige Werte
    if ( !h || !(h->head) || !(h->thisElement->next) ) return NULL;

    // wenn es keinen Vorgaenger vom aktuellen Element gibt, existiet nur ein
    // Element, das Head, also gib dessen Daten zurueck
    if ( !(h->thisElement) ) return &(h->head->data); 

    // in allen anderen Faellen
    // gib die Daten des aktuellen Elements zurueck
    return &(h->thisElement->next->data);
}

/*-------------------------------------------------------------------------*/

// Funktion zum Zuruecksetzen des Vorgaengers des aktuellen Elements
// kein Rueckgabewert
// Parameter: Listhandler der zu bearbeitenden Liste
void rewindList(list_handle_t *h) {
    // wenn der Handler gueltig ist, setze den Vorgaenger des aktuellen
    // Elements auf NULL
    if ( h ) h->thisElement = NULL;
}

/*-------------------------------------------------------------------------*/

// Funktion, um schrittweise durch die Liste zu gehen
// Rueckgabewert: Zeiger auf die Daten des aktuellen Listenelements
// Parameter: Listhandeler der zu bearbeitenden Liste
userdata_t *traverseList(list_handle_t *h) {
    // Zeiger fuer die Daten des Listenelements
    userdata_t *dPtr;

    // wenn der Listenhandler ungueltig ist
    // oder der Vorgaenger des aktuellen Elements gleich dem letzten 
    // Element ist, ist die Liste ungueltig, Rueckgabewert NULL
    if ( (!h) || h->thisElement == h->lastElement ) {
    return NULL;
    }

    // wenn die Liste nur ein Element hat, ist der Rueckgabewert 
    // der Zeiger auf die Daten des Heads
    // thisElement wird fuer den naechsten Schritt hochgesetzt
    if ( h->thisElement == NULL ) {
    h->thisElement = h->head;
        return &(h->head->data);
    }

    // in allen anderen Faellen ist der Rueckgabewert ein Zeiger
    // auf die Daten des letzten Elements
    dPtr = &(h->thisElement->next->data);

    // das aktuelle Element wird auf das naechste Element gesetzt
    // (fuer den naechsten Schritt)
    h->thisElement = h->thisElement->next;

    // Rueckgabe der Daten
    return dPtr;

}
/*-------------------------------------------------------------------------*/

// Funktion zum Ausgeben der Liste
// kein Rueckgabewert
// Parameter: Listhandler der zu bearbeitenden Liste
void printList(list_handle_t *h) {
    // Zeiger auf die Daten
    userdata_t *dPtr;

    // Liste zuruecksetzen
    rewindList(h);

    // Daten holen
    dPtr = traverseList(h);
    // wenn die Daten gueltig sind, ausgeben bis Ende 
    while(dPtr != NULL) {

    printf("key = %d name = %s\n", 
           dPtr->key, dPtr->name);
        dPtr = traverseList(h);
    }
}

/*-------------------------------------------------------------------------*/
/* Hauptprogramm: Beispiel zum Arbeiten mit Listen */
/*-------------------------------------------------------------------------*/

int main() {
    // zwei Listhandler
    list_handle_t *list1Handle;
    list_handle_t *list2Handle;
    // Variable fuer Daten
    userdata_t d;
    // Zeiger auf Daten
    userdata_t *dPtr;
    // Listenelement
    struct list_element_t* bm;

    // zwei Listen erzeugen
    list1Handle = createList();
    list2Handle = createList();

    // Daten erzeugen
    d.key = 10;
    // Kopieren von String in char-array:
    // der Ziel char-array muss lang genug sein,
    // um den Quellstring + Null-Character
    // abzuspeichern
    strcpy(d.name,"name1");
    // Daten an die Liste 1 anhaengen
    appendList(list1Handle,d);

    // noch mehr Daten erzeugen und anhaengen
    d.key = 5;
    strcpy(d.name,"name2");
    appendList(list1Handle,d);

    d.key = 7;
    strcpy(d.name,"name3");
    appendList(list1Handle,d);

    // Liste 1 ausgeben
    printf("1. Lesevorgang:\n");
    printList(list1Handle);

    // Liste 1 zuruecksetzen
    rewindList(list1Handle);

    // aktuelles Element ausgeben
    printf("lies aktuelles Element:\n");
    dPtr = traverseList(list1Handle);
    printf("key = %d name = %s\n",dPtr->key, dPtr->name);

    // Daten veraendern
    printf("Veraendere die Daten des aktuellen Elementes in der Liste\n");
    dPtr->key = 200;
    strcpy(dPtr->name,"name200");

    // Liste zum zweiten Mal ausgeben
    printf("2. Lesevorgang:\n");
    printList(list1Handle);
    printf("key = %d name = %s\n",dPtr->key, dPtr->name);

    // Liste zuruecksetzen
    rewindList(list1Handle);
    // zwei Elemente weitergehen
    dPtr = traverseList(list1Handle);
    dPtr = traverseList(list1Handle);
    // Element lesen
    dPtr = readElementList(list1Handle);
    // Bookmark setzen
    printf("Setze Bookmark bei: key = %d name = %s\n", 
                dPtr->key, dPtr->name);
    bm = bookmarkList(list1Handle);

    // neue Daten erzeugen und einfuegen
    d.key = 99;
    strcpy(d.name,"name99");
    insertList(list1Handle,d);

    // Liste zum dritten Mal ausgeben
    printf("3. Lesevorgang:\n");
    printList(list1Handle);

    // zur Bookmark gehen
    gotoBookmarkList(list1Handle,bm);
    dPtr = readElementList(list1Handle);
    printf("Gelesen vom Bookmark: key = %d name = %s\n",
                dPtr->key, dPtr->name);

    // Liste zuruecksetzen
    rewindList(list1Handle);

    // Daten erzeugen und einfuegen
    d.key = 100;
    strcpy(d.name,"name100");
    insertList(list1Handle,d);

    // Liste zum vierten Mal ausgeben
    printf("4. Lesevorgang:\n");
    printList(list1Handle);

    // Daten erzeugen und einfuegen
    d.key = 101;
    strcpy(d.name,"name101");
    insertList(list1Handle,d);

    // Liste zum fuenften Mal ausgeben
    printf("5. Lesevorgang:\n");
    printList(list1Handle);
}

Shade Of Mine

was ist denn jetzt eigentlich genau die Frage?

Dill

ja, wo genau klemmts? ist dir nicht klar _worauf_ die ptr jeweils zeigen, oder warum man jetzt grade _diesen_ ptr für jenes problem benutzt ...

andro

habe mir jetzt nochmal alles in ruhe angeguckt. Jetzt tun sich mir zwei wichtige Fragen auf.
1.) Der Listhandler dient in diesem Beispiel also dazu, um sich ein paar Zeiger zu ersparen, oder ?
2.)die Funktion void insertList... kann man das mal etwas anschaulicher machen:

// 3. Fall: es gibt mehr als ein Element in der Liste
    // in diesem Fall wird der Nachfolger des neuen Elements das bisher
    // aktuelle (thisElement zeigt auf dessen Vorgaenger!)
    // der Nachfolger des Vorgaengers des aktuellen Elements muss jetzt auf
    // das neu eingefuegte Element zeigen

Was hat hier konkret "thisElement zeigt auf dessen Vorgaenger" für eine Funktion, die ja auch im Listhandler verankert ist.?

Jede Hilfe kommt mir gelegen.

Dill

struct element *thisElement; /*Zeiger auf den Vorgänger*/

die sache mit dem "vorgänger" ist verwirrend. das ist im kontext mit der verwendung in den funktionen gemeint. eigentlich zeigt er nur auf irgendein element, nach dem einfügen etwa auf das grade eingefügte element.
und für das nächste element das eingefügt wird ist es dann eben der vorgänger, da das neue hinter h->thiselement eingefügt wird.

else {

    /*noch hängt l in der luft, wurde zwar gemalloced aber hat kein      
      vorgänger/nachfolger*/

    l->next = h->thisElement->next;
    /*jetzt hat l ein nachfolger, es zeigt auf den ehem nachfolger von 
      h->thisElement*/

    h->thisElement->next = l;
    /*jetzt wird "zeigt auf dessen vorgänger" klar 
      h->thisElement->next zeigt auf l, also ist es jetzt der vorgänger*/ 
    }

    // zu guter Letzt wird der Vorgaenger des aktuellen Elements
    // auf das neu eingefuegte Element gesetzt
    h->thisElement = l;
    /*und ist dann wieder slbst ein vorgänger für neue elemente*/

hmm weiss nicht obs nur mir so geht, finde die kommentierung (total konfus und verwirrend) und die datenstruktur (langweilig: elemente werden willkürlich eingesetzt) sehr seltsam.

kann dir nur nochmal www.pronix.de ans herz legen.

Dill

Original erstellt von andro:
**Was hat hier konkret "thisElement zeigt auf dessen Vorgaenger" für eine Funktion, die ja auch im Listhandler verankert ist.?

**

ist die funktion klargeworden?
man braucht halt nen anker, an den man das neue ele anhängen kann.
und das ist hier halt h->thisElement. gleichzeitig kann es auch noch den nachfolger für das neue ele liefern nämnlich h->thisElement->next

nach dem eifügen sieht das dann so aus:

h->thisElement->l->h->thiselement->(natürlich jetzt EX-)next

andro

hi,
deine comments gefallen mir auch besser, aber ich habe das thema insgesamt noch nicht verstanden, vielleicht liegts wirklich noch an den basics und damit die klar sind, frage ich lieber nochmal nach.

geg:
h->thisElement->next = l;
/*jetzt wird "zeigt auf dessen vorgänger" klar h->thisElement->next zeigt auf l, also ist es jetzt der vorgänger*/

meine verständnis:
h ist der kopfzeiger, der auf das erste element (thisElement) zeigt, dessen zeiger next wieder auf irgendwas zeigt stimmt doch, oder ?

aber warum: h->thisElement->next zeigt auf l ??? Ist das nicht wie a=b, so dass a der wert von b zugewiesen wird und kein Zeiger... Habe Probleme mit der Syntax

grüsse und danke für die geduld.

[ Dieser Beitrag wurde am 04.05.2003 um 18:31 Uhr von andro editiert. ]

andro

should i rtfm ?

Dill

Original erstellt von andro:
should i rtfm ?

RTFM: www.pronix.de --> std C --> Einführung in Pointer

Dill

du solltest dir vor allem mal klarmachen was der -> operator macht