| Vorheriges Thema anzeigen :: Nächstes Thema anzeigen |
| Autor |
Nachricht |
newby
JLI'ler
Anmeldedatum: 17.08.2007
Beiträge: 106
Medaillen: Keine
|
 Verfasst am: 21.09.2008, 12:05 Titel: verkettete liste |
 |
|
hallo,
ich versuch mir gerade eine klasse für sehr große zahlen zu schreiben. Hierzu möchte ich die zahlen binär in einer verketteten liste mit bool-werten speichern. Allerdings haben alle elemente meiner liste die gleiche adresse(was heißst das es nur ein element gibt), zeigen aber auf verschiedene naechste elemente:
| CPP: | struct Element
{
Element *next_element;
bool value;
};
class BigInteger
{
private:
Element *firstelement;
public:
BigInteger(int startvalue = 0);
};
BigInteger::BigInteger(int startvalue)
{
firstelement = 0;
int rest = 0;
int quotient = startvalue;
while(quotient != 0)
{
rest = quotient % 2;
quotient = quotient / 2;
Element *newelement = new Element;
(*newelement).value = (bool)rest;
(*newelement).next_element = firstelement;
firstelement = newelement;
cout<<"Adresse: ";
cout<<&newelement<<endl;
cout<<"Adresse des naechsten Elements: ";
cout<<(*newelement).next_element<<endl;
cout<<"Wert: ";
cout<<(*newelement).value<<endl;
system("pause");
}
}
|
|
|
| Nach oben |
|
 |
