list.c

Denna kod är public domain. Om ni hittar fel eller vill ändra något i koden blir jag jätteglad om ni skickar dessa ändringar till jesper [at] fantasi [punkt] se.


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

/**
 * Ett element i listan. Har en referens till data och en till nsta
 * element i listan.
 */
typedef struct Element
{
   void* data;
   struct Element* next;
} Element;

/**
 * Datastrukturen fr listan. Hller ordning p listans lngd och
 * huvudet fr sjlva listan.
 */
typedef struct List
{
   int length;
   Element* list;
} List;

/**
 * En iterator ver listan. Utver referensen till det aktuella
 * elementet behver vi ven hlla ordning p det tidigare elementet
 * fr att kunna radera element.
 */
typedef struct Iterator
{
   Element** prev;
   Element** curr;
} Iterator;


/**
 * Skapa en ny lista.
 */
List* listNew(void)
{
   return (List*)calloc(1, sizeof(List));
}

/**
 * Lgg in ett element frst i listan.
 */
void listAdd(List* list, void* data)
{
   Element* elem = malloc(sizeof(Element));

   if (elem != NULL)
   {
      list->length++;
      elem->data = data;
      elem->next = list->list;
      list->list = elem;
   }
}

/**
 * Radera ett element i listan givet en referens till elementet.
 * Returnerar det borttagna elementet eller NULL om inget hittades.
 */
void* listRemoveElem(List* list, void* elem)
{
   Element* curr = list->list;
   Element** prev = &(list->list);

   while (curr != NULL && curr->data != elem)
   {
      prev = &(curr->next);
      curr = curr->next;
   }

   if (curr != NULL)
   {
      void* data = curr->data;
      *prev = curr->next;
      free(curr);
      return data;
   }

   return NULL;
}

/**
 * Radera ett element i listan.
 * comp  - En funktion som tar tv referenser till datat som ska jmfras.
 *         Objekten som ska jmfras tas in via void-pekare eftersom listan
 *         r generell och kan hlla vilken typ av data som hellst.
 * value - En referens till ett objekt med samma vrde enligt den givna
 *         komparatorn.
 * Returnerar det borttagna elementet eller NULL om inget hittades.
 * Se exemplet nedan.
 */
void* listRemove(List* list, void* value, int comp(void* a, void* b))
{
   Element* curr = list->list;
   Element** prev = &(list->list);

   while (curr != NULL && comp(curr->data, value) != 0)
   {
      prev = &(curr->next);
      curr = curr->next;
   }

   if (curr != NULL)
   {
      void* data = curr->data;
      *prev = curr->next;
      free(curr);
      return data;
   }

   return NULL;
}

/**
 * Returnerar lngden p listan.
 */
int listLength(List* list)
{
   return list->length;
}

/**
 * Skapar en iterator ver listan. Se exemplet nedan fr att se hur
 * man anvnder en iterator.
 */
void listIteratorInit(Iterator* iter, List* list)
{
   iter->prev = iter->curr = &(list->list);
}

/**
 * Returnerar nsta element i listan givet en iterator.
 */
void* getNext(Iterator* iter)
{
   void* data;

   if (*(iter->curr) == NULL)
      return NULL;

   data = (*(iter->curr))->data;
   iter->prev = iter->curr;
   iter->curr = &((*(iter->curr))->next);
   return data;
}

/**
 * Raderar det senaste elementet som returnerades av getNext.
 */
void removeCurrent(Iterator* iter)
{
   Element* elem = *(iter->prev);

   *(iter->prev) = *(iter->curr);
   iter->curr = iter->prev;

   elem->data = NULL;
   elem->next = NULL;
   free(elem);
}



/**************************************************************/
/** Exempel                                                  **/
/**************************************************************/

/**
 * En funktion som jmfr tv heltal. Talen som jmfrs tas in via
 * argumenten. Notera att funktionen tar pekare som argument. Man
 * mste allts skicka in adresserna till de heltalsvariabler man vill
 * jmfra.
 */
int compareInt(void *a, void *b)
{
   return *(int*)a - *(int*)b;
}

/**
 * Exemplet skapar en lista med 25 heltal. Sedan anvnder den de olika
 * metodrna fr att plocka bort element ur listan. De 25 heltalen
 * lagras hr i en array. Det r endast av bekvmlighetsskl och har
 * ingen betydelse fr listan. Det vanliga r annars att man har en
 * ngot strre datastruktur som man vill lagra i listan och man
 * lgger d in data i listan allt eftersom man skapar dessa
 * datastrukturer.
 */
int main(void)
{
   List* list = listNew();
   Iterator iter;
   int a[25];
   int i;
   int *el;

   /* Skapa listan. Notera att vi skickar in adressen till varje heltal
    * konverterad till en void-pekare.
    */
   for (i = 0; i < 25; i++)
   {
      a[i] = i;
      listAdd(list, (void*)&a[i]);
   }

   /* Skapa en iterator och g igenom listan. Radera var femte element
    * med hjlp av iteratorns remove-funktion.
    */
   listIteratorInit(&iter, list);
   while ((el = (int*)getNext(&iter)))
   {
      printf("[Loop 1] Hittade: %d\n", *el);
      if (*el % 5 == 0)
      {
         removeCurrent(&iter);
         printf("[Loop 1] Tog bort: %d\n", *el);
      }
   }

   /* Radera elementen 24, 21, 1 och 0 med funktionen som tar en
    * direkt adress till elementet som ska raderas.
    */
   (void)listRemoveElem(list, &a[24]);
   (void)listRemoveElem(list, &a[21]);
   (void)listRemoveElem(list, &a[1]);
   (void)listRemoveElem(list, &a[0]);

   /* Skapa en ny iterator och radera alla element som r strre n tio.
    */
   listIteratorInit(&iter, list);
   while ((el = (int*)getNext(&iter)))
   {
      printf("[Loop 2] Hittade: %d\n", *el);
      if (*el > 10)
      {
         removeCurrent(&iter);
         printf("[Loop 2] Tog bort: %d\n", *el);
      }
   }

   /* Radera elementen 4, 6 och 7 med hjlp av funktionen som jmfr
    * tv heltal. Vi skickar allts inte in ngon adress till det som ska
    * raderas, bara ett annat heltal med samma vrde.
    */
   for (i = 4; i < 8; i++)
   {
      if ((el = listRemove(list, &i, &compareInt)) != NULL)
         printf("[Loop 3] Tog bort: %d\n", *el);
   }

   /* Radera alla element som finns kvar.
    */
   listIteratorInit(&iter, list);
   while ((el = (int*)getNext(&iter)))
   {
      printf("[Loop 4] Hittade: %d\n", *el);
      removeCurrent(&iter);
      printf("[Loop 4] Tog bort: %d\n", *el);
   }

   /* Skapa en ny iterator och frsk att g igenom listan. Listan r
    * dock tom s ingen utskrift ska ske.
    */
   listIteratorInit(&iter, list);
   while ((el = (int*)getNext(&iter)))
   {
      printf("[Loop 5] Listan skulle vara tom, hittade: %d\n", *el);
   }

   return EXIT_SUCCESS;
}