✔ Queue in C

[Ozzy Ozborn]

Hi,

für ein projekt muss ich eine Queue für eine Mittelwertberechnung in C programmieren. Leider habe ich davon aber gar keine Ahnung. In C++ habe ich schon häufiger eine Queue realisiert, aber in C scheint das ja alles etwas komplizierter zu sein...

Hat jemand von Euch vielleicht ein kleines Stück Code, wo man mal ganz einfach sieht, wie das geht? Soll für 10 Elemente sein...

MfG, und vielen Dank schon einmal, Ozzy

 

[RedWing]

Hallo,

schau doch mal:

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

typedef struct _IntegerList {
    int element;
    struct _IntegerList *next;
    struct _IntegerList *last;
} IntegerList;

IntegerList *
integer_list_create (int first_element)
{
  IntegerList *new_list;

  new_list = (IntegerList *) malloc (sizeof (IntegerList));
  new_list->next = NULL;
  new_list->element = first_element;
  new_list->last = new_list;

  return new_list;
}

/**
 * typical append implementation
 */
void
integer_list_append_recursive (IntegerList *list, int element)
{
  if (list)
    {
      integer_list_append_recursive (list->next, element);
      if (list->next == NULL)
	    {
	      list->next = (IntegerList *) malloc (sizeof (IntegerList));
	      list->next->element = element;
	      list->next->next = NULL;
	    }
    }
}

/**
 * optimized append implementation
 */
void
integer_list_append_constant_time (IntegerList *list, int element)
{
  list->last->next = (IntegerList *) malloc (sizeof (IntegerList));
  list->last->next->element = element;
  list->last->next->next = NULL;
  list->last = list->last->next;
}

void
integer_list_print_recursive (IntegerList *list)
{
  if (list)
    {
      printf ("%d\t", list->element);
      integer_list_print_recursive (list->next);
    }
  else
    printf ("\n");
}

void
integer_list_free (IntegerList *list)
{
  if (list)
    {
      integer_list_free (list->next);
      free (list);
    }
}

int
main (int argc, char **argv)
{
  IntegerList *list;
  int i;

  list = integer_list_create (0);

  for (i = 1; i < 10; i++)
    integer_list_append_constant_time (list, i);

  integer_list_print_recursive (list);

  integer_list_free (list);

  return 0;
}

Falls noch fragen offen sein sollten immerzu ...

Gruß,
RedWing

 

[Ozzy Ozborn]

Hi,

danke für Deine Antwort, sieht sehr gut aus! Ich habe es jetzt aber erst einmal anders gelöst: Da ich in der Queue ja nur 10 Elemente habe, habe ich mir einfach ein Array angelegt. Head und Tail sind bei mir keine Pointer, sondern speichern die Position, wo der Head, bzw. Tail steht. Eine put und eine get-Funktion, und das wars.
Wirklich elegant ist das natürlich nicht, aber eben klein. Aber ich denke, über kurz oder lang werde ich dann auf Deine Lösung zurückgreifen!

MfG, und vielen Dank noch einmal, Ozzy

 

[RedWing]

Hallo,

alles klar. Falls du dennoch in die Verlegenheit kommen solltest, dann schau dir lieber das update an, da das "architektonisch sauberer" ist:

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

typedef struct _IntegerListElement {
    int element_value;
    struct _IntegerListElement *next;
} IntegerListElement;

typedef struct _IntegerList {
    IntegerListElement *first;
    IntegerListElement *last;
} IntegerList;


/* begin: private function section */
static void
integer_list_append_element (IntegerListElement *element, int element_value)
{
  if (element)
    {
      integer_list_append_element (element->next, element_value);
      if (!element->next)
	    {
	      element->next =
	          (IntegerListElement *) malloc (sizeof (IntegerListElement));
	      element->next->element_value = element_value;
	      element->next->next = NULL;
	    }
    }
}

static void
integer_list_print_element (IntegerListElement *element)
{
  if (element)
    {
      printf ("%d\t", element->element_value);
      integer_list_print_element (element->next);
    }
  else
    printf ("\n");

}

static void
integer_list_free_element (IntegerListElement *element)
{
  if (element)
    {
      integer_list_free_element (element->next);
      free (element);
    }
}
/* end: private function section */

/* begin: public function section */

/**
 * typical append implementation
 */
void
integer_list_append (IntegerList *list, int element_value)
{
  if (list->first)
    integer_list_append_element (list->first, element_value);
  else
    {
      list->first =
	    (IntegerListElement *) malloc (sizeof (IntegerListElement));
      list->first->element_value = element_value;
      list->first->next = NULL;
    }
}

/**
 * optimized append implementation
 */
void
integer_list_append_constant_time (IntegerList *list, int element_value)
{
  if (!list->first)
    {
      list->first =
	    (IntegerListElement *) malloc (sizeof (IntegerListElement));
      list->first->next = NULL;
      list->first->element_value = element_value;
      list->last = list->first;
    }
  else
    {
      list->last->next =
	    (IntegerListElement *) malloc (sizeof (IntegerListElement));
      list->last->next->element_value = element_value;
      list->last->next->next = NULL;
      list->last = list->last->next;
    }
}


void
integer_list_print (IntegerList *list)
{
  integer_list_print_element (list->first);
}

IntegerList *
integer_list_create ()
{
  IntegerList *new_list;

  new_list = (IntegerList *) malloc (sizeof (IntegerList));
  new_list->first = NULL;
  new_list->last = NULL;

  return new_list;
}

void
integer_list_free (IntegerList *list)
{
  if (list)
    {
      integer_list_free_element (list->first);
      free (list);
    }
}
/* end: public function section */

int
main (int argc, char **argv)
{
  IntegerList *list;
  int i;

  list = integer_list_create ();

  for (i = 1; i < 10; i++)
    integer_list_append_constant_time (list, i);

  integer_list_print (list);

  integer_list_free (list);

  return 0;
}

Gruß,
RedWing