list.cDenna 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 nästa
* element i listan.
*/
typedef struct Element
{
void* data;
struct Element* next;
} Element;
/**
* Datastrukturen för listan. Håller ordning på listans längd och
* huvudet för själva listan.
*/
typedef struct List
{
int length;
Element* list;
} List;
/**
* En iterator över listan. Utöver referensen till det aktuella
* elementet behöver vi även hålla ordning på det tidigare elementet
* för 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));
}
/**
* Lägg in ett element först 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 jämföras.
* Objekten som ska jämföras tas in via void-pekare eftersom listan
* är generell och kan hålla vilken typ av data som hellst.
* value - En referens till ett objekt med samma värde 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 längden på listan.
*/
int listLength(List* list)
{
return list->length;
}
/**
* Skapar en iterator över listan. Se exemplet nedan för att se hur
* man använder en iterator.
*/
void listIteratorInit(Iterator* iter, List* list)
{
iter->prev = iter->curr = &(list->list);
}
/**
* Returnerar nästa 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 jämför två heltal. Talen som jämförs tas in via
* argumenten. Notera att funktionen tar pekare som argument. Man
* måste alltså skicka in adresserna till de heltalsvariabler man vill
* jämföra.
*/
int compareInt(void *a, void *b)
{
return *(int*)a - *(int*)b;
}
/**
* Exemplet skapar en lista med 25 heltal. Sedan använder den de olika
* metodrna för att plocka bort element ur listan. De 25 heltalen
* lagras här i en array. Det är endast av bekvämlighetsskäl och har
* ingen betydelse för listan. Det vanliga är annars att man har en
* något större datastruktur som man vill lagra i listan och man
* lägger 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 hjälp 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 större ä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 hjälp av funktionen som jämför
* två heltal. Vi skickar alltså inte in någon adress till det som ska
* raderas, bara ett annat heltal med samma värde.
*/
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 försök 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;
}
| 
