Array Implementierung - Einfach verkettete Liste

lu4k

...danke für den schnellen post...

doch rein logisch verstehe ich das Prinzip... nur fehlt mir die Praxis beim Sourcen...

HighLigerBiMBam

Hier gibt es einige Threads zu diesem Thema Suchfunktionen könnten dir ganz schnell eine Lösung dazu bringen.

lu4k

bereits versucht... und nochmals...

Die Syntax ist das Problem.!!!

CStoll

Dann solltest du nochmal zurückkehren zu den Grundlagen

Nur ein Entwurf:

const unsigned int MAXSIZE = 100; // Maximalgröße der Liste

class Liste
{
  struct element
  {
    int wert; // oder was immer du in der Liste speichern willst
    int nachfolger;
  };

  element werte[MAXSIZE]; // die eigentlichen Daten
  int frei[MAXSIZE];      // die Frei-Liste
  int frei_anfang;        // erstes Element der Frei-Liste
  ...
};

Der Konstruktor muß die Frei-Liste jetzt so initialisieren, daß alle Elemente dort erfasst werden (0 ist ein zulässiger Index, ich würde -1 für "Listenende" verwenden).

Beim Einfügen nimmst du das Element, dessen Index in "frei_anfang" steht, und passt diese Variable entsprechend an, beim Löschen genau umgekehrt.

314159265358979

Hab ich mich jetzt verlesen, oder sollte das nicht eine verkettete Liste sein. Das hier ist ne Mischung ohne Vorteile.

CStoll

Du hast dich verlesen:

lu4k schrieb:

(a)
Erzeugen Sie eine Datenstruktur Liste1 und verwenden Sie die Array-Implementierung zur Speicherung der verketteten Liste. Hier muss zusätzlich eine Funktion implementiert werden, die abfragt, ob der Speicher leer ist.

(und der Ausgangsbeitrag sieht eher so aus, als ob er verstehen will/soll/darf, was da im Hintergrund passiert)

314159265358979

Naja, das ist aber keine "Array-Implementierung" sondern eine "Schrott-Implementierung". Irgendwas ist da doch faul.

CStoll

Dann zeig du doch mal, was du dir unter einer Array-Implementation vorstellen würdest

314159265358979

Ich kann mir keine sinnvolle Array-Implementierung einer verketteten Liste vorstellen, die Idee ist einfach schwachsinnig.

"Schwachsinnig" ist ein sehr starkes Wort - zu stark für diesen Zusammenhang. Letztendlich läuft es ja darauf hinaus, der Liste einen lokalen dynamischen Speicher zu verschaffen - das ist ziemlich umständlich, aber unter bestimmten Umständen alles andere als eine schwachsinnige Idee. Insbesondere in stark nebenläufigen Szenarien kann es eine Menge bringen, wenn die verschiedenen Threads sich nicht andauernd um den selben Heap prügeln müssen. Wenn man keinen lokalen Speicher mehr hat, kann man ja immer noch darauf ausweichen.

Dass alle jemals angeforderten Elemente die gleiche Größe haben, dürfte die Speicherverwaltung deutlich vereinfachen; meine erste Idee wäre, neben der eigentlichen Liste eine Liste gelöschter Elemente vorzuhalten - damit sollte man die Allokation in O(1) hinbekommen können. Das ist allerdings nichts, was ich um diese Zeit noch hinkriege - ich werde mich nach etwas Schlaf mal daransetzen.

Skym0sh0

stimmt. der erste gedanke war bei mir auch: "das ist schwachsinn, das mit eienr festen größe zu machen..." genau wie bei mister PI

aber stimmt, man muss sich nicht mehr um die speicher allokationen kümmern und das hat seine vorteile...
aber auch da würde ich die größe dynamisch machen, sprich im constructor angeben lassen, so wäre das nämlich auch praxistauglich...

volkard

Skym0sh0 schrieb:

aber auch da würde ich die größe dynamisch machen, sprich im constructor angeben lassen, so wäre das nämlich auch praxistauglich...

Naja, das Übungsbeispiel muß nicht so ausgereift sein, zumal man das leicht nachrüsten kann.

Was ich nie nachvollziehen kann, ist, warum man die armen Datenstrukturen immer vergewaltigt. Sortiertes Einfügen darf man einer einfach verketteten Liste einfach nicht antun. Es hätte doch vollig gereicht, sie als Stack ihr Leben fristen zu lassen.

314159265358979

seldon schrieb:

"Schwachsinnig" ist ein sehr starkes Wort - zu stark für diesen Zusammenhang. Letztendlich läuft es ja darauf hinaus, der Liste einen lokalen dynamischen Speicher zu verschaffen - das ist ziemlich umständlich, aber unter bestimmten Umständen alles andere als eine schwachsinnige Idee. Insbesondere in stark nebenläufigen Szenarien kann es eine Menge bringen, wenn die verschiedenen Threads sich nicht andauernd um den selben Heap prügeln müssen. Wenn man keinen lokalen Speicher mehr hat, kann man ja immer noch darauf ausweichen.

Dass alle jemals angeforderten Elemente die gleiche Größe haben, dürfte die Speicherverwaltung deutlich vereinfachen; meine erste Idee wäre, neben der eigentlichen Liste eine Liste gelöschter Elemente vorzuhalten - damit sollte man die Allokation in O(1) hinbekommen können. Das ist allerdings nichts, was ich um diese Zeit noch hinkriege - ich werde mich nach etwas Schlaf mal daransetzen.

