proggen.org

Verfasst: **Mo Nov 07, 2016 1:47 pm**

Ich babe derzeit ein kleinees Problem mit diesem C Code:

typedef struct listEntry {
    int value;
    struct listEnry *next;
} listEntry;

// Ausgangselement: Zeiger auf das erste Element
static struct listEntry *begin = NULL;

void initList(void) {
    begin = (listEntry*) malloc(sizeof(struct listEntry));
    begin->next = NULL;
}

void insert(int value) { //
    listEntry *prevEl;
    listEntry *iterEl = begin;
    listEntry *newEl = (listEntry*) malloc(sizeof(struct listEntry));
    newEl->value = value;

    /*
     * Ueber die Elemente iterieren
     */
    while(iterEl->next != NULL) {
        prevEl = iterEl;
        iterEl = iterEl->next;
        if(iterEl->value > value)
            break;
    }

    if(prevEl == begin) { // 4, -1, 0 fuehrt zu Fehler
        newEl->next = begin->next;
        begin->next = newEl;
    } else if(iterEl->next == NULL) {
        iterEl->next = newEl;
        newEl->next = NULL;
    } else {
        newEl->next = prevEl->next;
        prevEl->next = newEl;
    }
}

Ich wollte eine sortierte einfach verkettete erstellen, also wo man nur einen Zeiger auf das naechste Element hat und wo man keinen Zeiger auf den Vorgänger hat und es funktioniet auch alles, bis auf die insert Methode (Ja, das aber ...

).

Ich rufe dabei die insert Methode mit den Werten 4, -1 und 0 auf und dabei sollten die Elemente ja eigentlich immer sortiert sein, also von kleiner nach größer (-1, 0, 4) und bei 4 und der -1 läuft das auch noch aber aber wenn ich die 0 eingebe, steht diese plötzlich am Ende, statt hinter der -1. Das funktioniet auch bei alle anderen Werten nicht, wenn ich zwei Zahlen eingebe und eine Zahl dazwischen, die dann größer als die erste und kleiner als die zweite ist aber ich sehe den Fehler nicht? Was mache ich falsch?

Bei Bedarf kann ich auch das ganze Projekt hochladen. Eine Sache fällt mir da auch noch ein, und zwar habe ich unter anderem in der Zeile

Code: Alles auswählen

iterEl = iterEl->next;

den Fehler

Code: Alles auswählen

assignment from incompatible pointer type [enabled by default]

aber das sind doch die selben Typen oder nicht?
Kann man die insert Methode evtl. auch noch ein wenig vereinfachen oder passt das so wohl?

Verfasst: **Mo Nov 07, 2016 6:47 pm**

Hast Du schon einmal einen Debugger benutzt? Dafür sind solche Programme da, um andere Programme nach Fehlern zu untersuchen. Du kannst Dir den Inhalt von Variablen anzeigen lassen, Programme Schritt für Schritt ablaufen lassen, Dir den Callstack anschauen (welche Funktion hat welche Funktion aufgerufen?)

Falls Du keinen Debugger hast, dann kannst Du auch die Variableninhalte in eine Datei schreiben.

Das einzige Problem, wenn unlösbar erscheinende Probleme auftreten ist der Mangel an Informationen! Das ist wie in einer Beziehungskriese. Mehr Kommunikation löst alle Probleme.

Schau Dir auch Beispiele andere Programmierer an zu deinem Thema, und vergleiche die Lösungswege.

https://perlgeek.de/de/artikel/einfach- ... ete-listen

Verfasst: **Di Nov 08, 2016 12:52 am**

Zenerid hat geschrieben:Ich babe derzeit ein kleinees Problem mit diesem C Code:

Ich wollte eine sortierte einfach verkettete erstellen, also wo man nur einen Zeiger auf das naechste Element hat und wo man keinen Zeiger auf den Vorgänger hat und es funktioniet auch alles, bis auf die insert Methode (Ja, das aber ... ).

