void Parameter speichern (Listen)

Harbor

Hallo, ich bin leider noch relativ neu in dem Gebiet von C.
Wir haben eine Hausaufgabe aufbekommen, wobei wir eine doppelte, verkettete Liste erstellen sollen. Dafür wurde uns ein Headerfile gegeben.

typedef struct
{
    void *pData;
    struct tCnct *next;
    struct tCnct *prev;
}tCnct;/* Datentyp fuer Connector */

typedef struct
{
    tCnct *anfang;
    tCnct *ende;
    tCnct *current;

}tList;	/* Datentyp fuer die Liste */

typedef struct
{
    char *Name;
    char *Vorname;
    int tel;
}tData;

int insertBehind  (tList* pList, void *pItemIns);

Nun habe ich bereits eine Liste erstellt und diese verkettet.
Die Frage ist nun, ich übergebe als 2. Parameter eine Struktur vom Typ tData. Wie Speicher ich diese? Muss ich da irgendwas fasten?

Meine Main

int main(int argc, const char * argv[])
{

    tList *ptmp;
    tData *tmp = malloc(sizeof(tData));

    tmp->Name = "xxx";
    tmp->Vorname = "wdsf";
    tmp->tel = 123;

    ptmp = createList();

    insertBehind(ptmp, &tmp);

Und die Listenfunktion

int insertBehind (tList* pList, void *pItemIns)
{
    tCnct *new;

    if(pList->ende == NULL) // Es gibt noch keine Elemente in der Liste
    {
        new = malloc(sizeof(tCnct));
        if(new == NULL) return 1;

        new->pData = (tData*)pItemIns;

        pList->anfang = pList->current = pList->ende = new; // Speicheradresse von "new" auf alle Elemente zuordnen

    }else // Es gibt schon ein Element
    {
        tCnct *ptr, *ptr2;

        ptr = pList->anfang; // Anfangsadresse holen
        while(ptr->next != NULL) // Pürfen, ob ein weiteres Element existiert
            ptr = ptr->next;

        ptr2 = ptr;

        new = malloc(sizeof(tCnct));
        if(new == NULL) return 1;

        ptr2->next = new;
        new->pData = pItemIns;
        pList->ende = pList->current = new;
        new->prev = ptr2;

    }
    return 0;
}

Habe da echt keine Idee, denn im Debugger sehe ich nur eine Adresse, wohin der Pointer zeigt.

Danke

http://img5.fotos-hochladen.net/thumbnail/bildymxwz6jfo8_thumb.jpg

Bashar

Harbor schrieb:

int main(int argc, const char * argv[])
{
    
    tList *ptmp;
    tData *tmp = malloc(sizeof(tData));
    
    
    tmp->Name = "xxx";
    tmp->Vorname = "wdsf";
    tmp->tel = 123;
    
    ptmp = createList();
    
    insertBehind(ptmp, &tmp);
//                     ^
//                   ohne &

Harbor

Ok, klappt aber leider immer noch nicht so richtig.
Hier ist nochmal eine Veranschaulichung, falls das Problem nicht verständlich war.

http://img5.fotos-hochladen.net/thumbnail/listelurbwigtno_thumb.jpg

Harbor schrieb:

Die Frage ist nun, ich übergebe als 2. Parameter eine Struktur vom Typ tData.

[quote="Harbor "]Nein, tust du nicht.
Die Funktion insertBehind erwartet einen Zeiger auf irgendein Dataobject.
Du übergibst aber die Adresse von diesem Zeiger (durch das &)

Harbor schrieb:

Wie Speicher ich diese? Muss ich da irgendwas fasten?

Den SPeicher bekommst du an die Funktion übergeben. Da stehen dann ja schon die Daten drin.
In diesem Fall musst du nicht casten, das void-Zeiger in alle anderen konvertierbar sind.

malloc liefert dir einen Zeiger auf den Speicher. Da steht dann irgendwelcher Müll drin.
Du musst immer (auch wenn die Liste leer ist) die next und prev Einträge anpassen.

Weißt du was bei tmp->Name = "xxx"; passiert?
Und viel Spaß mit der Vorwahl bei der Telefonnummer

typedef struct
{
    void *pData; // Der Debugger sieht nur den void-Pointer
    struct tCnct *next;
    struct tCnct *prev;
}tCnct;/* Datentyp fuer Connector */

woher soll der Debugger dann wissen, welchen Datentyp du da abspeicherts.
Du kannst das ja erstmal durch einen tData *pData; ersetzen.
Dann musst du aber tData vor tCnct deklarieren.

Wutz

Die "Design"vorgabe des 2. Parameters als void* ist Naivunsinn deines Lehrers ebenso wie verkettete Listen per se akademische Luftnummern sind.
Solches "Design" nötigt dich zu völlig überflüssigen Zeigercasts. Du schaffst damit unnötige Abhängigkeiten, die leicht zu Fehlern und Unübersichtlichkeit führen.

Wutz schrieb:

... ebenso wie verkettete Listen per se akademische Luftnummern sind.

Das habe ich schon öfter hier im Forum gelesen. Warum eigentlich? Werden verkettete Listen in der Praxis nicht verwendet? Was nimmt man statt dessen?

Gruß
M

Nathan

M^M schrieb:

Wutz schrieb:

... ebenso wie verkettete Listen per se akademische Luftnummern sind.

Das habe ich schon öfter hier im Forum gelesen. Warum eigentlich? Werden verkettete Listen in der Praxis nicht verwendet? Was nimmt man statt dessen?

Gruß
M

Verkette Listen sind sehr schlecht, wenn man regelmäßig auf die Elemente zugreifen will. Sie sind zwar schnell, was das Einfügen angeht, aber der langsame Zugriff ist ein riesiger Nachteil.
Eine Alternative wäre einfach via malloc ein Array anzufordern, sagen wir, was 10 Elemente fasst. Sind 10 Elementen drin, wird ein neues Array angefordert, sagen wir, was 20 Elemente fasst, die Elemente hinüberkopiert und das alte Array freigegeben. Ähnlich bei einer erneuten Vergrößerung. So ein Container bietet konstante Zugriffszeit auf jedes Element und das Anfügen von Elementen am Ende ist auch schnell, so lange kein neues Array angefordert werden muss.

Harbor

Nathan schrieb:

Eine Alternative wäre einfach via malloc ein Array anzufordern, sagen wir, was 10 Elemente fasst. Sind 10 Elementen drin, wird ein neues Array angefordert, sagen wir, was 20 Elemente fasst, die Elemente hinüberkopiert und das alte Array freigegeben. Ähnlich bei einer erneuten Vergrößerung. So ein Container bietet konstante Zugriffszeit auf jedes Element und das Anfügen von Elementen am Ende ist auch schnell, so lange kein neues Array angefordert werden muss.

Wäre es da nicht noch sinnvoller, den Array mit realloc zu erweitern anstatt einen neuen zu erstellen und die Daten rüber zu kopieren?

Nathan schrieb:

Verkette Listen sind sehr schlecht, wenn man regelmäßig auf die Elemente zugreifen will. Sie sind zwar schnell, was das Einfügen angeht, aber der langsame Zugriff ist ein riesiger Nachteil.
Eine Alternative wäre einfach via malloc ein Array anzufordern, sagen wir, was 10 Elemente fasst. Sind 10 Elementen drin, wird ein neues Array angefordert, sagen wir, was 20 Elemente fasst, die Elemente hinüberkopiert und das alte Array freigegeben. Ähnlich bei einer erneuten Vergrößerung. So ein Container bietet konstante Zugriffszeit auf jedes Element und das Anfügen von Elementen am Ende ist auch schnell, so lange kein neues Array angefordert werden muss.

Ok, das verstehe ich ja. Aber was ist, wenn ich ein Element nicht am Ende, sondern irgendwo mittendrin einfügen möchte? Dann bin ich die ganze Zeit nur am rumkopieren.
Oder wenn ein einzelnes Element sehr groß ist und Speicher eine Rolle spielt?

Mir kommt es hier immer so vor, als währen verkettete Listen das Pohlsche Rad der Programmierung, oder (noch schlimmer) ein Instrument inkompetenter Lehrer, mit dem sie ihre Schüler foltern...

Gruß
M

Nathan

Die C++ Standardbibliothek bietet diverse Container:
http://en.cppreference.com/w/cpp/container
An den Beschreibungen sieht man schön die Laufzeitkomplexitäten.
Und wenn man wirklich einen großen Container hat, an dem viel in der Mitte einfügt und die Elemente nur nacheinander durchlaufen muss, dann nimmt man natürlich auch eine Liste.

Nathan schrieb:

Und wenn man wirklich einen großen Container hat, an dem viel in der Mitte einfügt und die Elemente nur nacheinander durchlaufen muss, dann nimmt man natürlich auch eine Liste.

Danke, also doch keine akademische Luftnummer

Gruß
M

Harbor schrieb:

Wäre es da nicht noch sinnvoller, den Array mit realloc zu erweitern anstatt einen neuen zu erstellen und die Daten rüber zu kopieren?

Ja, natürlich. Wenn realloc den Speicherblock allerdings nicht vergrößern kann, allokiert es auch einfach einen neuen und kopiert die Daten rüber. In der Regel erhöht es dabei die Größe um mehr als angefordert, damit nachfolgende Aufrufe ohne Kopieren durchgeführt werden können. Also in etwa das was Nathan beschrieben hat.

SeppJ

M^M schrieb:

Danke, also doch keine akademische Luftnummer

Ich fürchte, in den meisten Fällen doch. Denn der Fall, dass man oft (oder überhaupt) etwas in der Mitte eines Containers einfügen möchte ist praktisch eben extrem selten. Ich programmiere eine ganze Weile und es ist, wenn ich mich recht erinnere, mir noch nie vorgekommen, dass eine verkettete Liste die beste Wahl war. Wenn man nämlich etwas in der Mitte einfügen will, dann weil der Container nach irgendeinem Kriterium sortiert ist. In dem Fall gibt es aber wesentlich bessere Datenstrukturen.