linkedlist.c

关于遗传算法的一些见地。特别是关于简单遗传程序设计的实现。

    prev->next = new_element;
    }
  list->prev = new_element;
  new_element->next = list;

  return new_element;
  }


DLList *dlink_insert_index(DLList *list, vpointer data, int index)
  {
  DLList *new_element;
  DLList *this_list;
  
  if (index < 0)
    {
/* FIXME: Prehaps I should insert from end of list instead? */
    return dlink_append(list, data);
    }
  else if (index == 0)
    {
    return dlink_prepend(list, data);
    }
  
  this_list = dlink_nth(list, index);
  if (!this_list)
    return dlink_append(list, data);
  
  new_element = dlink_new();
  new_element->data = data;
  
  if (this_list->prev)
    {
    this_list->prev->next = new_element;
    new_element->prev = this_list->prev;
    }
  new_element->next = this_list;
  this_list->prev = new_element;
  
  if (this_list == list)
    return new_element;
  else
    return list;
  }


DLList *dlink_delete_all_data(DLList *list, vpointer data)
  {            
  DLList *tmp=list;
 
  while (tmp)
    {
    if (tmp->data == data)
      {
      if (tmp->prev) tmp->prev->next = tmp->next;
      if (tmp->next) tmp->next->prev = tmp->prev;

      if (list == tmp) list = list->next;

      dlink_free(tmp);
      }

    tmp = tmp->next;
    }

  return list;
  }


DLList *dlink_delete_data(DLList *list, vpointer data)
  {
  DLList *tmp=list;
  
  while (tmp)
    {
    if (tmp->data == data)
      {
      if (tmp->prev) tmp->prev->next = tmp->next;
      if (tmp->next) tmp->next->prev = tmp->prev;
	  
      if (list == tmp) list = list->next;
	  
      dlink_free(tmp);
	  
      return list;
      }

    tmp = tmp->next;
    }

  return list;
  }


DLList *dlink_delete_link(DLList *list, DLList *link)
  {
  if (!link) return NULL;

  if (link->prev) link->prev->next = link->next;
  if (link->next) link->next->prev = link->prev;
      
  if (link == list) list = list->next;
      
  link->prev = NULL;
  link->next = NULL;
  
  return list;
  }


DLList *dlink_clone(DLList *list)
  {
  DLList *new_element = NULL;
  DLList *last;

  if (!list) return NULL;

  new_element = dlink_new();
  new_element->data = list->data;
  last = new_element;
  list = list->next;
  while (list)
    {
    last->next = dlink_new();
    last->next->prev = last;
    last = last->next;
    last->data = list->data;
    list = list->next;
    }

  return new_element;
  }


DLList *dlink_reverse(DLList *list)
  {
  DLList *last=NULL;
  
  while (list)
    {
    last = list;
    list = last->next;
    last->next = last->prev;
    last->prev = list;
    }
  
  return last;
  }


DLList *dlink_nth(DLList *list, const int index)
  {  
  int	i=index;

  while (i > 0 && list)
    {
    list = list->next;
    i--;
    }
  
  return list;
  }


DLList *dlink_pth(DLList *list, const int index)
  {
  int	i=index;

  while (i > 0 && list)
    {
    list = list->prev;
    i--;
    }
  
  return list;
  }


vpointer dlink_nth_data(DLList *list, const int index)
  {
  list = dlink_nth(list, index);
  
  return list?list->data:NULL;
  }


vpointer dlink_pth_data(DLList *list, const int index)
  {
  list = dlink_pth(list, index);
  
  return list?list->data:NULL;
  }


DLList *dlink_find(DLList *list, vpointer data)
  {
  while (list && list->data != data)
    list = list->next;
  
  return list;
  }


DLList *dlink_find_custom(DLList *list, vpointer data, LLCompareFunc func)
  {
  if (!func) die("Null pointer to LLCompareFunc passed.");

  while (list && func(list->data, data)==FALSE)
    list = list->next;

  return list;
  }


int dlink_index_link(DLList *list, DLList *link)
  {
  int i=0;

  while (list)
    {
    if (list == link) return i;
    i++;
    list = list->next;
    }

  return -1;
  }


int dlink_index_data(DLList *list, vpointer data)
  {
  int i=0;

  while (list)
    {
    if (list->data == data) return i;
    i++;
    list = list->next;
    }

  return -1;
  }


DLList *dlink_last(DLList *list)
  {
  if (!list) return NULL;

  while (list->next)
    list = list->next;
  
  return list;
  }


DLList *dlink_first(DLList *list)
  {
  if (!list) return NULL;

  while (list->prev) list = list->prev;
  
  return list;
  }


