[C++] Kleines Prob mit doppelt verketteter Liste

[pippo]

Hab im Internet folgenden Code gefunden:


#include <iostream>
using namespace std;

struct node {
node *left;
node *right;
int data;
//bool erstes;
};

struct node * new_list(){
struct node *neu = (struct node*) malloc(sizeof(struct node));
neu->data = -1;
neu->right = neu;
neu->left = neu;
return neu;
};

struct node * insert_right(struct node *list, int data){
struct node *neu = (struct node *) malloc(sizeof(struct node));
neu->data = data;
neu->left = list;
neu->right = list->right;
list->right = neu;
neu->right->left = neu;
return neu;
}

struct node * loeschen(struct node *list){
list->right->left = list->left;
list->left->right = list->right;
return list->left;
}

struct node * restore(struct node *list){
list->right->left = list;
list->left->right = list;
return list;
}

void print_all(struct node* list){
struct node *head = list;
struct node *current = list;
cout << head->data;
while (head != (current = current->right)){
cout << current->data;
}
cout << endl;
}
int main () {

/* erstelle eine neue Liste: */
struct node *head = new_list();
struct node *current = head;
int i;

/* Bevoelkere die List mit den Zahlen 1 bis 10 */
for(i = 1; i <= 10; i++){
current = insert_right(current, i);
}

/* Gebe die Liste aus, einmal von head aus startent, einmal vom
letzten Element aus: */
print_all(head);
print_all(current);

/* loesche das vorletzte Element: */
current = current->left;
current = loeschen(current);
cout << "Liste nach loeschen:\n";
print_all(head);

current = loeschen(head);
cout << "Liste nach loeschen des Kopfes:\n";
print_all(current);

head = restore(head);
cout << "Liste nach Wiederherstellen des Kopfes:\n";
print_all(head);
return 0;
}

Jetzt will ich aber alles über Klassen machen und dieses "struct" rauswerfen. Gut, dachte ich mir, bist ein ganz schlauer und schreibst einfach alles um ;D
Leider bekomm ich dann einige Fehler. Dass man in den Klassen dann alles public machen muss, ist mir klar. Aber was muss noch geändert werden?

Zum Beispiel in "struct node * new_list(){" vermisst er ein ; vor dem public und will mir "neu" nicht anerkennen.

[Coda]

Nichts eigentlich. Was der Sinn der Aktion sein soll ist mir aber auch nicht klar, weil struct und class später im Programmcode absolut äquivalent sind und es dadurch auch nicht auf einmal Objektorientiert ist.

[pippo]

In der FH verwenden wir aber kein struct mehr, deshalb will ich einfach mit Klassen arbeiten. Wir hatten eigentlich gelernt, dass man sowas eigentlich ändern kann, da eine Struktur im Endeffekt ja nur eine öffentliche Klasse mit weniger Funktionsumfang ist. Aber scheinbar gehts doch nicht so einfach. Was muss man denn noch beachten?

[Coda]

In der FH verwenden wir aber kein struct mehr, deshalb will ich einfach mit Klassen arbeiten. Wir hatten eigentlich gelernt, dass man sowas eigentlich ändern kann, da eine Struktur im Endeffekt ja nur eine öffentliche Klasse mit weniger Funktionsumfang ist. Aber scheinbar gehts doch nicht so einfach. Was muss man denn noch beachten?

Nichts. Du hast mit Sicherheit einen Syntaxfehler.

class {
public:
...Zeug...
};

ist absolut äquivalent zu

struct {
...Zeug...
};

Es bleibt trotzdem bescheuert. Klassen verwendet man wenn man Objekte beschreibt, was hier nicht der Fall ist.

[pippo]

Wir habens halt mal so gelernt. In VS2005 bin ich einfach auf Suchen/Ersetzen gegangen und hab somit alle "struct" durch "class" ersetzt und überall noch das public eingesetzt. Daraufhin hab ich halt dann die Syntaxfehler bekommen. Mehr hab ich nicht gemacht.

Hier das Prgramm in geänderter Version, womit ich die Syntaxfehler bekomme:

#include <iostream>
using namespace std;

class node {
public:
node *left;
node *right;
int data;
//bool erstes;
};

class node * new_list(){
public:
class node *neu = (class node*) malloc(sizeof(class node));
neu->data = -1;
neu->right = neu;
neu->left = neu;
return neu;
};

class node * insert_right(class node *list, int data){
public:
class node *neu = (class node *) malloc(sizeof(class node));
neu->data = data;
neu->left = list;
neu->right = list->right;
list->right = neu;
neu->right->left = neu;
return neu;
}

