Array Implementierung - Einfach verkettete Liste

[lu4k]

Hey,
hab da folgendes Problem...

Implementieren Sie jeweils eine einfach verkettete Liste und die Grundoperationen Element aufsteigend sortiert einfügen, Element löschen sowie Element auffinden.
Nach dem löschen, sollen die Elemente aufsteigend sortiert werden.

(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.

(b)
Erzeugen Sie nun eine neue Datenstruktur Liste2 und verwenden Sie nun zur Implementierung der verketteten Liste die dynamische Speicherung der Listen Elemente.

__________________________
Zu a) mein Ansatz...

Unter Datenstruktur verstehe ich eine Klasse zu erzeugen...

#include <iostream>
using namespace std;

class Liste1
{
private:
int array[10]{1;2;3;4;5;6;9;8;7;10};
*p_prev; //<- ???
public:
// ???...

} ;

Wie sieht der Konstruktor/Dekonstruktor dazu aus ?

Wie sieht eine einfach verkettete Liste aus ? Reicht "1" Zeiger ? *p_prev ??

Wie prüfe ich ob der Speicher frei ist ?

Wie eine Klasse IM GROBEN aussieht weiß ich.

header-datei

cpp datei

main cpp

etc, Methoden, Funktionen,private, protected usw...

Aus dem Skript:

Es werden 2 Arrays erzeugt, in einem werden die Daten gespeichert, in dem anderen die Adreessn bzw. indizes der nächst höheren Zahl im Datenobj?! oder Array ?!
Es handelt sich um eine sogenannte "Freispeicher-liste" -> fsp...

Datenfeld
a

______________

0 | frei
______________

1 | 10
______________

2 |
______________

3 | 20
______________

4 | 30
______________

5 | 30
_____________

6 | 5
______________

7 | 25
______________

Freispeicherliste
fsp
_______________

0 | 6
______________

1 | 3
_____________

2 | -1
______________

3 | 7
______________

4 | 0
______________

5 | -1
______________

6 | 1
______________

7 | 4
______________

Idee: verwende 2 Felder

-array a: enthält die Daten der verk. Liste
-array fps indizes für die nachfolgerelemente der verk. Liste
-Definition der Indizies in fsp:
-1 = frei
0 = Ende der Liste
n>0 = Index des Nachfolgers im Datenfeld

-zahlen von klein nach groß eingeben und dann mit Hilfe der Fsp die Zahlen von klein nach groß in das array einfügen.

zu b)
Ich denke hier brauch ich nicht mehr die Array-Implementierung....?!?!

Doppelt verkettete Liste hat 2 Zeiger die auf den Vorgänger und Nachfolger Zeigen.

-Das Element-, -Sortieren, -einfügen und auffinden sollte weniger schwierig sein ...???

Wie das genau funktioniert weiß ich leider nicht, deshalb hier der Hilfeaufruf =))

Vielleicht hat ja jmd lust und Zeit zu helfen und ein wenig zu Sourcen :))

Für jede Anregung offen.
Danke im voraus !

[CStoll]

Bei einer verketteten Liste werden die Elemente verkettet, indem jeder weiß, wo sein Nachfolger steht. Das heißt, bei der Array-Lösung würdest du den Index des Nachfolgers im Array speichern (da halte ich ein struct element{int wert;int nachfolger;} sinnvoller als zwei parallele Arrays). Außerdem benötigst du noch eine Möglichkeit dir zu merken, welche Elemente frei sind.

Bei der Variante mit dem dynamischen Speicher verwendest, mußt du dann den Index durch Zeiger ersetzen und forderst den Speicher per new an und gibst ihn per delete wieder frei - in dem Fall kümmert sich das System darum herauszufinden, wo du freien Speicherplatz bekommen könntest.

[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.

[seldon]

"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.