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

[roadracer]

Hallo,
ich benutze eine dynamische Datenstruktur, in der ich Fehlermeldungen speichere. Die Struktur sieht so aus:

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:

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
helper2 = helper1->previous; und
helper1 = helper2->previous;, aber z.B. nicht bei
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.

[sommerfee]

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".



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?



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!?

[roadracer]

Danke schon mal. Das mit dem struct err_mesg war ja mal wieder klar. :cool: 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
v = f(v); etwas unübersichtlich. :p

[peschmae]

Danke schon mal. Das mit dem struct err_mesg war ja mal wieder klar. :cool: 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ä

[msi]

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.

[roadracer]

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.

[quinte17]

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?


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?

[msi]

sry, aber kommt das nicht _stark_ auf die implementierung an?


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.

[quinte17]

deine einfache verkettete liste funktioniert so leider nicht.

soll ich dir jetzt auch noch funktionnen schreiben, damit du siehst dass die funktioniert?


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.

[msi]

soll ich dir jetzt auch noch funktionnen schreiben, damit du siehst dass die funktioniert?


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).

[quinte17]

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.

[msi]

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)

[quinte17]

klar kann ich mir diese fälle vorstellen, aber für fehlerlisten ist ein fifo doch das mittel der wahl oder nicht?

[roadracer]

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