Das kapier ich jetzt nicht, kanns mir wer erklären?

padreigh

Ich würde mal vermuten eine Liste die indexe in den Array speichert - umsortiert wird nicht das Element sondern nur der Index. Wenn was rausgelöscht wird den Index woanders speichern um dann bei neuzuweisungen den Platz im Array zu überschreiben. Ist bei bekannter Obergrenze für Anzahl der Elemente in der Liste vermutlich etwas performanter als eine dynamisch reallokierende Struktur zu verwenden - im Rahmen der 2.x GHz Prozzer die in PCs drin stecken macht das aber vermutlich nur wenig Sinn in den meisten Anwendungen.

volkard

314159265358979 schrieb:

Das kapier ich jetzt nicht, kanns mir wer erklären?

Ich kann mal versuchen, andere Worte dafür zu nehmen.

seldon schrieb:

Letztendlich läuft es ja darauf hinaus, der Liste einen lokalen dynamischen Speicher zu verschaffen - das ist ziemlich umständlich, aber unter bestimmten Umständen alles andere als eine schwachsinnige Idee. Insbesondere in stark nebenläufigen Szenarien kann es eine Menge bringen, wenn die verschiedenen Threads sich nicht andauernd um den selben Heap prügeln müssen.

Normalerweise besorgt man sich für jeden Knoten mit new Speicher und gibt jeden mit delete wieder frei. Aber bei 6 Prozessoren und 12 Threads muß sichergestellt werden, daß die vielen gleichzeitig ablaufenden news nicht den Heap aus versehen zerstören, weil sie gleichzeitig wo schreiben. Das verhindert man, indem man dafür sorgt, daß nur einer schreiben kann, aber das bedeutet, daß schlimmstenfalls nur einer arbeitet und elf Threads warten.
Das ist ganz verhindert, wenn sich ein Thread erste ein fettes Array holt und dadrin eine Liste macht.

seldon schrieb:

Wenn man keinen lokalen Speicher mehr hat, kann man ja immer noch darauf ausweichen.

Ah, eine Kombination aus Speicher, der dem Thread gehört und den 12 gleichzeitigen news, also gerade nicht so richtig gleichzeitigen.

seldon schrieb:

Dass alle jemals angeforderten Elemente die gleiche Größe haben, dürfte die Speicherverwaltung deutlich vereinfachen; meine erste Idee wäre, neben der eigentlichen Liste eine Liste gelöschter Elemente vorzuhalten - damit sollte man die Allokation in O(1) hinbekommen können. Das ist allerdings nichts, was ich um diese Zeit noch hinkriege - ich werde mich nach etwas Schlaf mal daransetzen.

void removeFirst(){
   Node* toDie=anchor;
   anchor=anchor->next;
   delete toDie;
}

wird zu

void removeFirst(){
   Node* toDie=anchor;
   anchor=anchor->next;

   toDie->next=freeAnchor;
   freeAnchor=toDie;
}

und

void addFirst(double data){
   Node* newNode=new Node;
   newNode->data=data;
   newNode->next=anchor;
   anchor=newNode;
}

wird zu

void addFirst(double data){
   Node* newNode;
   if(freeAnchor){
      newNode=freeAnchor;
      freeAnchor=freeAnchor->next;
   }
   else{//Wenn man keinen lokalen Speicher mehr hat, 
      newNode=new Anchor;//kann man ja immer noch darauf ausweichen.
   }
   newNode->data=data;
   newNode->next=anchor;
   anchor=newNode;
}

volkard

padreigh schrieb:

im Rahmen der 2.x GHz Prozzer die in PCs drin stecken macht das aber vermutlich nur wenig Sinn in den meisten Anwendungen.

Das Argument, nur mit anderen Hertz-Zahlen hört man seit 30 Jahren mindestens.
Aber bis heute hat sich nichts daran geändert, daß der Benutzer auf den Rechner wartet, und daß doppelt so schnell ungefähr doppelt so schnell ist.

padreigh

volkard schrieb:

Aber bis heute hat sich nichts daran geändert, daß der Benutzer auf den Rechner wartet, und daß doppelt so schnell ungefähr doppelt so schnell ist.

Stimmt beides, und ersteres Nervt mich laufend (unter Win stärker als unter Linux). Trotzdem behaupte ich das 98.75% der Anwendungen nicht dadurch besser werden das jeder sich was eigenes Strickt. Sowas gehört gekapselt in die Libraries die man benutzt. Wenn du zu den 1.25% gehörst die diese Libraries entwickeln, bitte, nutze jeden Trick der ein Microsekündchen rauskitzelt - ich benutzt die dann vielleicht neben der STL auch mal. Der Rest der Programme ist mit verständlichem und wartbarem Code besser gedient - und als Constraint für eine Übungsaufgabe für angehende InformWasauchimmer ist das ziemlich .... obskur.

volkard

padreigh schrieb:

...

Die Array-Version (a) ist ja nur Hinführung zur richtigen version (b).
Das mit dem Array läßt sich besser debuggen.

Den stl-containern kann man so ein Array auch als Allokator unterschubsen.

Skym0sh0

volkard schrieb:

Den stl-containern kann man so ein Array auch als Allokator unterschubsen.

volkard, kannst du mir kurz mal in 1-2 sätzen erklären was ein allokator überhaupt ist?!?

314159265358979

Danke volkard, ich denke ich habe es jetzt verstanden.

Ein Allokator ist ein Objekt, dass dir deinen Speicher alloziert, auf welche Art auch immer.