Besste verkette Liste
-
Hallo,
ich wollte mal einen Thread aufmachen, in dem alle die Möglichkeit haben,
die besste Implementierung einer einfach verketteten Liste inkl. aller Grundfunktionen (goTop, goBottom, goNext, addElement, deleteElement, deleteList, sortList, etc.) zu suchen.Ich habe eine nicht wirklich schnelle Variante:
/****************************************************************************** * * * Funktion: goNext * * * *******************************************************************************/ Typen* goNext(Typen *temp) { if(temp -> next != NULL) return(temp -> next); else return(temp); } /* Ende von Funktion goNext(Typen *temp) */ /****************************************************************************** * * * Funktion: goTop * * * *******************************************************************************/ Typen* goTop(Typen *temp) { temp = ende; return(temp); } /* Ende von Funktion goTop(Typen *temp) */ /****************************************************************************** * * * Funktion: goBottom * * * *******************************************************************************/ Typen* goBottom(Typen *temp) { temp = anfang; return(temp); } /* Ende von Funktion goBottom(Typen *temp) */ /****************************************************************************** * * * Funktion: initList * * * *******************************************************************************/ Typen* initList() { // Lege eine neue Liste an und reserviere Speicher struct Typen *temp; temp = (Typen*) MALLOC (sizeof(Typen)); temp -> name = (char*) MALLOC (sizeof(char)); temp -> name = NULL; temp -> next = NULL; // Setze die Zeiger um anfang = temp; ende = temp; return(temp); } /* Ende von Funktion initList() */ /****************************************************************************** * * * Funktion: addList * * * *******************************************************************************/ Typen* addList(char* type_name, Typen *alt) { alt = goTop(alt); // Rueckgabevariable struct Typen *temp = NULL; temp = (Typen*) MALLOC (sizeof(Typen)); temp -> name = (char*) MALLOC ((strlen(type_name)); strcpy(temp -> name,type_name); // Setze die Zeiger um temp -> next = NULL; alt -> next = temp; ende = temp; return(temp); } /* Ende von Funktion addList(char* type_name, Typen *alt) */ /****************************************************************************** * * * Funktion: deleteTypen * * * *******************************************************************************/ Typen* deleteTypen(Typen *aktuell) { // Rueckgabevariable Typen *temp; aktuell = goBottom(aktuell); // Wenn es ein Element gibt if(aktuell->next!=NULL) { // Solange es ein uebernaechstes Element gibt, gehe vor while(aktuell->next->next != NULL) aktuell = goNext(aktuell); // temp ist jetzt das vorletzte Element temp = aktuell; // aktuell zeigt auf das letzte Element aktuell = goNext(aktuell); // setze die Zeiger um temp->next = NULL; ende = temp; // gebe den Speicher des letzten elementes wieder frei free(aktuell); // gebe das (ehemals) vorletzte Element zurueck return(temp); } /* Ende von if(aktuell->next!=NULL) */ else { return(aktuell); } } /* Ende von Funktion deleteTypen(Typen *aktuell) */ /****************************************************************************** * * * Funktion: writeList * * * *******************************************************************************/ void writeList(Typen *temp) { // Temporaere Laufvariable int x=1; FILE *f_ptr; f_ptr=fopen(FILENAME, "w"); /* a+ */ if(f_ptr==NULL) { if(dbug) fprintf(stderr,"Datei wurde nicht erstellt.\n"); } else { if(dbug) fprintf(stderr,"Datei wurde erstellt.\n"); } // Gehe an den Anfang der linearen Liste temp = goBottom(temp); // Gehe zum naechsten Element --> da das erste Element ein Dummy- // Element ist temp = goNext(temp); // Schreibe jedes Element in die temporaere Textdatei do { if(temp->next != NULL) { fprintf(f_ptr,"%s\n",temp->name); temp = goNext(temp); } else { fprintf(f_ptr,"%s\n",temp->name); x=0; } }while(x); fclose(f_ptr); } /* Ende von Funktion writeList(Typen *temp) */ /****************************************************************************** * * * Funktion: writeEinElementInListe * * * *******************************************************************************/ void writeEinElementInListe(Typen *temp) { FILE *f_ptr; f_ptr=fopen(FILENAME,"a+"); if(f_ptr==NULL) { if(dbug) fprintf(stderr,"Datei wurde nicht erstellt.\n"); } else { if(dbug) fprintf(stderr,"Datei wurde erstellt.\n"); } temp = goTop(temp); // Schreibe das letzte (also das aktuellste) // Element der Liste in die Textdatei fprintf(f_ptr,"%s\n",temp->name); fclose(f_ptr); } /* Ende von Funktion writeEinElementInListe(Typen *temp) */ /****************************************************************************** * * * Funktion: readList * * * *******************************************************************************/ Typen* readList(Typen *temp) { FILE *f_ptr; char name[80]; f_ptr = fopen(FILENAME, "r"); temp = goTop(temp); if(f_ptr!=NULL) { fscanf(f_ptr,"%s\n", name); temp = addList(name,temp); while(!feof(f_ptr)) { fscanf(f_ptr,"%s\n", name); temp = addList(name,temp); } fclose(f_ptr); } else if(dbug) fprintf(stderr,"Datei konnte nicht gelesen werden.\n"); return(temp); } /* Ende von Funktion readList(Typen *temp) */
-
Ich habe die Struktur vergessen:
typedef struct Typen { char* name; struct Typen *next; }Typen;
-
Auf jeden Fall solltest du 'anfang' und 'ende' zu einer eigenen struct (z.B. 'liste') zusammenfassen und diese dann den ganzen Funktionen mitgeben. Außerdem fehlt noch eine Suchmöglichkeit sowie eine Funktion, um etwas in der Mitte anhängen oder löschen zu können.
PS: Und addList reserviert ein Byte zu wenig für die Daten.