int dlink_size(DLList *list)
  {
  int	size=0;
  
  while (list)
    {
    size++;
    list = list->next;
    }
  
  return size;
  }


boolean dlink_foreach(DLList *list, LLForeachFunc func, vpointer userdata)
  {

  if (!func) die("Null pointer to LLForeachFunc passed.");

  while (list)
    {
    if ((*func)(list->data, userdata)) return TRUE;
    list = list->next;
    }

  return FALSE;
  }


boolean dlink_foreach_reverse(DLList *list, LLForeachFunc func, vpointer userdata)
  {

  if (!func) die("Null pointer to LLForeachFunc passed.");

  while (list)
    {
    if ((*func)(list->data, userdata)) return TRUE;
    list = list->prev;
    }

  return FALSE;
  }


DLList *dlink_insert_sorted(DLList *list, vpointer data, LLCompareFunc func)
  {
  DLList *this_list;
  DLList *prev_list;
  DLList *new_element;

  if (!func) die("Null pointer to LLCompareFunc passed.");

  new_element = dlink_new();
  new_element->data = data;

  if (!list) return new_element;

  this_list = list;
  prev_list = NULL;

  while (this_list && func(this_list->data, data)<0)
    {
    prev_list = this_list;
    this_list = this_list->next;
    }

  new_element->prev = prev_list;
  new_element->next = this_list;

  if (this_list)
    {
    this_list->prev = new_element;
    if (!prev_list) return new_element;
    }

  prev_list->next = new_element;

  return list;
  }


/*
 * Testing:
 */

void linkedlist_diagnostics(void)
  {
  printf("=== Linked list diagnostics ==================================\n");
  printf("Version:                   %s\n", GA_VERSION_STRING);
  printf("Build date:                %s\n", GA_BUILD_DATE_STRING);
  printf("Compilation machine characteristics:\n%s\n", GA_UNAME_STRING);

  printf("--------------------------------------------------------------\n");
  printf("structure          sizeof\n");
  printf("SLList             %lu\n", (unsigned long) sizeof(SLList));
  printf("DLList             %lu\n", (unsigned long) sizeof(DLList));
  printf("==============================================================\n");

  return;
  }



static boolean test_list_print(vpointer a, vpointer b)
  {
  int val = *((int*)a);
  printf("%d ", val);
  return FALSE;
  }


static int test_list_compare_one(constvpointer a, constvpointer b)
  {
  int one = *((const int*)a);
  int two = *((const int*)b);
  return one-two;
  }


static int test_list_compare_two(constvpointer a, constvpointer b)
  {
  int one = *((const int*)a);
  int two = *((const int*)b);
  return two-one;
  }


/*
 * This function is 'borrowed' from glib.
 * This shows that the glib-emulation works.
 */
#ifdef LINKEDLIST_COMPILE_MAIN
int main(int argc, char **argv)
#else
boolean linkedlist_test(void)
#endif