class node * loeschen(class node *list){
public:
list->right->left = list->left;
list->left->right = list->right;
return list->left;
}

class node * restore(class node *list){
public:
list->right->left = list;
list->left->right = list;
return list;
}

void print_all(class node* list){
public:
class node *head = list;
class node *current = list;
cout << head->data;
while (head != (current = current->right)){
cout << current->data;
}
cout << endl;
}
int main () {

/* erstelle eine neue Liste: */
class node *head = new_list();
class node *current = head;
int i;

/* Bevoelkere die List mit den Zahlen 1 bis 10 */
for(i = 1; i <= 10; i++){
current = insert_right(current, i);
}

/* Gebe die Liste aus, einmal von head aus startent, einmal vom
letzten Element aus: */
print_all(head);
print_all(current);

/* loesche das vorletzte Element: */
current = current->left;
current = loeschen(current);
cout << "Liste nach loeschen:\n";
print_all(head);

current = loeschen(head);
cout << "Liste nach loeschen des Kopfes:\n";
print_all(current);

head = restore(head);
cout << "Liste nach Wiederherstellen des Kopfes:\n";
print_all(head);
return 0;
}
Das kann ja jetzt jeder mit Copy/Paste nachvollziehen, falls jemand lust hast :)

[Gauron Kampeck]

Ich könnte mir vorstellen, dass Ausdrücke wie "class node * new_list()" in C++ nicht möglich sind - wobei ich auch "struct node * new_list()" noch nie gesehen hab, aber in C lernt man ja nie aus, immerhin wird es von VC++2005 kompiliert;) .
Ich würd das ganze komplett objektorientiert angehen, d.h. eine Klasse "node" erstellen mit den Attributen "left", "right" und "data", und den ganzen Kram darunter (new_list, insert_right, usw.) als Methoden der Klasse implementieren.

[pippo]

Einfacher gesagt als getan :) Hab jetzt schon länger nix mehr richtiges mit Klassen gemacht, drum hab ich mir auch diesen Beispielcode gesucht

[beos]

Eigentlich darf man kein class vor Methodennamen schreiben .....

Und vor Instanzen der Klasse auch nicht....

node * insert_right(class node *list, int data)
{
node *neu = (class node *) malloc(sizeof(class node));
neu->data = data;
neu->left = list;
neu->right = list->right;
list->right = neu;
neu->right->left = neu;
return neu;
}


Desweitern solltest Du die Methoden in die Klassen schreiben - und die Pointer und das Int Element NICHT public machen - sondern nur die Methoden:

z.B.

class node
{
public:
node * insert_right(node *list, int data);
private:
node *left;
node *right;
int data;
};

Damit es übersichtlicher wird, schreibst Du die Methodenimplementierung nicht in die Klasse, sonder darunter...

node::node * insert_right(class node *list, int data)
{
node *neu = (class node *) malloc(sizeof(class node));
neu->data = data;
neu->left = list;
neu->right = list->right;
list->right = neu;
neu->right->left = neu;
return neu;
}


Hoffe es klappt :)

[noid]

Wir habens halt mal so gelernt. In VS2005 bin ich einfach auf Suchen/Ersetzen gegangen und hab somit alle "struct" durch "class" ersetzt und überall noch das public eingesetzt. Daraufhin hab ich halt dann die Syntaxfehler bekommen. Mehr hab ich nicht gemacht.

Hier das Prgramm in geänderter Version, womit ich die Syntaxfehler bekomme:

#include <iostream>
using namespace std;

class node {
public:
node *left;
node *right;
int data;
//bool erstes;
};

class node * new_list(){
public:
class node *neu = (class node*) malloc(sizeof(class node));
neu->data = -1;
neu->right = neu;
neu->left = neu;
return neu;
};

class node * insert_right(class node *list, int data){
public:
class node *neu = (class node *) malloc(sizeof(class node));
neu->data = data;
neu->left = list;
neu->right = list->right;
list->right = neu;
neu->right->left = neu;
return neu;
}

class node * loeschen(class node *list){
public:
list->right->left = list->left;
list->left->right = list->right;
return list->left;
}

class node * restore(class node *list){
public:
list->right->left = list;
list->left->right = list;
return list;
}

