#include #include /*--- anwendungsspezifischer Datentyp, Beispiel ---*/ typedef struct { char name[50]; unsigned int salary; } my_data_t; /*--- doppelt verzeigerte Liste mit Einträgen des o.g. Datentyps ---*/ struct list_entry_t { my_data_t data; struct list_entry_t *next; struct list_entry_t *prev; }; /*--- list handle ---*/ typedef struct { struct list_entry_t *headMarker; struct list_entry_t *lastMarker; /*--- currentEntry wird so verwendet, dass das nächste zu lesende Datenelement immer unter currentEntry->next zu suchen ist ---*/ struct list_entry_t *currentEntry; unsigned int length; } list_handle_t; /*********************************************************** * Funktionen des Listenpakets * Listen werden hier als ABSTRAKTER DATENTYP (ADT) realisiert: * Die Datenstrukturen der Implementierung sind * versteckt. * Alle Operationen im Anwendungsprogramm werden durch * Aufruf von ZUGRIFFSFUNKTIONEN ausgelöst. * Die Zugriffsfunktionen lassen sich gliedern in * - Konstruktoren: Finktionen zur Erzeugung * einer neuen Instanz des Datentyps * - Observer (Beobachter): "Auskunftsfunktionen", * die Informationen ueber den Inhalt des ADT * geben, ohne die Instanz zu verändern * - Modifier: Funktionen, die den Datentyp ändern ***********************************************************/ list_handle_t *createList(void) { list_handle_t *handle = (list_handle_t *) calloc(1,sizeof(list_handle_t)); handle->headMarker = (struct list_entry_t *) calloc(1,sizeof(struct list_entry_t)); handle->lastMarker = (struct list_entry_t *) calloc(1,sizeof(struct list_entry_t)); handle->headMarker->next = handle->lastMarker; handle->headMarker->prev = handle->headMarker; handle->lastMarker->prev = handle->headMarker; handle->lastMarker->next = handle->lastMarker; handle->currentEntry = handle->headMarker; handle->length = 0; return handle; } /*-------------------------------------------------------*/ int appendToList(list_handle_t *handle, my_data_t *d) { int retval = -1; if ( handle && d ) { struct list_entry_t *entry = (struct list_entry_t *) calloc(1,sizeof(struct list_entry_t)); memcpy(&(entry->data),d,sizeof(my_data_t)); entry->prev = handle->lastMarker->prev; entry->next = handle->lastMarker; handle->lastMarker->prev->next = entry; handle->lastMarker->prev = entry; handle->length++; retval = handle->length; } return retval; } /*--------------------------------------------------------------------*/ int insertToList(list_handle_t *handle, my_data_t *d) { int retval = -1; if ( handle && d ) { struct list_entry_t *entry = (struct list_entry_t *) calloc(1,sizeof(struct list_entry_t)); memcpy(&(entry->data),d,sizeof(my_data_t)); entry->prev = handle->headMarker; entry->next = handle->headMarker->next; handle->headMarker->next->prev = entry; handle->headMarker->next = entry; handle->length++; retval = handle->length; } return retval; } /*------------------------------------------------------------*/ my_data_t* readNextFromList(list_handle_t *handle) { my_data_t *d = NULL; if ( handle && handle->currentEntry->next != handle->lastMarker ) { /* Designentscheidung: Nutzer bekommt einen ZEIGER auf die Nutzdaten des Eintrags. Wenn dieser Eintrag später verändert oder gelöscht wird, findet der Benutzer danach NICHT mehr die ursprünglichen Daten. VORTEIL: Schnelle Operation, unabhängig von der Größe von my_data_t. */ d = &(handle->currentEntry->next->data); handle->currentEntry = handle->currentEntry->next; } return d; } /*--------------------------------------------------------- * Bereits traversierte Liste erneut vom Anfang an lesen *--------------------------------------------------------*/ int rereadList(list_handle_t *l) { int retcode = -1; if ( l ) { l->currentEntry = l->headMarker; retcode = l->length; } return retcode; } /*----------------------------------------------------- * Loesche das zuletzt gelesene Element in der Liste. *----------------------------------------------------*/ int deleteEntry(list_handle_t *l) { int retcode = -1; /*-- currentEntry zeigt auf das zuletzt gelesene Elemement der Liste, oder auf headMarker, wenn noch nichts gelesen wurde. Bedingung "currentEntry zeigt auf Nutzdaten" (und nicht etwa auf den Head Marker) kann durch l->currentEntry != l->headMarker abgefragt werden ---*/ if ( l->currentEntry != l->headMarker ) { struct list_entry_t *p = l->currentEntry; /* loesche currentEntry - currentEntry soll auf den Vorgänger des zu loeschenden Eintrags zeigen */ p->prev->next = p->next; p->next->prev = p->prev; l->currentEntry = p->prev; free(p); retcode = --(l->length); } else printf("cannot delete this entry!\n"); } /*--------------------------------------------------------*/ int getLength(list_handle_t *l) { return ( l ) ? l->length : -1 ; } /******************************************************** * Hauptprogramm *******************************************************/ int main() { int iCnt; list_handle_t *list1, *list2; my_data_t d1, *d2, *d3; list1 = createList(); strcpy(d1.name,"name1"); d1.salary = 1000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); strcpy(d1.name,"name2"); d1.salary = 2000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); strcpy(d1.name,"name3"); d1.salary = 3000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); strcpy(d1.name,"name4"); d1.salary = 4000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); strcpy(d1.name,"name5"); d1.salary = 5000; if ( appendToList(list1,&d1) <= 0 ) printf("Error at appendToList()\n"); strcpy(d1.name,"name0"); d1.salary = 0; if ( insertToList(list1,&d1) <= 0 ) printf("Error at insertToList()\n"); /*--- liste traversieren und Inhalt ausgeben ---*/ printf("*** 1. Listentraversion ***\n"); iCnt = 0; /*--- ACHTUNG: hier ist bewusst eine ZUWEISUNG in der Schleifenbedingung - Abbruch wenn Nullpointer von readNextFromList() zuerueckgegeben wird. ---*/ while ( d2 = readNextFromList(list1) ) printf("GOT ENTRY %d: NAME %s SALARY %d - LIST LENGTH IS %d\n", ++iCnt,d2->name,d2->salary,getLength(list1)); /*--- Liste erneut traversieren und das gelesene Element wieder loeschen ---*/ printf("*** 2. Listentraversion, mit Loeschen ***\n"); rereadList(list1); iCnt = 0; while ( d2 = readNextFromList(list1) ) { printf("GOT ENTRY %d: NAME %s SALARY %d - LIST LENGTH IS %d\n", ++iCnt,d2->name,d2->salary,getLength(list1)); deleteEntry(list1); /*--- Achtung: jetzt ist der Inhalt von d2 verschwunden! ---*/ } printf("LENGTH OF LIST = %d\n", getLength(list1)); }