#ifdef LINKEDLIST_EMULATE_GLIST
  {
  DLList *list, *t;
  SLList *slist, *st;
  int sorteddata[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  int data[10] = { 8, 9, 7, 0, 3, 2, 5, 1, 4, 6 };
  int i;

  printf("Checking doubly linked lists...\n");

  list = NULL;
  for (i = 0; i < 10; i++)
    list = g_list_append(list, &sorteddata[i]);
  list = g_list_reverse(list);

  for (i = 0; i < 10; i++)
    {
      t = g_list_nth (list, i);
      if (*((int*) t->data) != (9 - i))
	printf("Regular insert failed\n");
    }

  for (i = 0; i < 10; i++)
    if(g_list_position(list, g_list_nth (list, i)) != i)
      printf("g_list_position does not seem to be the inverse of g_list_nth\n");

  g_list_free(list);
  list = NULL;

  for (i = 0; i < 10; i++)
    list = g_list_insert_sorted(list, &data[i], test_list_compare_one);

  g_list_foreach(list, test_list_print, NULL);
  printf("\n");

  for (i = 0; i < 10; i++)
    {
      t = g_list_nth(list, i);
      if (*((int*) t->data) != i)
         printf("Sorted insert failed\n");
    }

  g_list_free(list);
  list = NULL;

  for (i = 0; i < 10; i++)
    list = g_list_insert_sorted(list, &data[i], test_list_compare_two);

  g_list_foreach(list, test_list_print, NULL);
  printf("\n");

  for (i = 0; i < 10; i++)
    {
      t = g_list_nth(list, i);
      if (*((int*) t->data) != (9 - i))
         printf("Sorted insert failed\n");
    }

  g_list_free(list);

  printf ("ok\n");

  printf ("Checking singly linked lists...\n");

  slist = NULL;
  for (i = 0; i < 10; i++)
    slist = g_slist_append(slist, &sorteddata[i]);
  slist = g_slist_reverse(slist);

  for (i = 0; i < 10; i++)
    {
      st = g_slist_nth(slist, i);
      if (*((int*) st->data) != (9 - i))
	printf ("failed\n");
    }

  g_slist_free(slist);
  slist = NULL;

  for (i = 0; i < 10; i++)
    slist = g_slist_insert_sorted(slist, &data[i], test_list_compare_one);

  g_slist_foreach(slist, test_list_print, NULL);
  printf("\n");

  for (i = 0; i < 10; i++)
    {
      st = g_slist_nth (slist, i);
      if (*((int*) st->data) != i)
         printf ("Sorted insert failed\n");
    }

  g_slist_free(slist);
  slist = NULL;

  for (i = 0; i < 10; i++)
    slist = g_slist_insert_sorted(slist, &data[i], test_list_compare_two);

  g_slist_foreach(slist, test_list_print, NULL);
  printf("\n");

  for (i = 0; i < 10; i++)
    {
      st = g_slist_nth(slist, i);
      if (*((int*) st->data) != (9 - i))
         printf("Sorted insert failed\n");
    }

  g_slist_free(slist);

  printf("ok\n");

#else
  {
  DLList *list, *t;
  SLList *slist, *st;
  int sorteddata[10] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
  int data[10] = { 8, 9, 7, 0, 3, 2, 5, 1, 4, 6 };
  int i;

  printf("Checking doubly linked lists...\n");

  list = NULL;
  for (i = 0; i < 10; i++)
    list = dlink_append(list, &sorteddata[i]);
  list = dlink_reverse(list);

  for (i = 0; i < 10; i++)
    {
      t = dlink_nth(list, i);
      if (*((int*) t->data) != (9 - i))
	printf("Regular insert failed\n");
    }

  for (i = 0; i < 10; i++)
    if(dlink_index_link(list, dlink_nth(list, i)) != (int) i)
      printf("dlink_index_link does not seem to be the inverse of dlink_nth_data\n");

  dlink_free_all(list);
  list = NULL;

  for (i = 0; i < 10; i++)
    list = dlink_insert_sorted(list, &data[i], test_list_compare_one);

  dlink_foreach(list, test_list_print, NULL);
  printf("\n");

  for (i = 0; i < 10; i++)
    {
      t = dlink_nth(list, i);
      if (*((int*) t->data) != i)
         printf("Sorted insert failed\n");
    }

  dlink_free_all(list);
  list = NULL;

  for (i = 0; i < 10; i++)
    list = dlink_insert_sorted(list, &data[i], test_list_compare_two);

  dlink_foreach(list, test_list_print, NULL);
  printf("\n");

  for (i = 0; i < 10; i++)
    {
      t = dlink_nth(list, i);
      if (*((int*) t->data) != (9 - i))
         printf("Sorted insert failed\n");
    }

  dlink_free_all(list);

  printf ("ok\n");

  printf ("Checking singly linked lists...\n");

  slist = NULL;
  for (i = 0; i < 10; i++)
    slist = slink_append(slist, &sorteddata[i]);
  slist = slink_reverse(slist);

  for (i = 0; i < 10; i++)
    {
      st = slink_nth(slist, i);
      if (*((int*) st->data) != (9 - i))
	printf ("failed\n");
    }

  slink_free_all(slist);
  slist = NULL;

  for (i = 0; i < 10; i++)
    slist = slink_insert_sorted(slist, &data[i], test_list_compare_one);

  slink_foreach(slist, test_list_print, NULL);
  printf("\n");

  for (i = 0; i < 10; i++)
    {
      st = slink_nth(slist, i);
      if (*((int*) st->data) != (int) i)
         printf ("Sorted insert failed\n");
    }

  slink_free_all(slist);
  slist = NULL;

  for (i = 0; i < 10; i++)
    slist = slink_insert_sorted(slist, &data[i], test_list_compare_two);

  slink_foreach(slist, test_list_print, NULL);
  printf("\n");

  for (i = 0; i < 10; i++)
    {
      st = slink_nth(slist, i);
      if (*((int*) st->data) != (9 - i))
         printf("Sorted insert failed\n");
    }

  slink_free_all(slist);

  printf("ok\n");
#endif

#ifdef LINKEDLIST_COMPILE_MAIN
  exit(EXIT_SUCCESS);
#else
  return TRUE;
#endif
  }