Anzeige:
Ergebnis 1 bis 14 von 14

Thema: [C] Zu dumm für Zeiger in dynamischen Datenstrukturen

  1. #1
    Registrierter Benutzer Avatar von roadracer
    Registriert seit
    16.02.2010
    Ort
    Wolfenbüttel
    Beiträge
    48

    [C] Zu dumm für Zeiger in dynamischen Datenstrukturen

    Hallo,
    ich benutze eine dynamische Datenstruktur, in der ich Fehlermeldungen speichere. Die Struktur sieht so aus:
    Code:
    struct err_msg {
        char *errorstring;
        int failure;
        struct err_mesg *next;
        struct err_mesg *previous;
    };
    Ich möchte jetzt einfach nachdem ich alle Elemente angehängt habe über die previous-Zeiger wieder zu ersten Element springen. Dazu habe ich folgende Funktion geschrieben:
    Code:
    void goto_first_element(struct err_msg **element) {
        struct err_msg *helper1, *helper2;
        helper1 = *element;
        while (helper1->previous != NULL) {
            helper2 = helper1->previous;
            if (helper2->previous == NULL)
                break;
            else
                helper1 = helper2->previous;
        }
        *element = helper1;
    }
    Nun bekomme ich aber immer wenn ich den Code kompiliere die Warnung: "warning: assignment from incompatible pointer type" für die Zeilen
    Code:
    helper2 = helper1->previous;
    und
    Code:
    helper1 = helper2->previous;
    , aber z.B. nicht bei
    Code:
    helper1 = *element;
    Bevor jetzt jemand sagt ich sollte am einfachsten ein Anfangs-Zeiger benutzen, der hat zwar recht, hat sich aber halt so ergeben und ist eigentlich auch egal, weil ich die selbe Warnung auch in anderen Funktionen mit ähnlicher Funktionsweise bekomme.
    OpenSUSE 12.1 x86 KDE 4.7

    Alle Rechtschreibfehler unterliegen der GFDL und dürfen so oder in veränderter Form genutzt und weiter gegeben werden.

  2. #2
    Registrierter Benutzer Avatar von sommerfee
    Registriert seit
    02.07.2006
    Beiträge
    1.603
    Zitat Zitat von roadracer Beitrag anzeigen
    Code:
    struct err_msg {
        char *errorstring;
        int failure;
        struct err_mesg *next;
        struct err_mesg *previous;
    };
    Oben steht "struct err_msg", aber die Zeiger next und previous verweisen auf "struct err_mesg".

    Code:
    void goto_first_element(struct err_msg **element) {
        struct err_msg *helper1, *helper2;
        helper1 = *element;
        while (helper1->previous != NULL) {
            helper2 = helper1->previous;
            if (helper2->previous == NULL)
                break;
            else
                helper1 = helper2->previous;
        }
        *element = helper1;
    }
    Warum nicht einfach so?

    Code:
    struct err_msg *first_element(const struct err_msg *element)
    {
      while ( element->previous != NULL ) element = element->previous;
      return element;
    }
    Deinen Code verstehe ich auch nicht ganz, der geht doch zum zweiten und nicht zum ersten Element!?

  3. #3
    Registrierter Benutzer Avatar von roadracer
    Registriert seit
    16.02.2010
    Ort
    Wolfenbüttel
    Beiträge
    48
    Danke schon mal. Das mit dem struct err_mesg war ja mal wieder klar. Aber wieso gibt der Compiler keine Fehlermeldung aus? Es existiert ja kein struct err_mesg.

    Und du hast auch recht, meine Funktion springt nur bis zum zweiten Element. Logikfehler. Ist aber auch das erste mal, das ich dynamische Datenstrukturen verwende, also wird's beim nächsten mal hoffentlich besser.
    Und warum ich das mit call-by-reference impletiert habe und nicht mit dem Rückgabewert? Ganz einfach ich finde
    Code:
    v = f(v);
    etwas unübersichtlich.
    OpenSUSE 12.1 x86 KDE 4.7

    Alle Rechtschreibfehler unterliegen der GFDL und dürfen so oder in veränderter Form genutzt und weiter gegeben werden.

  4. #4
    Registrierter Benutzer Avatar von peschmae
    Registriert seit
    14.03.2002
    Ort
    Schweizland
    Beiträge
    4.549
    Zitat Zitat von roadracer Beitrag anzeigen
    Danke schon mal. Das mit dem struct err_mesg war ja mal wieder klar. Aber wieso gibt der Compiler keine Fehlermeldung aus? Es existiert ja kein struct err_mesg.
    Das ist in C irgendwie mit allem so, C gibt dir nicht nur den Hammer um dir auf den Daumen zu schlagen, es guckt auch noch schadenfroh zu.

    Steht sicher irgendwo im C Standard dass das normale Verhalten bei Pointern auf undeklarierte typen ist, dass er einen Voidpointer draus macht, eventuell auch einen charpointer - ist ja fast dasselbe

    Hab da mal schnell reingeguckt und in C99 auf Anhieb erst mal nichts gefunden. Ist aber auch nicht soo leserlich das Ding.

    MfG Peschmä
    Geändert von peschmae (06-02-2011 um 17:32 Uhr)
    The greatest trick the Devil ever pulled was convincing the world he didn't exist. -- The Usual Suspects (1995)
    Hey, I feel their pain. It's irritating as hell when people act like they have rights. The great old one (2006)

  5. #5
    Registrierter Benutzer
    Registriert seit
    14.01.2002
    Beiträge
    657
    du kannst dir die ganze funktion sparen. schreib einfach immer

    while ( element->previous != NULL ) element = element->previous;


    dann bist du beim ersten element. eine funktion dafür macht doch keinen sinn imo.

    außerdem ist eine verkettete liste extrem ineffizient um an das erste element zu kommen (Komplexität O(n)). Wenn du also diese Operation öfter auf langen Listen ausführst, solltest du dir vllt was anderes überlegen.

  6. #6
    Registrierter Benutzer Avatar von roadracer
    Registriert seit
    16.02.2010
    Ort
    Wolfenbüttel
    Beiträge
    48
    Zitat Zitat von msi Beitrag anzeigen
    außerdem ist eine verkettete liste extrem ineffizient um an das erste element zu kommen (Komplexität O(n)). Wenn du also diese Operation öfter auf langen Listen ausführst, solltest du dir vllt was anderes überlegen.
    Ist eigentlich relativ egal in diesem Fall, ich brauche's nur zum parsen eines config-files. Ich speichere so die ganzen Fehler. Wird alles also nur einmal zur Laufzeit des Programms ausgeführt.
    OpenSUSE 12.1 x86 KDE 4.7

    Alle Rechtschreibfehler unterliegen der GFDL und dürfen so oder in veränderter Form genutzt und weiter gegeben werden.

  7. #7
    Registrierter Benutzer
    Registriert seit
    28.08.2002
    Beiträge
    496
    Zitat Zitat von msi Beitrag anzeigen
    außerdem ist eine verkettete liste extrem ineffizient um an das erste element zu kommen (Komplexität O(n)). Wenn du also diese Operation öfter auf langen Listen ausführst, solltest du dir vllt was anderes überlegen.
    sry, aber kommt das nicht _stark_ auf die implementierung an?
    Code:
    struct liste{
    int element;
    struct liste *next;
    }
    
    struct kopf{
    struct liste *first;
    struct liste *last;
    }
    bei last wird immer eingefügt. und bei first hast immer das erste element wo du auch leicht was rausnehmen darfst. (nur beim erstenmal einfügen muss first und last angepasst werden) somit:
    einfügen = O(1)!
    herausnehmen = O(1)!

    durchsuchen wird dadurch natürlich nicht besser.
    oder übersehe ich hier was?

  8. #8
    Registrierter Benutzer
    Registriert seit
    14.01.2002
    Beiträge
    657
    Zitat Zitat von quinte17 Beitrag anzeigen
    sry, aber kommt das nicht _stark_ auf die implementierung an?
    Code:
    struct liste{
    int element;
    struct liste *next;
    }
    
    struct kopf{
    struct liste *first;
    struct liste *last;
    }
    bei last wird immer eingefügt. und bei first hast immer das erste element wo du auch leicht was rausnehmen darfst. (nur beim erstenmal einfügen muss first und last angepasst werden) somit:
    einfügen = O(1)!
    herausnehmen = O(1)!

    durchsuchen wird dadurch natürlich nicht besser.
    oder übersehe ich hier was?
    deine einfache verkettete liste funktioniert so leider nicht. aber ich denke du meinst eine doppelt verkettete mit

    struct liste{
    int element;
    struct liste *next;
    struct liste *prev;
    }

    Ja so ist die doppelt verkettete Liste auch effizient, allerdings so wie der oP sie implementiert hat, nämlich ohne head und tail pointer nicht, da muss er erst mit kompl. O(n) den anfang/das ende suchen.
    deswegen sag ich ja anderst implementieren.

  9. #9
    Registrierter Benutzer
    Registriert seit
    28.08.2002
    Beiträge
    496
    Zitat Zitat von msi Beitrag anzeigen
    deine einfache verkettete liste funktioniert so leider nicht.
    soll ich dir jetzt auch noch funktionnen schreiben, damit du siehst dass die funktioniert?
    Code:
    struct liste{
    int element;
    struct liste *next;
    };
    
    struct kopf{
    struct liste *first;
    struct liste *last;
    } a;
    
    void insert(int x){
      struct liste *tmp;
      tmp = malloc(sizeof(struct liste));
      tmp->next = NULL;
      tmp->element = x;
      if(!first) // liste leer
      {
        a.first = tmp;
        a.last = tmp;
      }
      else // nicht leer
      {
        (a.last)->next = tmp;
        a.last = tmp;
      }
    }
    
    int get()
    {
      if(!a.first)
        error("liste zu leer");
      struct liste *freeelement;
      int tmp= (a.first)->element;
      freeelement = a.first;
      a.first = (a.first)->next;
      if(a.first == NULL) // letztes element ging raus
        a.last == NULL;
      free(freeelement);
      return tmp;
    }
    nicht kompilegetestet verdeutlicht aber dass es funktioniert.

  10. #10
    Registrierter Benutzer
    Registriert seit
    14.01.2002
    Beiträge
    657
    Zitat Zitat von quinte17 Beitrag anzeigen
    soll ich dir jetzt auch noch funktionnen schreiben, damit du siehst dass die funktioniert?
    Code:
    struct liste{
    int element;
    struct liste *next;
    };
    
    struct kopf{
    struct liste *first;
    struct liste *last;
    } a;
    
    void insert(int x){
      struct liste *tmp;
      tmp = malloc(sizeof(struct liste));
      tmp->next = NULL;
      tmp->element = x;
      if(!first) // liste leer
      {
        a.first = tmp;
        a.last = tmp;
      }
      else // nicht leer
      {
        (a.last)->next = tmp;
        a.last = tmp;
      }
    }
    
    int get()
    {
      if(!a.first)
        error("liste zu leer");
      struct liste *freeelement;
      int tmp= (a.first)->element;
      freeelement = a.first;
      a.first = (a.first)->next;
      if(a.first == NULL) // letztes element ging raus
        a.last == NULL;
      free(freeelement);
      return tmp;
    }
    nicht kompilegetestet verdeutlicht aber dass es funktioniert.

    und wie lösch ich jetzt in O(1) du hast den prev pointer vergessen in der struct. ohne den kannst du nur das erste element der liste in O(1) löschen, für das letzte brauchst du O(n).

  11. #11
    Registrierter Benutzer
    Registriert seit
    28.08.2002
    Beiträge
    496
    man fügt immer HINTEN an
    und nimmt VORNE raus
    da braucht man mal gar keine pointer in beide richtungen. das entspricht einem FIFO. klar, wenn du irgendwo in der mitte löschen willst, oder das gerade eingefügte element, dann wirds unangenehmer.

  12. #12
    Registrierter Benutzer
    Registriert seit
    14.01.2002
    Beiträge
    657
    Zitat Zitat von quinte17 Beitrag anzeigen
    man fügt immer HINTEN an
    und nimmt VORNE raus
    da braucht man mal gar keine pointer in beide richtungen. das entspricht einem FIFO. klar, wenn du irgendwo in der mitte löschen willst, oder das gerade eingefügte element, dann wirds unangenehmer.
    kannst du dir wirklich keinen fall vorstelllen, wo man hinten rausnimmt oder irgendwo in der mitte? da brauchst du dann beide pointer (zB linux prozesslisten)

  13. #13
    Registrierter Benutzer
    Registriert seit
    28.08.2002
    Beiträge
    496
    klar kann ich mir diese fälle vorstellen, aber für fehlerlisten ist ein fifo doch das mittel der wahl oder nicht?

  14. #14
    Registrierter Benutzer Avatar von roadracer
    Registriert seit
    16.02.2010
    Ort
    Wolfenbüttel
    Beiträge
    48
    naja, da ist es glaube ich ziemlich egal ob fifo, lifo, filo, fi oder sonst was, theoretisch reicht ja auch li (last in), dann alle durcharbeiten und am ende alle löschen. fertig
    OpenSUSE 12.1 x86 KDE 4.7

    Alle Rechtschreibfehler unterliegen der GFDL und dürfen so oder in veränderter Form genutzt und weiter gegeben werden.

Lesezeichen

Berechtigungen

  • Neue Themen erstellen: Nein
  • Themen beantworten: Nein
  • Anhänge hochladen: Nein
  • Beiträge bearbeiten: Nein
  •