1. Dashboard
  2. Forum
    1. Unerledigte Themen
  3. Mitglieder
    1. Letzte Aktivitäten
    2. Benutzer online
    3. Team-Mitglieder
    4. Trophäen
    5. Mitgliedersuche
  4. Tutorial Bereich
  • Anmelden
  • Registrieren
  • Suche
Dieses Thema
  • Alles
  • Dieses Thema
  • Dieses Forum
  • Seiten
  • Forum
  • Lexikon
  • Erweiterte Suche
  1. Informatik Forum
  2. Webmaster & Internet
  3. Entwicklung

Art "ArrayList" in C

  • xruxl
  • 12. November 2009 um 20:48
  • Unerledigt
  • xruxl
    3
    xruxl
    Mitglied
    Punkte
    65
    Beiträge
    8
    • 12. November 2009 um 20:48
    • #1

    Ich brauche eine Art "ArrayList", in der ich eine unbestimmte Anzahl von Strings speichern kann. Ich hab mir dazu eine Lösung überlegt, die auch funktioniert, aber ich weiß nicht ob das vom Konzept her so richtig ist.

    Das Konzept (vereinfacht):

    Code
    **char liste = NULL;
    
    
    //Einlesen
    int numElements = 0;
    while (/* lese Eingabedaten */) {
       numElements++;
       liste = realloc(liste, sizeof(*char)*numElements);
       strncopy(*(liste + numElements - 1), /* Eingabe */, MAXLENGTH);
    }
    
    
    //Ausgabe
    int i;
    for (i = 0; i < numElements; i++) {
       fprintf(stdout, "%s", *(liste + numElements));
    }
    
    
    //Speicher löschen
    for (i = 0; i < numElements; i++) {
       free(*(liste + numElements));
    }
    
    
    free(liste);
    Alles anzeigen

    Besonders das Speicherfreigeben ist mir auch noch nicht ganz klar. Die Schleife um den Speicher für die einzelnen Strings freizugeben ist meiner Meinung nach nötig, weil sonst nur die Pointer auf die Strings gelöscht werden, stimmt das? Und gibt realloc() den alten Speicherbereich (wenn verschoben) selbst wieder frei oder muss ich das machen?

  • Plantschkuh!
    24
    Plantschkuh!
    Mitglied
    Reaktionen
    163
    Punkte
    6.173
    Beiträge
    1.181
    • 12. November 2009 um 21:58
    • #2
    Zitat von xruxl
    Code
    numElements++;
       liste = realloc(liste, sizeof(*char)*numElements);


    Das ist vom Konzept her richtig, kann aber bei sehr vielen Elementen ziemlich lahm werden: realloc muß immer wieder alle "alten" Elemente kopieren, im Allgemeinen werden quadratisch viele Elemente kopiert werden. Der gängige Ratschlag ist, die Größe der Liste bei Bedarf exponentiell steigen zu lassen, indem man bei jedem realloc doppelt so viel anlegt wie beim letzten; dann verschwendet man im schlimmsten Fall gleich viel Speicher wie man verwendet, aber man braucht nur logarithmisch viele Aufrufe von realloc und dementsprechend nur O(N log N) Kopien (für N = numElements).

    Solche Optimierungen kann man sich aber für später aufheben.

    Zitat
    Code
    strncopy(*(liste + numElements - 1), /* Eingabe */, MAXLENGTH);


    Als erstes Argument meinst du liste[numElements - 1]. Das ist mit deinem Ausdruck zu 100% gleichbedeutend, aber es ist für Menschen lesbarer. Und natürlich mußt du das Element liste[numElements - 1] auch irgendwie initialisieren, z.B. mit malloc. Du mußt dann auch nicht unbedingt strncpy und MAXLENGTH verwenden. Und: Überleg dir, was passiert, wenn die Eingabe MAXLENGTH oder mehr Zeichen enthält (falls das überhaupt möglich ist).

    Abgesehen davon ist an dieser Zeile nichts auszusetzen :)

    Zitat
    Code
    for (i = 0; i < numElements; i++) {
       free(*(liste + numElements));
    }


    Du meinst liste[i], nicht liste[numElements]. Und ja, das geht so, wenn du oben jedes Element der Liste mit malloc, calloc oder realloc initialisierst.

    Zitat
    Code
    free(liste);


    Sehr brav :)

    Zitat

    Und gibt realloc() den alten Speicherbereich (wenn verschoben) selbst wieder frei oder muss ich das machen?


    realloc macht das für dich.

    *plantsch*

  • Kampi
    27
    Kampi
    Mitglied
    Reaktionen
    193
    Punkte
    7.828
    Beiträge
    1.468
    • 12. November 2009 um 22:17
    • #3

    vielleicht noch ein paar hints damit du weiszt wo man sich solche fragen selbst beantworten kann:

    double-size-realloc: okay, wenn man genug code liest stolpert man drueber, eben einer dieser klassichen tricks.

    pointer und arrays: dazu gibt es ein kapitel auf der auch sonst empfehlenswerten seite c-faq.com (leider im moment offline :-/ )

    wie verhaelt sich <insert glibc function here>: "man <insert glibc function here>" da steht zum beispiel ganz klar:

    Zitat von man realloc


    If the area pointed to was moved, a free(ptr) is done.

    [edit]und damit ich etwas neues beitrage fuers selbststudium: warum ist prefix ++ besser als postfix und warum ist es in dem fall vollkommen egal[/edit]

    Willfähriges Mitglied des Fefe-Zeitbinder-Botnets und der Open Source Tea Party.

    Einmal editiert, zuletzt von Kampi (12. November 2009 um 22:26)

  • Maximilian Rupp 27. Dezember 2024 um 00:26

    Hat das Thema aus dem Forum Programmieren nach Entwicklung verschoben.

Jetzt mitmachen!

Sie haben noch kein Benutzerkonto auf unserer Seite? Registrieren Sie sich kostenlos und nehmen Sie an unserer Community teil!

Benutzerkonto erstellen Anmelden

Rechtliches

Impressum

Datenschutzerklärung