void print_all(class node* list){
public:
class node *head = list;
class node *current = list;
cout << head->data;
while (head != (current = current->right)){
cout << current->data;
}
cout << endl;
}
int main () {

/* erstelle eine neue Liste: */
class node *head = new_list();
class node *current = head;
int i;

/* Bevoelkere die List mit den Zahlen 1 bis 10 */
for(i = 1; i <= 10; i++){
current = insert_right(current, i);
}

/* Gebe die Liste aus, einmal von head aus startent, einmal vom
letzten Element aus: */
print_all(head);
print_all(current);

/* loesche das vorletzte Element: */
current = current->left;
current = loeschen(current);
cout << "Liste nach loeschen:\n";
print_all(head);

current = loeschen(head);
cout << "Liste nach loeschen des Kopfes:\n";
print_all(current);

head = restore(head);
cout << "Liste nach Wiederherstellen des Kopfes:\n";
print_all(head);
return 0;
}
Das kann ja jetzt jeder mit Copy/Paste nachvollziehen, falls jemand lust hast :)


node * restore(node *list){

list->right->left = list;
list->left->right = list;
return list;
}


class kommt hier nicht mehr vor, oder? hab's jetzt nicht getestet - aber in main kommt auch kein "class" mehr vor node.
und wenn du schon einfach struct gegen class tauschst, dann schreib den konstruktor richtig und implementier diese funktionen auch als member-fkt.

Ich könnte mir vorstellen, dass Ausdrücke wie "class node * new_list()" in C++ nicht möglich sind - wobei ich auch "struct node * new_list()" noch nie gesehen hab, aber in C lernt man ja nie aus, immerhin wird es von VC++2005 kompiliert;) .
Ich würd das ganze komplett objektorientiert angehen, d.h. eine Klasse "node" erstellen mit den Attributen "left", "right" und "data", und den ganzen Kram darunter (new_list, insert_right, usw.) als Methoden der Klasse implementieren.

das ist ne fkt "new_list" die keine parameter nimmt, aber einen zeiger auf struct node zurückgibt.

[Coda]

Wir habens halt mal so gelernt.

Einfach fressen und nicht drüber nachdenken. :uclap:

Einfacher gesagt als getan :) Hab jetzt schon länger nix mehr richtiges mit Klassen gemacht, drum hab ich mir auch diesen Beispielcode gesucht

Ach jetzt seh ich's das ist doch C und nicht C++. Da kannst du nicht einfach struct mit class ersetzen. Das kompiliert auch so nicht als C++.

[pippo]

@ beos
Danke. Habs geändert, aber leider hab ich jetzt noch mehr Fehler.

Könnte vielleicht jemand den Code für C++ ändern, oder hat vielleicht nen anderen verständlichen zur Hand? :)

[pestolicious]

eliminier' mal "public:" in den Methoden, dann gehts

[pippo]

Ne, das hatt ich schon gemacht. Habs jetzt auch geschafft die Klassen umzuschreiben um somit die Fehlermeldungen von 19 auf 5 zu reduzieren :)

Hab jetzt folgenden Code:
#include <iostream>
using namespace std;

class node {
public:
node *insert_right(node *list, int data);
node *new_list(node *list, int data);
node *loeschen(node *list);
node *restore(node *list);
//private:
node *left;
node *right;
int data;
};

node *node::new_list(node *list, int data){
node *neu = (class node*) malloc(sizeof(class node));
neu->data = data;
neu->right = neu;
neu->left = neu;
return neu;
}

node *node::insert_right(class node *list, int data){
node *neu = (class node *) malloc(sizeof(class node));
neu->data = data;
neu->left = list;
neu->right = list->right;
list->right = neu;
neu->right->left = neu;
return neu;
}

node *node::loeschen(class node *list){
list->right->left = list->left;
list->left->right = list->right;
return list->left;
}

node *node::restore(class node *list){
list->right->left = list;
list->left->right = list;
return list;
}

void print_all(class node* list){
class node *head = list;
class node *current = list;
cout << head->data;
while (head != (current = current->right)){
cout << current->data;
}
cout << endl;
}
int main () {

/* erstelle eine neue Liste: */
node *head = new_list();
node *current = head;
int i;

/* Bevoelkere die List mit den Zahlen 1 bis 10 */
for(i = 1; i <= 10; i++){
current = insert_right(current, i);
}

/* Gebe die Liste aus, einmal von head aus startent, einmal vom
letzten Element aus: */
print_all(head);
print_all(current);

/* loesche das vorletzte Element: */
current = current->left;
current = loeschen(current);
cout << "Liste nach loeschen:\n";
print_all(head);

current = loeschen(head);
cout << "Liste nach loeschen des Kopfes:\n";
print_all(current);

head = restore(head);
cout << "Liste nach Wiederherstellen des Kopfes:\n";
print_all(head);
return 0;
}
Dummerweise braucht jetzt die main auch noch umschreiben, aber irgendwie sitz ich grad auf der Leitung :) Verständlicherweise muss ich den Methoden ja eine Liste übergeben und natürlich sind Methoden ohne gültigem Objekt auch garnicht bekannt.