The Lord of Programming
Living Legend
Alter: 36
Anmeldedatum: 14.03.2003
Beiträge: 3122
Medaillen: Keine
|
|
| Nach oben |
|
|
newby
JLI'ler
Anmeldedatum: 17.08.2007
Beiträge: 106
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 14:09 Titel: |
|
|
| ja, warum das nicht funktioniert^^ wie gesagt, es gibt nur ein element, welches aber mehrmals verkettet wird |
|
| Nach oben |
|
|
FH
Super JLI'ler
Alter: 36
Anmeldedatum: 16.10.2004
Beiträge: 437
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 14:55 Titel: Re: verkettete liste |
|
|
Du solltest dir überlegen, ob es nicht einfacher ist, eine std::list zu verwenden, anstatt die Liste selbst zu machen.
Aber wenn du darauf bestehst, die Liste selbst zu machen, hast du in der while-Schleife nen Denkfehler drin:
Wichtig dafür sind diese beiden Zeilen aus deiner while-Schleife:
| CPP: | (*newelement).next_element = firstelement;
firstelement = newelement; |
Im ersten Schleifendurchlauf passiert hier folgendes:
der member next_element von newelement wird auf 0 gesetzt (da firstelement noch 0 ist), und das ist gut so, denn es gibt noch kein nächstes Element.
Dann wird firstelement auf newelement gesetzt. Das sollte eigentlich nur beim ersten Schleifendurchlauf passieren, wird hier aber ständig gemacht.
Und beim zweiten Schleifendurchlauf wird noch dazu next_element auf firstelement und damit auf das erste Element gesetzt, was nicht Sinn der Sache sein kann.
Eigentlich müsste es so laufen:
next_element auf 0 setzen.
Dann, wenn firstelement noch 0 ist, firstelement auf newelement setzen.
Ansonsten sich das letzte Element aus der Liste holen (hierzu wäre ein Zeiger auf lastelement in der Klasse toll), den next_element-zeiger des letzten Listenelements auf newelement deuten lassen. Außerdem jetzt den lastelement-zeiger auf newelement setzen.
Ich hoffe mal, ich konnte klar machen, was ich meine.
Gruß
FH
_________________
goto work, send your kids to school
follow fashion, act normal
walk on the pavement, watch T.V.
save for your old age, obey the law
Repeat after me: I am free |
|
| Nach oben |
|
|
newby
JLI'ler
Anmeldedatum: 17.08.2007
Beiträge: 106
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 17:40 Titel: |
|
|
hab den code mit deinen tips jetzt mal geändert:
| CPP: | struct Element
{
Element *next_element;
bool value;
};
class BigInteger
{
private:
Element *firstelement;
Element *lastelement;
public:
BigInteger(int startvalue = 0);
};
BigInteger::BigInteger(int startvalue)
{
firstelement = 0;
lastelement = 0;
int rest = 0;
int quotient = startvalue;
while(quotient != 0)
{
rest = quotient % 2;
quotient = quotient / 2;
Element *newelement = new Element;
(*newelement).value = (bool)rest;
if(lastelement != 0) (*lastelement).next_element = newelement;
lastelement = newelement;
(*newelement).next_element = 0;
if(firstelement == 0) firstelement = newelement;
cout<<"Adresse: ";
cout<<&newelement<<endl;
cout<<"Adresse des letztzen Elements: ";
cout<<&lastelement<<endl;
cout<<"Wert: ";
cout<<(*newelement).value<<endl;
system("pause");
}
}
|
meiner meinung nach sollte das so ablaufen:
1. in der schleife wird ein neues element erzeugt und der wert wird zugewiesen.
2. wenn es schon ein element gibt, wird der next_element zeiger des letzten elements auf das neue element gezeigt
3. das letzte element ist jetzt das neue element
4. der next_element zeiger des neuen elements wird auf null gesetzt, da es noch kein nächstes gibt
5. wenn es noch kein element gibt, wird das neue element firstlement
wo ist denn da schon wieder der denkfehler? |
|
| Nach oben |
|
|
David
Super JLI'ler
Alter: 39
Anmeldedatum: 13.10.2005
Beiträge: 315
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 17:53 Titel: |
|
|
| Ohje, es gibt doch wesentlich bessere Ansätze für sowas. Eine verkettete Liste ist eigentlich total ungeeignet... Nimm doch z.B. std::vector<bool>. |
|
| Nach oben |
|
|
Deviloper
Junior JLI'ler
Anmeldedatum: 31.05.2006
Beiträge: 77
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 18:25 Titel: |
|
|
Ehm mal so ne frage ... du weißt das du das Ergebnis bei deiner Berechnung noch drehen musst? 
| CPP: | class Integer
{
std::list<bool> m_value;
bool m_positiv;
public:
Integer(const long value)
: m_positiv(value >= 0)
{
unsigned long tmp(m_positiv ? value : -value);
while (tmp > 0)
{
m_value.push_front(temp % 2);
tmp /= 2;
}
}
}; |
sollte reichen ... |
|
| Nach oben |
|
|
newby
JLI'ler
Anmeldedatum: 17.08.2007
Beiträge: 106
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 18:33 Titel: |
|
|
warum muss ich das ergebnis denn noch drehen? ich will die ganzen rechenoperationen usw sowieso selber schreiben.
@david
ich will überhaupt keine headerdatei inkludieren, ich will pures c++^^ |
|
| Nach oben |
|
|
Deviloper
Junior JLI'ler
Anmeldedatum: 31.05.2006
Beiträge: 77
Medaillen: Keine
|
|
| Nach oben |
|
|
DirectXer
Dark JLI'ler
Anmeldedatum: 05.02.2005
Beiträge: 1201
Wohnort: Köln
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 19:28 Titel: |
|
|
| newby hat Folgendes geschrieben: | @david
ich will überhaupt keine headerdatei inkludieren, ich will pures c++^^ |
das ist pures c++ als es purer nicht sein könnte. die stl-header (c++ standard, indiziert durch weglassen von .h beim inkludieren) sind reinstes c++ in seiner effektivsten form. du wärst wesentlich besser dran damit; allerdings kann ich nachvollziehen dass du das alleine machen willst, damit lernt man am meisten (ich gehe davon aus dass du dadurch die struktur erlernen willst und nicht die bednutzung der stl, was allerdings sehr nützlich ist, ebenfalls). Am besten machst du beide versionen. ;D
Gruß DXer |
|
| Nach oben |
|
|
David
Super JLI'ler
Alter: 39
Anmeldedatum: 13.10.2005
Beiträge: 315
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 21:53 Titel: |
|
|
| newby hat Folgendes geschrieben: |
@david
ich will überhaupt keine headerdatei inkludieren, ich will pures c++^^ |
Trotzdem ist der Ansatz über verlinkte Listen Unsinn.
@DirectXer:
Du meinst die Standard C++ Bibliotheksheader, nicht STL, oder? Außerdem sind die Unterschiedlichen Implementationen der Standard Bibliothek nicht unbedingt "effektiv". |
|
| Nach oben |
|
|
Deviloper
Junior JLI'ler
Anmeldedatum: 31.05.2006
Beiträge: 77
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 22:00 Titel: |
|
|
Kommt immer darauf an, was du denn für Objekte in den std.-containern hast usw. ... aber meist ist die Implementierung doch recht schnell und stabil!
Der Ansatz ist nicht unbedingt unsinnig. Ob du jetzt mit nem string arbeitest (wie nen ganzteil bibliotheken), also einem char-array oder mitn bool-array, das einzige was du dir sparst ist das umrechnen 2er zu 10er System. |
|
| Nach oben |
|
|
David
Super JLI'ler
Alter: 39
Anmeldedatum: 13.10.2005
Beiträge: 315
Medaillen: Keine
|
| Verfasst am: 21.09.2008, 22:48 Titel: |
|
|
| Deviloper hat Folgendes geschrieben: |
Der Ansatz ist nicht unbedingt unsinnig. Ob du jetzt mit nem string arbeitest (wie nen ganzteil bibliotheken), also einem char-array oder mitn bool-array, das einzige was du dir sparst ist das umrechnen 2er zu 10er System. |
Und die Zeiger zum verketten der Elemente. Außerdem ließe sich, da er ja ohnehin ein Bool-Array verwenden will, das Ganze komprimieren (=> statt sizeof(bool)+sizeof(void*) pro Element also nur 1 Bit). |
|
| Nach oben |
|
|
newby
JLI'ler
Anmeldedatum: 17.08.2007
Beiträge: 106
Medaillen: Keine
|
| Verfasst am: 22.09.2008, 13:26 Titel: |
|
|
wenn ich in einer schleife bei jedem durchlauf ein element erzeuge, wird das immer an der gleichen stelle erzeugt! das ist doch nicht sinn der sache oder? ich will doch jedes mal ein neues und das alte soll nicht überschrieben werden. Was versteh ich an dem Prinzip jetzt nicht?
| CPP: | for(int i=0;i<20;i++)
{
Element *newelement = new Element;
cout<<"Adresse: "<<&newelement<<endl;
}
|
|
|
| Nach oben |
|
|
David
Super JLI'ler
Alter: 39
Anmeldedatum: 13.10.2005
Beiträge: 315
Medaillen: Keine
|
| Verfasst am: 22.09.2008, 13:38 Titel: |
|
|
| Was für eine Ausgabe hast du denn? |
|
| Nach oben |
|
|
|
FAQ
Suchen
Mitgliederliste
Benutzergruppen
Medaillen
Registrieren
Profil
Einloggen, um private Nachrichten zu lesen
Login