Ich rufe dabei die insert Methode mit den Werten 4, -1 und 0 auf und dabei sollten die Elemente ja eigentlich immer sortiert sein, also von kleiner nach größer (-1, 0, 4) und bei 4 und der -1 läuft das auch noch aber aber wenn ich die 0 eingebe, steht diese plötzlich am Ende, statt hinter der -1. Das funktioniet auch bei alle anderen Werten nicht, wenn ich zwei Zahlen eingebe und eine Zahl dazwischen, die dann größer als die erste und kleiner als die zweite ist aber ich sehe den Fehler nicht? Was mache ich falsch?

Ich weiß ja nicht, wie Du die Aufrufe machst, aber ich gehe mal davon aus, dass Du die init-Routine aufrufst. Die Init-Routine belegt "begin" mit einem Listenelement, dessen Wert nicht initialisiert ist und keinen Nachfolger hat.

Anschließend gehe ich davon aus, dass Du eine beliebige Zahl mit insert einfügst. iterEl ist dann das mit initList angelegte Element, dessen Nachfolger Null ist.

Code: Alles auswählen

void insert(int value) { //
    listEntry *prevEl;
    listEntry *iterEl = begin;
    listEntry *newEl = (listEntry*) malloc(sizeof(struct listEntry));
    newEl->value = value;

    /*
     * Ueber die Elemente iterieren
     */
    while(iterEl->next != NULL) {

Also ist next == NULL, weswegen folgende Zeilen nicht ausgeführt werden.

Code: Alles auswählen

        prevEl = iterEl;
        iterEl = iterEl->next;
        if(iterEl->value > value)
            break;
    }

prevEl ist also nie initialisiert worden, weswegen diese Zeile irgendwas macht, aber keiner weiß, was:

Code: Alles auswählen

    if(prevEl == begin) { // 4, -1, 0 fuehrt zu Fehler
        newEl->next = begin->next;
        begin->next = newEl;
    }

Wahrscheinlich ist die Bedingung falsch, aber folgende ist dann erstmal richtig:

Code: Alles auswählen

else if(iterEl->next == NULL) {
        iterEl->next = newEl;
        newEl->next = NULL;
    } else {
        newEl->next = prevEl->next;
        prevEl->next = newEl;
    }
}

Da besteht also noch Handlungsbedarf.

Zenerid hat geschrieben:Eine Sache fällt mir da auch noch ein, und zwar habe ich unter anderem in der Zeile
Code: Alles auswählen
iterEl = iterEl->next;
den Fehler
Code: Alles auswählen
assignment from incompatible pointer type [enabled by default]

Vermutlich, weil Du einmal den per typedef definierten Typ nutzt und einmal struct listEntry.
Nutze entweder immer listEntry oder immer struct listEntry.

Zenerid hat geschrieben: Kann man die insert Methode evtl. auch noch ein wenig vereinfachen oder passt das so wohl?

Warum hast Du die Init-Methode?

Eigentlich hast Du nur zwei Fälle: Du musst es irgendwo einfügen, wo Du den next-Pointer setzen musst oder hinten, wo er Null ist. Du betrachtest drei Fälle und Deine Init Methode ist fraglich.
Da geht noch was

Verfasst: **Fr Nov 11, 2016 1:18 am**

@Necip
Ja, der Debugger ist mir durchaus bekannt aber Pointer zu debuggen finde ich schon sehr schwierig oder kann man sich das irgendwie grafisch darstellen lassen? Pointer zeigen ja schließlich nur auf Speicheradressen. Was mir da eher hilft, ist das ganze mal aufzuzeichnen. Das Problem ist ja auch vergleichsweise noch einfacher aber irgendwie kam ich nicht auf den Fehler. Das mit den Pointern so gedanklich durchzuspielen ist schon so ne Sache, finde ich zumindest.

Xin hat geschrieben:Ich weiß ja nicht, wie Du die Aufrufe machst, aber ich gehe mal davon aus, dass Du die init-Routine aufrufst. Die Init-Routine belegt "begin" mit einem Listenelement, dessen Wert nicht initialisiert ist und keinen Nachfolger hat.

Anschließend gehe ich davon aus, dass Du eine beliebige Zahl mit insert einfügst. iterEl ist dann das mit initList angelegte Element, dessen Nachfolger Null ist.