[del_4901]

Das ist kein Java!

Wenn du schon malloc verwendest, dann free das irgendwo auch.
Der Autor hat das best. absichtlich vergessen, damit es keiner für seine Hausaufgaben kopieren kann. Mal ganz davon abgesehen das malloc in C++ Code nichts zu suchen hat.

[pippo]

Das ist mir jetzt ehrlich gesagt nicht so wichtig. Ich trödel jetz schon 2 Tage damit rum, eine doppelt verkettete Liste zu erstellen, weil es einfach nirgends ein einfaches und sinnvolles beispiel für C++ gibt.

[pippo]

So, hab mich jetzt mal selber ne Zeit lang hingesetzt und ne doppelt verkettete Liste geschrieben:

#include <iostream>
using namespace std;

class Knoten {
private:
Knoten *pVorheriges;
Knoten *pNaechstes;
Knoten *pAnfang;
Knoten *pEnde;
int Data;

public:
Knoten () {pVorheriges = NULL; pNaechstes = this; pAnfang = NULL; pEnde = NULL; Data=0;}
~Knoten () {}
void Liste_erstellen(Knoten *Liste, int Data);
void Liste_ausgeben(Knoten *Liste);
void Einfuegen(Knoten *Liste, int Data);
};

void Knoten::Liste_erstellen(Knoten *Liste, int Data) {
if(Liste->pNaechstes==this) {
Liste->Data=Data;
pNaechstes=NULL;
cout << "Anhaengen von " << Data << " bei " << Liste << endl;
}

else {
Knoten *neu = new Knoten;
Knoten *Current = Liste;

while(Current->pNaechstes!=NULL) Current = Current->pNaechstes;

cout << "Erstellen von " << Data << " bei " << neu << endl;
neu->Data=Data;
neu->pVorheriges=Current;
neu->pNaechstes=NULL;
Current->pNaechstes=neu;
}
}

void Knoten::Liste_ausgeben(Knoten *Liste) {
Knoten *Current = Liste;

while (Current->pNaechstes!=NULL) {
cout << "Ausgeben von " << Current->Data << " bei " << Current << endl;
Current=Current->pNaechstes;
}
}

void Knoten::Einfuegen(Knoten *Liste, int Data) {
Knoten *Current = Liste;

while(Current->pNaechstes->Data<Data) Current = Current->pNaechstes;

Knoten *neu = new Knoten;
neu->Data=Data;
neu->pNaechstes=Current->pNaechstes;
neu->pVorheriges=Current;
Current->pNaechstes=neu;
Current->pNaechstes->pVorheriges=neu;
}

int main () {
Knoten *Liste = new Knoten;

for(int i=0; i<10; i++) {
if(i==5) i++;
Liste->Liste_erstellen(Liste, i);
}
Liste->Einfuegen(Liste, 5);

Liste->Liste_ausgeben(Liste);
cin.get();

return 0;
}

Gibts vielleicht irgendwelche Verbesserungsvorschläge dazu? Was ich noch nicht so elegant finde ist die Überprüfung mittels des this-Zeigers, ob es sich um den ersten Knoten handelt. Denke das könnte man noch besser lösen, oder?

[del_4901]

1. immernoch kein delete! (das ist nicht unwichtig, denn wenn man einmal mit der Schlamperei anfängt kriegt man es schwer wieder raus)

Tipp: wenn du irgendwo new schreibst, dann auch gleich an entsprechender Stelle (häufig im destruktor) das dazu gehörige delete. In diesem falle würde ich bei element löschen ein delete machen, und dafür sogen, dass wenn die liste zerstört wird auch alles was dranhängt gelöscht wird. (dafür solltest du Pkt2 beachten)

2. Ich würde die Listenoperationen in eine extra Klasse kapseln, im mom schleppst du 2 Pointer sinnlos in jedem Knoten mit rum. Wenn die Liste zerstört wird, sorge dafür das alle Knoten den Speicher wieder frei geben.

[pippo]

Danke! Das mit dem Delete hab ich gemacht. Wie genau soll das mit der eigenen Klasse für die Listenoperationen denn aussehen? Die 2 Zeiger, die ich jetzt schon habe und noch 1 für das entsprechende Objekt?