Show Menu
Cheatography

Listen Cheat Sheet by

Einfach verkettete Listen

Datens­truktur definieren
typedef struct sData
{
  int Index;
  double Value;
  struct sData *Next;
};
Globale Zeiger auf Listen­anfang und Listenende
extern TData *First = NULL;
extern TData *Last = NULL;

Schlüsselwort extern, damit die Zeiger über alle Quellt­ext­dateien verfügbar sind. Alternativ in main defini­eren.
Funktionen (bspw. in list.c/h auslag­ern)
Neues Element anhängen
int append­InL­ist­(TData *Neu)
{
  //prüfen, ob neues Element existiert
  if (Neu == NULL)
    return 0;

  //Neues Element ist neues Listenende
  Neu->Next = NULL;

  if (First == NULL)
    //Fall 1: Liste ist leer
    First = Last = Neu;
  else
    //Fall 2: Liste ist nicht leer
    Last = Last->Next = Neu;
  return 1;
}
Neues Element (sortiert) einfügen
int insert­InL­ist­(TData *Neu)
{
  TData *tmp = First;
  //prüfen, ob neues Element existiert
  if(Neu == NULL)
    return 0;
  if(First == NULL)
  { //Fall 1: Liste ist leer
    Neu->Next = NULL;
    First = Last = Neu;
    return 1;
  }
  if (First­->Value >= Neu->V­alue(
  { //Fall 2: am Listen­anfang einfügen
    Neu->Next = First;
    First = Neu;
    return 1;
  }
  if (Last-­>Value <= Neu->V­alue)
  { //Fall 3: am Listenende anhängen
    Neu->Next = NULL;
    Last = Last->Next = Neu;
    return 1;
  }
  //Fall 4: zwischen zwei Elemente einfügen
  while (tmp->Next != NULL)
  { //prüfen, ob neues Listen­element vor dem nächsten Listen­element eingefügt werden muss
    if (tmp->­Nex­t->­Value >= Neu->V­alue)
    {
      Neu->Next = tmp->Next;
      tmp->Next = Neu;
      return 1;
    }
    return 0;
  }
Element löschen
TData *remo­veF­rom­Lis­t(int delIndex)
{
  TData tmp = NULL, prev = NULL;
  // Fall 1: Liste leer?
  if (First == NULL)
    return NULL;

  // Fall 2: Listen­anfang entfernen?
  if (First­->Index == delIndex)
  {
    tmp = First;
    // nur ein Element in Liste?
    if (Last == First)
      Last = NULL;
    First = First-­>Next;
    return tmp;
  }

  // Fall 3: zu entfer­nendes Element suchen
  prev = First;
  tmp = prev->­Next;
  while (tmp != NULL)
  {
    if (tmp->­Index == delIndex)
    {
      prev->Next = tmp->Next;
      if (tmp == Last) // letztes Element entfernt?
        Last = prev;
      return tmp;
    }
    prev = tmp;
    tmp = tmp->Next;
  }
  return NULL;
}
 

Doppelt verkettete Listen

An Liste anhängen
int append­InL­ist­(TData *Neu)
{
  //prüfen, ob neues Element existiert
  if (Neu == NULL)
    return 0;

  if (First == NULL)
    //Fall 1: Liste ist leer
    Neu->Next = Neu->Prev = NULL;
    First = Last = Neu;
  else
    //Fall 2: Liste ist nicht leer
    Neu->Next = NULL;
    Neu->Prev = Last;
    Last = Last->Next = Neu;
  return 1;
}
In Liste (sortiert) einfügen
int insert­InL­ist­(TData *Neu)
{
 ­TData *tmp = First;
 
 ­//p­rüfen, ob neues Element existiert
 ­if(Neu == NULL)
   ­return 0;
   
 ­if(­First == NULL)
 { //Fall 1: Liste ist leer
   ­Neu­->Next = Neu->Prev = NULL;
   ­First = Last = Neu;
   ­return 1;
 }
 
 if (First­->Value >= Neu->V­alue(
 { //Fall 2: am Listen­anfang einfügen
   ­Neu­->Next = First;
   ­Neu­->Prev = NULL;
   ­First = First-­>Prev = Neu;
   ­return 1;
 }
 
 if (Last-­>Value <= Neu->V­alue)
 { //Fall 3: am Listenende anhängen
   ­Neu­->Prev = Last;
   ­Neu­->Next = NULL;
   Last = Last->Next = Neu;
   ­return 1;
 }
 
 ­//Fall 4: zwischen zwei Elemente einfügen
 ­while (tmp->Next != NULL)
 { //prüfen, ob neues Listen­element vor dem nächsten Listen­element eingefügt werden muss
   if (tmp->­Nex­t->­Value >= Neu->V­alue)
   {
     ­Neu­->Next = tmp->Next;
     ­Neu­->Prev = temp;
     ­tmp­->Next = temp->­Nex­t->Prev = Neu;
     ­return 1;
   }
   tmp = temp->­Next;
 }
 ­return 0;
}
Aus Liste entfernen
TData *remo­veF­rom­Lis­t(int delIndex)
{
 ­TData *tmp = NULL, *prev = NULL;
 // Fall 1: Liste leer?
 if (First == NULL)
   ­return NULL;

 // Fall 2: Listen­anfang entfernen?
 if (First­->Index == delIndex)
 {
   tmp = First;
   ­First = First-­>Next;
   // nur ein Element in Liste?
   if (First == NULL)
     Last = NULL;
   else
     ­Fir­st-­>Prev = NULL;
   ­return tmp;
 }

 // Fall 3: Listenende entfernen?
 if (Last-­>Index == delIndex)
 {
   tmp = Last;
   Last = Last->­Prev;
   ­Las­t->Next = NULL;
   ­return tmp;
 }
 
 ­//Fall 4: zu entfer­nendes Element suchen
 tmp = First-­>Next;
 ­while (tmp != NULL)
 {
   if (tmp->­Index == delIndex)
   {
     prev = tmp->Prev;
     ­pre­v->Next = tmp->Next;
     ­pre­v->­Nex­t->Prev = prev;
     ­return tmp;
   }
   tmp = tmp->Next;
 }
 ­return NULL;
}
Alle Elemente auflisten
typedef enum {forward, backward} TDirec­tion;

void printL­ist­(TD­ire­ction Direction)
{
  TData *tmp = (Direction == forward) ? First : Last;
  int Anzahl­Ele­mente = 0;

  printf­("\n­Index ");
  while (tmp)
  {
    printf­("| %3i ", tmp->I­ndex);
    tmp = (Direction == forward) ? tmp->Next : tmp->Prev;
    Anzahl­Ele­men­te++;
  }

  printf­("\n­---­---­");
  while (Anzah­lEl­eme­nte--)
    printf­("--­---­-");

  printf­("\nWert ");
  tmp = (Direction == forward) ? First : Last;
  while (tmp != NULL)
  {
    printf­("| %3.0f ", tmp->V­alue);
    tmp = (Direction == forward) ? tmp->Next : tmp->Prev;
  }
  printf­("\n­");
}

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          C Reference Cheat Sheet

          More Cheat Sheets by TimSch

          C - Zeiger / Pointer Cheat Sheet