Die Annahmen sind alle richtig, wobei das iterEl auch zum iterieren über die Liste benutzt wird. Das kann man doch so sagen, oder nicht?
Die init-Methode ist ja auch beim Code dabei aber ich wollte jetzt nicht noch die main Methode hier mit einfügen. Ich habe es auch mittlerweile (denke ich), fertig. Ich habe jetzt mal einige Fälle getestet und es scheint zu funktionieren.

Xin hat geschrieben:Vermutlich, weil Du einmal den per typedef definierten Typ nutzt und einmal struct listEntry.
Nutze entweder immer listEntry oder immer struct listEntry.

Es lag nicht daran, was ich auch erst noch nach dem schreiben dachte. Aber es lag an der struct Definiton.:

Code: Alles auswählen

struct listEnry *next;

wenn man da mal genau hinschaut, sieht man, dass da ein t bei Entry fehlt. Achja, das ist dann wohl mal wieder C-typsich? Es gab nur diese Warnings aber keinen Syntax Fehler oder Fehler nachher bei der Programmausführung.

Xin hat geschrieben:Warum hast Du die Init-Methode?

Naja, einfach nur um die Liste zu initialisieren. Ich wollte das einfach alles schön getrennt haben. Ich habe derzeit auch nur eine Liste, aber warscheinlich wäre es besser, wenn man das initialisierte Listenelement, also den Anfang zurückgibt. Dann könnte man auch mehrere Listen erstellen und diese vielleicht nachher auch noch miteinander verketten oder ähnliches. Das mache ich glaube ich auch einmal.

Jetzt sieht die insert Methode so aus:

Code: Alles auswählen

void insert(int value) {
    listEntry *prevEl;
    listEntry *iterEl = begin;
    listEntry *newEl = (listEntry*) malloc(sizeof(listEntry));
    newEl->value = value;

    if(!isempty()) {
        prevEl = iterEl;
        /*
         * Ueber die Elemente der Liste iterieren
         */
        while(iterEl->next != NULL) {
            prevEl = iterEl;
            iterEl = iterEl->next;
            if(iterEl->value > value)
                break;
        }

        if(iterEl->next == NULL && value > iterEl->value) {
            iterEl->next = newEl;
            newEl->next = NULL;
        } else { 
            prevEl->next = newEl;
            newEl->next = iterEl;
        }
    } else {
        iterEl->next = newEl;
        newEl->next = NULL;
    }
}

Was haltet ihr bzw. du davon? Ist es so besser oder kann man da noch etwas vereinfachen oder sonst noch irgendwie etwas verbessern? Ich habe auch schon darüber nachgedacht, wie man da vielleicht noch etwas verbessern könnte aber mir fällt da so nichts zu ein.

Verfasst: **Fr Nov 11, 2016 1:14 pm**

Was hältst Du davon?

Code: Alles auswählen

#include <stdio.h>
#include <stdlib.h>

struct listEntry {
    int value;
    struct listEntry *next;
};

static struct listEntry * begin;

void initList()
{
  begin = NULL;
};

void show()
{
  for( struct listEntry * it=begin; it; it=it->next )
    printf( "Element: %d\n", it->value );
}

void insert( int value )
{
  struct listEntry ** pIt = &begin;
  struct listEntry * newElem = (struct listEntry *) malloc( sizeof(struct listEntry) );
  newElem->value = value;

  while( *pIt && (*pIt)->value < value )
    pIt = &(*pIt)->next;

  newElem->next = *pIt;
  *pIt = newElem;
}

int main( void )
{
  initList();
  insert( 4 );
  insert( -1 );
  insert( 0 );

  show();

  return EXIT_SUCCESS;
}

proggen.org

Einfache verkettete (sortierte) Liste

Einfache verkettete (sortierte) Liste

Re: Einfache verkettete (sortierte) Liste

Re: Einfache verkettete (sortierte) Liste

Re: Einfache verkettete (sortierte) Liste

Re: Einfache verkettete (sortierte) Liste