Thomas Kramer

IT-COW | C-Aufgaben: Einfach verkettete Listen

C-Aufgaben: Einfach verkettete Listen

By Administrator at April 22, 2011 15:35
Filed Under: C(++), Programmierung allgemein, Studium

Eine der einfacheren Aufgaben war die Realisierung von einfach verketteten Listen, davon hatte ich zwei Varianten in C erstellt.

 

Es gibt einfach und doppelt verkettete Listen, bei einfach verketteten Listen gibt es nur den next-Zeiger auf das nächste Element, bei doppelt verketteten Listen zusätzlich noch einen prev-Zeiger auf das vorherige Element.

 

Bei doppelt verketteten Listen gibt es einen Performance-Vorteil beim Löschen eines Eintrags, weil man bei einfach verketteten Listen erst vom Anfang bis zum vorherigen Element des zu löschenden Eintrags durchgehen muss um den next-Zeiger des vorherigen Elements korrigieren zu können – bei doppelt verketteten Listen kennt man direkt den Vorgänger. Bei so wenigen Einträgen spielt das aber keine Rolle.

 

Da ich mehr an Arrays gewöhnt bin war meine erste Version mehr eine Mischung aus Arrays und verketteten Listen. Die zweite Variante benutzte dann nur noch verkettete Listen.

 

Nachfolgend die Quellcodes beider Varianten. Besonders zu beachten war das der next-Zeiger des letzten Elements explizit auf NULL gesetzt sein muss weil das kompilierte Programm unter Windows ansonsten beim Traversieren durch die Elemente abstürzt – unter Linux ist die Benutzung von Pointern fehlertoleranter als unter Windows, was mir auch mein Dozent bestätigt hatte.

 

Variante 1

 

/*
* =====================================================================================
*
*       Filename:  
*
*    Description:  verkettete Listen, Variante eins mit Arrays
*
*        Version:  0.1
*        Created:
*       Revision:  none
*       Co mpiler:  gcc
*
*         Author:  Thomas Kramer
*        Company:
*
* =====================================================================================
*/

#include <iostream>
#include <iomanip>

using namespace std;

struct Element {
  long     key;
  long     info;
  struct Element *next;
};

const int groesse=4;
const int gesuchter_Wert=5;

Element *L;
Element *cursor;
Element *Elemente[groesse];

int main()
{
  if (groesse<1)
  {
      cout << "Fehler: mit weniger als einem Listenelement ergibt Programm keinen Sinn. Programmabbruch." << '\n';
      return 1;
  } else {
    L = Elemente[0];
  }

  for (int i=0;i<groesse;i+=1)
  {
      Elemente[i]       = new Element;
      Elemente[i]->key  = i+1;
      Elemente[i]->info = ((i+1)*10)+(i+1);
      Elemente[i]->next = NULL;

      /* erst beim 2. Schleifendurchlauf kann der Nachfolger zugewiesen werden */
      if (i>0)
      {
          Elemente[i-1]->next = Elemente[i];
      }
      /* cout << i << ' ' << Elemente[i]->key << ' ' << Elemente[i]->info << '\n'; */
  }

  cursor=Elemente[0];
  while ((cursor!=NULL) && (cursor->key!=gesuchter_Wert))
  {
     cursor=cursor->next;
  }

  if (cursor==NULL)
  {
      cout << "Fehler, gesuchter Wert wurde nicht gefunden.";
      return 1;
  } else
  {
    cout << "Listenelement gefunden: " << setw(12) << cursor << endl << endl;
    cout << " key"  << "     =" << setw(12) << cursor->key  << endl;
    cout << " info" << "    ="  << setw(12) << cursor->info << endl;
    cout << " next" << "    ="  << setw(12) << cursor->next << endl;

    return 0;
  }

}

 

Variante 2

 

Zu beachten bei Variante zwei ist das hier für die vier Elemente x1, x2, x3 und x4 feste Objekte und keine Zeiger verwendet werden (welche vorher erst explizit instanziiert werden müssten), daher kann einfach vom ersten bis zum letzten Element der Inhalt zugewiesen werden – ansonsten hätte natürlich die umgekehrte Reihenfolge benutzt werden müssen (wegen den next-Pointern).

 

/*
* =====================================================================================
*
*       Filename: 
*
*    Description:  verkettete Listen, Variante zwei
*
*        Version:  0.1
*        Created:
*       Revision:  none
*       Co mpiler:  gcc
*
*         Author:  Thomas Kramer
*        Company:
*
* =====================================================================================
*/

#include <iostream>
#include <iomanip>

using namespace std;

struct Element {
  long     key;
  long     info;
  struct Element *next;
};

Element *L;
Element *cursor;
Element x1;
Element x2;
Element x3;
Element x4;

const int gesuchter_Wert=3;

int main()
{
  int i=0;

  x1.key  = i+1;
  x1.info = ((i+1)*10)+(i+1);
  x1.next = &x2;

  i+=1;

  x2.key  = i+1;
  x2.info = ((i+1)*10)+(i+1);
  x2.next = &x3;

  i+=1;

  x3.key  = i+1;
  x3.info = ((i+1)*10)+(i+1);
  x3.next = &x4;

  i+=1;

  x4.key  = i+1;
  x4.info = ((i+1)*10)+(i+1);
  x4.next = NULL;

  if (&x1!=NULL)
  {
    L=&x1;
  } else {
    L=NULL;
  }

  cursor=L;
  while ((cursor!=NULL) && (cursor->key!=gesuchter_Wert))
  {
     cursor=cursor->next;
  }

  if (cursor==NULL)
  {
      cout << "Fehler, gesuchter Wert wurde nicht gefunden.";
      return 1;
  } else
  {
    cout << "Listenelement gefunden: " << setw(12) << cursor << endl << endl;
    cout << " key"  << "     =" << setw(12) << cursor->key  << endl;
    cout << " info" << "    ="  << setw(12) << cursor->info << endl;
    cout << " next" << "    ="  << setw(12) << cursor->next << endl;

    return 0;
  }
}

 

Kommentar schreiben




  Country flag
biuquote
  • Kommentar
  • Live Vorschau
Loading


Tag-Wolke

Monats-Liste